A checkout API cached session payloads by id so a restart would not rebuild every cart from the database. Capacity was the contract: the heap was not allowed to grow forever. The first version was an unbounded HashMap. Staging held a few thousand sessions and looked fine. Production never evicted; the map grew until the JVM ran out of memory. The intern then stored pairs in an ArrayList and used indexOf on every get to move that session to the end. The eviction order was LRU. Peak traffic turned each lookup into a scan of the whole cache, and the request timed out.
LRU Cache asks for O(1) get and put, evicting the least recently used key. A hash table already gives get-by-key. Scanning a list of residents to find, promote, or drop the oldest uses that and still pays linear time per call.
This is an interview writeup, not a hashing or linked-list lecture. The hash-table post owns buckets and collisions. The linked list post owns splice and dummy nodes. First Unique Character and Ransom Note hash counts. A map of counts is not recency. Here we only care about mapping key to the live node so get and put can splice that node to most-recent without a scan.
The problem
Implement a cache with a fixed capacity. The constructor takes that capacity. get(key) returns the stored value, or -1 if the key is missing; a hit counts as a use. put(key, value) inserts or overwrites; that also counts as a use. When a put would grow the cache past capacity, evict the least recently used key first. Capacity is at least 1 unless a follow-up says otherwise.
capacity 2
put(42, 100)
put(17, 200)
get(42) → 100
put(88, 300) // evicts 17
get(17) → -1
put(42, 150) // overwrite; still two keys
get(88) → 300
put(9, 400) // evicts 88
get(88) → -1
get(42) → 150
get(9) → 400Note: A missing get returns -1 and does not insert a slot. An existing put overwrites the value and counts as a use; it does not occupy a second slot.
Scan and move-to-end is the honest brute force
Keep an ArrayList of pairs. Least-recent sits at index 0; most-recent at the end. get and put scan for the key, remove that pair, and append it. A new key appends; if the list is now over capacity, drop index 0. Correct. Linear per operation.
class LRUCacheScan {
static final class Pair {
int key;
int value;
Pair(int key, int value) {
this.key = key;
this.value = value;
}
}
final int capacity;
final List<Pair> order = new ArrayList<>();
LRUCacheScan(int capacity) {
this.capacity = capacity;
}
int get(int key) {
for (int i = 0; i < order.size(); i++) {
if (order.get(i).key == key) {
Pair p = order.remove(i);
order.add(p);
return p.value;
}
}
return -1;
}
void put(int key, int value) {
for (int i = 0; i < order.size(); i++) {
if (order.get(i).key == key) {
Pair p = order.remove(i);
p.value = value;
order.add(p);
return;
}
}
order.add(new Pair(key, value));
if (order.size() > capacity) {
order.remove(0);
}
}
}At capacity 2 this is a rounding error. At thousands of sessions you paid a full scan for a question a map-to-node plus a splice answers in expected constant time: where is this key, and which resident is oldest?
Hash the key to a node, then splice it to most-recent
A HashMap stores key → node. A doubly linked list of those same nodes is the recency order. Dummy head is the most-recent side; dummy tail is the least-recent side. Real nodes sit between them. head.next is the MRU; tail.prev is the LRU. You rewire those nodes — you do not copy values into a second structure, the same identity rule as Reverse Linked List.
get: map lookup. Miss →-1, no new node. Hit → unlink, link afterhead, return the value.putof a present key: overwriteval, unlink, link afterhead. Size does not change.putof a new key: allocate a node, put it in the map, link afterhead. Ifmap.size() > capacity, unlinktail.prevandmap.removethat node’s key.
Walk the same session. The sentinels are never in the map.
capacity = 2
sentinels: head (MRU side) … tail (LRU side)
put(42, 100)
map {42}
head ↔ 42:100 ↔ tail
put(17, 200)
map {42, 17}
head ↔ 17:200 ↔ 42:100 ↔ tail
get(42) → 100 unlink 42, link after head
head ↔ 42:100 ↔ 17:200 ↔ tail
put(88, 300) new node; size 3 > 2; evict tail.prev = 17
head ↔ 88:300 ↔ 42:100 ↔ tail
map {42, 88}
get(17) → -1 miss; do not insert
put(42, 150) overwrite; size stays 2
head ↔ 42:150 ↔ 88:300 ↔ tail
put(9, 400) new node; evict 88
head ↔ 9:400 ↔ 42:150 ↔ tail
map {42, 9}The Java is that class. The node holds key so eviction can delete from the map without a second scan.
class LRUCache {
static final class Node {
int key;
int val;
Node prev;
Node next;
Node(int key, int val) {
this.key = key;
this.val = val;
}
}
final int capacity;
final Map<Integer, Node> map = new HashMap<>();
final Node head = new Node(-1, -1);
final Node tail = new Node(-1, -1);
LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
int get(int key) {
Node node = map.get(key);
if (node == null) {
return -1;
}
unlink(node);
linkAfterHead(node);
return node.val;
}
void put(int key, int value) {
Node node = map.get(key);
if (node != null) {
node.val = value;
unlink(node);
linkAfterHead(node);
return;
}
node = new Node(key, value);
map.put(key, node);
linkAfterHead(node);
if (map.size() > capacity) {
Node lru = tail.prev;
unlink(lru);
map.remove(lru.key);
}
}
void unlink(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
void linkAfterHead(Node node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
}Time is expected O(1) per get and put — one map lookup, a constant number of pointer writes. Space is O(capacity) for the map and the nodes between the sentinels. Do not re-lecture hash buckets or dummy-node theory at the whiteboard unless they ask; those posts already own them.
Note: Dummy head and tail are sentinels, not cache entries. Every real node has both neighbors, so unlink and link have no null-head special case.
Note: Unlink before you link after head. A missing get returns -1 and must not fabricate a node. An update overwrites val on the existing node and promotes it; it does not grow the map.
What interviewers usually poke next
- LinkedHashMap access-order plus
removeEldestEntry. Java already ships an LRU map. That is a legal follow-up, not the board default — they usually want the hashmap-plus-list splice written out. - LFU, not LRU. Least-frequently-used evicts by count, not recency. Frequency plus recency is a different structure. Do not mix the two unless they switch the prompt.
- Thread safety. This
HashMapand this list are not concurrent. Two threads racingget/putcan corrupt the links. Say you would lock the cache or use a concurrent cache library. - Capacity 0 or 1. Capacity 1 is a single slot: every new key evicts the only resident. Capacity 0, if they allow it, means every
putinserts then immediately evicts —getalways misses. Ask before you special-case. getwithout a move. If they change the spec sogetis a peek, you look up and return without splicing. That is no longer LRU on read. Confirm before you skip the promote.
You are done with this problem when you can say, out loud, why scanning the list of pairs is correct, why the map must hold the node rather than just the value, and why move-to-head unlinks first.