skip to content

What goes wrong if an array-backed stack grows when full and shrinks at half capacity?

level: middleimportance: should knowfreq 36%

answer

  1. picture a stack sitting exactly at the boundary
  2. alternate one push and one pop
  3. each resize copies everything
  4. the triggers are touching each other
  5. hysteresis: land far from both thresholds

basics

~20 s

Growing at full and shrinking at half leaves no gap between the triggers, so a stack at the boundary oscillates: push grows and copies, pop shrinks and copies back. Every operation becomes O(n). Shrink at one-quarter instead.

solid answer

~50 s

Growing when the buffer is full and shrinking when it is half full leaves no gap between the two triggers. Take a stack whose count is exactly at capacity: the next push doubles the buffer and copies everything; the next pop drops the count to half the new capacity, which fires the shrink and copies everything back; the next push finds a full buffer again. Alternating push and pop therefore costs O(n) *per operation*, not O(1) amortized — the amortization argument fails because a resize is no longer followed by a long run of cheap operations that pay for it. The fix is hysteresis: shrink at one-quarter occupancy (halving the capacity), so after either resize the count sits near the middle of the new capacity and roughly n/2 cheap operations must happen before any resize can fire again.

code

pseudocode · 14 lines
pseudocode
push(s, x):
    if s.count == length(s.buf):
        resize(s, 2 * length(s.buf))          // grow when full
    s.buf[s.count] = x
    s.count = s.count + 1

pop(s):
    s.count = s.count - 1
    x = s.buf[s.count]
    if s.count <= length(s.buf) / 2:
        resize(s, length(s.buf) / 2)          // shrink when half full
    return x

// resize(s, m) allocates a block of m slots and copies s.count elements

go deeper

for a junior

Know that an array-backed structure has a capacity separate from its element count, and that returning memory means copying into a smaller block. Recognise that resize policy is a decision, not something the structure does automatically for free.

for a middle

Trace the oscillation out loud with concrete numbers, then explain the offset in terms of how far the count sits from both triggers after a resize. This is the level at which the amortized accounting argument is expected, not just the rule.

for a senior

Be ready to decide the policy for a real workload: which structures should shrink at all, whether release should be explicit, and how you would detect thrash in production from allocation-rate or latency signals rather than by reading code.

for a principal

Frame it as a default for a codebase: predictable per-operation latency versus memory returned promptly is an organisational choice, and the wrong default surfaces as fleet-wide footprint or as unexplained tail latency long after the code was written.

## Why shrinking at all An array-backed stack that only grows never gives memory back. A stack that peaked at ten million elements and now holds twelve still owns the ten-million-slot buffer. For long-lived structures that is a real leak-shaped problem, so implementations often add a shrink policy: when occupancy drops far enough, allocate a smaller block, copy the surviving elements, and release the old one. The question is where to put the trigger, and the naive symmetric answer — grow when full, shrink when half empty — is broken. ## The thrash, traced Suppose capacity is 8 and count is 8. 1. **push** → buffer is full → grow to capacity 16, copy 8 elements, store the new one. count = 9. 2. **pop** → count = 8. Is 8 <= 16/2? Yes → shrink to capacity 8, copy 8 elements. 3. **push** → count 8 equals capacity 8 → grow to 16, copy 8 elements. 4. **pop** → shrink again... Every single operation now copies the entire stack. A workload that pushes and pops around one working depth — which is exactly what a parser stack, an undo stack, or a work queue at steady state does — runs at O(n) per operation forever. Nothing about it is amortized any more. ## Why the amortized argument dies Amortized O(1) is not a hopeful average; it is an accounting argument. It says: the expensive resize can be paid for by charging a small constant to each of the many cheap operations that necessarily happened before it. With growth at full and shrink at half, that "necessarily happened before it" clause is false. A resize can be immediately followed by another resize with one cheap operation in between, so there is no reservoir of prepaid work to draw on. The bound is only as good as the guarantee that resizes are rare relative to the work between them. ## Hysteresis: separate the thresholds The standard fix is to shrink at **one-quarter** occupancy and halve the capacity when doing so. Check what that buys: - After a **growth**, count is about half the new capacity. To fire a shrink, the count must fall from capacity/2 to capacity/4 — about n/4 pops. - After a **shrink**, capacity has halved and count is about half the new capacity again. To fire a growth, count must climb from capacity/2 to capacity — about n/2 pushes. Either way, a resize leaves the structure in the *middle* of its new capacity band, with a linear number of cheap operations required before any resize can fire again. That gap is what the amortized argument needs, and it restores O(1) amortized for arbitrary interleavings of push and pop, not just for monotone runs of pushes. The specific constants are not sacred — shrink at 1/3 with a shrink to 2/3 capacity works too. What is required is that the post-resize occupancy is strictly between the two thresholds, with room on both sides. ## The other legitimate answer: do not shrink Many production stacks and queues simply never shrink automatically, and expose an explicit "release the excess" operation instead. This is a defensible choice: it makes pop unconditionally O(1) worst case, avoids the whole threshold question, and lets the caller decide when a copy is acceptable. The cost is that peak size becomes permanent footprint. The tradeoff is between predictable per-operation latency and memory returned promptly; a long-lived structure that had one huge burst argues for shrinking, a hot short-lived structure argues against. ## What to say in an interview The move that separates a middle answer from a junior one is naming the oscillation concretely — "alternating push and pop at the boundary makes every operation copy" — and then explaining the *reason* the offset fixes it: after any resize the structure must be a linear distance away from both triggers. Candidates who only say "shrink at a quarter because that is the convention" have memorised the rule without the argument, and the follow-up about a stack held at one working depth will expose it.

  • Why does shrinking at one-quarter and halving the capacity fix it?
    Because it leaves the count in the middle of the new capacity after every resize. Following a shrink, occupancy is about half, so roughly n/2 pushes are needed before the buffer fills; following a growth, occupancy is about half, so roughly n/4 pops are needed before the shrink trigger. Either way a linear number of cheap operations must occur between resizes, which is exactly the reservoir the amortized accounting spends.
  • Is never shrinking a defensible policy?
    Yes, and many implementations choose it. Never shrinking makes pop unconditionally O(1) worst case and removes the threshold question entirely, at the cost of holding peak footprint forever. It suits hot, short-lived structures and structures whose peak is close to their steady state. A long-lived structure that had one enormous burst is the case where automatic shrinking, or an explicit caller-triggered release, earns its keep.
  • Does this thrash affect a linked-node stack?
    No. Linked backing has no capacity and no bulk copy, so there is no threshold to cross and nothing to oscillate. Memory is returned node by node as elements are popped, which is the one place linked backing gives smoother behaviour without any policy tuning. The price is paid steadily instead: a per-element allocation on the way in and a release on the way out.

A thermostat that starts heating and starts cooling at the same temperature never settles — it fights itself. Resize thresholds need the same dead band a thermostat does.

saying these in an interview costs you the question

  • Says symmetric thresholds are obviously correct
  • Claims resizing is rare so oscillation cannot happen
  • Confuses the fix with simply growing by a bigger factor
  • Treats amortized O(1) as guaranteed regardless of policy
  • Thinks pop can never trigger a copy

context

resolving links…