LFU Cache Interview: Frequency Buckets, Tie-Breaking, and Update Invariants

An LFU cache interview begins where LRU ends. Evict the least frequently used key, but if several keys have the same frequency, choose a deterministic tie rule—usually least recently used within that frequency. A heap can implement the order in O(log n). The canonical O(1)-average answer instead groups nodes into frequency buckets and keeps recency order inside each bucket.

The Shah, Mitra, and Matani technical report presents an O(1) LFU eviction scheme. That is a primary technical source for the structure, not evidence that LFU is best for every workload. Pure lifetime frequency can keep yesterday's hot key forever, so production follow-ups often add aging or an admission policy such as TinyLFU.

LFU Cache Interview: Quick Answer

Maintain key → node, frequency → ordered bucket, and minFreq. A node stores key, value, and current frequency. A successful get removes the node from its old bucket, deletes an empty bucket, increments frequency, and inserts it at the MRU side of the new bucket. If the empty old bucket was minFreq, increment minFreq by one.

A new key starts at frequency one, so insertion sets minFreq=1. When full, evict the LRU node from bucket minFreq. An existing-key put updates the value and, under the common contract, counts as access; state that choice. Capacity zero stores nothing. Hash maps and constant-time ordered buckets give average O(1) get and put under ordinary hashing assumptions.

State All Three Invariants

Every cached key maps to exactly one node. Every node appears in exactly one bucket whose label equals the node's frequency. Inside a bucket, order runs MRU to LRU or the reverse—choose and keep it consistent. minFreq equals the smallest frequency among cached nodes; it has no meaningful value when the cache is empty.

Bucket membership and key lookup form a bijection. A slow invariant checker can traverse all buckets, verify node frequency, detect duplicate node identities, compare keys with the map, and recompute the minimum. This is especially useful because a wrong minFreq may remain hidden until a later eviction.

Centralize the Promotion Transition

Let touch(node) own every frequency change. Record f=node.freq, remove the node from bucket f, and if that bucket becomes empty, delete it. If minFreq==f, set it to f+1; no smaller frequency can exist because f was the minimum, and the touched node moves exactly one step. Then set node.freq=f+1 and add it to the MRU side of that bucket.

Do not scan for a new minimum. The transition proof makes constant time possible. A bug that increments minFreq whenever any bucket empties is wrong: an empty frequency 7 says nothing about existing frequency 2 nodes. Another bug leaves empty buckets and evicts from them. Keep creation, removal, and min updates in the same helper.

Trace the LRU Tie-Break

With capacity two, put(A,1) and put(B,2) leave both at frequency one, with B more recent. get(A) promotes A to frequency two, so B is the unique LFU victim. put(C,3) evicts B and inserts C at frequency one, resetting minFreq=1. Now get(C) moves C to frequency two. A and C tie on frequency; A is older within bucket two, so put(D,4) evicts A.

This trace exercises both reasons for eviction: lower frequency and LRU within a tie. It also catches failure to reset minimum on insertion. Write expected bucket order after every step, not only final return values.

Implement with Ordered Buckets

from collections import OrderedDict, defaultdict

class LFU:
    def __init__(self, capacity):
        self.capacity = capacity
        self.values = {}          # key -> [value, frequency]
        self.buckets = defaultdict(OrderedDict)
        self.min_freq = 0

    def _touch(self, key):
        value, freq = self.values[key]
        del self.buckets[freq][key]
        if not self.buckets[freq]:
            del self.buckets[freq]
            if self.min_freq == freq:
                self.min_freq += 1
        self.values[key][1] += 1
        self.buckets[freq + 1][key] = None
        return value

OrderedDict makes each frequency bucket recency-aware. A manual doubly linked list is appropriate when the interviewer requires node-level implementation; the same invariants apply. Complete get/put from the transition rather than duplicating promotion logic.

Define Put and Capacity Semantics

If capacity is zero, return before touching buckets. For an existing key, update its value and call touch under the common “write is use” contract. If writes should not affect frequency, update only the value—but state the divergence. For a new key at full capacity, pop the LRU key from buckets[minFreq], remove it from values, then insert frequency one and set minFreq=1.

Weighted capacity complicates eviction because several victims may be needed and the lowest-frequency large object may not be the best value. TTL introduces an expiry order separate from frequency. Pinning can leave the min bucket ineligible. Each requirement changes the policy or complexity; do not preserve the O(1) label by ignoring it.

Explain Aging and Admission

Lifetime LFU can suffer cache pollution. A key accessed 10,000 times yesterday may remain while moderately popular current keys churn at frequency one. Aging periodically decays counts, uses epochs, or caps frequencies, but updating every node at once is expensive. Lazy decay stores epochs or relative counters and makes comparisons more complex.

TinyLFU is an admission policy: an approximate frequency sketch decides whether a candidate should displace a resident, often alongside a recency-based main cache. It is not the same as storing every resident in exact LFU buckets. Mention it as a policy follow-up, label approximation and decay, and keep the coding baseline exact. Measure hit rate and workload phase changes before declaring one policy better.

Compare LFU with Simpler Policies

LRU adapts quickly to recency and needs one global order. LFU favors repeatedly popular keys but needs frequency state and a tie rule. FIFO ignores both reuse and frequency but is simple. Random eviction can perform surprisingly well under some workloads and minimizes bookkeeping. The workload's reuse distribution decides, not the policy name.

A min-heap of (frequency,time,key,version) is easier to explain but pushes a new record on every access and skips stale records at eviction, giving logarithmic work and potential heap growth. Balanced trees maintain a full order with logarithmic updates. Frequency buckets achieve average constant time because promotion is always from f to f+1 and eviction consults one known minimum bucket.

Distributed exact LFU is costly because every hit becomes shared write state. Per-shard policies are scalable but not a global optimum. Approximate counters, sampled admission, and local caches trade exactness for throughput. State the scope of “least frequent” before scaling.

Make the Answer Reviewable

Turn the lfu 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 on get/put, tie, update, and capacity semantics. Write the three invariants in five. Use ten minutes for buckets and promotion, ten for put/eviction, and eight for the A/B/C/D trace. Spend six on complexity and invariant checks. Reserve seven for aging, TTL, weights, or distribution. Keep minFreq transitions visible; that scalar is the usual source of hidden failures.

Final Takeaway

O(1) LFU needs more than a frequency count. Keys own nodes, frequencies own recency-ordered buckets, and minFreq points to the only eviction bucket. Promotion must update all three states atomically, insertion resets the minimum to one, and ties use a declared LRU order. Then explain where exact lifetime frequency fails and why aging or admission is a separate policy decision.

Sources and Further Reading

• Shah, Mitra, and Matani: O(1) LFU
• TinyLFU: A Highly Efficient Cache Admission Policy
• Python OrderedDict
• Python defaultdict

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.