LRU Cache Interview: Invariants, Eviction, and Follow-Up Requirements

An LRU cache interview is not mainly a linked-list syntax test. It asks whether two structures can describe one set of entries without drifting. A hashmap gives key → node lookup. A doubly linked list orders those same nodes from most recently used to least recently used. get and an update of an existing key normally refresh recency; inserting beyond capacity evicts exactly the tail-side data node.

Python officially documents OrderedDict.move_to_end() and popitem(last=False), and its collections docs include LRU-style recipes. functools.lru_cache provides a standard memoization policy with observable hit/miss information. In an interview, build the requested structure, then use library behavior only as a comparison—not as a substitute for the invariant.

LRU Cache Interview: Quick Answer

Use dummy head and tail sentinels. head.next is MRU; tail.prev is LRU. Every cached node appears exactly once between them and exactly once in the map. remove(node) reconnects its neighbors. add_front(node) inserts after head. touch(node) removes then adds front. On put(existing), update value and touch without changing size. On new insertion, evict tail.prev only when size exceeds capacity.

Reject negative capacity and handle zero capacity without trying to remove a sentinel. State average O(1) for hashmap operations under normal assumptions and worst-case O(1) pointer splices; do not extend that promise to TTL scans, byte-sized capacity, persistence, or distributed coherence without a new design.

Write the Bijection and Boundary Invariants

The list contains exactly the nodes referenced by the map. Each data node has non-null previous and next links while cached. head.prev and tail.next are unused; head.next.prev == head and tail.prev.next == tail. Forward traversal from head reaches tail without a cycle, and the number of data nodes equals len(map).

Define recency: after a successful get or put, that key is immediately after head. The least recent data node is immediately before tail. Failed gets usually do not affect order. A peek follow-up may read without refresh; name it separately. These statements make pointer helpers testable and prevent accidental eviction from the wrong end.

Implement Pointer Helpers Once

class Node:
    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = None

def detach(node):
    node.prev.next = node.next
    node.next.prev = node.prev

def after(head, node):
    node.prev, node.next = head, head.next
    head.next.prev = node
    head.next = node

Cache operations should call these helpers rather than duplicating four pointer assignments. Detach only nodes known to be linked; adding the same node twice creates cycles or duplicates. Sentinels remove empty-list special cases, but capacity zero still needs the logical rule “store nothing.” Keep map deletion and list detachment in one eviction function.

Trace Updates and Eviction

With capacity two: put(A,1) gives [A]; put(B,2) gives [B,A]; get(A) returns 1 and gives [A,B]; put(C,3) temporarily adds C, then evicts B, leaving [C,A]. put(A,9) updates in place and yields [A,C] with two entries—not a second A.

A common bug updates the map with a new Node for A but leaves the old A in the list. Another updates the value without touching recency. A third evicts after insertion but removes only from the list, leaking the map entry. The bijection scan catches all three. Tests should compare both returned values and order after every operation.

Handle Capacity and Size Policies

Entry-count capacity is the baseline. For capacity zero, every put is a no-op and every get misses. For byte capacity, each item has a weight; an insertion may evict several nodes, and one item larger than the limit must be rejected or left uncached. The loop becomes while total_weight > capacity, and updates must subtract the old weight before adding the new one.

Eviction callbacks add failure questions. Remove the node from authoritative cache state before calling untrusted cleanup, or define rollback if callback failure must keep it. Pinning entries can make the LRU tail ineligible, requiring another index or a scan that breaks constant time. Do not hide these costs behind the original complexity claim.

Add TTL without Confusing Expiry and Recency

TTL defines eligibility by time; LRU defines eviction among eligible cached entries. Lazy expiry checks a node on access and removes it if expired, but expired cold entries can occupy capacity. A min-heap of expiry times supports eager cleanup with lazy version checks, adding O(log n) maintenance and stale heap entries. A timing wheel suits coarse large-scale expiry.

Decide whether updating a key refreshes TTL and whether an expired get counts as a miss without recency change. Use a monotonic clock for durations. If TTL and LRU both choose victims, expire first, then use LRU for capacity. This follow-up adds a second ordering dimension; one linked list cannot efficiently provide both earliest expiry and least recency.

Name Concurrency and Persistence Limits

A single mutex around get and put preserves map-list atomicity and is a correct starting point, though it serializes hits. Moving a node on every read makes LRU write-heavy. Segmented caches, approximate recency, or read buffers improve concurrency at the cost of exact global LRU. State the chosen consistency before proposing lock striping.

Persistence changes the object entirely. A process crash can lose in-memory state; write-through, write-back, and cache-aside policies have different source-of-truth rules. Serializing only the hashmap loses recency unless order is stored too. Distributed caches cannot keep one exact global linked list cheaply across shards; local LRU per shard is common and may evict differently after rebalancing.

Test State after Every Operation

Test negative and zero capacity, one slot, repeated gets, missing gets, update at capacity, eviction order, duplicate keys, and arbitrary hashable values. After each step, traverse forward and backward, compare node identity sets with map values, count nodes, and check neighbor symmetry. These invariant checks are slow but ideal for a small test oracle.

Compare operation traces against a simple reference model: an ordinary dictionary plus a list of keys. The reference can be O(n) because tests stay small and independence matters more than speed. Randomly generate gets and puts, run both, and compare results and recency order after every operation.

Average hashmap lookup is not a hard real-time guarantee under adversarial hashing. Mention it if the interviewer presses on worst-case complexity, then stay within the usual coding assumption unless the prompt changes. Clear correctness beats designing a custom hash table inside an LRU question.

Make the Answer Reviewable

Turn the lru cache design into a small deterministic review before adding more scale. Write the initial state, five to ten timestamped inputs, every expected state transition, and the exact read result at two watermarks. Replay one input, deliver another out of order, pause one consumer, and rebuild the serving view from its durable boundary. The replay should not create an extra effect, the stale input should follow the declared version rule, and the rebuilt read should match the authoritative result through the same watermark.

Keep expected results independent of the implementation. If the same code produces both the output and the assertion, a shared assumption can hide the defect. Add one invariant check that scans all state, even if production serves a faster index. For a distributed design, say which part this fixture does not prove: it does not measure production latency, network partitions, or capacity. Load and fault tests come next, using the traffic and error budgets already stated.

Finish with an operational table: signal, healthy range, action, and user-visible consequence. Include ingestion or queue age, rejected or duplicate work, authoritative-versus-serving divergence, and tail read latency. This makes the proposal inspectable. An interviewer can now change one requirement and see exactly which state, test, and alert must change with it.

Separate what the review establishes from what it leaves open. A passing deterministic fixture proves the declared state transitions for those inputs. It does not establish performance at scale, fairness across real users, or behavior during every network failure. Add a capacity test for the estimated peak, a skew test concentrated on one key or partition, and a fault test at the acknowledgment boundary. Record versions and random seeds so failures can be replayed. When a result differs from expectation, reduce it to the smallest trace, name the violated invariant, and repair that transition before retuning capacity. This evidence-first sequence keeps correctness questions from being hidden inside infrastructure changes.

Keep the review artifact beside the implementation and date the environment that produced it. If a later optimization changes ordering, batching, numeric width, or retry behavior, rerun the same trace before accepting the new result. The invariant is the stable comparison point; the component diagram is not.

A 45-Minute Interview Structure

Spend four minutes defining refresh, miss, update, capacity, and return semantics. Write the invariants before code. Use five minutes for node and sentinels, fifteen for get/put and helpers, eight for the A/B/C trace, and six for invariant tests. Reserve seven for one follow-up such as TTL, weights, or concurrency. Update the complexity statement when the follow-up changes the structure.

Final Takeaway

An LRU cache is correct when its map and list remain a bijection and the list ends have one stable meaning. Centralize detach and insert helpers, refresh on the declared successful operations, update existing nodes without growth, and handle zero capacity. Follow-ups such as TTL, weights, concurrency, and persistence add state or ordering and deserve new invariants rather than patched slogans.

Sources and Further Reading

• Python collections OrderedDict
• Python functools.lru_cache
• Python data model hashing
• Python threading locks

Documentation supports the stated system or algorithm behavior; individual question records support only their own practice contracts. Architecture recommendations and interview sequencing are editorial inference.