1. LRU Cache Problem Breakdown & Complexity Requirements
Why individual data structures fail and why a hybrid approach is required
The LRU Cache problem asks you to design a fixed-capacity data structure that supports two operations:
get(key): Return the value if the key exists, otherwise return -1. Accessing an item marks it as the most recently used.put(key, value): Update the value if the key exists, or insert the key-value pair. If the number of keys exceeds capacity, evict the least recently used key.- Typical target: Both
get and put can have expected average $O(1)$ time when hash-map operations are expected average $O(1)$ and list updates use known node references.
Why Single Data Structures Fail
- Array / Dynamic List: Provides $O(1)$ access by index, but search by key is $O(N)$ and moving an element to the front requires $O(N)$ shifts.
- Singly Linked List: Supports $O(1)$ insertion at the head, but searching for an arbitrary node is $O(N)$, and removing a node requires $O(N)$ traversal to find the preceding node pointer.
- Standard Hash Map: Provides $O(1)$ average key-value lookup, but maintains no sequential ordering of recency.
The Dual Data Structure Solution
To get expected average $O(1)$ lookup plus constant-time list updates, combine two data structures:
- Hash Map (
Map<Key, Node>): Maps each key to its node in the linked list. Lookup is expected average $O(1)$ under typical hash distribution assumptions. - Doubly Linked List: Keeps nodes in recency order. With a direct node reference, unlinking or moving that node takes constant time.
2. The Dummy Sentinel Node Technique (Head & Tail)
How dummy sentinels simplify pointer manipulation
Handling edge cases when inserting or removing nodes at linked-list boundaries (empty list, one element, head eviction, tail eviction) can require additional null checks:
if (head == null) { ... }
if (node == tail) { ... }
if (node.prev != null) { ... }
Sentinel nodes provide permanent boundaries, which can simplify these cases and reduce conditional branches.
The Sentinel Technique
Initialize two permanent dummy nodes: head and tail.
- In an empty cache, connect
head.next = tail and tail.prev = head. - Real cached nodes always sit strictly between
head and tail. - Head is the Most Recently Used (MRU) position: freshly accessed or inserted nodes are placed right after
head. - Tail is the Least Recently Used (LRU) position: the node right before
tail (tail.prev) is always the eviction candidate.
The 4 Core O(1) Primitives
addNode(Node node): Links node between head and head.next.removeNode(Node node): Unlinks node by connecting node.prev.next = node.next and node.next.prev = node.prev.moveToHead(Node node): Calls removeNode(node) followed by addNode(node).popTail(): Calls removeNode(tail.prev) and returns the evicted node so its key can be purged from the HashMap.
3. Complete Production-Grade Java Implementation
Idiomatic object-oriented implementation with custom Node class
Below is the complete, self-contained Java implementation of the LRU Cache matching LeetCode 146 requirements:
Complete O(1) LRU Cache Implementation in Java with Dummy Sentinelspublic class LRUCache {
// Doubly Linked List Node
private static class Node {
int key;
int value;
Node prev;
Node next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private final Map<Integer, Node> cache;
private final Node head;
private final Node tail;
public LRUCache(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("Capacity must be positive");
}
this.capacity = capacity;
this.cache = new HashMap<>(capacity);
// Initialize dummy sentinels to eliminate null pointer conditionals
this.head = new Node(0, 0);
this.tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = cache.get(key);
if (node == null) {
return -1;
}
// Move accessed node to head (most recently used)
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node existingNode = cache.get(key);
if (existingNode != null) {
// Update existing value and move to MRU head
existingNode.value = value;
moveToHead(existingNode);
} else {
Node newNode = new Node(key, value);
cache.put(key, newNode);
addNode(newNode);
// If capacity exceeded, evict LRU tail
if (cache.size() > capacity) {
Node lru = popTail();
cache.remove(lru.key);
}
}
}
// Helper: Insert node immediately after dummy head
private void addNode(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
// Helper: Unlink an arbitrary node in O(1)
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
// Helper: Move existing node to most-recently-used position
private void moveToHead(Node node) {
removeNode(node);
addNode(node);
}
// Helper: Evict least-recently-used node right before dummy tail
private Node popTail() {
Node lru = tail.prev;
removeNode(lru);
return lru;
}
}
4. Multi-Language Implementations: Python & Modern C++
How to write idiomatic LRU Cache in Python and C++20
Python Implementation (Using collections.OrderedDict)
In Python, collections.OrderedDict maintains insertion order and exposes move_to_end(key) and popitem(last=False):
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # Evicts LRU item (front)
C++20 Implementation (std::unordered_map + std::list)
In C++, use std::list (a doubly linked list) and std::unordered_map storing iterators. Use std::list::splice to relocate nodes in $O(1)$ without copying or memory reallocation:
#include <unordered_map>
#include <list>
class LRUCache {
private:
int capacity;
// List stores pair of {key, value}
std::list<std::pair<int, int>> dll;
// Map stores iterator pointing directly to node in dll
std::unordered_map<int, std::list<std::pair<int, int>>::iterator> map;
public:
LRUCache(int cap) : capacity(cap) {}
int get(int key) {
auto it = map.find(key);
if (it == map.end()) return -1;
// Splice moves node to front of dll in O(1)
dll.splice(dll.begin(), dll, it->second);
return it->second->second;
}
void put(int key, int value) {
auto it = map.find(key);
if (it != map.end()) {
it->second->second = value;
dll.splice(dll.begin(), dll, it->second);
return;
}
if (dll.size() == capacity) {
int lruKey = dll.back().first;
map.erase(lruKey);
dll.pop_back();
}
dll.emplace_front(key, value);
map[key] = dll.begin();
}
};
5. Concurrency & Thread-Safety Extensions
Scaling LRU Cache across multiple concurrent threads
Concurrent cache implementations need to coordinate concurrent access. A single synchronized wrapper can limit parallelism when those methods are contended; the impact depends on workload and implementation.
The ReadWriteLock Trap in LRU Cache
Many candidates suggest using ReentrantReadWriteLock, assuming get() can use the read lock while put() uses the write lock.
- The Catch: In an LRU Cache,
get() is NOT a read-only operation! get() must move the accessed node to the MRU head, mutating prev and next pointers. Therefore, get() requires a WRITE lock, defeating the entire purpose of ReadWriteLock!
Scalable Concurrency Solutions
- Segmented Locking (Striped Locks): Divide the key space into $S$ independent segments (like legacy
ConcurrentHashMap). Each segment has its own capacity and independent lock. - Buffered or approximate eviction maintenance:
- Some cache designs separate key lookup from recency or eviction maintenance.
- Synchronization, buffering, and consistency guarantees vary by implementation; consult the selected library's current documentation and source.
6. Common Interview Follow-Ups & Edge Cases
Handling TTL expiration, LFU comparison, and memory-bounded sizing
Interviewers will often extend the standard LRU question with these follow-ups:
1. Adding Time-To-Live (TTL) Expiration
How do you support cache keys that expire after a specified duration?
- Approach: Add an
expiresAt timestamp to the Node. - Lazy Expiration: On
get(key), check if now > node.expiresAt. If expired, evict the node and return -1. - Active Cleanup: Maintain a secondary Min-Heap (PriorityQueue) or time-wheel ordered by
expiresAt, and run a periodic background cleanup task to purge expired entries before capacity fills up.
2. LRU vs LFU (Least Frequently Used)
- LRU: Evicts based on time since last access. Susceptible to cache pollution during one-off full-table scans.
- LFU: Evicts based on access frequency counter. Preserves frequently used items better, but requires more memory and historical frequency counters can become stale without age decay.
References & Further Reading
Frequently Asked Questions
How does a Doubly Linked List enable constant-time LRU node updates?
To unlink a known node in constant time, a doubly linked list stores its previous and next pointers. A singly linked list normally requires traversal to find the preceding node.
How do dummy head and tail sentinel nodes simplify LRU cache pointer manipulation?
Dummy head and tail sentinels act as permanent boundaries. The real cached nodes always sit strictly between them. This eliminates edge cases (such as inserting into an empty list, removing the only node, or boundary null pointer checks), reducing code complexity and preventing runtime NullPointerExceptions.
Why does standard ReentrantReadWriteLock fail to scale for a concurrent LRU cache?
In a standard cache, get() is a read operation. However, in an LRU cache, get() mutates the list pointers to reposition the accessed node to the most recently used head. Consequently, get() requires a write lock, causing all concurrent reader threads to serialize and eliminating the concurrency benefits of ReadWriteLock.
What is the difference between LRU (Least Recently Used) and LFU (Least Frequently Used)?
LRU evicts the item that was accessed the furthest in the past, regardless of how many times it was used before. LFU tracks access frequency and evicts the item with the lowest hit count. LFU is better at resisting cache pollution from one-off bulk scans, but requires more complex O(1) bookkeeping and frequency decay mechanisms.
How can you add Time-To-Live (TTL) expiration to an LRU cache?
Add an expiresAt timestamp field to each cache node. Implement lazy expiration on get() (if current time exceeds expiresAt, delete the node and return -1) and active background expiration using a PriorityQueue (Min-Heap) sorted by expiresAt to periodically remove expired entries.
How can concurrent cache implementations separate lookup from eviction maintenance?
Some cache designs separate key lookup from recency or eviction maintenance, but synchronization and buffering are implementation-specific. Consult the chosen library's current documentation and source rather than assuming a particular design.