In an LRU cache, what goes wrong when a write to an existing key updates the value but skips the relink?
answer
- A write is a use, too
- Correctness survives; something else degrades
- Follow the busiest key over time
- What if the update takes the insert branch?
- Map size versus list length must agree
basics
~20 sThe write stops counting as a use, so a constantly rewritten key drifts to the stale end and gets evicted while it is the hottest entry in the cache. Correctness survives; the hit rate collapses.
solid answer
~50 sA write is a use, and skipping the relink hides that fact from the recency order. The entry stays wherever it was, so a key that is overwritten a thousand times a second keeps sliding toward the eviction end as other keys are touched, and is eventually dropped while it is the busiest thing in the cache — then re-inserted on the next miss, producing a self-inflicted thrash loop that no correctness test will catch. The sibling bug is worse: if the update path instead falls into the insert branch, you splice a *second* node for the same key while the map points only at the new one. The old node is now unreachable from the map but still occupies a list slot, so the map's size and the list's length diverge, eviction eventually picks the orphan, and erasing its key deletes the live entry.
code
pseudocode · 13 linesput(key, value):
if contains(index, key):
node = index[key]
node.value = value
// node stays where it is
else:
node = new_node(key, value)
index[key] = node
link_after(head, node)
if count(index) > capacity:
victim = tail.prev
unlink(victim)
erase(index, victim.key)go deeper
Know that overwriting a key still counts as using it, and that a cache which forgets that will throw away the entry it is being written to most often.
Trace both write branches and state the invariant they preserve: one node per key, the map's keys equal to the list's keys, and the count within capacity.
Show how you would catch this in practice — an invariant checker over randomised traces, plus assertions on which key survives a scripted eviction, rather than relying on a hit-rate metric to reveal it.
Own the general lesson: a bug that leaves the data structure valid but the policy wrong will never fail a functional test, so the design needs explicit policy assertions or the regression ships.
## The invariant the write path must preserve Every correct implementation of this composition maintains one invariant, and every classic bug is a violation of it: > The set of keys in the map is exactly the set of keys on nodes between the two sentinels; each key appears on exactly one node; the map's reference for a key points at that node; and the count of live entries never exceeds capacity. Write that sentence down before writing the code, and the bugs below stop being surprises. ## Branch one: update without relink The fragment in this question updates the payload of an existing node and returns. The invariant above still holds — no duplicate node, no orphan, no over-capacity — so every functional test passes. What is broken is the *recency signal*. In a photo service's thumbnail cache, imagine one variant that is re-rendered and re-written on every upload of the same album cover. Its key is written constantly and read rarely. Because writes do not relink, the node never moves toward the recent end. Meanwhile every read of every other key pushes those nodes ahead of it. The hottest write target steadily sinks to the tail and is evicted, which forces the next write to allocate a fresh node — and the cycle repeats. You have built a cache that evicts precisely what it is being asked to hold, and the only symptom is a hit rate that is lower than it should be. This class of bug survives code review because the code is not *wrong*, it is *under-informed*. The fix is one line: after updating the payload, splice the node in at the recent end, the same way the read path does. ## Branch two: update that takes the insert path The more dangerous variant is a write path that never checks for an existing key and always creates a node. Now the map's entry for that key is overwritten to point at the new node, and the old node is still linked between its neighbours. The invariant breaks in two places at once: - **Length divergence.** The list holds more nodes than the map holds keys. If your capacity check counts map entries, it will under-count and the cache silently grows past its bound; if it counts list nodes, it will over-count and evict live entries early. - **Eviction corruption.** Eventually the orphan reaches the stale end and is chosen as the victim. Eviction unlinks it — harmless — and then erases *its key* from the map. But the map's entry for that key is the **live** node. You have just deleted a hot, correctly-linked entry from the map while its node remains in the list, creating a second orphan. The corruption compounds. Both branches are why the write path is written as an explicit two-case decision: if the key is present, update in place *and relink*; otherwise create, link, index, and only then check capacity. ## Ordering the eviction check A related family of bugs lives in *when* capacity is enforced. Two orderings look equivalent and are not: - **Insert, then evict while over capacity.** The cache transiently holds one extra entry, then drops the stale end. Correct — and note the victim cannot be the node you just inserted, because it sits at the recent end. - **Evict when at capacity, then insert.** This is the ordering that goes wrong, because it runs *before* you know whether the write is an insert or an update. A write that merely overwrites an existing key will evict a perfectly good entry that it did not need to make room for. At capacity 1, that means every overwrite of the single resident key first throws that key out, and depending on how the branches are arranged you may then update a node you have already unlinked. Capacity 1 is worth testing explicitly for exactly this reason: it collapses "the node I am inserting", "the node at the recent end" and "the node at the stale end" into the same object, so any confusion between them becomes a visible failure rather than a rare one. ## The sentinels earn their keep here The head and tail sentinels — permanent nodes that never carry data — remove every end-of-list branch from these paths. Splicing at the recent end is always "insert after head"; choosing a victim is always "the node before tail"; unlinking is always "my predecessor's next becomes my successor, my successor's previous becomes my predecessor". With sentinels, the empty cache, the one-entry cache and the full cache execute identical code. Without them, each of those cases needs a null check, and the missing null check is the bug. ## How to prove it works Write an invariant checker: walk the list from head to tail, collect the keys, and assert the collected multiset equals the map's key set, that the walk length matches the map's size, that every map reference points at the node bearing that key, and that the count is within capacity. Call it after every operation in a randomised test that mixes reads, first-writes, overwrites and evictions at capacities 1, 2 and 3. Every bug described above fails that checker on a short trace, and it costs a dozen lines.
- How would a randomised test catch this without asserting on hit rate?Assert the recency order directly. After a scripted trace — insert A, insert B, overwrite A, insert C at capacity 2 — check which key survived. A correct cache drops B; the missing-relink version drops A, the key just written. Pair that with an invariant walk comparing the list's key multiset against the map's key set after every operation.
- Why is capacity 1 a disproportionately useful test case?Because it collapses three roles onto one node: the entry you are inserting, the recent end and the stale end become the same object. Any confusion between "evict then insert" and "insert then evict", or between the update branch and the insert branch, produces a visible failure instead of a rare one that needs a long trace to reproduce.
- What single check keeps the two write branches honest?The presence test on the key must come first and must be the only thing that selects the branch. If the key is present the node already exists, so the correct action is update-in-place plus relink, and no capacity check is needed because the entry count did not change. Only the insert branch can push the cache over its bound.
saying these in an interview costs you the question
- Treats a write as not counting as a use
- Creates a new node without checking for the key
- Evicts before knowing the write is an insert
- Never tests capacity 1 or 2
- Assumes the map and list lengths cannot diverge