Cache Eviction
01 / The shared mechanism
A fixed-capacity store with O(1) get and put. The trick is the data structure: every eviction policy is a different answer to which entry do I drop when the cache is full? Two classic ones share the same O(1) trick — LRU pairs a hash map with a doubly-linked list so the just-touched key can be moved to the front in constant time; LFU tracks per-key frequency in buckets so the lowest-frequency bucket is always reachable in O(1).
02 / The one-sentence essence
Track per-key frequency in buckets keyed by freq; a minFreq pointer always points to the bucket holding the eviction candidate — so “find the LFU” is O(1) instead of an O(N) scan. Ties broken by LRU within a bucket.Problembuild an LFU cache with O(1) get / putcap4ops8
Empty LFU cache with capacity 4. We’ll run 8 ops.
step
0 / 13
op
—
minFreq
—
size
0 / 4
0 / 13
03 / The pattern signature
# state: map[k] → node; buckets[freq] = DLL; minFreqdef get(k):if k not in map: return −1node ← map[k]buckets[node.freq].remove(node)if buckets[minFreq] empty and node.freq == minFreq: minFreq += 1node.freq += 1; buckets[node.freq].push_head(node)return node.val def put(k, v):if k in map: map[k].val ← v; get(k); returnif size == capacity:victim ← buckets[minFreq].pop_tail()map.delete(victim.key)node ← Node(k, v, freq=1)buckets[1].push_head(node); map[k] ← node; minFreq ← 1
04 / When to recognize this pattern
"frequency wins over recency"
The whole reason to reach for LFU instead of LRU is when the workload has a stable hot set — a few keys are accessed far more than the rest, and you want to keep them resident even if they haven’t been touched for a while. The frequency counter is the signal; recency only breaks ties.
"tie-break by recency"
Within a single frequency bucket, the doubly-linked list keeps insertion / promotion order. New entries land at the head; eviction pops the tail. So two keys at the same lowest frequency are ordered by “who was touched longest ago” — pure LRU. LFU is LRU stratified by frequency.
"minFreq pointer"
A single integer is the entire reason this stays O(1). Every promotion either keeps
minFreq unchanged or bumps it by one (if it just emptied buckets[minFreq]). Every insert resets it to 1. No scan, no heap, no log factor — just bookkeeping.05 / Common pitfalls
Forgetting to reset
minFreq = 1 on insert.A fresh insert always lands in
buckets[1] with frequency 1 — so minFreq must become 1 regardless of what it was before. Skip the reset and the next eviction will pop from the wrong bucket, dropping a hotter key than it should.Not advancing
minFreq when its bucket empties via promotion.When a
get bumps the last node out of buckets[minFreq], that bucket is now empty — minFreq must advance to the next non-empty freq (typically minFreq + 1). Forget this and the next eviction looks into an empty bucket; either you crash or you silently drop the wrong entry. The check belongs in one place — right after every “remove from old bucket” step.Evicting before checking capacity.
The eviction step is only triggered when
size == capacity and the key is new. Run the eviction unconditionally and you’ll drop a node on every put, including updates and non-full inserts — the cache stays smaller than it should and hit rate craters. Branch order matters: update? evict? insert? in that exact order.06 / Go practice — on LeetCode
Four problems. LFU Cache is the canonical implementation question. The other three stretch the “frequency-bookkeeping” muscle in different shapes — same hash-map-plus-bucket-list architecture, different invariants.
— / When to use which
LRU
Use when recency is the signal that matters — the entry you used most recently is the one most likely to be used again. Hash map maps key → node; doubly-linked list keeps the order. Get and put each touch O(1) pointers and one map lookup.
hashmap + doubly-linked list · LC 146
LFU
Use when frequency matters — a hot key with many recent hits should survive even if a never-touched-again key was inserted last. Hash map → node; per-frequency bucket lists; a `minFreq` pointer to the bucket holding the next eviction candidate. O(1) at the cost of more bookkeeping.
hashmap + frequency buckets · LC 460