You have two stacks, implement a queue.
Here's a favorite programming question for interviews that even those long out of college can do. Delightfully, one I hadn't been asked recently, except by Kris and Andy.
You have two stacks, implement a queue.
In programming, a stack is a first-in-last-out data structure with two functions: push and pop. You can push a piece of data to add it to the top of the stack, on top of all of the other pieces of data already on the stick, and you can pop the most-recently-added piece of data off the top of the stack to remove it from the stack and return its value to you.
A queue is a first-in-first-out data structure with two functions: enqueue and dequeue. You can enqueue a piece of data to add it to the end of the stack (whichever end you have declared to be the back), behind all the other pieces of data already in the queue; and you can dequeue the oldest piece of data from the opposite end of the queue, which is the front of the queue, and return its value to you.
With that all said, given two stacks, implement a queue.
If you're not reading this from the feed, it should display in black, and you should be able to mouse over or select the text for my hand-wavy notes.
The solution is "push on first, pull on second."
If the second stack is empty, you can't dequeue, so you take the value from the first queue, pop it. push on the second, and then pop from the second.
Essentially, you move items between the two stacks, popping from the first and pushing onto the second, to get to the last one on the first, then dequeue.
The worst case scenario is when you have to enqueue, dequeue, enqueue, dequeue, because that means moving all the items from one stack, then to the other stack, then back to the first stack then back the other stack, to add items to the bottom of the first stack, then the bottom of the second stack.
Follow up questions include, "What's the worst case scenario in data retrieval with the two-stacks-as-a-queue?" and "How would you do a runtime analysis of your implementation?"
Other exercises I've had recently are, "In a distributed system, implement put-if-absent." and "Implement a serialize function for an object with an integer and a string." The later includes follow ups on how do you determine the function's efficiency, and how does it change with 16 bit, 32 bit, and 64 bit systems?
Add new comment