Questions / Quant development, Algorithms & structures
Amortized queue work can arrive in one burst
A queue uses an input stack and an output stack. Each enqueue pushes to input; when output is empty, dequeue moves all input items to output before popping. For five enqueues followed by five dequeues, how many primitive stack pushes and pops occur?
Answer it in the app It's free. You get hints, a second try if you miss, and a follow-up question.
Show the answer and worked solution
Answer: 20 stack operations
- All five items undergo four stack operations exactly once. The total is 5*4 = 20, excluding emptiness checks.
Interview shortcut. Each item: push in, pop in, push out, pop out.
In the app this has a follow-up where one thing about the setup changes. Try the follow-up.