Problem Statement
Design an LRU (Least Recently Used) Cache supporting:
get(key)
put(key,value)
Both operations must run in:
O(1)
Brute Force Intuition
Use:
ArrayList
Whenever an element is accessed:
Search it.
Move it to the front.
If capacity exceeds:
Remove last element.
Complexity
- get → O(N)
- put → O(N)
Moving Towards the Optimal Approach
We need:
Fast Lookup
and
Fast Deletion / Insertion
Use:
HashMap
+
Doubly Linked List
Pattern Recognition
Need O(1) Lookup
+
Need O(1) Update
=> HashMap + DLL
Key Observation
HashMap:
key
↓
Node Address
DLL stores usage order.
Most Recently Used:
Front
Least Recently Used:
Back
Operations
get()
Found ?
↓
Move Node to Front
↓
Return Value
put()
Already Exists?
Update
Move Front
Else:
Insert Front
If capacity exceeded:
Remove Tail
Complexity Analysis
| Operation | Complexity |
|---|---|
| Get | O(1) |
| Put | O(1) |
Interview One-Liner
Combine a HashMap for O(1) lookup and a Doubly Linked List for O(1) insertion, deletion, and eviction of the least recently used element.
Pattern Learned
Cache
+
Order Matters
=> HashMap + Doubly Linked List