InternDoor

A queue made of two stacks

Easydesign · stack · queueDesign a class

Reported in interviews at (where)

Build TwoStackQueue, a queue of whole numbers: the first number in is the first one out. Inside it, keep the numbers in two stacks and touch them only the way a stack allows: push onto the top, pop from the top, look at the top, ask whether it is empty.

TwoStackQueue() starts empty.

push(x) adds x at the back of the queue.

pop() removes the number at the front of the queue and returns it.

peek() returns the number at the front without removing it.

empty() returns whether the queue holds no numbers.

pop and peek are only called while the queue holds at least one number. Each number should move from one stack to the other at most once, so a long run of calls costs O(1) per call on average.

Example 1
Input
["TwoStackQueue","push","push","peek","pop","push","pop","pop","empty"]
[[],[4],[9],[],[],[2],[],[],[]]
Output
[null,null,null,4,4,null,9,2,true]

Numbers leave in the order they came in: 4, then 9, then 2, even though 2 was pushed after a pop.

Example 2
Input
["TwoStackQueue","empty","push","empty","peek","pop","empty"]
[[],[],[0],[],[],[],[]]
Output
[null,true,null,false,0,0,true]

peek leaves the number in place; pop takes it out.

Limits

  • 0 <= x <= 1000000000
  • pop and peek are only called on a queue that holds a number
  • at most 20000 calls after the constructor

Hints

Hint 1

Let one stack take every push. Let the other hand out the front: its top should always be the oldest number it holds.

Hint 2

Only when the second stack is empty, pour the whole first stack into it. The order flips, so the oldest number lands on top.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.