Get a free weekly practice problem!

Keep that axe sharp.

× No thanks

You only have free questions left (including this one).

But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.

Implement a queue with 2 stacks. Your queue should have an enqueue and a dequeue method and it should be "first in first out" (FIFO).

Optimize for the time cost of m calls on your queue. These can be any mix of enqueue and dequeue calls.

Assume you already have a stack implementation and it gives time push and pop.

We can get runtime for m calls. Crazy, right?

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

Each enqueue is clearly time, and so is each dequeue when outStack has items. Dequeue on an empty outStack is order of the number of items in inStack at that moment, which can vary significantly.

Notice that the more expensive a dequeue on an empty outStack is (that is, the more items we have to move from inStack to outStack), the more -time dequeues off of a non-empty outStack it wins us in the future. Once items are moved from inStack to outStack they just sit there, ready to be dequeued in O(1) time. An item never moves "backwards" in our data structure.

We might guess that this "averages out" so that in a set of m enqueues and dequeues the total cost of all dequeues is actually just . To check this rigorously, we can use the accounting method, counting the time cost per item instead of per enqueue or dequeue.

So let's look at the worst case for a single item, which is the case where it is enqueued and then later dequeued. In this case, the item enters inStack (costing 1 push), then later moves to outStack (costing 1 pop and 1 push), then later comes off outStack to get returned (costing 1 pop).

Each of these 4 pushes and pops is time. So our total cost per item is . Our m enqueue and dequeue operations put m or fewer items into the system, giving a total runtime of .

Start your free trial!

Log in or sign up with one click to get immediate access to free mock interview questions

What's next?

Reset editor

Powered by qualified.io

. . .