An editor caps its undo history at 100 edits — why is a plain stack the wrong structure and a deque right?
answer
- The cap adds a second access point
- Which end holds the oldest entry
- A stack reaches exactly one end
- Cost of removing from a stack's bottom
- Append at the back, evict at the front
basics
~20 sUndo reads the newest entry, but a cap must discard the oldest — and those live at opposite ends. A stack only reaches one end, so trimming the oldest costs O(n); a deque appends at the back and evicts from the front, both constant time.
solid answer
~50 sUndo itself is LIFO, so people reach for a stack, and for an unbounded history that is fine. A capacity limit changes the problem: when the 101st edit arrives you must drop the *oldest* entry, and in a stack the oldest sits at the bottom, reachable only by removing everything above it. That makes trimming O(n) per edit, or forces a rebuild of the whole structure. A deque holds both disciplines at once: push each new edit at the back, undo by popping from the back, and when size exceeds the cap pop once from the front. All three are O(1), and the history's memory is bounded by construction rather than by a periodic cleanup. The detail worth volunteering is that the evicted slot must be cleared so the discarded edit is no longer reachable, otherwise the cap bounds the count but not the memory.
go deeper
Be ready to say where the oldest entry sits when new entries are pushed on top, and why reaching it from a stack means moving everything above it first.
Explain that a capped history needs two access points at opposite ends, and price the alternatives — drain and refill, array shifting, batch compaction — against constant-time front eviction.
Demonstrate the operational side: clearing the evicted slot so the cap bounds memory and not just the count, and switching the eviction predicate from an entry count to an accumulated payload budget.
Own the requirement itself. Decide what the history cap is really protecting — session memory on the weakest supported device — and whether losing the oldest edits silently is acceptable product behavior at that boundary.
## Why "undo is a stack" is the wrong reflex here Ask any engineer which structure backs undo and the answer is "a stack" — and for an unbounded history that is correct, because undo is genuinely LIFO: the edit you take back is the most recent one. The reflex fails the moment a **capacity limit** enters the requirements, and capacity limits are the norm: an editor holding an unbounded history of large document edits grows without bound in a long session. Once the history is capped, the feature has **two** access points, not one: - **The newest end** — new edits are appended here, and undo consumes from here. This end is LIFO. - **The oldest end** — when the history exceeds its cap, the entry discarded is the one added longest ago. This end is FIFO-flavoured eviction. Those ends are opposite. A structure that only reaches one of them cannot serve both cheaply, and a stack by definition reaches exactly one. ## What it actually costs to cap a stack Suppose the history is a stack of 100 edits and the 101st arrives. The oldest edit is at the bottom. Your options, all bad: - **Drain and refill.** Pop all 100 entries into a temporary structure, discard the last one out, push the rest back. That is O(n) per edit, and n here is the cap, so every keystroke-level edit pays a hundred moves. - **Back it with an array and shift.** Keep the entries in a plain array with index 0 as oldest, and on overflow remove index 0. Every remaining element shifts one slot — again O(n) per edit. - **Trim lazily in batches.** Let the history grow to 2× the cap and then compact. This restores an O(1) amortized cost, but it doubles the peak memory the cap was introduced to bound, and it introduces a periodic pause exactly when the user is typing fastest. It trades the problem rather than solving it. - **Let it grow and hope.** The original problem, unfixed. None of these is wrong *asymptotically absurd* — O(n) with n = 100 is survivable — but they are all the wrong shape, and an interviewer is checking whether you notice the structural mismatch rather than whether you can afford the copy. ## The deque formulation A deque makes the whole feature three constant-time lines of logic: - **Record an edit:** push it at the back. - **Undo:** pop from the back — the newest entry, exactly the LIFO discipline the feature needs. - **Enforce the cap:** after recording, if the size exceeds the cap, pop once from the front. One structure, two disciplines, one at each end. That is the leaf's real lesson: a bounded history is not a stack problem, it is a *both-ends* problem, and the deque is the structure whose contract is "both ends are cheap". Some libraries expose this directly as a capacity-bounded deque that discards from the far end on push, so the cap enforcement disappears into the type. Where that is not available, the explicit `if size > cap: pop_front` is two lines and just as correct. ## The detail that separates answers **Clearing the evicted slot.** Popping the front removes the entry from the deque's logical view, but an array-backed deque still has a slot that referenced it. If that reference is not cleared, the discarded edit — potentially a large document snapshot — stays reachable and the cap bounds the *count* while the *memory* keeps climbing. Mentioning this unprompted signals you have shipped something like this rather than only reasoned about it. **Counting entries versus counting bytes.** A cap of 100 edits is a proxy for a memory budget, and a bad one: a hundred single-character insertions cost almost nothing, while a hundred large paste operations can dwarf the document. The more honest cap tracks the accumulated payload size and evicts from the front repeatedly — a `while total > budget: pop_front` — until the history fits. The structure does not change; only the eviction predicate does, and the front-eviction operation must still be O(1) for that loop to be affordable. **What eviction means to the user.** Silently dropping the oldest entry is a product decision, not just a data-structure one: the user loses the ability to undo past a point. That is normally the right call — it is why the cap exists — but the boundary should be visible in the interface rather than surprising, and the choice belongs in the requirements conversation. ## How to answer Say the two ends out loud first — newest for append and undo, oldest for eviction — then show that a stack owns one end and a deque owns both, then price the alternatives. Finish with the cleared-slot detail. The failing answer is "a stack, obviously, because undo is LIFO", which is right about the access pattern and blind to the requirement that was actually added.
- Someone proposes letting the history grow to twice the cap and then compacting. What is wrong with that?It restores an amortized O(1) cost but defeats the purpose of the cap: peak memory doubles, which is the resource the cap was introduced to bound. It also concentrates the work into a periodic pause that lands whenever the user is editing fastest. Front eviction on a deque costs the same asymptotically with no memory overshoot and no burst, so the batch version trades a real guarantee for nothing.
- After popping the front entry, is anything else required to actually bound memory?Yes — clear the vacated slot. An array-backed deque still holds a reference in the slot the entry occupied, so an uncleared slot keeps a discarded edit reachable. The cap then bounds the number of live entries while memory keeps growing, which is the exact bug the cap existed to prevent. Implementations that reuse slots as the head advances must clear on removal, not just move the index.
- The cap is really a memory budget, not an edit count. Does the structure change?No, only the eviction predicate. Track the accumulated payload of the stored edits and, after appending, pop from the front repeatedly until the total fits the budget. That loop is only affordable because front removal is O(1); with a stack each iteration would be O(n). It also handles the pathological case an edit count misses — a few very large edits consuming the whole budget.
A capped history is a conveyor belt with a fixed length: work is added and taken back at the near end, and anything that reaches the far end simply falls off.
saying these in an interview costs you the question
- Says undo is LIFO so a stack is obviously enough
- Proposes shifting an array on every overflow
- Thinks the oldest entry is reachable from a stack's top
- Ignores that the evicted slot keeps a reference alive
- Treats an edit count as a reliable memory bound