Cache (LRU / LFU)

Step 1 · Clarify — 4 minutes

• What is the capacity measured in — entries or bytes? — say entries, and add the one sentence that shows you know better: “real caches weigh entries, because a 2 KB value and a 2 MB value are not the same tenant of a fixed memory budget.”
• What should get return on a miss? — an empty Optional (or null, or undefined). Not an exception. A miss is the normal case, not an error.
• Does the cache load on a miss, or does the caller? — simplest is: the caller loads and calls put. Mention that a loading cache which takes a supplier is the nicer API and is what Caffeine and Guava do.
• LRU only, or should the policy be pluggable? — this is the question that decides the shape of your answer. Ask it early and they will usually say “start with LRU, then we will talk.” That is your cue to build the seam from the first minute.
• Will several threads use it? — say yes, one lock, and be ready for the twist in the follow-ups: get mutates.
• TTL, persistence, distribution, stampede protection? — out of scope in one sentence. TTL is expiry, which is a different axis from eviction, and mixing them up costs you time. Depth on that lives in In-memory key-value store.

Step 2 · Why neither structure alone works

Start from the two operations and ask what each costs. get(key) needs to find a value by key. evict() needs to find the least-recently-used entry. There is no single ordinary structure that does both in constant time — and understanding why is the entire design.

Step 3 · The pointer surgery, spelled out

“And then it moves to the front” is where most candidates stop. Do not. Moving a node is two operations — unlink and insert at head — and between them there are exactly six assignments. Say them, write them, and the interviewer stops probing.

private void unlink(Node<K> n) {
    n.prev.next = n.next;      // 1
    n.next.prev = n.prev;      // 2
    n.prev = null; n.next = null;
}

private void insertAtHead(Node<K> n) {
    n.next = head.next;        // 3
    n.prev = head;             // 4
    head.next.prev = n;        // 5   <- must happen BEFORE line 6
    head.next = n;             // 6
}

// "this key was just used" — the whole of LRU
void recordAccess(K key) {
    Node<K> n = nodes.get(key);
    if (n == null) return;
    unlink(n);
    insertAtHead(n);
}

// "who dies next?" — no scan, no comparison, no loop
K evictCandidate() {
    return tail.prev == head ? null : tail.prev.key;
}

Why the list must be doubly linked

This is the question that separates people who memorised the answer from people who understand it. You found the node through the map in O(1). To unlink it you need to change its predecessor's next pointer. With only next pointers, the node has no idea who its predecessor is — and the only way to find out is to walk from the head until you find the node whose next is you.

Step 4 · The two flows, precisely

Step 5 · The seam — EvictionPolicy is an interface

Here is the moment the problem stops being a LeetCode exercise and becomes a design answer. Cache should own storage, capacity and counters. It should not own an opinion about who dies. Give the opinion its own type, with four methods:

interface EvictionPolicy<K> {
    void recordInsert(K key);   // a brand-new key entered the cache
    void recordAccess(K key);   // an existing key was read or overwritten
    void recordRemove(K key);   // a key left the cache
    K    evictCandidate();      // who dies next — null if empty
}

Now read Cache.get() again: it looks up the value, bumps a counter, and calls recordAccess. It never says the word recency. Swap new LruPolicy() for new LfuPolicy() in the constructor and zero lines inside Cache change. That is Strategy doing exactly what it is for, and it is the Open/Closed (OCP) principle stated as code: open to a new policy, closed to editing the cache.

Step 6 · LFU is a different structure, not a tweak

“Now evict the least-frequently-used key instead.” The naive move is to add a count field to each node and scan for the minimum — which is O(n) and undoes everything you just built. LFU needs its own three pieces:

1. key → frequency — how many times each key has been touched.
2. frequency → a doubly-linked list of the keys at that frequency, ordered by recency inside the bucket.
3. minFreq — a single integer holding the lowest frequency currently in use. This is the whole trick: without it, finding the victim means searching the buckets.

On access, a key moves from bucket f to bucket f+1. If bucket f is now empty and f == minFreq, then minFreq++ — and that is the only place minFreq ever increases, because a key can only ever gain one frequency at a time. On insert, the new key goes into bucket 1 and minFreq = 1, because a fresh key is always the new minimum. Eviction takes the oldest entry in bucket minFreq — so the tie inside a frequency bucket is broken by recency, which is to say LFU has an LRU hiding inside it. Say that sentence; interviewers ask about the tie-break specifically.

Thread safety — where the surprise is

Ask any candidate to make a cache thread-safe and they reach for a read-write lock: “many readers, one writer.” It is the wrong instinct here, and knowing why is worth a point. get() is not a read. It calls recordAccess, which unlinks a node and relinks it at the head — six pointer writes on a structure shared by everyone. Two concurrent gets on different keys can corrupt the list into a cycle, and then a later traversal never terminates.

• The 60-minute answer: one lock (synchronized, or a ReentrantLock) around get and put. Four characters of code and it is correct. Say it, write it, move on. Background: Locks, Mutex, Semaphore.
• Why a ReadWriteLock does not help: everything takes the write lock anyway, because every operation mutates. You get the complexity of Read-Write locks and none of the concurrency.
• How you would actually scale it: striping — split the key space into N independent segments, each with its own map, list and lock, so keys that hash to different segments never contend. The cost is that eviction becomes per-segment, so the policy is now approximate across the whole cache. That is a fine trade and it is what real caches do.
• What production caches do instead: Caffeine keeps the reads lock-free by writing each access into a small ring buffer and replaying those buffers onto the linked list later, in one thread. The reordering leaves the read path entirely. Mention it in one sentence; do not attempt it.

What the seam actually buys you

The 60 minutes

The follow-ups

• “Java has this built in, doesn't it?” → yes: new LinkedHashMap<>(cap, 0.75f, true) with removeEldestEntry overridden is a six-line LRU, and the true is access order. Name it — it shows you know the library. Then say the quiet part: “in this round I assume you want the hand-rolled version, since that is what is being tested.” Offering the shortcut and declining it reads better than not knowing it.
• “Now make it LFU.” → the whole point of the seam. New class, buckets plus minFreq, Cache untouched. If they push further: the tie inside a bucket is LRU, and pure LFU pollutes.
• “Make it thread-safe.” → one lock; explain that get mutates so a read-write lock buys nothing; mention striping and Caffeine's buffered replay as how you would scale it.
• “Distribute it across ten servers.” → a per-node LRU means ten caches with ten independent hit ratios and ten copies of the hot keys. Either route keys by consistent hashing so each key lives on one node, or accept the duplication and treat it as ten small caches. Invalidation across nodes is the genuinely hard part.
• “Write-through, write-back or write-around?” → write-through updates cache and store together (simple, always consistent, slower writes); write-back updates the cache and flushes later (fast, and you can lose data); write-around writes straight to the store and lets the next read populate the cache (good when writes are rarely re-read soon).
• “What happens when a hot key expires and a thousand requests miss at once?” → the thundering herd. One request loads and the rest wait on the same future, or you refresh slightly before expiry. One sentence, then stop — it is a whole problem of its own.
• “How would you test it?” → a fixed access trace with expected contents after each step, plus the boundary cases: capacity 1, put on an existing key, get on a missing key, and evicting down to empty.

How this round is lost

• A singly-linked list. It looks fine until you try to unlink a node found through the map, and then the whole O(1) claim collapses into a walk from the head.
• No sentinels. Every pointer assignment grows a null check, the empty-list and single-node cases get their own branches, and the first NullPointerException lands about four minutes later.
• Forgetting to move the node on get. This is the worst failure in the whole problem, because the code still works. Nothing throws. Nothing looks wrong. Your LRU is quietly a FIFO, and the only symptom is a hit ratio that is worse than it should be. The prototype has a chip for exactly this — see what you notice.
• put on an existing key evicting something. Overwriting a value must not change the size and must not kill a neighbour. Test it; it is one line and everybody skips it.
• The policy welded into the cache class. It works, and then “now make it LFU” has nowhere to land, and you spend the last fifteen minutes untangling get() instead of writing a second policy.
• Scanning for the LFU minimum. Adding a count field and calling Collections.min is the single most common way to answer the LFU follow-up wrongly. minFreq exists precisely so you never search.

The shape you just learned

Strip the caching away and there are two reusable ideas here. The first: when one structure cannot answer both of your questions, keep two and make them point at each other. The second: when a rule is likely to change, give the rule its own type — because the caller then never has to know which rule is in force.

• Any LRU-ish eviction — connection pools that close the idlest connection, session stores, image and tile caches, browser back/forward stacks.
• Ordered maps in general — a hash map plus a linked list is exactly what LinkedHashMap and Python's dict are, and now you know why insertion order is free in one and not the other.
• Task schedulers — the “which task runs next” decision is the same seam as “which key dies next”, and it belongs behind an interface for exactly the same reason. See Strategy.
• Rate limiters and quota buckets — a counter per key with a way to find the extreme value quickly; the minFreq trick generalises to “maintain the answer instead of searching for it”.
• Undo stacks and MRU file lists — the same list, the same move-to-front, the same tail-drop when the list gets too long.

Where this design stops working

• At high concurrency. One lock around a structure that every read mutates is a hard serialisation point. The escapes are striping (approximate eviction, real parallelism) or moving the reordering off the read path entirely, which is what Caffeine's buffered replay does.
• When entries have wildly different sizes. Counting entries stops meaning anything; you need a weigher and a byte budget, and then eviction is “drop until under the limit” rather than “drop one”.
• When the workload scans. One pass over a large table walks LRU's entire contents out of the cache and leaves nothing useful behind. This is precisely what LFU and TinyLFU exist to resist.
• When the cache is distributed. A per-node LRU means N independent caches, N hit ratios, and N copies of the hot keys. Routing keys to owners fixes the duplication and introduces invalidation, which is a harder problem than eviction ever was.
• When staleness matters more than memory. Then you want expiry, not eviction, and the two mechanisms are independent — an entry can be evicted while fresh and go stale while resident.