Design an LRU Cache, Low Level Design (LLD) Interview
Design a generic, fixed-capacity LRU (Least Recently Used) cache that supports O(1) get and put by combining a hash map for lookup with a doubly linked list for recency ordering.
Asked at: Amazon, Microsoft, Google, Atlassian, Uber, Flipkart, Swiggy, and almost every product-company machine-coding / LLD round. It is the single most common cache design question and also appears as LeetCode 146.
Why this is asked
Interviewers love it because it sits exactly at the intersection of data structures and object-oriented design. In about 45 minutes a candidate has to (1) pick the right pair of data structures and justify the O(1) claim, (2) write bug-free pointer manipulation on a doubly linked list, (3) design clean classes with generics so the cache is reusable, and (4) reason about eviction policy and thread-safety. It exposes whether you can keep invariants straight under pressure, and it naturally extends into LFU, TTL, and write-through variants for follow-ups.
Requirements
Functional
- get(key): return the value if the key is present, else return null/None or a miss sentinel. A successful get marks the key as the most recently used.
- put(key, value): insert or update the value for a key. This also marks the key as most recently used.
- When the cache is at capacity and a new key is inserted, evict the least recently used entry before inserting.
- Both get and put must run in O(1) average time.
- The cache is generic over key and value types (LRUCache<K, V>).
- Capacity is fixed at construction time and must be a positive integer.
- Updating the value of an existing key counts as a use and must not change the cache size.
- Optional follow-ups: size(), contains(key), clear(), an eviction listener/callback, per-entry TTL, and thread-safe access.
Constraints & non-functional
- O(1) time for get and put, O(capacity) space.
- No external libraries for the core structure (you build the doubly linked list yourself; a LinkedHashMap is allowed only if the interviewer permits it).
- Must handle capacity == 1 and repeated puts on the same key correctly.
- Must not leak nodes: an evicted node must be removed from both the map and the list.
- If thread-safety is required, get must also be treated as a mutation because it reorders the list.
Core classes & entities
LRUCache<K, V>
The public facade. Holds the capacity, the lookup map, and the doubly linked list. Coordinates lookups, recency updates, and eviction. This is the only class the caller touches.
attrs: capacity: int, map: HashMap<K, Node<K, V>>, list: DoublyLinkedList<K, V>
methods: get(key: K): V, put(key: K, value: V): void, size(): int, contains(key: K): boolean, clear(): void
Node<K, V>
A single cache entry living inside the doubly linked list. Stores the key (needed so we can delete from the map on eviction), the value, and prev/next pointers. Storing the key in the node is the trick that makes eviction O(1).
attrs: key: K, value: V, prev: Node<K, V>, next: Node<K, V>
methods: (plain data holder, no behavior)
DoublyLinkedList<K, V>
Maintains recency order using two sentinel nodes (head and tail dummies). Most recently used sits next to head, least recently used sits next to tail. Exposes O(1) move-to-front, add-to-front, remove-node, and remove-last.
attrs: head: Node<K, V> (dummy sentinel), tail: Node<K, V> (dummy sentinel)
methods: addToFront(node), remove(node), moveToFront(node), removeLast(): Node<K, V>
EvictionListener<K, V> (optional)
Callback hook invoked when an entry is evicted, so a write-through cache or metrics layer can react. Demonstrates the Observer pattern as a clean follow-up.
methods: onEvict(key: K, value: V): void
EvictionPolicy<K, V> (optional)
Strategy abstraction that decides which key to evict. The default implementation is LRU, but swapping in an LFU or FIFO implementation requires no change to LRUCache. Shows the Strategy pattern for the open-ended follow-up.
methods: recordAccess(key: K), recordInsert(key: K), evictKey(): K
Relationships
- LRUCache → composition → Node. The cache owns all nodes; their lifetime is bounded by the cache. When the cache is cleared, the nodes are gone.
- LRUCache → composition → DoublyLinkedList. The cache owns exactly one list that holds the recency order.
- LRUCache → association → Node. The HashMap maps each key to its Node so lookup is O(1). The same Node is referenced from both the map and the list (two views over one object).
- DoublyLinkedList → aggregation → Node. The list links nodes via prev/next. The same node objects are shared with the map, so the list does not deep-own them independently.
- LRUCache → association → EvictionListener. Optional injected callback notified on eviction (Observer).
- LRUCache → association → EvictionPolicy. Optional injected strategy that decides the victim (Strategy). LRU is the default.
Design patterns used
Strategy in EvictionPolicy interface with LRU as the default implementation; alternatives are LFU and FIFO.
The eviction rule is the one axis interviewers love to vary. Pulling it behind an interface means the cache mechanics (map + list) stay untouched when you switch policies. It directly answers the 'now make it LFU' follow-up without a rewrite.
Observer in EvictionListener.onEvict callback fired when an entry is removed.
A write-through or write-back cache needs to flush an evicted value to the backing store, and metrics layers want hit/miss/eviction counts. An observer decouples the cache from whoever cares about evictions.
Facade in LRUCache itself hides the Node and DoublyLinkedList internals behind a tiny get/put surface.
Callers should never see pointer manipulation. The two-line public API is the entire contract; the list is an implementation detail.
Null Object / Sentinel in The dummy head and tail nodes in the doubly linked list.
Sentinels remove every null-check from insert and remove. There is always a node before and after a real entry, so addToFront and remove are branch-free and far less bug-prone, which matters a lot in a timed coding round.
Factory Method (optional) in A static LRUCache.of(capacity) or a CacheBuilder for configuring policy, listener, and thread-safety.
When the constructor grows (capacity + policy + listener + locking), a builder keeps construction readable and validates capacity in one place.
Enums
Key API / methods
LRUCache(int capacity)Construct a cache with a fixed positive capacity. Throws IllegalArgumentException if capacity <= 0.
V get(K key)Return the value for key and move it to most-recently-used. Returns null (Java) / None (Python) on a miss. O(1).
void put(K key, V value)Insert or update key=value and mark it most-recently-used. If inserting a new key would exceed capacity, evict the LRU entry first. O(1).
int size()Return the current number of stored entries (never greater than capacity). O(1).
boolean contains(K key)Return whether a key is present WITHOUT changing its recency. Useful for tests; do not implement it via get() or you will reorder the list.
void clear()Remove all entries and reset the list to just the two sentinels. O(capacity) or O(1) if you simply re-link head/tail and drop the map.
private Node<K,V> removeLast()Internal helper that unlinks and returns the node next to the tail sentinel (the LRU victim). O(1).
Code skeleton
// ---------- Core LRU Cache: HashMap + Doubly Linked List, O(1) ----------
// Sentinel head/tail remove all null checks. Node carries its key so
// eviction can delete from the map in O(1).
class LRUCache<K, V> {
private static final class Node<K, V> {
K key;
V value;
Node<K, V> prev, next;
Node(K key, V value) { this.key = key; this.value = value; }
}
private final int capacity;
private final Map<K, Node<K, V>> map = new HashMap<>();
private final Node<K, V> head = new Node<>(null, null); // most recent side
private final Node<K, V> tail = new Node<>(null, null); // least recent side
public LRUCache(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException("capacity must be > 0");
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public V get(K key) {
Node<K, V> node = map.get(key);
if (node == null) return null; // MISS, list untouched
moveToFront(node); // mark most recently used
return node.value;
}
public void put(K key, V value) {
Node<K, V> node = map.get(key);
if (node != null) { // UPDATE: no size change, no eviction
node.value = value;
moveToFront(node);
return;
}
if (map.size() == capacity) { // FULL: evict LRU first
Node<K, V> victim = removeLast();
map.remove(victim.key); // needs key stored in node
// onEvict(victim.key, victim.value); // Observer hook
}
Node<K, V> fresh = new Node<>(key, value);
addToFront(fresh);
map.put(key, fresh);
}
public int size() { return map.size(); }
public boolean contains(K key) { return map.containsKey(key); } // no reorder
// ---- doubly linked list helpers (all O(1)) ----
private void addToFront(Node<K, V> n) {
n.prev = head;
n.next = head.next;
head.next.prev = n;
head.next = n;
}
private void remove(Node<K, V> n) {
n.prev.next = n.next;
n.next.prev = n.prev;
n.prev = n.next = null; // help GC, avoid stale links
}
private void moveToFront(Node<K, V> n) {
remove(n);
addToFront(n);
}
private Node<K, V> removeLast() { // node next to tail sentinel = LRU
Node<K, V> last = tail.prev;
remove(last);
return last;
}
}
// ---------- Thread-safe wrapper (coarse lock) ----------
// Simplest correct approach: guard the whole operation. get() must lock too
// because it reorders the list. For higher throughput discuss striped locks
// or just delegate to java.util.concurrent.ConcurrentHashMap-backed designs
// (e.g. Caffeine) which use access-order ring buffers instead of a global lock.
class ThreadSafeLRUCache<K, V> {
private final LRUCache<K, V> delegate;
private final ReentrantLock lock = new ReentrantLock();
public ThreadSafeLRUCache(int cap) { delegate = new LRUCache<>(cap); }
public V get(K k) { lock.lock(); try { return delegate.get(k); } finally { lock.open(); } }
public void put(K k, V v) { lock.lock(); try { delegate.put(k, v); } finally { lock.open(); } }
}How it works
Start by nailing the data structure choice out loud, because that is what the question is really testing. You need two operations in O(1): look a value up by key, and find/remove the least recently used entry. A hash map gives O(1) lookup by key but has no notion of order. A doubly linked list gives O(1) insert and remove at any position you already hold a pointer to, and it can maintain order. Neither alone is enough, so you combine them. The map stores key to node references; the list stores the same node objects in recency order. The map answers "where is this entry," the list answers "which entry is stale."
The list uses two dummy sentinel nodes, head and tail, that never hold real data. By convention the node right after head is the most recently used, and the node right before tail is the least recently used. Sentinels matter in an interview because they eliminate every edge case around inserting into an empty list or removing the only element. addToFront, remove, and moveToFront become four-line pointer updates with no null checks, which is exactly what you want when the clock is running.
Walk through get(key). Look the key up in the map. On a miss, return the miss value and leave the list alone. On a hit, you have the node directly, so you call moveToFront which unlinks it from its current spot and relinks it right after head, then return its value. Both steps are O(1) because you never scan the list, you operate on the node pointer the map handed you.
Now put(key, value), which has three branches. First, if the key already exists, this is an update: overwrite the value, move the node to front, and return. Crucially the size does not change and nothing is evicted, even if the cache is full. Second, if the key is new and the cache is at capacity, evict before inserting: removeLast unlinks the node next to the tail sentinel, and you delete that node's key from the map. This is the moment the design pays off. Because each node stores its own key, you can do map.remove(victim.key) in O(1). If you had stored only the value in the node, you would be stuck with the node but no way to find its map entry. Third, create a fresh node, addToFront, and put it in the map.
For thread-safety, the key insight to verbalize is that get is not a read, it is a write, because moveToFront mutates the list. So a "readers don't need locks" optimization is wrong here. The simplest correct answer is a single ReentrantLock or synchronized methods guarding both get and put. If the interviewer pushes on contention, explain that production caches like Caffeine avoid the global lock by recording accesses in lock-free ring buffers and replaying them onto the LRU order asynchronously, trading exact recency for throughput. That shows you understand the tradeoff between correctness and scalability without over-engineering the whiteboard version.
Edge cases & gotchas
- Capacity of 1: every put of a new key must evict the previous one. A common bug is evicting then re-inserting in the wrong order.
- put on an existing key: update value and move to front, but do NOT increase size and do NOT evict. Forgetting this either grows the map past capacity or double-counts size.
- get on a missing key: return the miss sentinel and do not touch the list. Do not accidentally insert a null entry.
- Inserting the new node before evicting when already full: must evict first (or at least not let size exceed capacity); otherwise you can transiently hold capacity+1 nodes and pick the wrong victim.
- The victim node must be deleted from BOTH the map and the list. Removing from only one leaks memory or corrupts lookups.
- Storing only the value (not the key) in the node: then on eviction you have the node but no key to delete from the map. The node must carry its key.
- Null keys / null values: decide and document. Many implementations reject null keys; a stored null value is ambiguous with a miss unless you use a sentinel or a contains() check.
- Re-put of the same key when capacity is full: this is an update, not an insert, so no eviction even though the cache is full.
- Concurrency: get mutates the list (moveToFront), so a naive 'reads are safe' assumption is wrong. Two concurrent gets can corrupt prev/next pointers.
- Iterator invalidation: if you expose iteration, a concurrent get/put reorders the list and can break a live iterator.