Microsoft Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
11
of 11 vote

Keep 2 stacks, let's call them inbox and outbox.

Queue:
- 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();
}

}

- Anshul February 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Great!

- Anonymous February 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- sri February 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anon February 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@aron,
i got it wrong... code is fine & clean!

- sri February 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Shouldn't we check the max size of the queue ? Suppose the maximum size of the queue is MAX_SIZE . If there are n elements already present in outbox , should'nt we allow only (MAX_SIZE - n) elements in inbox

- sumit.083 May 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- Nitin Gupta February 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It's the Tower of Hanoi algorithm.

- David February 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Enqueue: push onto Stack A.
2. Dequeue: push all elements from (1) onto Stack B. Pop top-element from Stack B until empty. If Enqueue is necessary, push onto Stack A while Stack B is not empty.
3. When stack B is empty, push elements from stack A to Stack B.
4. and so on...

- Jack February 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public E dequeue() { //generic - not syncronized
	if (outbox.isEmpty()) { // Asymptotic condition - When it goes empty O(n)
		while (!inbox.isEmpty()) {
			outbox.push(inbox.pop());
		}
	}
return outbox.pop(); // O(1)
}

- Ashis February 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
        }
    }

- jinzha May 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Will maintain size variable separately, so that we don't need to bother about which stack is empty/full.

Enqueue:

If (not overflow)
 push to S1

Dequeue:

If(not underflow) {
    If(S2 is not empty)
        Pop from S2
    Else
       Pop all elements from S1 and push to S2. Finally Pop from S2

Is it not simple

- Kallu September 19, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More