The problem
Design a Least-Frequently-Used cache: get/put in O(1); evict the lowest-frequency key, breaking ties by least-recent use.
Stuck? Reveal hints one at a time
How to approach it
- 1On get: look up the node, remove the key from its freq bucket, add to freq+1 bucket, bump minFreq if the old bucket emptied at minFreq.
- 2On put existing: update the value, then do the same frequency bump.
- 3On put new at capacity: evict the FIRST key in the minFreq bucket (oldest of the least-frequent), then insert the new key with freq 1 and minFreq = 1.
- 4JS Map / Python dict preserve insertion order — a per-bucket Map doubles as the LRU list.
Key insight
minFreq only ever RESETS to 1 (new key) or INCREMENTS when its bucket drains — it never needs a search, which is what keeps everything O(1).
The solution
Watch out for
- Eviction happens BEFORE inserting the new key — and only when the key is genuinely new.
- capacity 0 must be a no-op; several accepted solutions crash on it.