Technical MCQ
1. When does a regular queue, when implemented with an array of size MAX SIZE, get full?
Rear = MAX_SIZE – 1
2. Before deletion condition into stack …… has to be checked
Underflow
3. Deletion in the linked stack takes place by deleting
Node pointed by the start process.
4. Which of the following methods inherits by the priority queue?
All of the mentioned
5. The concept “Pile of Plates” is applicable in which one of the following
Stack
6. A queue stores items in a first-in,first-out(FIFO order) guess the complexity of dequeues.
O(1)
7. A double-ended queue allows you to add and remove items from both sides of the queue at the same
time. They allow four operations: addFront (adding an item to the front of the queue), addRear (adding
an item to the back of the queue), removeFront (removing an item from the front of the queue), and
removeRear (removing an item from the back of the queue) (removing item from the bottom of the
queue). To implement this data str, you are simply given stacks.
2
8. Reversing a great deal of space for each stack in memory will ………..
Increase the number of times overflow may occur
9. We define some functions as given below : push( int x ) : This pushes the number x into a predefined
Queue ‘Q’. pop( ) : This pops out( delete ) the last element in the Queue ‘Q’. front( ) : Returns the
number on the top of the Queue ‘Q’.
Now a function “fun( )” is implemented using these three functions. What will be the output of the
function given below?
void fun( )
{
int i=1,j=0;
for(;i<=5;i++)
{
for(j=0;j<i;j++)
{
push( i );
push( i\*i );
}
int k;
for( k=0; k< i ; k++)
{
pop( );
}
printf("%d ", top( ));
} }
1 4 3 3 16
10. Following is C like pseudo code of a function that takes a number as an argument, and uses a stack S
to do processing.
void fun(int n)
{
Stack S; // Say it creates an empty stack S
while (n > 0)
{
// This line pushes the value of n%2 to stack S
push(&S, n%2);
n = n/2;
}
// Run while Stack S is not empty
while (!isEmpty(&S))
printf("%d ", pop(&S)); // pop an element from S and print it
}
What does the above function do in general?
Prints binary representation on n
*-**************************************************************************
PROGRAMMING
1. Problem statement
Given a square chessboard, the initial position of Knight and position of a target. Find out the minimum
steps a Knight will take to reach the target position.
Note: The initial and the target position co-ordinates of Knight have been given accoring to 1-base
indexing.
Input Format
First line of input contains N-the size of NxN chessboard. Next line of input contains two space
separated integer the x coordinate and y coordinate respectively of knight's position at chessboard
Next line of input contains two space separated integer the x coordinate and y coordinate respectively
of target's position at chessboard.
Constraints
1 <= N <= 1000
1 <= Knight_pos(X, Y), Targer_pos(X, Y) <= N
Output Format
Print the minimum number of steps required by the knight to reach from its current position to the
given target position
SOLUTION :
PYTHON CODE:
class cell:
def __init__(self, x = 0, y = 0, dist = 0):
self.x = x
self.y = y
self.dist = dist
def isInside(x, y, N):
if (x >= 1 and x <= N and
y >= 1 and y <= N):
return True
return False
def minStepToReachTarget(knightpos,
targetpos, N):
dx = [2, 2, -2, -2, 1, 1, -1, -1]
dy = [1, -1, 1, -1, 2, -2, 2, -2]
queue = []
queue.append(cell(knightpos[0], knightpos[1], 0))
visited = [[False for i in range(N + 1)]
for j in range(N + 1)]
# visit starting state
visited[knightpos[0]][knightpos[1]] = True
# loop untill we have one element in queue
while(len(queue) > 0):
t = queue[0]
queue.pop(0)
# if current cell is equal to target
# cell, return its distance
if(t.x == targetpos[0] and
t.y == targetpos[1]):
return t.dist
# iterate for all reachable states
for i in range(8):
x = t.x + dx[i]
y = t.y + dy[i]
if(isInside(x, y, N) and not visited[x][y]):
visited[x][y] = True
queue.append(cell(x, y, t.dist + 1))
# Driver Code
if __name__=='__main__':
N = int(input())
knightpos = list(map(int,input().split()))
targetpos = list(map(int,input().split()))
print(minStepToReachTarget(knightpos,targetpos, N))
2. Problem statement
Given an expression string x. Examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”“,”” are correct in
exp.
Input Format
A single string s containing the parenthesis.
Constraints
1<=length of string<=1000
Output Format
Print "1" if brackets are balanced else print "0".
SOLUTION :
PYTHON CODE:
def areBracketsBalanced(expr):
stack = []
for char in expr:
if char in ["(", "{", "["]:
stack.append(char)
else:
if not stack:
return False
current_char = stack.pop()
if current_char == '(':
if char != ")":
return False
if current_char == '{':
if char != "}":
return False
if current_char == '[':
if char != "]":
return False
if stack:
return False
return True
if __name__ == "__main__":
expr =input()
if areBracketsBalanced(expr):
print("1")
else:
print("0")
3. Problem statement
The stock span problem is a financial problem where we have a series of n daily price quotes for a
stock and we need to calculate the span of stock’s price for all n days. The span Si of the stock’s price
on a given day i is defined as the maximum number of consecutive days just before the given day, for
which the price of the stock on the current day is less than or equal to its price on the given day.
Input Format
First line contains n-the number of days. Next line contains n integers-the stock price of each day.
Constraints
1 ≤ N ≤ 10^5 1 ≤ Stock Prices ≤ 10^5
Output Format
Print an array of length N denoting the span for the i-th day.
PYTHON CODE:
n=int(input())
li=list(map(int,input().split()))
print(1,end=" ")
for i in range(1,n):
count=1
j=i-1
while(j>=0):
if li[i]>=li[j]:
count+=1
else:
break
j-=1
print(count,end=" ")
Post a Comment