Queues and amortised cost
Build a queue from two stacks, defend its O(1) amortised cost against worst case and average case, and keep a sliding-window maximum with a monotonic deque.
A queue preserves arrival order: first in, first out. That single property is what makes breadth-first search find shortest paths in an unweighted graph — the frontier is processed in distance order, so the first time a node is reached is by a shortest route — and it is what every buffer between a fast producer and a slow consumer relies on.
The interesting part is not the interface. It is the cost model, because the two standard queue implementations both have an operation that is occasionally expensive, and explaining that honestly is what the question is really about.
First, do not build one out of a list
In Python, list.pop(0) removes the front element and shifts every remaining
element down one slot. One pop is O(n); draining a queue of 100,000 elements
costs about n²/2 = 5 × 10⁹ element moves. collections.deque does both ends in
O(1) and is the container to reach for. In an interview, say which container you
are using and why in the same breath.
A queue from two stacks
If the only tool is a stack, one stack cannot do it: pushing is at the same end as popping, so you get LIFO. Two stacks can, because reversing a reversal restores the original order.
class Queue:
def __init__(self):
self.inbox, self.outbox = [], []
def push(self, x):
self.inbox.append(x)
def pop(self):
if not self.outbox: # refill ONLY when empty
while self.inbox:
self.outbox.append(self.inbox.pop())
return self.outbox.pop()
The if not self.outbox guard is the correctness of the whole thing. Transfer
while the outbox still holds items and the newer elements land on top of older
ones, which is exactly the order a queue must not produce.
Now the cost. One pop can move 100,000 elements — that is a genuine O(n)
operation and you should say so. But an element is moved between the stacks at
most once in its lifetime: it goes into the inbox, crosses to the outbox once,
and leaves. So every element accounts for at most four operations in total —
push to inbox, pop from inbox, push to outbox, pop from outbox. Across n pushes
and n pops that is at most 4n = 400,000 operations for n = 100,000, so the
sequence costs O(n) and each operation costs O(1) amortised.
Amortised, average, and worst case are three different claims
Candidates use these words interchangeably and lose the point they were about to make.
Worst case is the most expensive single operation, over all inputs. For this queue it is O(n): the pop that triggers a transfer.
Amortised is the worst-case total cost of a sequence of m operations,
divided by m. It is a guarantee with no probability in it — no input, adversarial
or otherwise, makes a run of m operations cost more than O(m) here. The dynamic
array is the other standard example: a resize copies everything, but if capacity
doubles each time, the copies across n appends form the geometric series
n/2 + n/4 + n/8 + … < n, so n appends cost under 2n moves in total and each
append is O(1) amortised. Growth factor decides the constant, not the bound.
CPython does not double: list_resize asks for newsize + (newsize >> 3) + 6,
about 1.125x, so capacities run 4, 8, 16, 24, 32, 40, 52, 64, 76, 92, 108, 128,
and 100,000 appends copy roughly 800,000 elements — about 8n against ~1.3n for a
doubling array. Four times the copying, still O(1) amortised.
Average case is an expectation over some distribution of inputs, and it is only as good as that distribution. A hash map lookup is O(1) average and O(n) worst case, because an adversary who knows the hash function can drive every key into one bucket. Amortised survives an adversary; average does not.
One consequence worth naming: amortised is a throughput promise, not a latency promise. If one append in a thousand copies the whole array, the mean stays flat and the tail does not — and, as with any service, p99 is what users feel. A background rehash exists precisely to convert an amortised cost into a bounded one.
The monotonic deque: sliding-window maximum
For every window of width k, report the maximum. Recomputing each window is
O(nk); at n = 100,000 and k = 1,000 that is 10⁸ comparisons. A heap is the
usual first improvement and it is worth being exact about which bound you get.
Push everything and discard stale tops lazily when they surface, and nothing
bounds the heap's size: on strictly increasing input no element is ever popped
while still in the window, the heap reaches all n entries, and the cost is
O(n log n). Getting a true O(n log k) means evicting out-of-window entries
eagerly, which needs an index map from element to heap position — heapq has no
such handle, so a plain binary heap cannot delete an arbitrary element in
O(log k). A deque gets it to O(n) with neither complication.
from collections import deque
def window_max(nums, k):
dq, out = deque(), [] # dq holds indices
for i, x in enumerate(nums):
while dq and nums[dq[-1]] <= x:
dq.pop() # older and no larger: can never win again
dq.append(i)
if dq[0] <= i - k:
dq.popleft() # the front left the window
if i >= k - 1:
out.append(nums[dq[0]])
return out
The invariant: the deque holds indices that lie inside the current window, in increasing index order, whose values strictly decrease from front to back.
Both ends earn their keep. The back is where the order is maintained: a new element x evicts every element that is both older and no larger, because those elements are now dominated — any future window containing them also contains x. The front is where the window expires: since indices increase from front to back, the only index that can fall out of the window is the front one.
That is why the front is always the answer. Nothing larger than it survives in the window, because a larger arrival would have popped it from the back; and nothing older than it survives, because older-and-smaller elements were popped when it arrived. The maximum of the window is the front, in O(1), every step.
The cost argument is the one from stacks and monotonic stacks: each index is appended once and removed once, so the total work is 2n regardless of k — 200,000 deque operations at n = 100,000, against 10⁸ for the naive scan.
In an interview
Two-stack queue and sliding-window maximum are both really questions about cost analysis. Write the code, then take the initiative: "One pop is O(n) in the worst case. Each element crosses between the stacks at most once, so n operations cost O(n) total — O(1) amortised."
Being precise about which of the three claims you are making, as in complexity by counting, is what separates a candidate who has memorised "it's O(1)" from one who can defend it.
The mistake that loses points is saying "amortised" when you mean "average", usually about hash maps. They are different guarantees, and an interviewer who works on latency-sensitive systems will notice immediately.
Check yourself
Someone removes the if not self.outbox guard and transfers the inbox on
every pop. Which property breaks — cost, correctness, or both?
Both. Elements pushed after the last transfer end up above older ones in the outbox, so the queue returns them out of order, and the repeated transfers make each pop O(n) rather than O(1) amortised.
A structure has O(1) amortised inserts. A colleague argues that means the average insert is fast but some could be slow. What is wrong with the wording, and what is the real caveat?
"Average" implies a distribution over inputs; amortised is a worst-case guarantee over any sequence, so no input pattern defeats it. The real caveat is latency: the bound is on the total, so one insert can still stall, which shows up at p99 rather than in the mean.
Window width k = 1,000 over n = 100,000 values. How many deque operations does the monotonic solution perform, and how does that compare with rescanning each window?
At most 2n = 200,000 — each index is appended once and popped once, and k does not appear. Rescanning is n × k = 10⁸ comparisons, roughly 500 times more.