PATNI Previous Years Solved Sample Placement Papers
-
Given only a single array of size 10 and no other memory is available. Which of the following operations is not feasible to implement (Given only push and pop operation)?
A) Push
B) Pop
C) Enqueue (Ans)
D) Returntop
-
Given an array of size n, let’s assume an element is ‘touched’ if and only if some operation is performed on it (for example, for performing a pop operation the top element is ‘touched’). Now you need to perform Dequeue operation. Each element in the array is touched at least?
A) Once
B) Twice
C) Thrice
D) Four times (Ans)
-
Which of the following is the most widely used external memory data structure?
A) AVL tree
B) B-tree (Ans)
C) Red-black tree
D) Both AVL tree and Red-black tree
-
B-tree of order n is a order-n multiway tree in which each non-root node contains __________
A) at most (n – 1)/2 keys
B) exact (n – 1)/2 keys
C) at least 2n keys
D) at least (n – 1)/2 keys (Ans)
-
A Double-ended queue supports operations such as adding and removing items from both the sides of the queue. You are given only stacks to implement this data structure. How many stacks are required to implement the operation?
A) 1
B) 2 (Ans)
C) 3
D) 4
-
You are asked to perform a queue operation using a stack. Assume the size of the stack is some value ‘n’ and there are ‘m’ number of variables in this stack. What is the time complexity of performing the deQueue operation?
A) O(m) (Ans)
B) O(n)
C) O(m*n)
D) Data is insufficient
-
Consider you have an array of some random size. You need to perform dequeue operation. You can perform it using stack operations (push and pop) or using queue operations itself (enQueue and Dequeue). The output is guaranteed to be the same. Find some differences:
A) They will have different time complexities (Ans)
B) The memory used will not be different
C) There are chances that the output might be different
D) No differences
-
Consider you have a stack whose elements in it are as follows:
5 4 3 2 << top
Where the top element is 2. You need to get the following stack:
6 5 4 3 2 << top
The operations that need to be performed are (You can perform only push and pop):
A) Push(pop()), push(6), push(pop()) (Ans)
B) Push(pop()), push(6)
C) Push(pop()), push(pop()), push(6)
D) Push(6)
-
What should be done when a left parenthesis ‘(‘ is encountered?
a) It is ignored
b) It is placed in the output
c) It is placed in the operator stack
d) The contents of the operator stack is emptied
Answer: c
Explanation: When a left parenthesis is encountered, it is placed on to the operator stack. When the corresponding right parenthesis is encountered, the stack is popped until the left parenthesis and remove both the parenthesis.
-
What is the postfix expression for the following infix expression?
a/b^c-d
a) abc^/d-
b) ab/cd^-
c) ab/^cdd
d) abcd^/-
Answer: a
Explanation: Using the infix to postfix conversion algorithm, the corresponding postfix expression for the infix expression is abc^/d-.
-
What is the corresponding postfix expression for the given infix expression?
a*(b+c)/d
a) ab*+cd/
b) ab+*cd/
c) abc*+/d
d) abc+*d/
Answer: d
-
What kind of linked list is best to answer questions like “What is the item at position n?”
a) Singly linked list
b) Doubly linked list
c) Circular linked list
d) Array implementation of linked list
Answer: d
Explanation: Arrays provide random access to elements by providing the index value within square brackets. In the linked list, we need to traverse through each element until we reach the nth position. Time taken to access an element represented in arrays is less than the singly, doubly and circular linked lists. Thus, array implementation is used to access the item at the position n.
-
Linked lists are not suitable for the implementation of ___________
a) Insertion sort
b) Radix sort
c) Polynomial manipulation
d) Binary search
Answer: d
Explanation: It cannot be implemented using linked lists.