LFU Cache Design

Description

An LFU (least frequently used) cache evicts the entry that has been used the fewest times, rather than the one used longest ago. It protects items that are popular over time from being pushed out by something touched once, which suits workloads with stable popularity - and it's a classic hard design-interview question because O(1) eviction needs careful bookkeeping. This skill covers that design, its one notorious bug, and when LFU beats LRU.

Tracking "how often has each key been used" is easy; finding the least-frequently-used key quickly is not, if the only tool is a plain frequency map:

class NaiveLFUCache {
    private Map<Integer, Integer> values = new HashMap<>();
    private Map<Integer, Integer> freq = new HashMap<>();
    private int capacity;

    public int get(int key) {
        if (!values.containsKey(key)) return -1;
        freq.merge(key, 1, Integer::sum);
        return values.get(key);
    }

    public void put(int key, int value) {
        if (!values.containsKey(key) && values.size() == capacity) {
            int leastFreqKey = Collections.min(freq.entrySet(), Map.Entry.comparingByValue()).getKey(); // scans every entry
            values.remove(leastFreqKey);
            freq.remove(leastFreqKey);
        }
        values.put(key, value);
        freq.merge(key, 1, Integer::sum);
    }
}

class NaiveLFUCache:
    def __init__(self, capacity: int):
        self._values: dict[int, int] = {}
        self._freq: dict[int, int] = {}
        self._capacity = capacity

    def get(self, key: int) -> int:
        if key not in self._values:
            return -1
        self._freq[key] += 1
        return self._values[key]

    def put(self, key: int, value: int) -> None:
        if key not in self._values and len(self._values) == self._capacity:
            least = min(self._freq, key=self._freq.get)     # scans every entry
            del self._values[least]
            del self._freq[least]
        self._values[key] = value
        self._freq[key] = self._freq.get(key, 0) + 1

Collections.min (Python: min(freq, key=freq.get)) has to walk every single entry in freq to find the minimum, every time the cache is full and a new key arrives - the exact same O(n)-per-eviction problem naive LRU has, just triggered by a frequency comparison instead of a recency scan.

We'll go from simple to more technical:

1. The design: values, frequencies, buckets of keys per frequency, and minFreq.
2. The "touch" operation that keeps everything in sync.
3. Where frequency beats recency, and where it misleads.
4. The minFreq bug, decay, and choosing between LFU and LRU.

The pattern

Map<Integer, Integer> keyToVal;
Map<Integer, Integer> keyToFreq;
Map<Integer, LinkedHashSet<Integer>> freqToKeys; // insertion order breaks ties by recency within a frequency
int minFreq;

key_to_val: dict[int, int]
key_to_freq: dict[int, int]
freq_to_keys: defaultdict[int, dict[int, None]]   # a dict keeps insertion order: ties break by recency
min_freq: int

On every get/put of an existing key ("touch"): remove the key from freqToKeys[oldFreq] (bumping minFreq if that was the last key at minFreq), increment its frequency, and re-add it to freqToKeys[newFreq]. On eviction: pull any key out of freqToKeys[minFreq] (the front, if you want strict recency tie-breaking) - it's guaranteed to be a least-frequently-used entry by definition of minFreq.

The "touch" is the heart of it:

private void touch(int key) {
    int oldFreq = keyToFreq.get(key);
    LinkedHashSet<Integer> bucket = freqToKeys.get(oldFreq);
    bucket.remove(key);
    if (bucket.isEmpty() && minFreq == oldFreq) minFreq++;       // emptied the lowest bucket
    keyToFreq.put(key, oldFreq + 1);
    freqToKeys.computeIfAbsent(oldFreq + 1, f -> new LinkedHashSet<>()).add(key);   // newest at the end
}

def _touch(self, key: int) -> None:
    old_freq = self._key_to_freq[key]
    bucket = self._freq_to_keys[old_freq]
    del bucket[key]
    if not bucket and self._min_freq == old_freq:
        self._min_freq += 1                               # emptied the lowest bucket
    self._key_to_freq[key] = old_freq + 1
    self._freq_to_keys[old_freq + 1][key] = None          # newest at the end

minFreq++ is safe because the key that emptied the bucket just landed at exactly oldFreq + 1. A brand-new key resets minFreq to 1, and eviction takes freqToKeys.get(minFreq).iterator().next() (Python: next(iter(freq_to_keys[min_freq]))) - the oldest key at the lowest frequency.

Where you'll see it

CDN and cache-tier eviction sometimes prefers frequency over recency specifically because a resource "recently touched exactly once" (LRU would protect it) can be less valuable to keep than one "touched constantly but not in the last second" (LRU would evict it first) - the right choice depends on the actual access pattern, not a universal rule that one policy beats the other.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. A key's frequency bucket has 3 other keys still in it after this key's frequency increases. Does minFreq need to change?

2. Why does put() reset minFreq to 1 whenever a brand-new key is inserted, regardless of what it was before?

3. You need a peek(key) that returns a value without affecting eviction order. Why is it wrong to implement it by calling get(key) and just ignoring whatever side effects that has?

Key takeaways

• Eviction always pulls from the current minFreq bucket - that's the entire reason minFreq is tracked instead of recomputed by scanning.
• minFreq must be recomputed (bumped) exactly when its bucket empties - not on every touch, only when that specific bucket runs out.
• Ties within a frequency break by recency, which is why each bucket is a LinkedHashSet, not a plain HashSet - in Python, a dict with None values, not a set.
• A new key always starts at frequency 1, which is always the new minimum - no comparison needed on insert.
• LFU trades more bookkeeping than LRU for immunity to "recently touched once" beating "constantly touched" - at the cost of old popularity being able to protect a now-cold entry.