LRU Cache
Build a fixed-size cache that removes the least recently used entry when full, with get and put in constant time. It is asked as both a coding and a design question.
Design and implement an in-memory cache with a fixed capacity. When it is full and a new key arrives, remove the entry that was used least recently. Both get and put must run in O(1) time, and many threads will call the cache.
Questions to ask first
- What counts as a use? Assume both `get` and `put` of an existing key make it the most recently used.
- What is the capacity unit? Assume a number of entries, not bytes.
- Do entries expire with time? Not for now. A time to live (TTL) per entry is an extension.
- Must it be thread safe? Yes, several threads call it at once.
- Can I use `LinkedHashMap`? Assume the interviewer wants the structure built by hand, but mention it.
- What does `get` return for a missing key? Assume `Optional.empty()` instead of null.
Requirements
- `get(key)` returns the value if present and marks the key as most recently used.
- `put(key, value)` inserts or updates the value and marks the key as most recently used.
- When a new key arrives and the cache is full, remove the least recently used entry first.
- Both operations run in O(1) time. This means constant time, no matter how many entries there are.
- The cache is safe to call from many threads at once.
Out of scope
- Expiry by time (TTL).
- A cache shared across many servers.
- Limits measured in bytes.
Entities
- Cache<K, V>: get(key), put(key, value), the contract callers see
- LRUCache: capacity, map, list, lock; the implementation
- Node: key, value, prev, next
- DoublyLinkedList: head, tail; addFirst, remove, moveToFront, removeLast
- EvictionListener: onEvict(key, value), an optional hook
- CacheStats: hits, misses, evictions
Classes in the model design
- Cache (interface)
- LRUCache (class)
- Node (class)
- DoublyLinkedList (class)
- EvictionListener (interface)
- CacheStats (class)
The main use case, step by step
- The cache has capacity 3 and holds A, B and C. The list order is C, B, A. The front is the most recent and the back is the least recent.
- `get(A)` looks up A in the HashMap in O(1) time and finds its Node. It calls `list.moveToFront(node)`, which unlinks the node and links it after the head. The order is now A, C, B.
- `put(D, 4)` finds no D in the map. The cache is full, so it calls `list.removeLast()`, which returns B, the least recently used entry.
- The cache removes B from the map using `node.key`. This is why each Node stores its key and not only its value.
- A new Node for D is added at the front and put in the map. The order is D, A, C. Every step changed a fixed number of links, so each call is O(1).
- All of this runs while holding one lock. Even `get` changes the list, so a read lock would not be safe.
Patterns used
- Encapsulation behind an interface: LRUCache hides the HashMap and the DoublyLinkedList behind the Cache interface.. Callers see only get and put. You can change the inside, for example to LinkedHashMap or an LFU rule, without changing any caller.
- Observer: EvictionListener, called when an entry is removed to make room.. Some callers must act on eviction, for example write a changed value to the database. A listener lets them do it without the cache knowing about databases.
Key code
Node and a doubly linked list with sentinels
public interface Cache<K, V> {
Optional<V> get(K key);
void put(K key, V value);
int size();
}
final class Node<K, V> {
final K key; // needed to remove the map entry on eviction
V value;
Node<K, V> prev;
Node<K, V> next;
Node(K key, V value) { this.key = key; this.value = value; }
}
/** Sentinel head and tail: real nodes always sit between them, so there are no null checks. */
final class DoublyLinkedList<K, V> {
private final Node<K, V> head = new Node<>(null, null);
private final Node<K, V> tail = new Node<>(null, null);
DoublyLinkedList() { head.next = tail; tail.prev = head; }
void addFirst(Node<K, V> n) {
n.prev = head;
n.next = head.next;
head.next.prev = n;
head.next = n;
}
void remove(Node<K, V> n) {
n.prev.next = n.next;
n.next.prev = n.prev;
}
void moveToFront(Node<K, V> n) { remove(n); addFirst(n); }
Node<K, V> removeLast() {
if (tail.prev == head) return null; // empty
Node<K, V> last = tail.prev;
remove(last);
return last;
}
}
LRUCache: get and put in O(1), under one lock
public final class LRUCache<K, V> implements Cache<K, V> {
private final int capacity;
private final Map<K, Node<K, V>> map = new HashMap<>();
private final DoublyLinkedList<K, V> list = new DoublyLinkedList<>();
private final ReentrantLock lock = new ReentrantLock();
public LRUCache(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
this.capacity = capacity;
}
@Override
public Optional<V> get(K key) {
lock.lock(); // get changes the order too, so a read lock is not enough
try {
Node<K, V> n = map.get(key);
if (n == null) return Optional.empty();
list.moveToFront(n);
return Optional.ofNullable(n.value);
} finally {
lock.unlock();
}
}
@Override
public void put(K key, V value) {
lock.lock();
try {
Node<K, V> n = map.get(key);
if (n != null) { // update: same node, new value, now most recent
n.value = value;
list.moveToFront(n);
return;
}
if (map.size() == capacity) {
Node<K, V> eldest = list.removeLast();
map.remove(eldest.key);
}
n = new Node<>(key, value);
list.addFirst(n);
map.put(key, n);
} finally {
lock.unlock();
}
}
@Override
public int size() {
lock.lock();
try { return map.size(); } finally { lock.unlock(); }
}
}
Deep dives
Which data structure gives O(1)?
Weak: A list of keys in use order. get must find the key in the list and move it, which is O(n): the time grows with the number of entries. At 1 lakh (100,000) entries, every call slows down.
Good: LinkedHashMap with accessOrder = true and removeEldestEntry overridden. Inside the JDK it is a HashMap plus a linked list, and it is O(1). It is the right answer at work. In an interview, say it, then offer to build it yourself.
Great: A HashMap from key to Node, plus your own doubly linked list. The map finds the node in O(1). The list moves or removes a node in O(1) because each node knows both neighbours. Sentinel head and tail nodes (dummy nodes that hold no data) remove every null check at the ends.
Trade-off: The hand-built version is about 60 lines and easy to get wrong at the links. Test the edges: capacity 1, updating an existing key, and getting the only key.
Making it thread safe
Weak: Replace HashMap with ConcurrentHashMap and stop there. The map is safe, but the list is not. Two threads moving nodes at once can break the links and lose entries.
Good: One ReentrantLock (or synchronized) around the whole of get and put. A read-write lock does not help, because get also writes: it moves the node to the front. This is correct and simple.
Great: Under heavy load the single lock becomes the bottleneck. Split the cache into N segments by key hash, each an LRUCache with its own lock. Threads with different keys rarely wait. Libraries like Caffeine go further: they record reads in a buffer and apply them to the list in batches.
Trade-off: With segments, eviction is least recently used within a segment, not across the whole cache. Start with one lock. Move to segments only when measurement shows the lock is the problem.
Supporting other eviction rules
Weak: Copy LRUCache into LFUCache and change a few lines. The two copies of the locking and map code drift apart over time.
Good: Keep storage in one class. Put the rule for which key leaves next behind an EvictionPolicy interface with keyAccessed(key), keyAdded(key) and evict(). LRU and LFU (least frequently used) become two policies.
Great: Same as Good, and keep O(1) for each policy. LFU in O(1) needs a map from use count to a linked list of keys, plus the current minimum count. Add a Clock for TTL so tests do not need to sleep.
Trade-off: A policy interface adds a call on every get and put and makes the code less direct. Use it when the interviewer asks for more than one rule. Otherwise a single LRUCache is clearer.
Now add one more feature
- Now add a time to live (TTL) per entry. Store an `expiresAt` time in each Node and pass a `Clock` in. `get` treats an expired node as missing and removes it. A background cleaner is optional, because expired nodes also reach the back of the list.
- Now limit by memory size instead of entry count. Add a `Weigher` interface that returns the size of a value. Keep a running total and evict from the back until the total fits.
- Now write evicted values to a database. Register an `EvictionListener`. Call it after releasing the lock, so a slow database does not block every other thread.
- Now report the hit rate. Add `CacheStats` with `LongAdder` counters, which stay fast under many threads. Each `get` adds one hit or one miss.
What each level is expected to show
SDE-1: HashMap plus doubly linked list, working `get` and `put` in O(1), correct eviction, and clean edge cases such as capacity 1 and updating an existing key. Knows that `get` changes the order.
SDE-2: All of SDE-1, plus a correct locking story (including why a read lock fails), a Cache interface so the rule can change, and a plan for scale: segments, LFU or TTL. Mentions LinkedHashMap and when to prefer it.
Common mistakes
- Forgetting to move the node to the front on `get`, which turns the cache into FIFO (first in, first out).
- Not storing the key in the Node, so eviction cannot remove the entry from the map.
- Updating an existing key by adding a second node instead of changing the old one.
- Using ConcurrentHashMap and believing the whole cache is now thread safe.
- Taking a read lock in `get`. Get moves a node, so it is a write.
- Calling the eviction listener while still holding the lock.