These are the notes for DSA episode 25, the classic design question that closes the linked list block. Build a cache with a fixed capacity where get and put both run in O(1) average time and, when it is full, the least recently used key is thrown out. The obvious way keeps an ArrayList in recency order: it is correct, but every call scans and shifts, so 4 lakh calls on a 1-lakh cache hit Time Limit Exceeded. The fix glues two structures together: a HashMap from key to node finds any key instantly, and a doubly linked list with dummy head and tail keeps the order and lets you unhook any node in O(1). Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
A phone has room for only 2 apps in memory. You open Maps, then Music. You switch back to Maps: it jumps to the front of the recent-apps screen. Then you open Camera, and there's no room. Maps was just used, so the phone closes Music, the app untouched the longest. That rule is LRU: least recently used.
| On the phone | In the code |
|---|---|
| Apps kept in memory | Entries in the cache |
| Room for 2 apps | capacity |
| Opening an app | get(key) or put(key, value): a "use" |
| The front of the recent-apps screen | The most recently used key (head.next) |
| The app closed to make room | The evicted key (tail.prev) |
A cache is a small, fast memory that keeps copies of things you used recently. A hit means the item is in the cache (fast); a miss means you go to the slow place (disk, network). When the cache is full you must evict (throw out) one entry. Browsers, databases, operating systems and CPUs all use LRU-style caches.
Problem statement
Design a class LRU(capacity) with:
get(key): return the value if the key is present, else-1. This counts as a use.put(key, value): insert or update the key. This counts as a use. If a new key makes the cache exceedcapacity, evict the least recently used key first.
Both must run in O(1) average time.
capacity 2:
put(1,1) put(2,2) get(1) put(3,3) get(2) put(4,4) get(1) get(3) get(4)
→ 1 -1 -1 3 4
Edge cases: capacity 1, put on an existing key (update the value and make it most recent), get of a missing key.
Brute force: an ArrayList in recency order
Keep [key, value] pairs in an ArrayList, oldest first, newest last. get scans for the key, removes it and appends it; put removes any old pair, appends, and drops index 0 when over capacity.
static class LRU {
int cap;
ArrayList<int[]> list = new ArrayList<>();
LRU(int cap) { this.cap = cap; }
int find(int key) {
for (int i = 0; i < list.size(); i++)
if (list.get(i)[0] == key) return i;
return -1;
}
int get(int key) {
int i = find(key);
if (i == -1) return -1;
int[] e = list.remove(i);
list.add(e);
return e[1];
}
void put(int key, int value) {
int i = find(key);
if (i != -1) list.remove(i);
list.add(new int[]{key, value});
if (list.size() > cap) list.remove(0);
}
}
The example prints 1 -1 -1 3 4. Correct.
The big input: 4 lakh calls
Capacity 1 lakh; put 2 lakh keys, then get 2 lakh keys:
int n = 100000;
LRU c = new LRU(n);
long t0 = System.nanoTime();
for (int i = 0; i < 2 * n; i++) c.put(i, i);
for (int i = 0; i < 2 * n; i++) c.get(i);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("4 lakh calls, " + ms + " ms");
Result: Time Limit Exceeded.
Why the brute force fails
find(key)scans the list: O(n).ArrayList.remove(i)andremove(0)shift every element afteri: O(n).
| Capacity | Steps (about 4 calls × n each, per key) |
|---|---|
| 1,000 | ~40 lakh: instant |
| 10,000 | ~40 crore |
| 1 lakh | ~4 × 10¹⁰: TLE |
We need two things at once: (1) find any key instantly, (2) move any entry to the "newest" end and drop the oldest instantly.
The key insight: two structures, glued together
Think of a hotel: the reception register maps a guest's name to a room (find anyone instantly), and the rooms along a corridor are kept in order of last visit. The register doesn't store the guest's luggage, it points at the room.
| Need | Structure | Cost |
|---|---|---|
| Find a key | HashMap<Integer, Node> |
O(1) average |
| Keep recency order | Doubly linked list, newest at the front | O(1) to move/unhook a node you hold |
| Know which key to delete on eviction | Node stores its key |
O(1) map.remove(lru.key) |
Why doubly linked? To unhook node x you need its previous node: x.prev.next = x.next; x.next.prev = x.prev;. In a singly linked list x doesn't know its previous node, so you'd walk from the head: O(n).
Why dummy head and tail? With a fake head and fake tail, every real node always has a real prev and next, so no null checks. The newest node is always head.next; the eviction victim is always tail.prev.
Trace with capacity 2:
| Operation | List (head → tail) | Map keys | Note |
|---|---|---|---|
| start | H ⇄ T | {} | empty |
| put(1,1), put(2,2) | H ⇄ 2 ⇄ 1 ⇄ T | 1, 2 | new nodes go after H |
| get(1) | H ⇄ 1 ⇄ 2 ⇄ T | 1, 2 | unhook 1, add after H |
| put(3,3) | H ⇄ 3 ⇄ 1 ⇄ T | 1, 3 | full: victim tail.prev = 2, removed from list and map |
The optimal solution in Java
import java.util.*;
public class Main {
static class Node {
int key, val;
Node prev, next;
Node(int k, int v) { key = k; val = v; }
}
static class LRU {
int cap;
HashMap<Integer, Node> map = new HashMap<>();
Node head = new Node(0, 0), tail = new Node(0, 0);
LRU(int cap) {
this.cap = cap;
head.next = tail; tail.prev = head;
}
void remove(Node x) {
x.prev.next = x.next;
x.next.prev = x.prev;
}
void addFront(Node x) {
x.next = head.next; x.prev = head;
head.next.prev = x; head.next = x;
}
int get(int key) {
Node x = map.get(key);
if (x == null) return -1;
remove(x); addFront(x);
return x.val;
}
void put(int key, int value) {
Node x = map.get(key);
if (x != null) { x.val = value; remove(x); addFront(x); return; }
x = new Node(key, value);
map.put(key, x); addFront(x);
if (map.size() > cap) {
Node lru = tail.prev;
remove(lru); map.remove(lru.key);
}
}
}
public static void main(String[] args) {
LRU c = new LRU(2);
c.put(1, 1); c.put(2, 2);
System.out.print(c.get(1) + " ");
c.put(3, 3);
System.out.print(c.get(2) + " ");
c.put(4, 4);
System.out.println(c.get(1) + " " + c.get(3) + " " + c.get(4));
LRU one = new LRU(1);
one.put(1, 10); one.put(2, 20);
System.out.println(one.get(1) + " " + one.get(2));
LRU u = new LRU(2);
u.put(1, 1); u.put(2, 2); u.put(1, 100); u.put(3, 3);
System.out.println(u.get(1) + " " + u.get(2) + " " + u.get(3));
}
}
Output:
1 -1 -1 3 4
-1 20
100 -1 3
- The example is correct.
- Capacity 1:
put(2, 20)evicts 1, soget(1)is-1,get(2)is20. - Updating key 1 to 100 makes it the most recent, so
put(3, 3)evicts 2:100 -1 3.
With capacity 1 lakh and the same 4 lakh calls: 4 lakh calls, 128 ms (the exact time varies run to run).
Java's shortcut: LinkedHashMap
LinkedHashMap is a hash map with a doubly linked list inside. The third constructor argument true means access order (every get/put moves the entry to the end), and removeEldestEntry decides eviction:
static class LRU extends LinkedHashMap<Integer, Integer> {
int cap;
LRU(int cap) { super(16, 0.75f, true); this.cap = cap; }
int get(int key) { return getOrDefault(key, -1); }
void put(int key, int value) { super.put(key, value); }
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> e) {
return size() > cap;
}
}
Same example, same output: 1 -1 -1 3 4. Use it in real projects; in interviews you're usually asked to build the hand-made version.
The same solution in C++
std::list is a doubly linked list, and splice moves a node to the front in O(1) without copying it. The map stores the node's iterator.
#include <bits/stdc++.h>
using namespace std;
class LRUCache {
int cap;
list<pair<int, int>> order; // front = most recent: {key, value}
unordered_map<int, list<pair<int, int>>::iterator> pos;
public:
LRUCache(int capacity) : cap(capacity) {}
int get(int key) {
auto it = pos.find(key);
if (it == pos.end()) return -1;
order.splice(order.begin(), order, it->second); // move to front in O(1)
return it->second->second;
}
void put(int key, int value) {
auto it = pos.find(key);
if (it != pos.end()) {
it->second->second = value;
order.splice(order.begin(), order, it->second);
return;
}
order.emplace_front(key, value);
pos[key] = order.begin();
if ((int)pos.size() > cap) {
pos.erase(order.back().first);
order.pop_back();
}
}
};
int main() {
LRUCache c(2);
c.put(1, 1); c.put(2, 2);
cout << c.get(1) << " ";
c.put(3, 3);
cout << c.get(2) << " ";
c.put(4, 4);
cout << c.get(1) << " " << c.get(3) << " " << c.get(4) << "\n";
}
Output: 1 -1 -1 3 4
The same solution in Python
class Node:
__slots__ = ("key", "val", "prev", "next")
def __init__(self, key=0, val=0):
self.key, self.val = key, val
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity):
self.cap = capacity
self.map = {}
self.head, self.tail = Node(), Node()
self.head.next, self.tail.prev = self.tail, self.head
def _remove(self, x):
x.prev.next, x.next.prev = x.next, x.prev
def _add_front(self, x):
x.prev, x.next = self.head, self.head.next
self.head.next.prev = x
self.head.next = x
def get(self, key):
x = self.map.get(key)
if x is None:
return -1
self._remove(x); self._add_front(x)
return x.val
def put(self, key, value):
x = self.map.get(key)
if x:
x.val = value
self._remove(x); self._add_front(x)
return
x = Node(key, value)
self.map[key] = x
self._add_front(x)
if len(self.map) > self.cap:
lru = self.tail.prev
self._remove(lru)
del self.map[lru.key]
c = LRUCache(2)
c.put(1, 1); c.put(2, 2)
r = [c.get(1)]
c.put(3, 3); r.append(c.get(2))
c.put(4, 4); r += [c.get(1), c.get(3), c.get(4)]
print(*r)
Output: 1 -1 -1 3 4
Python shortcut with collections.OrderedDict (move_to_end and popitem(last=False) are O(1)):
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.cap, self.d = capacity, OrderedDict()
def get(self, key):
if key not in self.d: return -1
self.d.move_to_end(key)
return self.d[key]
def put(self, key, value):
self.d[key] = value
self.d.move_to_end(key)
if len(self.d) > self.cap: self.d.popitem(last=False)
c = LRUCache(2)
c.put(1, 1); c.put(2, 2); r = [c.get(1)]; c.put(3, 3); r.append(c.get(2)); c.put(4, 4); r += [c.get(1), c.get(3), c.get(4)]
print(*r)
Output: 1 -1 -1 3 4
Three real bugs
Bug 1: forgetting map.remove(lru.key) on eviction
remove(lru); // the key stays in the map
Real output on the example: 1 2 1 3 4. get(2) should be -1, but the map still points at the evicted node, so the "ghost" comes back (and unhooking a node that's no longer in the list corrupts the neighbours). The map also keeps growing: a memory leak.
Bug 2: get doesn't move the node to the front
if (x == null) return -1;
return x.val;
Real output: 1 2 -1 3 4. Reading key 1 didn't count as a use, so put(3, 3) evicted 1 instead of 2. That's FIFO (first in, first out), not LRU.
Bug 3: a node without its key
static class Node {
int val;
...
Real compile error:
Main.java:38: error: cannot find symbol
remove(lru); map.remove(lru.key);
^
symbol: variable key
location: variable lru of type Node
1 error
At eviction you hold only the node; it is the only thing that can tell you which key to delete from the map.
Complexity
| Approach | get | put | Space | 4 lakh calls, cap 1 lakh |
|---|---|---|---|---|
| ArrayList in recency order | O(n) | O(n) | O(capacity) | Time Limit Exceeded |
| HashMap + singly linked list | O(n) (find the previous node) | O(n) | O(capacity) | too slow |
| HashMap + doubly linked list | O(1) avg | O(1) avg | O(capacity) | 128 ms |
LinkedHashMap(…, true) |
O(1) avg | O(1) avg | O(capacity) | same idea, built in |
"Average" because a hash map lookup is O(1) on average (it can degrade with many collisions).
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
remove(lru); without map.remove(lru.key) |
1 2 1 3 4 |
the map still points at evicted nodes | remove from the list and the map |
get doesn't move the node |
1 2 -1 3 4 |
reads don't count as use: FIFO | remove(x); addFront(x); in get |
Node without key |
error: cannot find symbol |
eviction can't tell the map what to delete | store key and val in the node |
put on an existing key adds a second node |
the map and the list disagree, wrong evictions | old node left in the list | update the value and move the node |
Using ArrayList / singly linked list |
Time Limit Exceeded | finding or unhooking is O(n) | HashMap + doubly linked list |
| No dummy nodes | NullPointerException at the ends |
head.prev/tail.next are null |
dummy head and tail |
Mini project: a photo-thumbnail cache
A gallery app keeps the thumbnails of the last 3 photos you opened in memory; anything else is loaded from disk. Add a peek (look without counting as a use) and a size, then count disk loads:
LRU c = new LRU(2);
c.put(1, 1); c.put(2, 2);
System.out.print(c.peek(1) + " ");
c.put(3, 3);
System.out.println(c.get(1) + " " + c.get(2) + " size " + c.size());
LRU thumbs = new LRU(3);
int[] opened = {7, 3, 7, 9, 4, 3, 7};
int loads = 0;
for (int photo : opened) {
if (thumbs.get(photo) == -1) { loads++; thumbs.put(photo, photo * 100); }
}
System.out.println("disk loads: " + loads + " of " + opened.length);
with, inside LRU:
int peek(int key) {
Node x = map.get(key);
return x == null ? -1 : x.val;
}
int size() { return map.size(); }
Real output:
1 -1 2 size 2
disk loads: 6 of 7
peek(1) didn't count as a use, so put(3, 3) evicted 1. Only the second open of photo 7 was a hit.
Practice
1. What does get return on an empty cache?
Solution
-1: map.get(key) is null.
2. Why does put on an existing key not trigger an eviction?
Solution
The number of keys doesn't change. The code updates the value, moves the node to the front, and returns before the size check.
3. Trace capacity 2: put(1,1) put(2,2) put(1,10) put(3,3) get(2) get(1).
Solution
put(1,10) makes 1 most recent, so put(3,3) evicts 2. get(2) = -1, get(1) = 10.
4. LFU cache (harder): evict the least frequently used key, ties broken by LRU.
Solution
Keep key → node (value, frequency), a map frequency → doubly linked list of nodes with that frequency (each list in LRU order), and minFreq. On a use, move the node from list f to list f + 1 (update minFreq if list f became empty and f == minFreq). To evict, remove tail.prev of the minFreq list. A new key gets frequency 1 and sets minFreq = 1. All operations O(1).
5. LRU with a time-to-live: entries expire after t seconds.
Solution
Store an expiresAt timestamp in each node. In get, if now >= expiresAt, remove the node from the list and the map and return -1. Eviction for capacity stays tail.prev.
Quick quiz
LRU c = new LRU(3);
c.put(1, 1); c.put(2, 2); c.put(3, 3);
c.get(1); c.put(4, 4); c.get(3); c.put(5, 5);
Which keys are left?
- 1, 3, 5
- 3, 4, 5
- 1, 4, 5
- 2, 3, 5
Answer
3, 4, 5. After get(1) the order (newest first) is 1, 3, 2, so put(4) evicts 2 → 4, 1, 3. get(3) → 3, 4, 1, so put(5) evicts 1 → 5, 3, 4. (Real output of System.out.println(c.map.keySet()): [3, 4, 5].)
Interview questions
- Design an LRU cache with O(1) get and put. HashMap from key to node + doubly linked list in recency order with dummy head and tail; move to front on every use; evict
tail.prev. - Why a doubly linked list, not singly? Unhooking a node needs its previous node; a singly linked list would need an O(n) walk.
- Why does the node store the key? On eviction, the node is all you have; you need its key to delete it from the map.
- Why dummy nodes? No null checks at either end; newest is
head.next, victim istail.prev. - Is it really O(1)? Average O(1): hash map operations are O(1) on average.
- How would you make it thread-safe? Simplest: a lock around
get/put(both mutate the list). For high concurrency: segment the cache into shards, each with its own lock. - What does Java give you for free?
LinkedHashMapwithaccessOrder = trueandremoveEldestEntry. - LRU vs LFU vs FIFO? LRU evicts the oldest use; LFU the fewest uses; FIFO the oldest insertion, ignoring reads.
Glossary
| Term | Meaning |
|---|---|
| Cache | A small, fast memory that keeps copies of recently used data |
| Hit / miss | The item is / isn't in the cache |
| Evict | Throw an entry out of a full cache to make room |
| LRU (least recently used) | Eviction policy: remove the entry whose last use is oldest |
| FIFO (first in, first out) | Remove the entry inserted first, ignoring reads |
| LFU (least frequently used) | Remove the entry used the fewest times |
| Capacity | The maximum number of entries the cache holds |
HashMap |
Key → value store with O(1) average lookup |
| Doubly linked list | Each node has prev and next, so any node can be unhooked in O(1) |
| Dummy (sentinel) node | A fake node at an end so real nodes never have null neighbours |
head.next / tail.prev |
The most recent node / the least recently used node |
LinkedHashMap (access order) |
Java's built-in hash map + doubly linked list |
| O(1) average | Constant time on average, independent of the cache size |
| Time Limit Exceeded (TLE) | Too slow for the judge's limit (8 s in the SyntaxPilot compiler) |
Summary
- An LRU cache evicts the key whose last use is oldest;
getandputboth count as uses. - An ordered
ArrayListis O(n) per call and times out. HashMap<key, Node>+ doubly linked list (dummy head/tail): move to front on every use, evicttail.prevandmap.remove(lru.key). O(1) average per call, O(capacity) space.- Java:
LinkedHashMap(16, 0.75f, true)+removeEldestEntry. Python:OrderedDict. C++:list+unordered_map+splice.
Next episode: Stacks: valid parentheses.