LRU, LFU and What Actually Hits
In short: an LRU (least-recently-used) cache keeps a doubly-linked list in recency order, plus a hash map from key to its node, so every operation is O(1): a hit splices its node to the front (MRU end), a miss evicts the tail (LRU end) and inserts the new key at the front. LFU (least-frequently-used) evicts by hit count instead of recency, breaking ties by recency. Neither is free: LRU can be worse than plain FIFO on some access patterns, because promoting a hit to the front pushes some other key closer to eviction — a key that FIFO, which never reorders on a hit, would have kept.
LRU can lose to a policy that doesn't even look
Quarry compares two eviction policies on the exact same trace: LRU, and plain FIFO (evict whatever arrived first — no reordering on a hit at all):
FIFO gets 2 hits; LRU gets only 1. Trace it: after 2, 3, both
policies hold {2, 3}. The third touch, 2, is a hit for both — but LRU
promotes 2 to the front, which makes 3 the new least-recently-used.
When 1 arrives next (a miss for both), LRU evicts 3 — the exact key 1's
successor, 3 again, needs a step later. FIFO never reordered on the hit, so
it evicts 2 (the oldest insertion) instead, and 3 survives to be a hit.
Reacting to a hit is not automatically the safer choice.
Break an LFU tie by forgetting to update it
LFU breaks a frequency tie by recency — whichever tied key was touched
longest ago goes. That tiebreak only works if a hit keeps the key's
last_used clock current, not just its frequency count:
This evicts "a" by mistake when "c" arrives, so the final lookup for "a" misses instead of hits. Add the missing last_used update to the hit branch.
With both branches updating last_used, "a" keeps winning the tie against
"b" (touched more recently, at step 4 vs step 3), "b" is the one evicted when
"c" needs room, and the final a lookup is a hit. Forgetting the update
doesn't crash anything — it just silently evicts the wrong key every time a
tie comes up, which is worse than crashing: nothing flags it.
Quick practice
order = ["c", "a", "b"]
order.remove("b")
order.insert(0, "b")
print(order)This evicts the wrong end of the queue, so "2" gets kicked out early and misses on its second visit instead of hitting. Fix the one call.
🎯 Your turn
Build lru_vs_fifo(capacity, keys): simulate both an LRU cache and a FIFO
cache over the same keys trace, and return {"lru_hits": ..., "fifo_hits": ...}.
lru_vs_fifo(2, [2, 3, 2, 1, 3])→{"lru_hits": 1, "fifo_hits": 2}
Hint: build simulate_lru_list and simulate_fifo first (a plain list
is fine for LRU here — the real O(1) doubly-linked version is the boss
exercise below), then sum each one's hit list.
Press ▶ Run, try the Live App chips, then ✓ Check.