1. 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) 4
Answer: b
Explanation:
To implement a deque (double-ended queue) using two stacks:
- addFront: You can push the new element onto the first stack (since adding to the front of the deque is equivalent to pushing to the stack).
- removeFront: Pop the top element from the first stack.
- addRear: You can’t directly push to the rear using a single stack, so you need to transfer all elements from the first stack to a second stack. Once all elements are transferred, you can push the new element onto the second stack (which now represents the rear of the deque).
- removeRear: Similarly, pop an element from the second stack (which is now the rear).
After performing operations on the second stack, if needed, elements can be transferred back to the first stack. This way, you simulate the behavior of adding or removing elements from both ends of the deque using two stacks.
2. 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 insufficient
Answer: a
Explanation:
To perform the deQueue operation using two stacks, we follow these steps:
- Transfer elements from the first stack to the second stack: This involves popping all elements from the first stack and pushing them onto the second stack. If there are ‘m’ elements, this will take O(m) time.
- Pop the front element from the second stack: After transferring all elements, we can simply pop the top of the second stack to get the front element. This is an O(1) operation.
- Transfer elements back to the first stack: After popping the front element, we need to transfer all remaining elements from the second stack back to the first stack. This will again take O(m-1) time for ‘m-1’ elements.
Thus, the time complexity for the deQueue operation is O(m), where ‘m’ is the number of elements in the queue.
3. 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: a
Explanation:
To perform a Dequeue operation using two stacks, we transfer all elements from the first stack to the second, which takes O(m) time, where ‘m’ is the number of elements. The actual dequeue operation (popping from the second stack) takes O(1) time, but after that, we need to transfer the elements back to the first stack, adding another O(m-1) time. Thus, the total time complexity is O(m), and an extra stack is required for the transfer, increasing the memory usage.
4. 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 needed to be performed are (You can perform only push and pop):
a) Push(pop()), push(6), push(pop())
b) Push(pop()), push(6)
c) Push(pop()), push(pop()), push(6)
d) Push(6)
Answer: a
Explanation:
To perform an enQueue operation using two stacks, you push all elements from the current stack to the second stack using pop and push operations. After transferring elements, you push the new element onto the second stack. This results in the new element being at the bottom of the stack. When transferring elements back to the first stack, the order is reversed, effectively simulating the enQueue operation.
5. 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)
Answer: b
Explanation:
The addFront operation is a simple push operation, which takes O(1) time. However, addRear requires transferring all elements from one stack to another by popping and pushing each element, which takes O(n) time where n is the number of elements in the stack. Therefore, addRear has a time complexity of O(n).
6. Why is implementation of stack operations on queues not feasible for a large dataset (Asssume the number of elements in the stack to be n)?
a) Because of its time complexity O(n)
b) Because of its time complexity O(log(n))
c) Extra memory is not required
d) There are no problems
Answer: a
Explanation:
To perform queue operations like enQueue and deQueue using stacks, all elements must be transferred from one stack to another. This requires popping each element from one stack and pushing it into the other, resulting in a time complexity of O(n), where n is the number of elements in the stack. Additionally, an extra stack is needed, which may not be efficient for handling large datasets.
7. 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) 43
Answer: d
Explanation:
To perform the operation, you must first transfer all elements from the current stack to a temporary stack, taking 10 seconds. Then, you push the required element, which takes 1 second. After that, you transfer all the elements from the temporary stack back to the original stack, which takes 10 + 10 = 20 seconds. Therefore, the total time is 10 (transfer to temp) + 1 (push required element) + 20 (transfer back) = 43 seconds.
8. You have two jars, one jar which has 10 rings and the other has none. They are placed one above the other. You want to remove the last ring in the jar. And the second jar is weak and cannot be used to store rings for a long time.
a) Empty the first jar by removing it one by one from the first jar and placing it into the second jar
b) Empty the first jar by removing it one by one from the first jar and placing it into the second jar and empty the second jar by placing all the rings into the first jar one by one
c) There exists no possible way to do this
d) Break the jar and remove the last one
Answer: b
Explanation:
This is similar to performing a dequeue operation using two stacks. The elements from the first jar (stack) are transferred to the second jar (temporary stack). After removing the last element from the first jar, the elements in the second jar are moved back to the first jar. This way, you maintain the queue’s order using two stacks, ensuring the FIFO principle.
9. Given only a single array of size 10 and no other memory is available. Which of the following operation is not feasible to implement (Given only push and pop operation)?
a) Push
b) Pop
c) Enqueue
d) Returntop
Answer: c
Explanation:
To perform an Enqueue operation using only push and pop operations, you would need an additional array or stack to store elements temporarily while maintaining the correct order. However, since there is no extra memory available, this approach becomes infeasible, making it impossible to perform Enqueue effectively with the given constraints.
10. 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 atleast?
a) Once
b) Twice
c) Thrice
d) Four times
Answer: d
Explanation:
To perform a Dequeue operation using two stacks, each element from the first stack is popped and pushed into the second stack. Then, the Dequeue operation is performed by popping the top of the second stack. Afterward, all elements from the second stack are popped and pushed back into the first stack. Therefore, each element is moved and accessed four times (twice for transferring between stacks and twice for the final push/pop), leading to a time complexity of O(4n), which simplifies to O(n).