Cruxly

Cruxly › Low-level design › LLD Exercises

LFU Cache

eviction by frequency, not recency — and both O(1) is a different structure than LRU's

Open the interactive lesson

Prompt: design an LFU (Least Frequently Used) cache. get(key) and put(key, value), both O(1), fixed capacity. On eviction, remove the entry with the lowest access frequency; if multiple entries tie for lowest frequency, evict the least recently used among them.

45 minutes. This is not "LRU with a counter bolted on" — frequency buckets that need their own O(1) eviction-within-a-bucket is a genuinely different structure, and the tie-break rule is where most attempts quietly become O(n).

Applying the five moves: nouns are Entry (key, value, frequency), FrequencyBucket (an LRU-ordered list of entries sharing one frequency), and a minFrequency pointer — that last one looks like an implementation detail but is genuinely part of the model, because without it finding the lowest-frequency bucket is a search, not a lookup. The invariant is "every entry lives in exactly the bucket matching its current frequency, and minFrequency always points at the lowest non-empty bucket" — two clauses, and the second is the one that breaks silently if a bucket empties and nothing updates the pointer. No interface seam belongs here (frequency decay would be one, but it's explicitly a follow-up rather than in scope — name it as deliberately deferred). Concurrency: like LRU, the honest first answer is one lock around the whole structure, because a get() mutates frequency and therefore moves an entry between buckets — meaning even reads are writes here, which is a sharper observation than it sounds and worth saying out loud, since it rules out the naive "reads don't need locking" assumption.

Scope, and why this is not 'LRU plus a counter'

In scope: get, put, both O(1), eviction by lowest frequency with LRU as the tie-breaker among equal frequencies. Out of scope (say it): frequency decay over time (a real feature of production LFU caches, meaningfully harder — name it as a follow-up), distributed/sharded LFU, persistence.

The tempting first design — a HashMap from key to frequency, plus a single structure sorted by frequency — breaks the O(1) requirement the moment you look at what get has to do. Every get increments a frequency, which means the key's position in a frequency-sorted structure changes; re-sorting or re-positioning within a sorted structure on every single get is not O(1), no matter how the sort is implemented.

The actual requirement — O(1) for both operations, with a two-level tie-break (frequency first, recency second) — forces a specific, less obvious structure: a map from frequency to a doubly-linked list of keys at that frequency, where each per-frequency list is itself LRU-ordered. Incrementing a key's frequency becomes removing it from its current frequency's list and appending it to the next frequency's list — a bucket-to-bucket move, which is O(1), not a re-sort of anything. This is the specific insight that separates LFU from "LRU with an extra field," and naming it before writing code is the strongest opening move.

The classes: frequency buckets, each an LRU list

public class LFUCache {
    private final int capacity;
    private int minFrequency = 0;               // tracks the lowest frequency currently in use — O(1) to find eviction target
    private final Map<Integer, Node> keyToNode = new HashMap<>();
    private final Map<Integer, LinkedHashSet<Node>> freqToNodes = new HashMap<>();  // insertion order = LRU within this frequency

    static class Node {
        int key, value, freq = 1;
        Node(int key, int value) { this.key = key; this.value = value; }
    }

    public int get(int key) {
        Node node = keyToNode.get(key);
        if (node == null) return -1;
        touch(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (capacity <= 0) return;
        Node node = keyToNode.get(key);
        if (node != null) { node.value = value; touch(node); return; }

        if (keyToNode.size() >= capacity) {
            // Evict the LRU entry from the LOWEST-frequency bucket — this is
            // the two-level tie-break, both parts O(1) because minFrequency
            // is tracked incrementally, never recomputed by scanning.
            LinkedHashSet<Node> minBucket = freqToNodes.get(minFrequency);
            Node evict = minBucket.iterator().next();      // first-inserted = least-recently-used in this bucket
            minBucket.remove(evict);
            keyToNode.remove(evict.key);
        }

        Node fresh = new Node(key, value);
        keyToNode.put(key, fresh);
        freqToNodes.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(fresh);
        minFrequency = 1;    // any newly-inserted key is at frequency 1, which is now the minimum
    }

    /** Moves a node from its current frequency's bucket to the next frequency's
     *  bucket — this is the O(1) operation that replaces re-sorting entirely. */
    private void touch(Node node) {
        int oldFreq = node.freq;
        freqToNodes.get(oldFreq).remove(node);
        if (freqToNodes.get(oldFreq).isEmpty()) {
            freqToNodes.remove(oldFreq);
            if (minFrequency == oldFreq) minFrequency++;   // the bucket that WAS the minimum is now gone
        }
        node.freq++;
        freqToNodes.computeIfAbsent(node.freq, k -> new LinkedHashSet<>()).add(node);
    }
}

minFrequency is maintained incrementally, never recomputed by scanning freqToNodes — it only ever needs to change in two places: reset to 1 on every put of a new key (a new key is always the new minimum), and incremented when touch empties out the bucket that was previously the minimum. Recomputing it by finding the smallest key in freqToNodes on demand would reintroduce an O(number of distinct frequencies) cost exactly where the design needs O(1).

Why LinkedHashSet inside each bucket, and the eviction tie-break

Using LinkedHashSet (or an intrusive doubly-linked list) for each frequency bucket, rather than a plain List, is what makes the tie-break itself O(1). A LinkedHashSet preserves insertion order and gives O(1) removal of an arbitrary element by reference — a plain ArrayList would need O(n) removal to take an element out of the middle, reintroducing exactly the cost the whole design is trying to avoid.

This is a genuinely different structure from LRU's single doubly-linked list, not a small variation — LRU has one ordered list because it has one dimension (recency); LFU has one ordered list per frequency value because it has two dimensions (frequency, then recency within frequency), and stating that this is why LFU is harder than LRU, rather than assuming they're the same problem with a different name, is the actual signal being tested.

Follow-ups they will ask

"Add frequency decay — old high-frequency entries shouldn't stay 'hot' forever if they stop being accessed." This is a real, meaningfully harder production concern: the clean frequency-bucket structure above assumes frequency only ever increases, and decay (halving frequencies periodically, or using a time-weighted score instead of a raw count) breaks the "just move to bucket N+1" simplicity, potentially requiring an entry to move to a lower bucket on a decay pass, which the current structure doesn't support without additional bookkeeping — naming this as a real structural challenge, not a one-line addition, is the honest answer.

"What if two entries have the same frequency AND were inserted at the exact same time?" This pushes on the tie-break rule's definition of "same time," which in a single-threaded or properly-locked implementation can't actually happen (insertion order into a LinkedHashSet is well-defined even for same-timestamp events) — the interesting version of this question is really about concurrent put/get calls racing, which needs the same lock-granularity discussion as the LRU cache elsewhere in this track: one lock around the whole cache is simple and correct, sharding by key hash trades exact LFU ordering for reduced contention.

"Why not just use a min-heap keyed by (frequency, last-access-time) instead of the bucket structure?" A min-heap gives O(log n) operations, not O(1) — the prompt's O(1) requirement specifically rules out any heap-based approach, and naming why a heap doesn't meet the stated bound (rather than defaulting to a heap because it's the first idea that comes to mind for "find the minimum") is exactly the kind of derivation-over-recall signal this whole exercise is testing for.

How to say it in the interview

"The tempting shortcut is a HashMap of key to frequency plus a single sorted structure by frequency, but re-sorting or re-positioning on every single get() breaks the O(1) requirement immediately. The actual answer needs a frequency-to-bucket map, where each bucket is itself an LRU-ordered list, so incrementing frequency is a bucket-to-bucket move, not a re-sort - and that nested structure is the real exercise, not a small variation on the LRU cache."

Checklist

Practice this interactively
Share this lessonWhatsAppLinkedInX

Related lessons