LRU Cache
A medium Linked List interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Linked List
- Sheets
- 2
- Core for
- 4 roles
The problem
Design a Least Recently Used (LRU) cache using a doubly linked list and a hash map, supporting get and put operations in O(1) time.
Example 1
- Input
- LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2); put(4,4); get(1); get(3); get(4)
- Output
- [null,null,null,1,null,-1,null,-1,3,4]
Example 2
- Input
- LRUCache(1); put(1,1); get(1); put(2,2); get(1)
- Output
- [null,null,1,null,-1]
Example 3
- Input
- LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2)
- Output
- [null,null,null,1,null,-1]
Constraints
- 1 <= capacity <= 3000
- 0 <= key, value <= 10^4
- at most 3*10^4 calls
How to think about it
Updated 2026-09-29A hash map delivers O(1) key lookup but cannot track chronological usage ordering. A doubly linked list supports O(1) node removal and insertion anywhere given a direct node reference. Storing pointers to doubly linked list nodes inside the hash map gives you both instant lookup and constant-time ordering updates.
Approaches, worst first
Map over a singly list
time O(n) · space O(capacity)
Maintain a map for values and an array or singly linked list of keys to track recency. Moving a key to the most recent position takes O(n) search or excision time on every get and every put, which violates the constant-time requirement the problem states.
Hash map with doubly linked listWrite this one
time O(1) · space O(capacity)
Use pseudo-head and pseudo-tail dummy nodes to eliminate boundary edge cases. The map stores `key -> Node`. On get, locate the node, unlink it, and prepend it after head. On put, update existing node and promote it, or insert a new node; if capacity is exceeded, evict the node preceding tail and remove it from the map.
Where people lose marks · 3
- Forgetting to delete the evicted node's key from the hash map when evicting the least recently used item causes map size and cache memory to leak.
- Updating an existing key via put without moving its node to the most-recently-used position leaves stale recency ordering.
- Storing only values in the doubly linked list nodes prevents deleting the corresponding entry from the map during eviction; nodes must store both key and value.
The theory behind it
Linked List — the ground this problem stands on. All Linked List problems
What Linked List is
A linked list is a chain of separate cargo cars connected by coupling hooks, scattered anywhere across memory rather than sitting in a tidy contiguous row. Each car, called a node, holds a single piece of data and a pointer directing traffic to the address of the next car in line. Because nodes connect only by directional links, jumping straight to the tenth car is impossible without walking past the first nine.
When to reach for it
Choose a linked list when a problem requires frequent insertions and deletions at known positions without shifting whole blocks of surrounding memory. Problems mentioning pointer splicing, reversing subsequences in place, merging sorted streams, or detecting cycles in linear chains strongly point here. It is ideal when total capacity is unpredictable and memory allocation must happen one individual node at a time.
How the pattern works
Think in terms of pointer rewiring before dereferencing. Keep a dummy head node pointing to the start of the list so modifications to the initial item do not require separate edge logic. Always save references to neighboring nodes into temporary variables before cutting or redirecting forward links. When diagnosing loops or locating middle nodes, advance two references simultaneously at differing velocities so traversal completes without supplementary storage.
More Linked List problems
Target Roles
Core requirement for 4 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .