LRU cache
Design an LRU cache with O(1) get and put: a hash map plus a doubly linked list, eviction, thread safety, TTL, and the LinkedHashMap and OrderedDict shortcuts.
On this page
- The problem: a cache that is slower than it should be
- 1. Clarify the requirements
- 2. The idea: two structures, each doing what it is good at
- 3. The class design
- 4. The code
- 5. Concurrency: a read is a write
- 6. TTL: expiry on top of LRU
- 7. Options and trade-offs
- 8. Extensions the interviewer will ask for
- When not to build this
- In the interview
- Quiz
The problem: a cache that is slower than it should be
An LRU cache (least recently used) keeps a fixed number of items and, when it is full, throws away the item that was used longest ago. It is one of the most common machine-coding questions because it fits in 45 minutes and still has a trap: the interviewer asks for get and put in O(1) time, meaning constant time however many items the cache holds.
The first attempt usually keeps the order in a list:
class NaiveLru {
Map<String, Integer> map = new HashMap<>();
List<String> order = new ArrayList<>(); // front = least recent
int capacity = 1000;
Integer get(String k) {
if (!map.containsKey(k)) return null;
order.remove(k); // O(n): searches the whole list
order.add(k);
return map.get(k);
}
void put(String k, int v) {
if (map.size() == capacity) map.remove(order.remove(0)); // O(n): shifts every element
map.put(k, v);
order.add(k); // bug: an existing key is now in the list twice
}
}
It works on the interviewer's three-line test and fails the follow-ups:
- O(n) per call.
order.remove(k)scans the list. With 100,000 entries, every read walks up to 100,000 strings. - Updating an existing key adds a duplicate to
order, so the list and the map disagree. - Not thread-safe. Two threads calling
getboth modifyorderat once. Note that in an LRU cache a read is also a write, because it changes the order.
1. Clarify the requirements
The interviewer says "Design an LRU cache." Write 4–5 questions you would ask before writing code, and the API you would agree on.
Compare with our answer
Questions worth asking: What is the capacity measured in, number of entries or bytes? Do get and put both need O(1)? Is it used from several threads? Should entries also expire after a time (TTL)? What should get return on a miss? May I use the standard library's ordered map?
A strong answer mentions: capacity unit (count or bytes) · O(1) for both operations · put on an existing key updates it and makes it most recent · thread safety · TTL as a possible extension · whether built-in shortcuts are allowed.
The agreed list for this page:
| Requirement | Detail |
|---|---|
get(key) | Returns the value or "missing", and marks the key most recently used |
put(key, value) | Inserts or updates; the key becomes most recently used |
| Capacity | A fixed number of entries, set in the constructor; must be positive |
| Eviction | When inserting a new key into a full cache, remove the least recently used entry first |
| Complexity | get and put in O(1) average time |
| Threads | Safe to call from many threads |
| Extension | Optional time-to-live (TTL): an entry expires a fixed time after it was written |
Out of scope: persistence, a distributed cache across machines, size in bytes (offered as an extension below), and statistics beyond hit and miss counters.
2. The idea: two structures, each doing what it is good at
No single standard structure gives both O(1) lookup by key and O(1) "move this item to the front". So you combine two:
- A hash map from key to a list node: finds any entry in O(1).
- A doubly linked list of nodes in order of use: each node knows its neighbours (
prevandnext), so it can be cut out and re-inserted with a few pointer writes, without searching. The front is the most recently used; the back is the next victim.
Two sentinel nodes, head and tail, are dummy nodes that hold no data and are never removed. They mean every real node always has a neighbour on both sides, so the code needs no if (node == first) special cases.
The map points into the list; the list keeps the order of use
How get and put work
| Operation | Steps | Cost |
|---|---|---|
get(k) hit | map lookup → unlink node → add after head | O(1) |
get(k) miss | map lookup returns nothing | O(1) |
put(k, v), key exists | update value → unlink → add after head | O(1) |
put(k, v), new key, not full | new node → add after head → map insert | O(1) |
put(k, v), new key, full | victim = tail.prev → unlink → delete its key from the map → insert as above | O(1) |
"O(1) average" is honest wording: hash-map operations are constant time on average, and can degrade with many collisions.
get moves a node to the front; put on a full cache evicts tail.prev
3. The class design
The classes and their relationships
| Class / type | Kind | Responsibility |
|---|---|---|
Cache<K,V> | interface | get, put, remove, size; callers depend on this, not on the eviction policy |
LruCache<K,V> | class | Owns the map, the list and the lock; implements LRU eviction |
Node<K,V> | private nested class | Key, value, expiry time, prev, next |
| Clock | interface (LongSupplier in Java, a function in Python) | Returns the current time; injected so tests control it |
Why these choices, one sentence each:
- An interface for the cache lets you swap LRU for LFU (least frequently used) or a no-op cache in tests without touching callers.
- Node is private: callers never see list pointers, so they cannot corrupt the list.
- An injected clock makes TTL testable: the test moves a fake clock forward 500 ms instead of sleeping.
Optional<V>in Java (orNonein Python) makes a miss explicit. Returning-1, as the LeetCode version does, breaks as soon as-1is a legitimate value.
4. The code
The model below has capacity, O(1) get/put/remove, optional TTL with lazy expiry (an expired entry is removed when someone reads it), hit/miss counters, one lock, and a demo that also runs eight threads against one cache. It also shows the library shortcut.
import java.util.*;
import java.util.concurrent.*;
import java.util.function.LongSupplier;
interface Cache<K, V> {
Optional<V> get(K key);
void put(K key, V value);
boolean remove(K key);
int size();
}
/** O(1) LRU cache: a hash map finds the node, a doubly linked list keeps the recency order. */
final class LruCache<K, V> implements Cache<K, V> {
private static final class Node<K, V> {
K key; V value; long expiresAt; // expiresAt = Long.MAX_VALUE means "never"
Node<K, V> prev, next;
Node(K key, V value, long expiresAt) { this.key = key; this.value = value; this.expiresAt = expiresAt; }
}
private final int capacity;
private final long ttlMillis; // 0 = no expiry
private final LongSupplier clock; // injected so tests can move time
private final Map<K, Node<K, V>> map = new HashMap<>();
private final Node<K, V> head = new Node<>(null, null, 0); // sentinel: most recent follows it
private final Node<K, V> tail = new Node<>(null, null, 0); // sentinel: least recent precedes it
private long hits, misses, evictions;
LruCache(int capacity) { this(capacity, 0, () -> System.nanoTime() / 1_000_000); } // monotonic ms, unlike currentTimeMillis
LruCache(int capacity, long ttlMillis, LongSupplier clock) {
if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
this.capacity = capacity; this.ttlMillis = ttlMillis; this.clock = clock;
head.next = tail; tail.prev = head;
}
// ---- list helpers: each is a few pointer writes, O(1) ----
private void unlink(Node<K, V> n) { n.prev.next = n.next; n.next.prev = n.prev; }
private void addFront(Node<K, V> n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }
private boolean expired(Node<K, V> n) { return clock.getAsLong() >= n.expiresAt; }
@Override public synchronized Optional<V> get(K key) {
Node<K, V> n = map.get(key);
if (n == null) { misses++; return Optional.empty(); }
if (expired(n)) { unlink(n); map.remove(key); misses++; return Optional.empty(); } // lazy expiry
unlink(n); addFront(n); // a read makes it the most recently used
hits++;
return Optional.of(n.value);
}
@Override public synchronized void put(K key, V value) {
long exp = ttlMillis > 0 ? clock.getAsLong() + ttlMillis : Long.MAX_VALUE;
Node<K, V> n = map.get(key);
if (n != null) { // update in place, then move to front
n.value = value; n.expiresAt = exp;
unlink(n); addFront(n);
return;
}
if (map.size() == capacity) { // full: evict the least recently used
Node<K, V> lru = tail.prev;
unlink(lru); map.remove(lru.key); evictions++;
}
n = new Node<>(key, value, exp);
addFront(n); map.put(key, n);
}
@Override public synchronized boolean remove(K key) {
Node<K, V> n = map.remove(key);
if (n == null) return false;
unlink(n); return true;
}
@Override public synchronized int size() { return map.size(); }
synchronized List<K> keysMostRecentFirst() {
List<K> out = new ArrayList<>();
for (Node<K, V> n = head.next; n != tail; n = n.next) out.add(n.key);
return out;
}
synchronized String stats() { return "hits=" + hits + " misses=" + misses + " evictions=" + evictions; }
}
/** The shortcut: LinkedHashMap in access order does the same job in a few lines. */
final class LinkedLru<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
LinkedLru(int capacity) { super(16, 0.75f, true); this.capacity = capacity; } // true = access order
@Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; }
}
public class LruDemo {
public static void main(String[] args) throws Exception {
LruCache<String, Integer> c = new LruCache<>(3);
c.put("a", 1); c.put("b", 2); c.put("c", 3);
System.out.println("order: " + c.keysMostRecentFirst());
c.get("a"); // a becomes most recent
c.put("d", 4); // full: evicts b, the least recent
System.out.println("after get(a), put(d): " + c.keysMostRecentFirst());
System.out.println("get(b): " + c.get("b").map(String::valueOf).orElse("miss"));
c.put("c", 30); // update moves c to the front
System.out.println("after put(c,30): " + c.keysMostRecentFirst());
System.out.println(c.stats());
// TTL with a fake clock: no sleeping in tests
long[] now = {1_000};
LruCache<String, String> t = new LruCache<>(2, 500, () -> now[0]);
t.put("session", "alice");
now[0] += 499; System.out.println("ttl at 499 ms: " + t.get("session").orElse("expired"));
now[0] += 1; System.out.println("ttl at 500 ms: " + t.get("session").orElse("expired"));
Map<String, Integer> lhm = new LinkedLru<>(2);
lhm.put("x", 1); lhm.put("y", 2); lhm.get("x"); lhm.put("z", 3);
System.out.println("LinkedHashMap version keeps: " + lhm.keySet());
// Concurrency: 8 threads hammer a cache of 100 keys; size never exceeds capacity
LruCache<Integer, Integer> shared = new LruCache<>(100);
ExecutorService pool = Executors.newFixedThreadPool(8);
List<Future<?>> fs = new ArrayList<>();
for (int th = 0; th < 8; th++) {
final int seed = th;
fs.add(pool.submit(() -> {
Random r = new Random(seed);
for (int i = 0; i < 50_000; i++) {
int k = r.nextInt(500);
if (shared.get(k).isEmpty()) shared.put(k, k);
}
}));
}
for (Future<?> f : fs) f.get();
pool.shutdown();
System.out.println("after 400,000 concurrent ops: size=" + shared.size()
+ ", list length=" + shared.keysMostRecentFirst().size());
}
}import random
import threading
import time
from collections import OrderedDict
from concurrent.futures import ThreadPoolExecutor
from typing import Callable, Generic, Hashable, Optional, TypeVar
K = TypeVar("K", bound=Hashable)
V = TypeVar("V")
NEVER = float("inf")
class _Node:
__slots__ = ("key", "value", "expires_at", "prev", "next")
def __init__(self, key=None, value=None, expires_at=NEVER):
self.key, self.value, self.expires_at = key, value, expires_at
self.prev = self.next = None
class LRUCache(Generic[K, V]):
"""O(1) LRU cache: a dict finds the node, a doubly linked list keeps the recency order."""
def __init__(self, capacity: int, ttl: float = 0,
clock: Callable[[], float] = time.monotonic):
if capacity <= 0:
raise ValueError("capacity must be positive")
self.capacity, self.ttl, self.clock = capacity, ttl, clock
self._map: dict = {}
self._head, self._tail = _Node(), _Node() # sentinels: no None checks at the ends
self._head.next, self._tail.prev = self._tail, self._head
self._lock = threading.Lock() # get() changes the list, so reads need it too
self.hits = self.misses = self.evictions = 0
# ---- list helpers: a few pointer writes, O(1) ----
def _unlink(self, n: _Node) -> None:
n.prev.next, n.next.prev = n.next, n.prev
def _add_front(self, n: _Node) -> None:
n.prev, n.next = self._head, self._head.next
self._head.next.prev = n
self._head.next = n
def get(self, key: K) -> Optional[V]:
with self._lock:
n = self._map.get(key)
if n is None:
self.misses += 1
return None
if self.clock() >= n.expires_at: # lazy expiry on read
self._unlink(n)
del self._map[key]
self.misses += 1
return None
self._unlink(n)
self._add_front(n) # a read makes it most recently used
self.hits += 1
return n.value
def put(self, key: K, value: V) -> None:
with self._lock:
exp = self.clock() + self.ttl if self.ttl > 0 else NEVER
n = self._map.get(key)
if n is not None: # update in place, then move to front
n.value, n.expires_at = value, exp
self._unlink(n)
self._add_front(n)
return
if len(self._map) == self.capacity: # full: evict the least recently used
lru = self._tail.prev
self._unlink(lru)
del self._map[lru.key]
self.evictions += 1
n = _Node(key, value, exp)
self._add_front(n)
self._map[key] = n
def remove(self, key: K) -> bool:
with self._lock:
n = self._map.pop(key, None)
if n is None:
return False
self._unlink(n)
return True
def __len__(self) -> int:
with self._lock:
return len(self._map)
def keys_most_recent_first(self) -> list:
with self._lock:
out, n = [], self._head.next
while n is not self._tail:
out.append(n.key)
n = n.next
return out
def stats(self) -> str:
with self._lock:
return f"hits={self.hits} misses={self.misses} evictions={self.evictions}"
class OrderedDictLRU:
"""The shortcut: OrderedDict keeps insertion order and can move a key to the end in O(1)."""
def __init__(self, capacity: int):
self.capacity, self._d = capacity, OrderedDict()
def get(self, key):
if key not in self._d:
return None
self._d.move_to_end(key) # end = most recent
return self._d[key]
def put(self, key, value):
self._d[key] = value
self._d.move_to_end(key)
if len(self._d) > self.capacity:
self._d.popitem(last=False) # front = least recent
if __name__ == "__main__":
c = LRUCache(3)
c.put("a", 1); c.put("b", 2); c.put("c", 3)
print("order: ", c.keys_most_recent_first())
c.get("a") # a becomes most recent
c.put("d", 4) # full: evicts b
print("after get(a), put(d):", c.keys_most_recent_first())
v = c.get("b")
print("get(b):", "miss" if v is None else v) # `or` would treat a cached 0 or "" as a miss
c.put("c", 30)
print("after put(c,30):", c.keys_most_recent_first())
print(c.stats())
now = [1.0] # fake clock, in seconds
t = LRUCache(2, ttl=0.5, clock=lambda: now[0])
t.put("session", "alice")
now[0] += 0.499; print("ttl at 499 ms:", t.get("session") or "expired")
now[0] += 0.001; print("ttl at 500 ms:", t.get("session") or "expired")
od = OrderedDictLRU(2)
od.put("x", 1); od.put("y", 2); od.get("x"); od.put("z", 3)
print("OrderedDict version keeps:", list(od._d))
shared = LRUCache(100)
def hammer(seed):
r = random.Random(seed)
for _ in range(50_000):
k = r.randrange(500)
if shared.get(k) is None:
shared.put(k, k)
with ThreadPoolExecutor(max_workers=8) as pool:
list(pool.map(hammer, range(8)))
print(f"after 400,000 concurrent ops: size={len(shared)}, "
f"list length={len(shared.keys_most_recent_first())}")Running the Java version prints (Python prints the same, with lists shown as ['c', 'b', 'a']):
order: [c, b, a]
after get(a), put(d): [d, a, c]
get(b): miss
after put(c,30): [c, d, a]
hits=1 misses=1 evictions=1
ttl at 499 ms: alice
ttl at 500 ms: expired
LinkedHashMap version keeps: [x, z]
after 400,000 concurrent ops: size=100, list length=100
Trace the first lines: after a, b, c the order is c, b, a. Reading a moves it to the front (a, c, b), so when d arrives the victim is b. Updating c moves it to the front without evicting anything, because the key already existed.
The shortcuts, and why interviewers may forbid them
Both languages ship an ordered hash map that does all of this:
- Java
LinkedHashMapwithaccessOrder = truemoves an entry to the end on everyget, and callsremoveEldestEntryafter each insert; returningsize() > capacitymakes it an LRU cache in five lines. - Python
OrderedDicthasmove_to_end(key)andpopitem(last=False), both O(1). (functools.lru_cacheis a decorator for caching function results, not a general key-value cache.)
Mention them early: "In production I would use LinkedHashMap; shall I build the structure myself?" Most interviewers say yes, build it, because the question exists to see you combine a map and a linked list. If they accept the shortcut, you finish early and spend the time on concurrency and TTL. Note that neither shortcut is thread-safe: LinkedHashMap in access order is modified by get, so reads need the lock too (Collections.synchronizedMap provides one).
5. Concurrency: a read is a write
In most maps, many readers can run at once. In an LRU cache, get moves a node, so it writes the list. Two unsynchronised get calls on neighbouring nodes interleave their pointer writes, and the list can lose a node or form a cycle; the next traversal then loops forever.
Two threads rewrite the same pointers, and the fix
| Race | What goes wrong | Fix |
|---|---|---|
Two gets on neighbours | Pointers overwritten; lost node or loop | One lock around every method, including get |
get while put evicts | get moves a node that put just unlinked; it comes back as a ghost | Same lock: eviction and the move cannot interleave |
| Size check then insert | Two puts both see size < capacity; the cache ends up over capacity | The check and the insert are inside one critical section |
| Read-write lock | Looks faster, but get needs the write lock, so readers gain nothing | Use a plain lock, or a design where reads do not move nodes |
The demo's eight threads do 400,000 operations and the size and the list length both end at exactly 100. Remove synchronized (or the with self._lock) and the Java version can fail with a broken list or a size above capacity. Python's global interpreter lock (GIL) makes each bytecode step atomic, but a move_to_front is many steps, so the lock is still required.
Striped LRU: one lock per shard
Lock striping means replacing one lock that guards everything with N locks that each guard a part. For a cache, each part is simply a complete, independent LruCache with its own map, list and lock. A key's hash picks its stripe, so the same key always lands in the same one, and two threads only contend when their keys hash to the same stripe. With 16 stripes and keys spread evenly, the chance that two random calls collide drops from certain to 1 in 16.
The wrapper needs no lock of its own, because it holds no shared mutable state: the list of stripes never changes after construction.
import java.util.*;
import java.util.concurrent.*;
/** N independent LRU caches, each with its own lock; a key always maps to the same stripe. */
final class StripedLruCache<K, V> implements Cache<K, V> {
private final List<LruCache<K, V>> stripes = new ArrayList<>();
StripedLruCache(int capacity, int stripeCount) {
int perStripe = (capacity + stripeCount - 1) / stripeCount; // round up
for (int i = 0; i < stripeCount; i++) stripes.add(new LruCache<>(perStripe));
}
private LruCache<K, V> stripeFor(K key) {
int h = key.hashCode();
h ^= (h >>> 16); // mix high bits into low ones, as HashMap does
return stripes.get(Math.floorMod(h, stripes.size()));
}
// No lock here: each call locks only its own stripe (LruCache's methods are synchronized).
@Override public Optional<V> get(K key) { return stripeFor(key).get(key); }
@Override public void put(K key, V value) { stripeFor(key).put(key, value); }
@Override public boolean remove(K key) { return stripeFor(key).remove(key); }
@Override public int size() { // a moving total, not a snapshot
int n = 0;
for (LruCache<K, V> s : stripes) n += s.size();
return n;
}
}
public class StripedDemo {
public static void main(String[] args) throws Exception {
Cache<Integer, Integer> cache = new StripedLruCache<>(1_000, 16);
ExecutorService pool = Executors.newFixedThreadPool(8);
List<Future<?>> jobs = new ArrayList<>();
for (int t = 0; t < 8; t++) {
final int seed = t;
jobs.add(pool.submit(() -> {
Random r = new Random(seed);
for (int i = 0; i < 200_000; i++) {
int k = r.nextInt(5_000);
if (cache.get(k).isEmpty()) cache.put(k, k * 10);
}
}));
}
for (Future<?> j : jobs) j.get();
pool.shutdown();
System.out.println("size after 1.6 M operations: " + cache.size() + " (at most 16 x 63 = 1008)");
cache.put(42, 420);
System.out.println("get(42) -> " + cache.get(42));
}
}import random
from concurrent.futures import ThreadPoolExecutor
from typing import Generic, Hashable, Optional, TypeVar
from lru_cache import LRUCache # the class from section 4
K = TypeVar("K", bound=Hashable)
V = TypeVar("V")
class StripedLRUCache(Generic[K, V]):
"""N independent LRU caches, each with its own lock; a key always maps to the same stripe."""
def __init__(self, capacity: int, stripe_count: int = 16):
per_stripe = -(-capacity // stripe_count) # round up
self._stripes = [LRUCache(per_stripe) for _ in range(stripe_count)]
def _stripe(self, key: K) -> LRUCache:
return self._stripes[hash(key) % len(self._stripes)]
# No lock here: each call takes only its own stripe's lock.
def get(self, key: K) -> Optional[V]:
return self._stripe(key).get(key)
def put(self, key: K, value: V) -> None:
self._stripe(key).put(key, value)
def remove(self, key: K) -> bool:
return self._stripe(key).remove(key)
def __len__(self) -> int: # a moving total, not a snapshot
return sum(len(s) for s in self._stripes)
if __name__ == "__main__":
cache: StripedLRUCache[int, int] = StripedLRUCache(1_000, 16)
def hammer(seed: int) -> None:
r = random.Random(seed)
for _ in range(50_000):
k = r.randrange(5_000)
if cache.get(k) is None:
cache.put(k, k * 10)
with ThreadPoolExecutor(8) as pool:
list(pool.map(hammer, range(8)))
print(f"size after 400 K operations: {len(cache)} (at most 16 x 63 = 1008)")
cache.put(42, 420)
print("get(42) ->", cache.get(42))Output (Java first; the Python demo does 400 K operations and prints the same size):
size after 1.6 M operations: 1008 (at most 16 x 63 = 1008)
get(42) -> Optional[420]
What you give up, and what to watch:
- Eviction is LRU per stripe. A full stripe evicts its own oldest key even when another stripe holds a key that is older overall. With many keys per stripe the hit rate is close to exact LRU.
- Capacity is rounded per stripe (1,000 / 16 rounds up to 63, so 1,008 in total), and a skewed hash can fill one stripe while others are half empty. Mix the hash bits, as the Java version does, and use a power-of-two stripe count of about 2 to 4 times the core count.
size()is not a snapshot: it adds stripes one by one while others change. Fine for metrics, not for decisions.- In CPython the GIL (global interpreter lock: only one thread runs Python bytecode at a time) limits the gain to shorter lock waits; real parallel speed-up needs a free-threaded build (Python 3.13+) or processes.
6. TTL: expiry on top of LRU
TTL and LRU answer different questions: LRU decides what to drop when full; TTL decides when data is too old to trust. The code stores expiresAt in each node and checks it on get, which is lazy expiry: an expired entry costs nothing until someone reads it.
The catch is that expired entries nobody reads still occupy slots until LRU eviction reaches them. That is usually fine, because they drift to the back of the list. If memory matters, add active expiry: a background task that periodically removes expired entries. Keeping entries ordered by expiry needs a second structure (a min-heap, or a list if every entry has the same TTL, since then write order equals expiry order). Redis does both, lazy checks on access and a periodic sampler.
7. Options and trade-offs
| Approach | Good at | Weak at | Use when |
|---|---|---|---|
| Hash map + doubly linked list (built above) | Exact LRU, O(1), you control everything | Pointer overhead per entry (two references plus a node object) | The interview; custom eviction rules |
LinkedHashMap / OrderedDict | Five lines, well tested | Not thread-safe; harder to add TTL or byte limits | Production code in one thread, or behind your own lock |
| Sharded LRU | Scales across cores | LRU is exact only within a shard | Hot in-process caches on many-core servers |
| Approximate LRU (sampling) | No list, low memory, little locking | May evict a key that is not the oldest | Very large caches (Redis) |
| LFU / W-TinyLFU (Caffeine) | Better hit rate when some keys stay popular | More complex; frequency counters to age | Production caches with skewed access |
8. Extensions the interviewer will ask for
- Capacity in bytes instead of entries: track
totalBytes; onput, evict from the tail whiletotalBytes > maxBytes. One insert may evict several small entries. (Try box below.) - Eviction callback: accept a listener
onEvict(key, value)in the constructor, called after the lock is released so a slow listener does not block the cache. This is the Observer idea; see the Observer pattern. - LFU instead of LRU: make eviction a policy behind the
Cacheinterface. O(1) LFU uses a map from frequency to an ordered set of keys, plus aminFreqpointer (built below). - Loading cache:
get(key, loader)computes the value on a miss. Two threads missing the same key should not both call the loader; keep a map of in-flight loads (aFutureper key) so the second waits for the first.
LFU: evict the least frequently used
LFU (least frequently used) evicts the key with the fewest uses, which keeps popular keys that LRU would drop after a burst of one-off reads (a nightly report scanning thousands of keys once). The O(1) design keeps three things:
| Structure | Holds |
|---|---|
entries | key → value and its use count (frequency) |
buckets | frequency → the keys with that frequency, oldest first (a LinkedHashSet in Java, an OrderedDict used as an ordered set in Python) |
minFreq | the lowest frequency that currently has keys |
A use (get, or put on an existing key) moves the key from bucket f to bucket f + 1; if bucket f is now empty and f was minFreq, minFreq becomes f + 1. A new key goes into bucket 1 and sets minFreq = 1. To evict, take the oldest key in bucket minFreq, so ties between equally used keys fall back to LRU. Every step is a hash lookup or an ordered-set insert or delete: O(1).
import java.util.*;
/** O(1) LFU cache. Evicts the least frequently used key; ties go to the least recently used. */
final class LfuCache<K, V> implements Cache<K, V> { // Cache is the interface from section 4
private static final class Entry<V> {
V value; int freq = 1;
Entry(V value) { this.value = value; }
}
private final int capacity;
private final Map<K, Entry<V>> entries = new HashMap<>();
// frequency -> keys with that frequency, oldest first (LinkedHashSet keeps insertion order)
private final Map<Integer, LinkedHashSet<K>> buckets = new HashMap<>();
private int minFreq = 0;
private long evictions;
LfuCache(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
this.capacity = capacity;
}
/** Move a key from its frequency bucket to the next one up. O(1). */
private void touch(K key, Entry<V> e) {
LinkedHashSet<K> old = buckets.get(e.freq);
old.remove(key);
if (old.isEmpty()) {
buckets.remove(e.freq);
if (minFreq == e.freq) minFreq++; // the key was the last one at the minimum
}
e.freq++;
buckets.computeIfAbsent(e.freq, f -> new LinkedHashSet<>()).add(key);
}
@Override public synchronized Optional<V> get(K key) {
Entry<V> e = entries.get(key);
if (e == null) return Optional.empty();
touch(key, e);
return Optional.of(e.value);
}
@Override public synchronized void put(K key, V value) {
Entry<V> e = entries.get(key);
if (e != null) { // update counts as a use, never evicts
e.value = value;
touch(key, e);
return;
}
if (entries.size() == capacity) {
LinkedHashSet<K> victims = buckets.get(minFreq);
K victim = victims.iterator().next(); // least recently used among the least frequent
victims.remove(victim);
if (victims.isEmpty()) buckets.remove(minFreq);
entries.remove(victim);
evictions++;
System.out.println(" evict " + victim + " (freq " + minFreq + ")");
}
entries.put(key, new Entry<>(value));
buckets.computeIfAbsent(1, f -> new LinkedHashSet<>()).add(key);
minFreq = 1; // a new key always has the lowest frequency
}
@Override public synchronized boolean remove(K key) {
Entry<V> e = entries.remove(key);
if (e == null) return false;
LinkedHashSet<K> b = buckets.get(e.freq);
b.remove(key);
if (b.isEmpty()) buckets.remove(e.freq);
// minFreq may now point at an empty bucket. That is safe: the cache is below capacity,
// so nothing is evicted before the next new key, and that put resets minFreq to 1.
return true;
}
@Override public synchronized int size() { return entries.size(); }
synchronized long evictions() { return evictions; }
}
public class LfuDemo {
public static void main(String[] args) {
Cache<String, Integer> c = new LfuCache<>(2);
c.put("a", 1);
c.put("b", 2);
c.get("a"); // a: freq 2, b: freq 1
System.out.println("put c");
c.put("c", 3); // full: evicts b, the least frequent
System.out.println("get b -> " + c.get("b"));
c.get("a"); c.get("c"); // a: freq 3, c: freq 2
System.out.println("put d");
c.put("d", 4); // evicts c (freq 2), not a (freq 3)
System.out.println("get a -> " + c.get("a") + ", get c -> " + c.get("c") + ", get d -> " + c.get("d"));
System.out.println("size " + c.size());
}
}import threading
from collections import OrderedDict, defaultdict
from typing import Generic, Hashable, Optional, TypeVar
K = TypeVar("K", bound=Hashable)
V = TypeVar("V")
class LFUCache(Generic[K, V]):
"""O(1) LFU cache. Evicts the least frequently used key; ties go to the least recently used."""
def __init__(self, capacity: int):
if capacity <= 0:
raise ValueError("capacity must be positive")
self.capacity = capacity
self._values: dict = {} # key -> value
self._freq: dict = {} # key -> use count
# frequency -> keys with that frequency, oldest first (an OrderedDict used as an ordered set)
self._buckets: defaultdict = defaultdict(OrderedDict)
self._min_freq = 0
self._lock = threading.Lock()
self.evictions = 0
def _touch(self, key: K) -> None:
"""Move a key from its frequency bucket to the next one up. O(1)."""
f = self._freq[key]
bucket = self._buckets[f]
del bucket[key]
if not bucket:
del self._buckets[f]
if self._min_freq == f: # the key was the last one at the minimum
self._min_freq += 1
self._freq[key] = f + 1
self._buckets[f + 1][key] = None
def get(self, key: K) -> Optional[V]:
with self._lock:
if key not in self._values:
return None
self._touch(key)
return self._values[key]
def put(self, key: K, value: V) -> None:
with self._lock:
if key in self._values: # update counts as a use, never evicts
self._values[key] = value
self._touch(key)
return
if len(self._values) == self.capacity:
victims = self._buckets[self._min_freq]
victim, _ = victims.popitem(last=False) # least recently used among the least frequent
if not victims:
del self._buckets[self._min_freq]
del self._values[victim], self._freq[victim]
self.evictions += 1
print(f" evict {victim} (freq {self._min_freq})")
self._values[key] = value
self._freq[key] = 1
self._buckets[1][key] = None
self._min_freq = 1 # a new key always has the lowest frequency
def remove(self, key: K) -> bool:
with self._lock:
if key not in self._values:
return False
f = self._freq.pop(key)
del self._values[key]
bucket = self._buckets[f]
del bucket[key]
if not bucket:
del self._buckets[f]
# A stale _min_freq is safe: below capacity nothing is evicted, and the next new key resets it.
return True
def __len__(self) -> int:
return len(self._values)
if __name__ == "__main__":
c: LFUCache[str, int] = LFUCache(2)
c.put("a", 1)
c.put("b", 2)
c.get("a") # a: freq 2, b: freq 1
print("put c")
c.put("c", 3) # full: evicts b, the least frequent
print("get b ->", c.get("b"))
c.get("a"); c.get("c") # a: freq 3, c: freq 2
print("put d")
c.put("d", 4) # evicts c (freq 2), not a (freq 3)
print(f"get a -> {c.get('a')}, get c -> {c.get('c')}, get d -> {c.get('d')}")
print("size", len(c))Output (identical in both languages apart from Optional versus None):
put c
evict b (freq 1)
get b -> Optional.empty
put d
evict c (freq 2)
get a -> Optional[1], get c -> Optional.empty, get d -> Optional[4]
size 2
c was used twice and a three times, so c goes even though it was used more recently than a; plain LRU would have evicted a.
When not to build this
- Function results in Python:
@functools.lru_cache(maxsize=1024)already does it, thread-safely. - Production Java: use Caffeine or Guava's cache; they handle concurrency, TTL, weights and statistics.
- Shared across servers: an in-process cache is per server. If every server must see the same data, use Redis or Memcached; see caching.
- Tiny caches (a dozen entries): a scan over an array is fast enough and simpler.
In the interview
This put passes a simple test but breaks the cache. Find three bugs and fix them.
public synchronized void put(K key, V value) {
if (map.size() == capacity) {
Node<K, V> lru = tail.prev;
unlink(lru);
}
Node<K, V> n = new Node<>(key, value, Long.MAX_VALUE);
addFront(n);
map.put(key, n);
}Compare with our answer
The bugs: (1) the evicted node's key is never removed from the map, so the map grows forever and get can return evicted values. (2) An existing key is treated as new: the old node stays in the list, so the list has two nodes for one key. (3) Updating an existing key in a full cache evicts an innocent entry, even though the size would not grow.
public synchronized void put(K key, V value) {
Node<K, V> n = map.get(key);
if (n != null) { // existing key: update and move, never evict
n.value = value;
unlink(n); addFront(n);
return;
}
if (map.size() == capacity) {
Node<K, V> lru = tail.prev;
unlink(lru);
map.remove(lru.key); // the node carries its key for exactly this
}
n = new Node<>(key, value, Long.MAX_VALUE);
addFront(n);
map.put(key, n);
}def put(self, key, value):
with self._lock:
n = self._map.get(key)
if n is not None: # existing key: update and move, never evict
n.value = value
self._unlink(n)
self._add_front(n)
return
if len(self._map) == self.capacity:
lru = self._tail.prev
self._unlink(lru)
del self._map[lru.key] # the node carries its key for exactly this
n = _Node(key, value)
self._add_front(n)
self._map[key] = nA strong answer mentions: removing the victim's key from the map · handling an existing key before the capacity check · not evicting on an update · the node storing its key · the whole method under one lock.
The cache now stores images of different sizes. Capacity becomes 50 MB in total, not a number of entries. What changes in the code? Write the new put.
Compare with our answer
Each node gets a size field and the cache keeps totalBytes. On put, remove the old node's size if the key exists, add the new one, then evict from the tail while the total is over the limit; one large image may push out several small ones. Reject a single item larger than the whole cache, or it would evict everything and still not fit.
public synchronized void put(K key, V value, long bytes) {
if (bytes > maxBytes) throw new IllegalArgumentException("item larger than the cache");
Node<K, V> old = map.remove(key);
if (old != null) { unlink(old); totalBytes -= old.bytes; }
Node<K, V> n = new Node<>(key, value, bytes);
addFront(n); map.put(key, n); totalBytes += bytes;
while (totalBytes > maxBytes) { // may evict several entries
Node<K, V> lru = tail.prev;
unlink(lru); map.remove(lru.key); totalBytes -= lru.bytes;
}
}def put(self, key, value, nbytes: int):
if nbytes > self.max_bytes:
raise ValueError("item larger than the cache")
with self._lock:
old = self._map.pop(key, None)
if old is not None:
self._unlink(old)
self.total_bytes -= old.nbytes
n = _Node(key, value, nbytes)
self._add_front(n)
self._map[key] = n
self.total_bytes += nbytes
while self.total_bytes > self.max_bytes: # may evict several entries
lru = self._tail.prev
self._unlink(lru)
del self._map[lru.key]
self.total_bytes -= lru.nbytesA strong answer mentions: a size per node and a running total · subtracting the old size on update · a while loop, not a single eviction · rejecting an item bigger than the cache · the new node inserted first, so it is never its own victim unless it alone is too big.
- Structure: hash map key → node, plus a doubly linked list in order of use; front = most recent,
tail.prev= victim. - Node stores key, value,
prev,next(andexpiresAtfor TTL). The key is needed to delete the map entry on eviction. - Sentinels
headandtailremove end-of-list special cases. - get: lookup, unlink, add to front. put: update-and-move if present; else evict if full, then insert. All O(1) average.
- Threads:
getwrites the list, so one lock around every method; shard by key hash to scale. - TTL: lazy check on read with an injected clock; optional background sweep.
- Shortcuts:
LinkedHashMap(…, true)+removeEldestEntry;OrderedDict.move_to_end+popitem(last=False). Neither is thread-safe. - Production: Caffeine (W-TinyLFU), Redis sampled LRU (
allkeys-lru). - Extensions: byte capacity (evict while over), eviction listener, LFU, loading cache with one load per key.
- LFU in O(1): key → (value, freq), freq → ordered set of keys,
minFreq; evict the oldest key in theminFreqbucket; age counts. Striping: N independent LRUs chosen by key hash, LRU exact only per stripe.
1. Your LRU cache uses a ReentrantReadWriteLock: get takes the read lock and put the write lock. Under load, the list occasionally becomes corrupted. Why?
In an LRU cache a read changes the recency order, which is a write to the linked list. Several get calls hold the read lock together and interleave their pointer writes. Starvation is a real property of some read-write locks, but it delays work rather than corrupting the list.
2. A cache with capacity 3 receives put(a), put(b), put(c), get(a), put(d), get(b). What does the last call return?
After get(a) the order is a, c, b (most recent first), so b is at the tail when d arrives. Evicting a would be FIFO (first in, first out), which ignores the read.
3. Why does each list node store its key as well as its value?
Eviction starts from tail.prev, a node. To remove the matching map entry in O(1) you need its key. The list is never walked to find a key; that is the map's job.
4. An interviewer allows LinkedHashMap. A candidate creates new LinkedHashMap<>(16, 0.75f, false) and overrides removeEldestEntry. What is wrong?
The third argument is accessOrder. false keeps insertion order, which gives FIFO eviction, not LRU. removeEldestEntry is called after each put, and the initial capacity is only a sizing hint.
5. Your in-process LRU cache, guarded by one lock, is the hottest lock on a 48-core service. Which change helps most while keeping behaviour close to LRU?
Sharding divides contention by the number of shards. volatile makes single writes visible but cannot make a six-pointer update atomic. Unlocked get corrupts the list, because get writes it. Redis adds a network or socket hop (around 0.1–0.5 ms) to a call that took microseconds.
6. Entries have a 10-minute TTL checked lazily on get. Memory usage stays high overnight even though most entries expired hours ago. What explains it?
Lazy expiry only acts on access. Unread entries keep their memory until capacity pressure evicts them, which may not happen at night. A periodic sweep (active expiry), as Redis does, fixes it.
7. A test for TTL currently calls Thread.sleep(600) and is slow and sometimes flaky on busy CI machines. What is the best fix?
With an injected clock the test sets the time exactly (499 ms: present, 500 ms: expired) and runs in microseconds. Longer TTLs, retries and busy loops all keep the real-time dependency.
8. An O(1) LFU cache with capacity 2 holds a (used 3 times) and c (used twice, more recently than a). A new key d is put. What happens?
LFU evicts the oldest key in the minFreq bucket, and c has the lowest count. Recency only breaks ties within one frequency. Halving counts is periodic ageing, not a step of every put.
Score 60% or more and the lesson is marked complete.