LFU Cache — Three Hash Maps and Frequency Buckets for O(1) Operations

Problem Statement#

Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class:

• LFUCache(int capacity) — initialises the object with the given capacity.
• int get(int key) — returns the value of key if it exists, otherwise returns -1.
• void put(int key, int value) — updates the value if key exists, or inserts the key. When the cache reaches capacity, evict the least frequently used key. For ties, evict the least recently used among them.

Both get and put must run in O(1) average time complexity.

Constraints:

• 1 <= capacity <= 10^4
• 0 <= key <= 10^5
• 0 <= value <= 10^9
• At most 2 × 10^5 calls to get and put

LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);
lfu.put(2, 2);
lfu.get(1);      // returns 1, frequency of key 1 becomes 2
lfu.put(3, 3);   // evicts key 2 (freq 1, least recently used among freq-1 keys)
lfu.get(2);      // returns -1 (evicted)
lfu.get(3);      // returns 3, frequency of key 3 becomes 2
lfu.put(4, 4);   // evicts key 1 (LRU among freq-2 keys)
lfu.get(1);      // returns -1
lfu.get(3);      // returns 3
lfu.get(4);      // returns 4

Why This Problem Matters#

LFU Cache (LC 460) is one of the hardest design problems in the LeetCode canon and a benchmark for senior engineering candidates at Google and Amazon. It requires combining four distinct data structures — three hash maps and an ordered dictionary per frequency — all coordinated to achieve O(1) for every operation.

The LRU Cache (LC 146) is the entry-level cache design question. LFU Cache is the advanced version. Where LRU evicts the least recently used item, LFU evicts the least frequently used, breaking ties by recency. This additional frequency dimension requires a significantly more complex design.

Real-world caches use frequency-based eviction: web browsers retain frequently visited pages, CDNs keep popular assets, and database buffer pools use frequency-aware replacement. Understanding how to implement LFU in O(1) is directly relevant to systems engineering roles.

The key insight — maintaining a minimum frequency pointer and using OrderedDicts per frequency bucket — is an elegant O(1) design that often surprises even experienced candidates who assume LFU must be O(log n) via a priority queue.

The Core Insight#

Three hash maps:

1. key_val: maps key to value.
2. key_freq: maps key to its current access frequency.
3. freq_keys: maps frequency to an ordered set of keys at that frequency (OrderedDict in Python, insertion-ordered Map in JavaScript). Within each bucket, keys are maintained in LRU order — oldest first.

Minimum frequency tracker: min_freq tracks the current minimum frequency. When eviction is needed, pop the oldest (LRU) key from freq_keys[min_freq].

_touch(key) helper: When a key is accessed:

1. Get its current frequency f.
2. Increment: key_freq[key] = f + 1.
3. Remove key from freq_keys[f].
4. If freq_keys[f] is now empty and f == min_freq, increment min_freq.
5. Add key to freq_keys[f+1] (at the end — most recently used position).

put for a new key:

1. If at capacity, evict the LRU key from freq_keys[min_freq].
2. Insert the new key with frequency 1 into freq_keys[1].
3. Reset min_freq = 1.

Visual Dry Run#

capacity = 2

Solution (Optimal)#

from collections import defaultdict, OrderedDict
 
class LFUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.min_freq = 0
        self.key_val = {}
        self.key_freq = {}
        self.freq_keys = defaultdict(OrderedDict)
 
    def _touch(self, key: int) -> None:
        f = self.key_freq[key]
        self.key_freq[key] += 1
        del self.freq_keys[f][key]
        if not self.freq_keys[f] and f == self.min_freq:
            self.min_freq += 1
        self.freq_keys[f + 1][key] = None
 
    def get(self, key: int) -> int:
        if key not in self.key_val:
            return -1
        self._touch(key)
        return self.key_val[key]
 
    def put(self, key: int, value: int) -> None:
        if self.cap <= 0:
            return
        if key in self.key_val:
            self.key_val[key] = value
            self._touch(key)
        else:
            if len(self.key_val) >= self.cap:
                evict_key, _ = self.freq_keys[self.min_freq].popitem(last=False)
                del self.key_val[evict_key]
                del self.key_freq[evict_key]
            self.key_val[key] = value
            self.key_freq[key] = 1
            self.freq_keys[1][key] = None
            self.min_freq = 1

class LFUCache {
    constructor(capacity) {
        this.cap = capacity;
        this.minFreq = 0;
        this.keyVal = new Map();
        this.keyFreq = new Map();
        this.freqKeys = new Map(); // freq -> Map<key, null> (insertion order = LRU)
    }
 
    _touch(key) {
        const f = this.keyFreq.get(key);
        this.keyFreq.set(key, f + 1);
        this.freqKeys.get(f).delete(key);
        if (this.freqKeys.get(f).size === 0 && f === this.minFreq) {
            this.minFreq++;
        }
        if (!this.freqKeys.has(f + 1)) this.freqKeys.set(f + 1, new Map());
        this.freqKeys.get(f + 1).set(key, null);
    }
 
    get(key) {
        if (!this.keyVal.has(key)) return -1;
        this._touch(key);
        return this.keyVal.get(key);
    }
 
    put(key, value) {
        if (this.cap <= 0) return;
        if (this.keyVal.has(key)) {
            this.keyVal.set(key, value);
            this._touch(key);
        } else {
            if (this.keyVal.size >= this.cap) {
                const bucket = this.freqKeys.get(this.minFreq);
                const evictKey = bucket.keys().next().value;
                bucket.delete(evictKey);
                this.keyVal.delete(evictKey);
                this.keyFreq.delete(evictKey);
            }
            this.keyVal.set(key, value);
            this.keyFreq.set(key, 1);
            if (!this.freqKeys.has(1)) this.freqKeys.set(1, new Map());
            this.freqKeys.get(1).set(key, null);
            this.minFreq = 1;
        }
    }
}

Time: O(1) for both get and put. All hash map and OrderedDict operations are O(1). Space: O(capacity) — total keys across all three maps is bounded by capacity.

Common Mistakes#

• Forgetting to update min_freq after _touch: If you do not increment min_freq when the minimum frequency bucket empties, the next eviction will try to pop from an empty bucket.
• Deleting from the wrong frequency bucket: Use key_freq[key] to find the CURRENT frequency BEFORE incrementing. The deletion must happen at the old frequency.
• Not resetting min_freq = 1 on new key insertion: Every new key starts at frequency 1. If this reset is omitted, the next eviction will target the wrong bucket.
• Evicting after insertion instead of before: Always evict BEFORE inserting the new key. Otherwise you might immediately evict the key you just added.
• Not handling capacity = 0: A zero-capacity cache is a no-op. Handle cap <= 0 explicitly.

Interview Tips#

• Always explain the three hash maps before writing any code.
• Draw the frequency bucket list and show how min_freq is maintained.
• Compare LFU to LRU: "LRU needs one hash map + one DLL. LFU needs three hash maps + per-frequency DLLs + min-freq tracker."
• Mention that an O(log n) alternative using a heap exists but is simpler — the O(1) design is what interviewers at Google are testing.

Follow-up Questions#

• How does LFU compare to LRU in implementation complexity? LRU: one hash map + one DLL. LFU: three hash maps + per-frequency DLLs + min-freq tracker. Significantly more complex.
• When is LFU better than LRU? When access patterns have strong frequency locality — popular items stay cached regardless of recency. LRU can be fooled by sequential scans.
• Can you implement LFU with O(log n) using a priority queue? Yes — simpler to implement but O(log n) per operation. Describe the trade-off.
• What is "scan resistance" and how does LFU address it? Sequential scans flood LRU caches with one-time-access data. LFU keeps popular items in cache despite scans because they have higher frequency.
• What is the ARC (Adaptive Replacement Cache) policy? ARC combines LRU and LFU properties adaptively — used in ZFS and some operating systems.

Key Takeaways#

• LFU Cache (LC 460) requires three hash maps: key-to-value, key-to-frequency, frequency-to-ordered-set-of-keys.
• The _touch(key) helper encapsulates all frequency bookkeeping in one place — call it from both get and put.
• min_freq is the critical invariant: always points to the lowest-frequency bucket for O(1) eviction.
• Always evict BEFORE inserting a new key, and always reset min_freq = 1 after inserting a new key.
• Time O(1) for all operations; space O(capacity).
• The difference from LRU: LRU tracks recency only; LFU tracks frequency first, then recency for tiebreaking.
• Python's OrderedDict and JavaScript's insertion-ordered Map are the right tools for per-frequency LRU ordering within each bucket.