56 / 75
Medium
LRU Cache
#56designhash-tablelinked-listdoubly-linked-list
Use HashMap + doubly linked list: map for O(1) access, DLL for O(1) eviction of LRU.
Example:
Input:
LRUCache(2), put(1,1), put(2,2), get(1), put(3,3), get(2)Output:
[null, null, null, 1, null, -1] (key 2 evicted)Common Mistakes:
- Not using doubly linked list (singly won't work for O(1) removal)
- Forgetting to update both map and DLL on operations
- Not using dummy head/tail nodes (complicates edge cases)
- Removing wrong node (should remove tail.prev, not tail)
Notes:
Classic design problem. LinkedHashMap in Java can simplify, but implement from scratch in interviews. Time O(1) for get/put, Space O(capacity).
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Use HashMap + doubly linked list: map for O(1) access, DLL for O(1) eviction of LRU.
Example:
Input:
LRUCache(2), put(1,1), put(2,2), get(1), put(3,3), get(2)Output:
[null, null, null, 1, null, -1] (key 2 evicted)Common Mistakes:
- Not using doubly linked list (singly won't work for O(1) removal)
- Forgetting to update both map and DLL on operations
- Not using dummy head/tail nodes (complicates edge cases)
- Removing wrong node (should remove tail.prev, not tail)
Notes:
Classic design problem. LinkedHashMap in Java can simplify, but implement from scratch in interviews. Time O(1) for get/put, Space O(capacity).
56/75
LRU Cache