LFU Cache
Problem
Design a Least Frequently Used cache with a fixed capacity. get(key) returns the value, or −1 if absent. put(key, value) inserts or updates a key. When the cache is full, evict the key with the lowest use count; break ties by evicting the least recently used of them. Every get or put on a key increases its count. Both operations must be O(1).
Example 1
Input: capacity 2: put(1,1), put(2,2), get(1), put(3,3), get(2), get(3), put(4,4), get(1), get(3), get(4) Output: 1, -1, 3, -1, 3, 4
Test cases
Case 1
Input: new LFUCache(2) .put(1, 1) .put(2, 2) .get(1) .put(3, 3) .get(2) .get(3) .put(4, 4) .get(1) .get(3) .get(4) Expected: [null,null,1,null,-1,3,null,-1,3,4]
Case 2
Input: new LFUCache(0) .put(0, 0) .get(0) Expected: [null,-1]
Case 3
Input: new LFUCache(2) .put(1, 1) .put(2, 2) .put(3, 3) .get(1) .get(2) .get(3) Expected: [null,null,null,-1,2,3]
View solutionHide solution1 approach
1. Frequency buckets of insertion-ordered sets
Time O(1) per operationSpace O(capacity)
key → [value, freq]; freq → Set of keys (JS Sets keep insertion order, so the first key is the least recent). Track minFreq; evict the first key of the minFreq bucket. A new key resets minFreq to 1.
class LFUCache { constructor(capacity) { this.cap = capacity; this.vals = new Map(); // key -> [value, freq] this.buckets = new Map(); // freq -> Set(keys), oldest first this.minFreq = 0; } #touch(key) { const entry = this.vals.get(key), f = entry[1]; this.buckets.get(f).delete(key); if (f === this.minFreq && this.buckets.get(f).size === 0) this.minFreq++; entry[1] = f + 1; if (!this.buckets.has(f + 1)) this.buckets.set(f + 1, new Set()); this.buckets.get(f + 1).add(key); } get(key) { if (!this.vals.has(key)) return -1; this.#touch(key); return this.vals.get(key)[0]; } put(key, value) { if (this.cap === 0) return; if (this.vals.has(key)) { this.vals.get(key)[0] = value; this.#touch(key); return; } if (this.vals.size === this.cap) { const bucket = this.buckets.get(this.minFreq); const evict = bucket.values().next().value; bucket.delete(evict); this.vals.delete(evict); } this.vals.set(key, [value, 1]); if (!this.buckets.has(1)) this.buckets.set(1, new Set()); this.buckets.get(1).add(key); this.minFreq = 1; }}In other languages the buckets are doubly linked lists; JS Set insertion order gives the same O(1) behaviour.