Problem Statement
get()
put()
Both operations must run in:
O(1)
Brute Force Intuition
Maintain:
Key
Value
Frequency
Whenever cache is full:
Find minimum frequency by scanning entire cache.
Remove that key.
Complexity
- get → O(1)
- put → O(N)
Moving Towards the Optimal Approach
Need fast access to:
Node
Frequency
Minimum Frequency
Use:
HashMap<Key,Node>
HashMap<Frequency,DLL>
Minimum Frequency Variable
Pattern Recognition
Cache
+
Frequency
=> Multiple Doubly Linked Lists
Key Observation
Each frequency has its own DLL.
Example:
Freq 1
1 ⇄ 7 ⇄ 10
Freq 2
5 ⇄ 9
Whenever frequency increases:
Remove from old DLL
↓
Insert into next frequency DLL
Operations
get()
Frequency++
Move Node
put()
If exists:
Update Value
Increase Frequency
Else:
If full:
Remove
Least Frequency
Least Recently Used
Insert new node into:
Frequency = 1
Complexity Analysis
| Operation | Complexity |
|---|---|
| Get | O(1) |
| Put | O(1) |
Interview One-Liner
Use a HashMap for node lookup, another HashMap for frequency-wise doubly linked lists, and maintain the minimum frequency for O(1) eviction.
Pattern Learned
Cache
+
Frequency
+
Recency
=> HashMap + Multiple DLLs
Memory Trick
LRU
HashMap
+
One DLL
↓
Least Recently Used
LFU
HashMap
+
Many DLLs
↓
Least Frequently Used
Similar Problems
- LRU Cache
- LFU Cache
- Design Browser History
- All O(1) Data Structure
- Insert Delete GetRandom O(1)
Top comments (0)