Implement an LRU Cache
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement get(key) and put(key, value) operations in O(1) average time complexity. When the cache reaches its capacity, it should invalidate and evict the least recently used key before inserting a new item.
Requirements
- ✓Initialize LRUCache with positive capacity.
- ✓int get(int key) returns the value of the key if it exists, otherwise -1.
- ✓void put(int key, int value) updates the value of the key if it exists. Otherwise, add the key-value pair to the cache. If keys exceed capacity, evict least recently used key.
- ✓Both get and put operations must run in O(1) average time complexity.
Constraints & Scale
- —1 <= capacity <= 3000
- —0 <= key <= 10^4
- —0 <= value <= 10^5
- —At most 2 * 10^5 calls will be made to get and put.
Interactive Architecture Blueprint1 view
Visual topology, node responsibilities, traffic flow steps, and bottlenecks.
What makes O(1) get and put tricky together? What data structure gives O(1) lookup? What data structure gives O(1) removal and insertion at arbitrary positions?
Hash map provides O(1) key lookup, but doesn't track ordering. Array tracks order, but eviction/shifting is O(N). Doubly linked list allows O(1) node deletion and insertion when a pointer is held. Combining a Hash Map with a Doubly Linked List achieves O(1) for both get and put.
Trade-offs
- ⚖Hash Map + Doubly Linked List: O(1) operations at cost of 2 pointers per node + hash map entry memory overhead.
- ⚖Array-based cache: lower memory overhead due to cache locality, but O(N) shifts on update/evict make it unsuitable for high throughput.
Concepts used in this stage