InterviewSolution

Explore topic-wise InterviewSolutions in .

This section includes InterviewSolutions, each offering curated multiple-choice questions to sharpen your knowledge and support exam preparation. Choose a topic below to get started.

1.	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 a Dequeue operation. Each element in the array is touched at least?(a) Once(b) Twice(c) Thrice(d) Four times
Answer» Correct option is (d) Four times To explain: First each element from the first STACK is popped, then pushed into the SECOND stack, DEQUEUE operation is done on the top of the stack and LATER the each element of second stack is popped then pushed into the first stack. Therfore each element is touched four times.

2.	Consider yourself to be in a planet where the computational power of chips to be slow. You have an array of size 10.You want to perform enqueue some element into this array. But you can perform only push and pop operations .Push and pop operation both take 1 sec respectively. The total time required to perform enQueue operation is?(a) 20(b) 40(c) 42(d) 43Answer with explanation needed.
Answer» Correct answer is (d) 43 Easy EXPLANATION - First you have to empty all the ELEMENTS of the current STACK into the TEMPORARY stack, push the required ELEMENT and empty the elements of the temporary stack into the original stack. Therfore taking 10+10+1+11+11= 43 seconds.

3.	A double-ended queue supports operations like adding and removing items from both the sides of the queue. They support four operations like addFront(adding item to top of the queue), addRear(adding item to the bottom of the queue), removeFront(removing item from the top of the queue) and removeRear(removing item from the bottom of the queue). You are given only stacks to implement this data structure. You can implement only push and pop operations. What’s the time complexity of performing addFront and addRear? (Assume ‘m’ to be the size of the stack and ‘n’ to be the number of elements)(a) O(m) and O(n)(b) O(1) and O(n)(c) O(n) and O(1)(d) O(n) and O(1)Please explain.
Answer» Right option is (b) O(1) and O(n) To EXPLAIN: addFront is just a NORMAL push operation. Push operation is of O(1). Whereas addRear is of O(n) as it requires two push(POP()) operations of all elements of a stack.

4.

A double-ended queue supports operations like adding and removing items from both the sides of the queue. They support four operations like addFront(adding item to top of the queue), addRear(adding item to the bottom of the queue), removeFront(removing item from the top of the queue) and removeRear(removing item from the bottom of the queue). You are given only stacks to implement this data structure. You can implement only push and pop operations. What’s the time complexity of performing addFront and addRear? (Assume ‘m’ to be the size of the stack and ‘n’ to be the number of elements)(a) O(m) and O(n)(b) O(1) and O(n)(c) O(n) and O(1)(d) O(n) and O(m)I want an answer and explanation.

Answer»

CORRECT OPTION is (B) O(1) and O(n)

addFront is just a normal push operation. Push operation is of O(1). Whereas addRear is of O(n) as it requires two push(pop()) OPERATIONS of all elements of a stack.

5.	Consider you have an array of some random size. You need to perform dequeue operation. You can perform it using stack operation (push and pop) or using queue operations itself (enQueue and Dequeue). The output is guaranteed to be same. Find some differences?(a) They will have different time complexities(b) The memory used will not be different(c) There are chances that output might be different(d) No differences
Answer» The CORRECT CHOICE is (a) They will have different time complexities The explanation is: To perform operations such as Dequeue using stack operation you need to empty all the elements from the current stack and push it into the next stack, resulting in a O(number of elements) complexity WHEREAS the time complexity of dequeue operation itself is O(1). And there is a need of a extra stack. THEREFORE more memory is needed.

6.	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. The time complexity of performing deQueue operation is (Using only stack operations like push and pop)(Tightly bound).(a) O(m)(b) O(n)(c) O(m*n)(d) Data is insufficientWhy the answer is (a)?
Answer» Right option is (a) O(m) The best I can EXPLAIN: To perform DEQUEUE operation you need to pop each element from the first stack and push it into the SECOND stack. In this case you need to pop ‘m’ times and need to perform push OPERATIONS ALSO ‘m’ times. Then you pop the first element from this second stack (constant time) and pass all the elements to the first stack (as done in the beginning)(‘m-1’ times). Therfore the time complexity is O(m).

7.	A Double-ended queue supports operations such as adding and removing items from both the sides of the queue. They support four operations like addFront(adding item to top of the queue), addRear(adding item to the bottom of the queue), removeFront(removing item from the top of the queue) and removeRear(removing item from the bottom of the queue). You are given only stacks to implement this data structure. You can implement only push and pop operations. What are the total number of stacks required for this operation?(you can reuse the stack)(a) 1(b) 2(c) 3(d) 4Please explain as well.
Answer» The correct option is (b) 2 To EXPLAIN: The addFront and removeFront operations can be performed using one STACK itself as push and pop are supported (ADDING and removing element from top of the stack) but to perform addRear and removeRear you need to pop each element from the current stack and push it into another stack, push or pop the element as per the asked operation from this stack and in the END pop elements from this stack to the first stack.