LFU Cache
Problem Statement
Design an LFUCache data structure. get(key) returns the value for key if it exists, otherwise -1. put(key, value) inserts or updates the value for key. When the cache is full, it must evict the least frequently used key. If multiple keys share the lowest frequency, evict the least recently used key among them. Both operations must run in O(1) average time.
Input
A constructor call LFUCache(capacity) followed by a sequence of get(key) and put(key, value) operations.
Output
For the constructor and put, output null. For get, output the stored value or -1 if the key is absent.
Constraints
- •
0 <= capacity <= 10^4 - •
0 <= key <= 10^5 - •
0 <= value <= 10^9 - •
At most 2 * 10^5 calls will be made to get and put
Examples
Example 1
operations = [LFUCache, put, put, get, put, get, get, put, get, get, get], arguments = [[2], [1,1], [2,2], [1], [3,3], [2], [3], [4,4], [1], [3], [4]]
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]Example 2
operations = [LFUCache, put, put, put, get, get, get], arguments = [[2], [2,1], [2,2], [3,3], [2], [3], [4]]
[null, null, null, null, 2, 3, -1]Learning Objectives
- Separate key lookup, frequency lookup, and recency ordering into cooperating structures.
- Maintain a **minFreq** tracker so eviction never scans all frequencies.
- Use doubly linked lists as frequency buckets to evict the least recent node inside the lowest frequency.
- Handle design edge cases such as capacity zero, value updates, and frequency promotion.
Intuition
Pattern Recognition
The signal is a cache design with two eviction rules: frequency first, recency as the tie-breaker. A plain hash map gives lookup but no eviction order. A single LRU list gives recency but not frequency. A heap can find low frequency but cannot update arbitrary nodes in strict O(1). The O(1) design needs two maps and linked buckets.
Think of every cache entry as a node that lives inside exactly one frequency bucket. The key map finds the node immediately. The frequency map finds the doubly linked list for that node's current count. Inside one frequency, the list is ordered by recency. minFreq points to the lowest non-empty frequency bucket, so eviction removes the tail-side node from that bucket without scanning.
Common mistakes
- ×Tracking frequency counts but not recency within the same frequency bucket.
- ×Scanning all keys or all frequencies during eviction, which breaks O(1).
- ×Forgetting that successful get and updating put both increase a key's frequency.
- ×Not updating **minFreq** when the last node leaves the current minimum-frequency bucket.
Algorithm Explanation
Key idea
Use nodesByKey for direct key lookup, listsByFreq for frequency buckets, and minFreq for the current eviction bucket. Each bucket is a doubly linked list ordered from most recent near the head to least recent near the tail. Accessing a node removes it from its old bucket, increments its frequency, and inserts it at the most-recent end of the new bucket.
Pointer walkthrough
Capacity is 2. After put(1,1) and put(2,2), bucket freq 1 is 2 -> 1 from most recent to least recent, and minFreq = 1. Calling get(1) removes node 1 from freq 1, increments it, and inserts it into freq 2, so buckets are freq 1: 2 and freq 2: 1. minFreq stays 1 because key 2 is still in freq 1. Now put(3,3) must evict from freq 1, and within that bucket the least recent node is key 2, so key 2 is removed before key 3 enters freq 1.
Algorithm
- The constructor stores capacity, creates the key map, creates the frequency map, and sets minFreq to 0.
- For get(key), return -1 if the key is absent. Otherwise promote the node's frequency and return its value.
- For put(key, value), return immediately when capacity is 0.
- If the key already exists, update its value, promote its frequency, and stop.
- If the cache is full, remove the least-recent node from the bucket at minFreq and delete its key from the key map.
- Create a new node with frequency 1, insert it at the most-recent end of bucket 1, store it in the key map, and set minFreq = 1.
Solutions
Solution: Two hash maps plus frequency buckets
Use this design when the interviewer requires strict O(1) average get and put. It is the standard LFU cache architecture and directly connects cache eviction to doubly linked list operations.
Each cache entry is a node containing key, value, freq, prev, and next. nodesByKey maps keys to nodes. listsByFreq maps a frequency count to a doubly linked list of nodes with that count, ordered by recency. Promoting a node is an O(1) remove from one list and O(1) insert into another. Eviction uses minFreq to choose the bucket and removes that bucket's least-recent tail node.
Step-by-step
- Keep dummy head and tail sentinels inside every frequency bucket so add and remove are uniform.
- On get, find the node by key. If it is missing, return -1.
- If present, remove it from its current frequency list and update minFreq if that list became empty.
- Increment the node's frequency and insert it at the most-recent end of the new frequency list.
- On put for an existing key, update the value and run the same promotion logic.
- On put for a new key, evict from the minFreq bucket if capacity is full, then insert the new node into frequency 1 and reset minFreq to 1.
Average O(1) per get and put
O(capacity)
The key map stores one node per live key, and frequency buckets together store the same nodes once.
Java implementation
Dry Run
Sample input
Capacity is 2. Operations: put(1,1), put(2,2), get(1), put(3,3), get(2), get(3). Buckets list most recent first.
| operation | return | frequency buckets after operation | minFreq | eviction note |
|---|---|---|---|---|
| put(1,1) | null | freq 1: 1 | 1 | none |
| put(2,2) | null | freq 1: 2 -> 1 | 1 | none |
| get(1) | 1 | freq 1: 2; freq 2: 1 | 1 | key 1 promoted |
| put(3,3) | null | freq 1: 3; freq 2: 1 | 1 | evict key 2 from lowest-frequency bucket |
| get(2) | -1 | freq 1: 3; freq 2: 1 | 1 | key 2 is absent |
| get(3) | 3 | freq 2: 3 -> 1 | 2 | key 3 promoted and freq 1 becomes empty |
The cache never scans all keys. Eviction reads minFreq, removes the tail-side node from that frequency's list, and updates the maps in constant time.
Interview Tips
Name the invariants before coding: every key maps to exactly one node, every node lives in exactly one frequency list, each frequency list is ordered by recency, and minFreq points to the lowest non-empty frequency. When explaining updates, say that put on an existing key counts as a use and must promote frequency. Mention capacity zero early because it prevents accidental eviction from an empty bucket.
Likely follow-ups
- How would you implement the same policy with Java **LinkedHashSet** per frequency bucket?
- How would you add time-to-live expiration while preserving fast eviction?
- How would you make this cache safe under concurrent get and put calls?
- How would you expose metrics such as hit rate, evictions, and current frequency distribution?
Similar Problems
Key Takeaways
- LFU eviction needs frequency first and recency as a tie-breaker.
- A key map gives direct node lookup; a frequency map groups nodes by usage count.
- Each frequency bucket is a doubly linked list ordered by recency for O(1) tie-breaking.
- The **minFreq** tracker is what prevents eviction from scanning all frequencies.