LFU Cache — LeetCode 460 Hard Design Problem

Problem Statement#

Design a Least Frequently Used (LFU) cache. Implement the LFUCache class.

• LFUCache(capacity) — initialize with positive capacity
• get(key) — return value if exists, else -1, increment frequency
• put(key, value) — insert or update. If full, evict least frequently used. Tie-break by least recently used inside the same frequency

Both operations must run in O(1) average time.

Constraints:

• 0 less-equal capacity less-equal 100000
• 0 less-equal key, value less-equal 100000000
• Up to 200000 calls

Input:  ["LFUCache","put","put","get","put","get","get","put","get","get","get"]
        [[2],[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]
Output: [null,null,null,1,null,-1,3,null,-1,3,4]

Why This Problem Matters#

LFU Cache is the staff-level upgrade of LRU. It tests whether you can manage three coordinated data structures and still hit O(1). Google, Apple, and Meta ask it for senior systems roles, especially for teams owning caching, databases, or browsers.

LFU also models real workloads better than LRU when access is skewed — popular keys should stay even if not touched recently. Modern CDNs and browser caches use LFU-with-aging variants.

The Core Insight#

The hard part is maintaining min-frequency in O(1). The trick is three structures.

• key_to_node: key to DLL node containing key, value, freq
• freq_to_dll: frequency to a doubly linked list of nodes at that frequency, ordered by recency
• min_freq: integer pointer to the smallest non-empty frequency

Get and put bump a node from its current freq DLL to freq+1 DLL. If the moved node was the only one at min_freq, increment min_freq. On overflow, evict from the tail of freq_to_dll[min_freq] and remove from key_to_node.

Visual Dry Run#

Capacity 2. Operations: put 1 1, put 2 2, get 1, put 3 3, get 2.

Solution (Optimal)#

from collections import OrderedDict, defaultdict
 
class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.key_to_val_freq = {}
        self.freq_to_keys = defaultdict(OrderedDict)
 
    def _bump(self, key):
        value, freq = self.key_to_val_freq[key]
        del self.freq_to_keys[freq][key]
        if not self.freq_to_keys[freq]:
            del self.freq_to_keys[freq]
            if self.min_freq == freq:
                self.min_freq += 1
        self.freq_to_keys[freq + 1][key] = None
        self.key_to_val_freq[key] = (value, freq + 1)
 
    def get(self, key: int) -> int:
        if key not in self.key_to_val_freq:
            return -1
        value = self.key_to_val_freq[key][0]
        self._bump(key)
        return value
 
    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        if key in self.key_to_val_freq:
            self.key_to_val_freq[key] = (value, self.key_to_val_freq[key][1])
            self._bump(key)
            return
        if len(self.key_to_val_freq) == self.capacity:
            evict_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
            del self.key_to_val_freq[evict_key]
        self.key_to_val_freq[key] = (value, 1)
        self.freq_to_keys[1][key] = None
        self.min_freq = 1

var LFUCache = function(capacity) {
    this.capacity = capacity;
    this.minFreq = 0;
    this.keyToValFreq = new Map();
    this.freqToKeys = new Map();
};
 
LFUCache.prototype._bump = function(key) {
    const [value, freq] = this.keyToValFreq.get(key);
    this.freqToKeys.get(freq).delete(key);
    if (this.freqToKeys.get(freq).size === 0) {
        this.freqToKeys.delete(freq);
        if (this.minFreq === freq) this.minFreq++;
    }
    if (!this.freqToKeys.has(freq + 1)) this.freqToKeys.set(freq + 1, new Map());
    this.freqToKeys.get(freq + 1).set(key, true);
    this.keyToValFreq.set(key, [value, freq + 1]);
};
 
LFUCache.prototype.get = function(key) {
    if (!this.keyToValFreq.has(key)) return -1;
    const value = this.keyToValFreq.get(key)[0];
    this._bump(key);
    return value;
};
 
LFUCache.prototype.put = function(key, value) {
    if (this.capacity === 0) return;
    if (this.keyToValFreq.has(key)) {
        const freq = this.keyToValFreq.get(key)[1];
        this.keyToValFreq.set(key, [value, freq]);
        this._bump(key);
        return;
    }
    if (this.keyToValFreq.size === this.capacity) {
        const list = this.freqToKeys.get(this.minFreq);
        const evictKey = list.keys().next().value;
        list.delete(evictKey);
        this.keyToValFreq.delete(evictKey);
    }
    this.keyToValFreq.set(key, [value, 1]);
    if (!this.freqToKeys.has(1)) this.freqToKeys.set(1, new Map());
    this.freqToKeys.get(1).set(key, true);
    this.minFreq = 1;
};

Time: O(1) for both get and put — all map and ordered-dict operations are amortized constant. Space: O(capacity).

Common Mistakes#

• Forgetting to update min_freq when the last key at a frequency is removed
• Resetting min_freq to 1 only on insert of a brand new key, not on bump
• Using a list instead of an ordered dict, losing O(1) deletion
• Tie-breaking by frequency instead of recency within the same frequency
• Returning early from put without bumping when key exists

Interview Tips#

• Draw the three structures clearly and label the invariants
• Start with the easier LRU, then explain the LFU upgrade
• Mention that Python OrderedDict and JavaScript Map preserve insertion order, which gives the LRU tie-breaker for free
• Walk through one bump and one eviction by hand
• Mention that production LFU often uses approximate counters like Count-Min Sketch

Follow-up Questions#

• Add aging — periodically halve all frequencies so old hot keys can decay
• Implement W-TinyLFU — admission policy used by Caffeine cache
• Make it thread-safe with sharding
• Bound memory by entry size, not count
• Compare hit rate of LRU vs LFU on a Zipfian workload

Key Takeaways#

• LFU Cache is LeetCode 460, a hard design problem
• Three structures key it: key map, freq map of ordered keys, min_freq
• min_freq updates only when the bucket becomes empty during a bump
• Tie-breaker on eviction is least recently used within the smallest frequency
• OrderedDict and Map insertion order replace a manual DLL
• Real systems use W-TinyLFU and frequency aging
• Both Python and JavaScript implementations achieve true O(1)