Microsoft Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
i think Queue function should be modified. This will not work after a dequeue, since all the elements will be in outbox. we should push new element to inbox only when outbox is empty. If its not, then we have to pop all elemtents from outbox and push them to inbox, then push the new element to inbox. correct me im wrong.
I think the methods are fine.
Because you only move the elements from inbox to outbox when outbox is empty. For instance, let's say you add elements A, B, C, D in this order into stack Inbox.
Now you have DCBA from top to bottom in inbox.
If you want to dequeue, you move these elements to outbox. Now outbox has ABCD from top to bottom and after dequeuing, you have BCD.
Then you add elements E and F.
Inbox: FE from top to bottom.
Dequeue 4 times.
#1-3: returns B, C and D from outbox.
#4: outbox is empty, so move elements from inbox.
Now outbox is EF from top to bottom and inbox is empty and you return E.
Suppose you want to make queue of length n
Take two stacks, Stack1 and Stack2 of length n each
-----------------------------------------------------------
1) Push -
Bottomline - Always push in Stack1.
IF Stack1 is full and Stack2 is not empty - Print Queue overflow
IF Stack1 is full and Stack2 is empty - Pop every item from Stack1 and push it in Stack2, till Stack1 is empty.
After that push new element on Stack1
2) Pop -
Bottomline - Always pop from Stack2
IF Stack2 is empty and Stack1 is empty - Print Queue Underflow.
IF Stack2 is empty and Stack1 is not empty- Pop every item from Stack1 and push it in Stack2.
Pop from Stack2.
class Queue
{
Stack enQueueStack = new Stack();
const int size = 10;
public void Enqueue(int n)
{
if (size > deQueueStack.Lenght)
{
while (deQueueStack.Lenght > 0)
{
enQueueStack.Push(deQueueStack.Pop());
}
enQueueStack.Push(n);
}
}
Stack deQueueStack = new Stack();
public int Dequeue()
{
while (deQueueStack.Lenght > 0)
{
deQueueStack.Push(enQueueStack.Pop());
}
return deQueueStack.Pop();
}
}
Keep 2 stacks, let's call them inbox and outbox.
- Anshul February 07, 2013Queue:
- Push the new element onto inbox
Dequeue:
- If outbox is empty, refill it by popping each element from inbox and pushing it onto outbox
- Pop and return the top element from outbox
Using this method, each element will be in each stack exactly once - meaning each element will be pushed twice and popped twice, giving amortized constant time operations.
Here's an implementation in Java:
public class Queue<E>
{
private Stack<E> inbox = new Stack<E>();
private Stack<E> outbox = new Stack<E>();
public void queue(E item) {
inbox.push(item);
}
public E dequeue() {
if (outbox.isEmpty()) {
while (!inbox.isEmpty()) {
outbox.push(inbox.pop());
}
}
return outbox.pop();
}
}