LRU Cache
Combine a hash map (for O(1) key lookup) with a doubly-linked list (for O(1) insertion/removal of the least recently used item). On access, move the item to the front. On capacity overflow, evict from the back.
How It Works
An LRU cache evicts the least recently used entry when capacity is exceeded, and both get and put must run in O(1). No single structure does this alone: a hash map gives O(1) key lookup but no notion of recency order, while a doubly-linked list maintains order but has O(n) search. Combine them — the map stores key → list node, and the list keeps nodes ordered from most to least recently used.
On every access, unlink the node and splice it to the front, both O(1) because the map hands you the node directly and doubly-linked nodes know their neighbors. On overflow, evict the tail node and delete its key from the map. Sentinel head and tail nodes remove all the edge-case branching.
Step-by-Step Visualization
Code
class LRUCache {
private int cap;
private LinkedHashMap<Integer, Integer> map;
LRUCache(int cap) { this.cap = cap; this.map = new LinkedHashMap<>(16, 0.75f, true); }
int get(int key) {
return map.getOrDefault(key, -1);
}
void put(int key, int val) {
map.put(key, val);
if (map.size() > cap)
map.remove(map.keySet().iterator().next());
}
}Tips & Gotchas
Practice Problems
- 1LRU Cache
- 2Design Linked List
- 3Design Browser History
- 4Snapshot Array
About the Hash Map Design Pattern
Some problems ask you to build data structures that combine a hash map with other structures to achieve specific performance guarantees.
If brute force is O(n²) because of a nested search, a hash map usually drops it to O(n). The tradeoff is O(n) extra space.
Common Hash Map Interview Problems
- Two Sum
- Subarray Sum Equals K
- Top K Frequent Elements
- LRU Cache
- Group Anagrams
- Longest Consecutive Sequence
Frequently Asked Questions
Why must the linked list be doubly linked rather than singly linked?
Removing a node from the middle requires rewiring its predecessor, and a singly-linked node cannot reach its predecessor without an O(n) walk. The prev pointer makes unlink-and-move-to-front a true O(1) operation.
Can I just use Java's LinkedHashMap or Python's OrderedDict?
In production, yes — LinkedHashMap with accessOrder=true plus removeEldestEntry is a complete LRU cache, and OrderedDict's move_to_end does the same. In interviews you are typically expected to build the map-plus-list machinery yourself, though mentioning the library shortcut shows awareness.
Does put of an existing key count as a use?
Yes. Updating a key's value refreshes its recency, so the node moves to the front just like a get. Forgetting this rule is a frequent source of wrong-answer submissions on the LRU Cache problem.