LeetCode 146 ·
Medium
LRU Cache
Design a cache with O(1) get and put that evicts the least-recently-used key at capacity.
Try it
Step through the core mechanic. The simulator below runs the linked list shape this problem is built on.
Walk the pattern
No dedicated step-through for this one yet. The shape is Linked list — its pattern page has the interactive walkthrough, the reference implementation, and a five-problem progression that this problem sits inside.
The approach
Hash map from key to a node in a doubly linked list ordered by recency. get/put move the node to the front; eviction pops the tail. The map gives O(1) lookup, the list gives O(1) reordering.
| Aspect | Value |
|---|---|
| Pattern | Linked list |
| Recognise it by | O(1) get/put with least-recently-used eviction. |
| Time complexity | O(1) |
| Space complexity | O(capacity) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.