Design an LRU / LFU Cache
"Design an LRU cache" is the rare interview prompt that sits right on the border between a data-structures question and a low-level design question. The data-structures half is the famous trick: a hash map that points into a doubly linked list gives you get and put in constant time. The design half is everything around the trick. Where does the eviction rule live? How do you swap LRU for LFU without rewriting the cache? How does time-based expiry interact with eviction? What happens when eight threads call get at once, given that get writes to the recency list?
Interviewers use this problem at every level. A junior candidate is expected to produce the map-plus-list structure and get the pointer surgery right. A senior candidate is expected to finish that in ten minutes, and then spend the rest of the time on policy as a pluggable strategy, on TTL, on locking granularity, and on the honest trade-offs between building it yourself and using LinkedHashMap. This page covers both, and it keeps every piece runnable.
If you haven't read The LLD Interview Framework, skim it first. This page follows the same ten steps.
1. Clarifying questions and requirements
The prompt is usually one line: "Design a cache with a fixed capacity that evicts the least recently used entry." Spend three or four minutes turning it into something you can build. These are the questions that actually change the design.
| Question | Why it matters | Answer we'll assume |
|---|---|---|
| Is capacity counted in entries or in bytes? | Bytes needs a weigher function and can evict several entries per insert | Entries (bytes is an extension) |
| Which eviction policy? Only LRU, or should LFU be possible too? | If more than one, the policy must be a seam | Both, and the caller picks |
Does get count as a "use"? Does put on an existing key? | Defines what "recently" and "frequently" mean | Both count |
| Do entries expire after a time-to-live? Per entry or cache-wide? | Adds a clock dependency and a second removal path | Optional per-entry TTL |
| Is it accessed from multiple threads? | get mutates order, so even reads need coordination | Yes |
Can values be null? | If yes, get can't use null to mean "miss" | No |
| What happens on a miss: return empty, or load the value? | A loading cache needs single-flight protection | Return empty (loading is an extension) |
| Do we need hit/miss statistics? | Cheap to add now, painful to retrofit | Yes, simple counters |
| Is the cache in one process, or shared across machines? | Distributed caching is a different, high-level question | One process |
Functional requirements
get(key)returns the value if present and not expired, and records the access. Otherwise it reports a miss.put(key, value)inserts or updates. If the cache is full and the key is new, exactly one entry is evicted first.put(key, value, ttl)does the same, and the entry stops being visible oncettlhas elapsed.remove(key)deletes an entry explicitly.- The eviction policy is chosen at construction: LRU, LFU, or a new one added later without editing the cache.
purgeExpired()sweeps out expired entries in bulk.stats()reports hits, misses and evictions.
Non-functional requirements
get,putandremoverun in O(1) time (amortized for hash map operations), for both LRU and LFU.- Memory is O(capacity). No unbounded side structures.
- Safe under concurrent access, with no lost updates and no corrupted linked lists.
- Testable without
sleep: time comes from an injected clock.
Out of scope
Persistence, cross-process sharing, write-through to a database, and size-aware (byte) capacity. Say these out loud so the interviewer knows you thought of them and chose not to build them.
2. Entities
Pick the nouns out of the requirements and decide which ones deserve to be classes.
| Entity | Responsibility | Notes |
|---|---|---|
Cache | The public API. Owns the key→entry map, the capacity check, TTL checks, stats and the lock | One class, deliberately small |
Entry | Value plus its expiry instant | Immutable. A put replaces it rather than mutating it |
EvictionPolicy | Tracks keys and answers "which key should go next?" | The Strategy interface |
LruPolicy | Recency order using a hash map into a doubly linked list | O(1) everything |
LfuPolicy | Frequency order using a linked list of frequency buckets | O(1) everything, including explicit removes |
Node / DoublyLinkedList | Intrusive list with sentinels, O(1) unlink | Shared by both policies |
Clock | Supplies "now" | Real clock in production, manual clock in tests |
Stats | Snapshot of counters | A value object |
The most important decision on that list is the split between Cache and EvictionPolicy. The cache knows values and time. The policy knows keys and order. Neither knows the other's concerns. That split is what lets LRU and LFU share every line of TTL, locking and stats code.
The policy never sees values, so it can't accidentally hold a stale one. The cache never sees list pointers, so it can't corrupt the order. Each has one reason to change.
3. Class diagram
classDiagram
class Cache {
-capacity: int
-data: Map of K to Entry
-policy: EvictionPolicy
-clock: Clock
-lock: ReentrantLock
-hits: long
-misses: long
-evictions: long
+get(key) V
+put(key, value, ttl)
+remove(key) boolean
+purgeExpired() int
+size() int
+stats() Stats
}
class Entry {
+value: V
+expiresAt: long
+isExpired(now) boolean
}
class EvictionPolicy {
<<interface>>
+recordInsert(key)
+recordAccess(key)
+recordRemove(key)
+evict() K
+size() int
}
class LruPolicy {
-nodes: Map of K to Node
-order: DoublyLinkedList
}
class LfuPolicy {
-nodes: Map of K to Node
-bucketOf: Map of K to Bucket
-head: Bucket
+frequency(key) int
}
class Bucket {
+freq: int
+keys: DoublyLinkedList
+prev: Bucket
+next: Bucket
}
class DoublyLinkedList {
-head: Node
-tail: Node
+addFirst(node)
+unlink(node)
+removeLast() Node
}
class Node {
+key: K
+prev: Node
+next: Node
}
class Clock {
<<interface>>
+nowMillis() long
}
class ManualClock {
+advance(millis)
}
Cache *-- Entry
Cache o-- EvictionPolicy
Cache --> Clock
EvictionPolicy <|.. LruPolicy
EvictionPolicy <|.. LfuPolicy
LruPolicy *-- DoublyLinkedList
LfuPolicy *-- Bucket
Bucket *-- DoublyLinkedList
DoublyLinkedList *-- Node
Clock <|.. ManualClock
Two details in the diagram are worth pointing out while you draw it:
Cacheaggregates the policy (hollow diamond). The policy is created outside and passed in, which is what makes it swappable.Buckethas its ownprevandnext. LFU keeps a linked list of frequency buckets, each holding a linked list of keys. That list-of-lists is the structure that makes LFU O(1) even when keys are removed out of order. Section 5 explains why the simplerminFreqtrick from LeetCode breaks here.
4. Key flows
get on a live entry
sequenceDiagram
participant C as Client
participant K as Cache
participant T as Clock
participant P as EvictionPolicy
C->>K: get("user:42")
K->>K: lock
K->>K: data.get("user:42") returns Entry
K->>T: nowMillis()
T-->>K: 1000
K->>K: entry not expired
K->>P: recordAccess("user:42")
P->>P: unlink node, add at head
K->>K: hits++, unlock
K-->>C: value
get on an expired entry (lazy expiry)
sequenceDiagram
participant C as Client
participant K as Cache
participant T as Clock
participant P as EvictionPolicy
C->>K: get("session:7")
K->>K: lock, data.get returns Entry
K->>T: nowMillis()
T-->>K: 5000, past expiresAt
K->>K: data.remove("session:7")
K->>P: recordRemove("session:7")
K->>K: misses++, unlock
K-->>C: miss
put of a new key into a full cache
sequenceDiagram
participant C as Client
participant K as Cache
participant P as EvictionPolicy
C->>K: put("c", 3)
K->>K: lock, key not present
K->>K: size equals capacity
K->>P: evict()
P->>P: removeLast from coldest list
P-->>K: victim "a"
K->>K: data.remove("a"), evictions++
K->>K: data.put("c", Entry)
K->>P: recordInsert("c")
K->>K: unlock
K-->>C: done
Notice the order in put: evict first, then insert. Under LRU the order happens not to matter, because a new key goes to the head and the victim comes from the tail. LFU is different: a brand-new key has frequency 1 and is the most likely victim. Inserting first and evicting second would make LFU evict the key you just added. Evicting first avoids that whole class of bug.
Entry lifecycle
stateDiagram-v2
[*] --> Live: put
Live --> Live: get or put refreshes order
Live --> Expired: clock passes expiresAt
Expired --> [*]: get or purgeExpired removes it
Expired --> Live: put on same key starts fresh
Live --> [*]: evicted by policy
Live --> [*]: remove
The Expired state is invisible to callers. An expired entry still occupies a slot until something touches it or a sweep runs. That's the cost of lazy expiry, and it's why purgeExpired() exists.
5. Patterns used, and the alternatives rejected
Strategy for eviction
The eviction rule is the part most likely to vary, so it goes behind an interface (Strategy). The interface has four "events" and one "decision":
recordInsert(key): a new key arrived.recordAccess(key): an existing key was read or overwritten.recordRemove(key): a key left for a reason the policy didn't choose (explicit remove or expiry).evict(): pick a victim, forget it, return it.
That event-shaped interface is the key insight. A policy is a little state machine fed by the cache. LRU reacts to recordAccess by moving a node to the head. LFU reacts by moving the node to the next frequency bucket. FIFO would ignore recordAccess entirely. The cache doesn't care.
Rejected: an enum PolicyType { LRU, LFU } with a switch inside the cache. This works for two policies and rots at three. Every method grows a branch, LRU's list and LFU's buckets both live in the cache as fields that are half-unused, and adding SLRU means editing the class that holds the lock. It also makes the cache untestable in isolation from its policies.
Rejected: inheritance (LruCache extends Cache, LfuCache extends Cache). Each subclass would have to override several hooks in the right order, and the base class would leak its locking discipline into them. Composition gives the same flexibility with a narrower contract.
Template-ish fixed algorithm in Cache
The cache's put is a fixed sequence: check TTL of the old entry, evict if full, insert, notify policy. It isn't a formal Template Method because nothing subclasses it, but the idea is similar. The skeleton is fixed and the variable step is delegated. Keeping the skeleton in one place is what lets us guarantee "exactly one eviction per insert into a full cache" for every policy.
Dependency injection for the clock
Clock is a one-method interface. In production it's System.currentTimeMillis (or a monotonic source). In tests it's a ManualClock that only moves when told to. That's the whole trick behind testing TTL without sleeping. See Designing for Testability.
Why a hand-rolled doubly linked list?
LRU needs three operations in O(1): move an arbitrary key to the front, remove an arbitrary key, and remove the oldest key. A hash map alone can't order. A plain list can order, but finding an arbitrary key is O(n). The combination works because the map stores a pointer to the list node, and a doubly linked node can unlink itself in O(1) given only itself (it knows both neighbours).
Sentinel head and tail nodes remove every null check from the pointer code. Without them, addFirst and unlink each need special cases for "list is empty" and "node is at an end", and those special cases are where interview bugs live.
Rejected: java.util.LinkedList or ArrayDeque. Neither exposes its nodes, so removing an arbitrary element is O(n). This is the most common wrong answer.
Rejected: a min-heap on last-access time. Updating an element's priority is O(log n), and you need an index map to find it at all.
LFU: why frequency buckets, and why a linked list of them
LFU must evict the key with the lowest access count, breaking ties by recency. A min-heap keyed on frequency gives O(log n) per access. The O(1) structure (described by Shah, Mitra and Matani in 2010) groups keys into buckets by frequency. Each bucket holds an LRU-ordered list of its keys, and accessing a key moves it from bucket f to bucket f + 1.
The popular LeetCode version stores buckets in a Map<Integer, List> plus a minFreq integer. On access, if the old bucket empties and it was the minimum, minFreq++. On insert, minFreq = 1. That's correct only when keys never leave except by eviction. Our cache removes keys in two other ways, explicit remove and TTL expiry. Remove the last key at frequency 3 when minFreq is 3 and the next lowest frequency might be 17. Finding it means scanning, which is no longer O(1).
Keeping the buckets themselves in a doubly linked list sorted by frequency fixes this. The lowest frequency is always head.next, a newly needed f + 1 bucket is spliced in right after bucket f, and an empty bucket unlinks itself. Every operation touches a constant number of pointers. This is a good thing to say out loud: "I'm choosing the list-of-buckets over minFreq because TTL and remove break the minFreq invariant."
The LinkedHashMap and OrderedDict shortcuts
Every mainstream language ships an ordered map that does LRU in a few lines.
// file: LinkedHashMapLru.java
import java.util.LinkedHashMap;
import java.util.Map;
/** accessOrder=true makes get() move the entry to the end; removeEldestEntry evicts. */
class LinkedHashMapLru<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
LinkedHashMapLru(int capacity) {
super(16, 0.75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
public static void main(String[] args) {
LinkedHashMapLru<String, Integer> lru = new LinkedHashMapLru<>(2);
lru.put("a", 1);
lru.put("b", 2);
lru.get("a");
lru.put("c", 3);
if (lru.containsKey("b") || !lru.containsKey("a")) throw new AssertionError("LRU order wrong");
System.out.println("LinkedHashMapLru ok: " + lru.keySet());
}
}
# file: ordered_dict_lru.py
from collections import OrderedDict
class OrderedDictLru:
def __init__(self, capacity: int) -> None:
self.capacity = capacity
self.data: OrderedDict = OrderedDict()
def get(self, key):
if key not in self.data:
return None
self.data.move_to_end(key)
return self.data[key]
def put(self, key, value) -> None:
self.data[key] = value
self.data.move_to_end(key)
if len(self.data) > self.capacity:
self.data.popitem(last=False)
if __name__ == "__main__":
lru = OrderedDictLru(2)
lru.put("a", 1)
lru.put("b", 2)
lru.get("a")
lru.put("c", 3)
assert lru.get("b") is None and lru.get("a") == 1
print("OrderedDictLru ok:", list(lru.data))
// file: map-lru.ts
// A JS Map iterates in insertion order, so delete + set moves a key to the end.
class MapLru<K, V> {
private readonly data = new Map<K, V>();
constructor(private readonly capacity: number) {}
get(key: K): V | undefined {
if (!this.data.has(key)) return undefined;
const value = this.data.get(key) as V;
this.data.delete(key);
this.data.set(key, value);
return value;
}
put(key: K, value: V): void {
this.data.delete(key);
this.data.set(key, value);
if (this.data.size > this.capacity) {
const oldest = this.data.keys().next().value as K;
this.data.delete(oldest);
}
}
keys(): K[] { return [...this.data.keys()]; }
}
const lru = new MapLru<string, number>(2);
lru.put("a", 1);
lru.put("b", 2);
lru.get("a");
lru.put("c", 3);
if (lru.get("b") !== undefined || lru.get("a") !== 1) throw new Error("LRU order wrong");
console.log("MapLru ok:", lru.keys());
In real code, use these. In an interview, ask first. Many interviewers will say "please don't use LinkedHashMap", for good reasons:
- The question is the data structure. If the library does the linking, the interviewer learns nothing about whether you can.
- They only do LRU. None of them give you LFU, so the shortcut doesn't survive the first follow-up.
- They hide the concurrency problem.
LinkedHashMapin access order is mutated byget. Wrapping it inCollections.synchronizedMapworks, but candidates often reach for a read-write lock and get it wrong, since every read is really a write. - They don't know about TTL. You'd bolt expiry on beside them anyway.
The right move is to mention the shortcut in one sentence ("in production I'd start with LinkedHashMap with accessOrder=true, or Caffeine"), and then build the real thing if asked.
6. Complete implementation
All three listings are complete and runnable. Each ends with a main that checks LRU order, LFU tie-breaking, LFU after explicit removal, TTL with a manual clock, and a concurrent stress test that verifies the map and the policy never disagree.
// file: CacheDemo.java
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicLong;
import java.util.concurrent.locks.ReentrantLock;
/** Source of "now". Injected so tests can move time by hand. */
interface Clock {
long nowMillis();
Clock SYSTEM = System::currentTimeMillis;
}
final class ManualClock implements Clock {
private final AtomicLong now = new AtomicLong();
public long nowMillis() { return now.get(); }
void advance(long millis) { now.addAndGet(millis); }
}
final class Node<K> {
final K key;
Node<K> prev, next;
Node(K key) { this.key = key; }
}
/** Sentinel-bounded doubly linked list. Head side = most recent. */
final class DoublyLinkedList<K> {
private final Node<K> head = new Node<>(null);
private final Node<K> tail = new Node<>(null);
private int size;
DoublyLinkedList() { head.next = tail; tail.prev = head; }
void addFirst(Node<K> n) {
n.prev = head;
n.next = head.next;
head.next.prev = n;
head.next = n;
size++;
}
void unlink(Node<K> n) {
n.prev.next = n.next;
n.next.prev = n.prev;
n.prev = n.next = null;
size--;
}
Node<K> removeLast() {
if (size == 0) return null;
Node<K> n = tail.prev;
unlink(n);
return n;
}
boolean isEmpty() { return size == 0; }
int size() { return size; }
}
/** Strategy: tracks keys and decides which one leaves when the cache is full. */
interface EvictionPolicy<K> {
void recordInsert(K key);
void recordAccess(K key);
void recordRemove(K key);
K evict();
int size();
}
final class LruPolicy<K> implements EvictionPolicy<K> {
private final Map<K, Node<K>> nodes = new HashMap<>();
private final DoublyLinkedList<K> order = new DoublyLinkedList<>();
public void recordInsert(K key) {
Node<K> n = new Node<>(key);
nodes.put(key, n);
order.addFirst(n);
}
public void recordAccess(K key) {
Node<K> n = nodes.get(key);
order.unlink(n);
order.addFirst(n);
}
public void recordRemove(K key) {
Node<K> n = nodes.remove(key);
if (n != null) order.unlink(n);
}
public K evict() {
Node<K> n = order.removeLast();
if (n == null) throw new IllegalStateException("nothing to evict");
nodes.remove(n.key);
return n.key;
}
public int size() { return nodes.size(); }
}
/** O(1) LFU: a sorted linked list of frequency buckets, each an LRU list of keys. */
final class LfuPolicy<K> implements EvictionPolicy<K> {
private static final class Bucket<K> {
final int freq;
final DoublyLinkedList<K> keys = new DoublyLinkedList<>();
Bucket<K> prev, next;
Bucket(int freq) { this.freq = freq; }
}
private final Map<K, Node<K>> nodes = new HashMap<>();
private final Map<K, Bucket<K>> bucketOf = new HashMap<>();
private final Bucket<K> head = new Bucket<>(0); // circular sentinel, head.next = lowest freq
LfuPolicy() { head.next = head; head.prev = head; }
private void insertAfter(Bucket<K> at, Bucket<K> b) {
b.prev = at;
b.next = at.next;
at.next.prev = b;
at.next = b;
}
private void unlinkIfEmpty(Bucket<K> b) {
if (!b.keys.isEmpty()) return;
b.prev.next = b.next;
b.next.prev = b.prev;
}
public void recordInsert(K key) {
Bucket<K> first = head.next;
if (first == head || first.freq != 1) {
first = new Bucket<>(1);
insertAfter(head, first);
}
Node<K> n = new Node<>(key);
first.keys.addFirst(n);
nodes.put(key, n);
bucketOf.put(key, first);
}
public void recordAccess(K key) {
Node<K> n = nodes.get(key);
Bucket<K> cur = bucketOf.get(key);
Bucket<K> next = cur.next;
if (next == head || next.freq != cur.freq + 1) {
next = new Bucket<>(cur.freq + 1);
insertAfter(cur, next);
}
cur.keys.unlink(n);
next.keys.addFirst(n);
bucketOf.put(key, next);
unlinkIfEmpty(cur);
}
public void recordRemove(K key) {
Node<K> n = nodes.remove(key);
if (n == null) return;
Bucket<K> b = bucketOf.remove(key);
b.keys.unlink(n);
unlinkIfEmpty(b);
}
public K evict() {
Bucket<K> lowest = head.next;
if (lowest == head) throw new IllegalStateException("nothing to evict");
Node<K> n = lowest.keys.removeLast(); // least recent among the least frequent
nodes.remove(n.key);
bucketOf.remove(n.key);
unlinkIfEmpty(lowest);
return n.key;
}
public int size() { return nodes.size(); }
int frequency(K key) {
Bucket<K> b = bucketOf.get(key);
return b == null ? 0 : b.freq;
}
}
record Stats(long hits, long misses, long evictions) {}
final class Cache<K, V> {
private record Entry<T>(T value, long expiresAt) {
boolean isExpired(long now) { return now >= expiresAt; }
}
private static final long NO_EXPIRY = Long.MAX_VALUE;
private final int capacity;
private final Map<K, Entry<V>> data = new HashMap<>();
private final EvictionPolicy<K> policy;
private final Clock clock;
private final ReentrantLock lock = new ReentrantLock();
private long hits, misses, evictions;
Cache(int capacity, EvictionPolicy<K> policy, Clock clock) {
if (capacity < 1) throw new IllegalArgumentException("capacity must be >= 1");
this.capacity = capacity;
this.policy = Objects.requireNonNull(policy);
this.clock = Objects.requireNonNull(clock);
}
static <K, V> Cache<K, V> lru(int capacity) { return new Cache<>(capacity, new LruPolicy<>(), Clock.SYSTEM); }
static <K, V> Cache<K, V> lfu(int capacity) { return new Cache<>(capacity, new LfuPolicy<>(), Clock.SYSTEM); }
/** Returns the value, or null on a miss (values are never null). */
V get(K key) {
lock.lock();
try {
Entry<V> e = data.get(key);
if (e == null || e.isExpired(clock.nowMillis())) {
if (e != null) removeEntry(key); // lazy expiry
misses++;
return null;
}
policy.recordAccess(key);
hits++;
return e.value();
} finally {
lock.unlock();
}
}
void put(K key, V value) { put(key, value, 0); }
/** ttlMillis == 0 means the entry never expires. */
void put(K key, V value, long ttlMillis) {
Objects.requireNonNull(key, "key");
Objects.requireNonNull(value, "value");
if (ttlMillis < 0) throw new IllegalArgumentException("ttl must be >= 0");
lock.lock();
try {
long now = clock.nowMillis();
long expiresAt = ttlMillis == 0 ? NO_EXPIRY : now + ttlMillis;
Entry<V> old = data.get(key);
if (old != null && !old.isExpired(now)) {
data.put(key, new Entry<>(value, expiresAt));
policy.recordAccess(key);
return;
}
if (old != null) removeEntry(key); // expired: treat as a brand-new key
if (data.size() == capacity) evictOne();
data.put(key, new Entry<>(value, expiresAt));
policy.recordInsert(key);
} finally {
lock.unlock();
}
}
boolean remove(K key) {
lock.lock();
try { return removeEntry(key); } finally { lock.unlock(); }
}
/** Active expiry: O(n) sweep, meant for a background timer. */
int purgeExpired() {
lock.lock();
try {
long now = clock.nowMillis();
List<K> dead = new ArrayList<>();
for (Map.Entry<K, Entry<V>> e : data.entrySet()) {
if (e.getValue().isExpired(now)) dead.add(e.getKey());
}
dead.forEach(this::removeEntry);
return dead.size();
} finally {
lock.unlock();
}
}
int size() {
lock.lock();
try { return data.size(); } finally { lock.unlock(); }
}
Stats stats() {
lock.lock();
try { return new Stats(hits, misses, evictions); } finally { lock.unlock(); }
}
void checkInvariants() {
lock.lock();
try {
if (data.size() != policy.size()) throw new IllegalStateException("map and policy disagree");
if (data.size() > capacity) throw new IllegalStateException("over capacity");
} finally {
lock.unlock();
}
}
private void evictOne() {
K victim = policy.evict();
data.remove(victim);
evictions++;
}
private boolean removeEntry(K key) {
if (data.remove(key) == null) return false;
policy.recordRemove(key);
return true;
}
}
class CacheDemo {
static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }
static void eq(Object expected, Object actual) {
if (!Objects.equals(expected, actual)) throw new AssertionError("expected " + expected + " got " + actual);
}
public static void main(String[] args) throws Exception {
ManualClock clock = new ManualClock();
// LRU: reading "a" protects it, so "b" is evicted.
Cache<String, Integer> lru = new Cache<>(2, new LruPolicy<>(), clock);
lru.put("a", 1);
lru.put("b", 2);
lru.get("a");
lru.put("c", 3);
eq(null, lru.get("b"));
eq(1, lru.get("a"));
eq(3, lru.get("c"));
// LFU: lowest frequency goes, ties broken by recency.
Cache<String, Integer> lfu = new Cache<>(2, new LfuPolicy<>(), clock);
lfu.put("x", 1);
lfu.put("y", 2);
lfu.put("z", 3); // x and y both freq 1, x is older
eq(null, lfu.get("x"));
lfu.get("y");
lfu.get("y"); // y freq 3, z freq 1
lfu.put("w", 4); // evicts z
eq(null, lfu.get("z"));
eq(2, lfu.get("y"));
// LFU after an explicit remove of the only lowest-frequency key.
LfuPolicy<String> p = new LfuPolicy<>();
p.recordInsert("a");
p.recordInsert("b");
p.recordInsert("c");
p.recordAccess("b");
p.recordAccess("c");
p.recordAccess("c");
p.recordRemove("a");
eq(2, p.frequency("b"));
eq("b", p.evict());
eq("c", p.evict());
// TTL with a manual clock: visible until now >= expiresAt.
Cache<String, String> ttl = new Cache<>(10, new LruPolicy<>(), clock);
ttl.put("session", "s1", 1000);
clock.advance(999);
eq("s1", ttl.get("session"));
clock.advance(1);
eq(null, ttl.get("session"));
for (int i = 0; i < 3; i++) ttl.put("t" + i, "v", 100);
ttl.put("forever", "v");
clock.advance(100);
eq(3, ttl.purgeExpired());
eq(1, ttl.size());
concurrentStress(new LruPolicy<>());
concurrentStress(new LfuPolicy<>());
System.out.println("CacheDemo: all checks passed");
}
static void concurrentStress(EvictionPolicy<Integer> policy) throws Exception {
Cache<Integer, Integer> cache = new Cache<>(64, policy, Clock.SYSTEM);
int threads = 8, ops = 20_000;
AtomicLong gets = new AtomicLong();
ExecutorService pool = Executors.newFixedThreadPool(threads);
CountDownLatch start = new CountDownLatch(1);
List<Future<Object>> futures = new ArrayList<>();
for (int t = 0; t < threads; t++) {
final int seed = t;
futures.add(pool.submit(() -> {
Random r = new Random(seed);
start.await();
for (int i = 0; i < ops; i++) {
int k = r.nextInt(200);
switch (r.nextInt(3)) {
case 0 -> cache.put(k, k * 10);
case 1 -> {
gets.incrementAndGet();
Integer v = cache.get(k);
if (v != null && v != k * 10) throw new AssertionError("wrong value for " + k);
}
default -> cache.remove(k);
}
}
return null;
}));
}
start.countDown();
for (Future<Object> f : futures) f.get();
pool.shutdown();
cache.checkInvariants();
Stats s = cache.stats();
check(s.hits() + s.misses() == gets.get(), "lost stat updates");
}
}
# file: cache.py
"""Bounded cache with pluggable eviction (LRU, LFU), per-entry TTL and one lock."""
from __future__ import annotations
import random
import threading
import time
from abc import ABC, abstractmethod
from dataclasses import dataclass
from typing import Callable, Dict, Generic, Hashable, List, Optional, Tuple, TypeVar
K = TypeVar("K", bound=Hashable)
V = TypeVar("V")
Clock = Callable[[], float] # returns seconds
class ManualClock:
"""A clock that only moves when a test tells it to."""
def __init__(self, start: float = 0.0) -> None:
self._now = start
def __call__(self) -> float:
return self._now
def advance(self, seconds: float) -> None:
self._now += seconds
class Node(Generic[K]):
__slots__ = ("key", "prev", "next")
def __init__(self, key: Optional[K]) -> None:
self.key = key
self.prev: Optional[Node[K]] = None
self.next: Optional[Node[K]] = None
class DoublyLinkedList(Generic[K]):
"""Sentinel-bounded list. The head side holds the most recent node."""
def __init__(self) -> None:
self.head: Node[K] = Node(None)
self.tail: Node[K] = Node(None)
self.head.next, self.tail.prev = self.tail, self.head
self.size = 0
def add_first(self, n: Node[K]) -> None:
first = self.head.next
assert first is not None
n.prev, n.next = self.head, first
first.prev = n
self.head.next = n
self.size += 1
def unlink(self, n: Node[K]) -> None:
assert n.prev is not None and n.next is not None
n.prev.next, n.next.prev = n.next, n.prev
n.prev = n.next = None
self.size -= 1
def remove_last(self) -> Optional[Node[K]]:
if self.size == 0:
return None
last = self.tail.prev
assert last is not None
self.unlink(last)
return last
class EvictionPolicy(ABC, Generic[K]):
@abstractmethod
def record_insert(self, key: K) -> None: ...
@abstractmethod
def record_access(self, key: K) -> None: ...
@abstractmethod
def record_remove(self, key: K) -> None: ...
@abstractmethod
def evict(self) -> K: ...
@abstractmethod
def __len__(self) -> int: ...
class LruPolicy(EvictionPolicy[K]):
def __init__(self) -> None:
self._nodes: Dict[K, Node[K]] = {}
self._order: DoublyLinkedList[K] = DoublyLinkedList()
def record_insert(self, key: K) -> None:
n: Node[K] = Node(key)
self._nodes[key] = n
self._order.add_first(n)
def record_access(self, key: K) -> None:
n = self._nodes[key]
self._order.unlink(n)
self._order.add_first(n)
def record_remove(self, key: K) -> None:
n = self._nodes.pop(key, None)
if n is not None:
self._order.unlink(n)
def evict(self) -> K:
n = self._order.remove_last()
if n is None:
raise LookupError("nothing to evict")
del self._nodes[n.key] # type: ignore[arg-type]
return n.key # type: ignore[return-value]
def __len__(self) -> int:
return len(self._nodes)
class _Bucket(Generic[K]):
__slots__ = ("freq", "keys", "prev", "next")
def __init__(self, freq: int) -> None:
self.freq = freq
self.keys: DoublyLinkedList[K] = DoublyLinkedList()
self.prev: _Bucket[K] = self
self.next: _Bucket[K] = self
class LfuPolicy(EvictionPolicy[K]):
"""O(1) LFU: buckets sorted by frequency in a circular list, each an LRU list."""
def __init__(self) -> None:
self._nodes: Dict[K, Node[K]] = {}
self._bucket_of: Dict[K, _Bucket[K]] = {}
self._head: _Bucket[K] = _Bucket(0) # sentinel, head.next is the lowest frequency
@staticmethod
def _insert_after(at: _Bucket[K], b: _Bucket[K]) -> None:
b.prev, b.next = at, at.next
at.next.prev = b
at.next = b
@staticmethod
def _unlink_if_empty(b: _Bucket[K]) -> None:
if b.keys.size == 0:
b.prev.next, b.next.prev = b.next, b.prev
def record_insert(self, key: K) -> None:
first = self._head.next
if first is self._head or first.freq != 1:
first = _Bucket(1)
self._insert_after(self._head, first)
n: Node[K] = Node(key)
first.keys.add_first(n)
self._nodes[key] = n
self._bucket_of[key] = first
def record_access(self, key: K) -> None:
n, cur = self._nodes[key], self._bucket_of[key]
nxt = cur.next
if nxt is self._head or nxt.freq != cur.freq + 1:
nxt = _Bucket(cur.freq + 1)
self._insert_after(cur, nxt)
cur.keys.unlink(n)
nxt.keys.add_first(n)
self._bucket_of[key] = nxt
self._unlink_if_empty(cur)
def record_remove(self, key: K) -> None:
n = self._nodes.pop(key, None)
if n is None:
return
b = self._bucket_of.pop(key)
b.keys.unlink(n)
self._unlink_if_empty(b)
def evict(self) -> K:
lowest = self._head.next
if lowest is self._head:
raise LookupError("nothing to evict")
n = lowest.keys.remove_last()
assert n is not None
key: K = n.key # type: ignore[assignment]
del self._nodes[key]
del self._bucket_of[key]
self._unlink_if_empty(lowest)
return key
def frequency(self, key: K) -> int:
b = self._bucket_of.get(key)
return 0 if b is None else b.freq
def __len__(self) -> int:
return len(self._nodes)
@dataclass(frozen=True)
class _Entry(Generic[V]):
value: V
expires_at: float # float("inf") when there is no TTL
def is_expired(self, now: float) -> bool:
return now >= self.expires_at
@dataclass(frozen=True)
class Stats:
hits: int
misses: int
evictions: int
class Cache(Generic[K, V]):
def __init__(self, capacity: int, policy: EvictionPolicy[K], clock: Clock = time.monotonic) -> None:
if capacity < 1:
raise ValueError("capacity must be >= 1")
self._capacity = capacity
self._data: Dict[K, _Entry[V]] = {}
self._policy = policy
self._clock = clock
self._lock = threading.Lock()
self._hits = self._misses = self._evictions = 0
def get(self, key: K) -> Optional[V]:
with self._lock:
e = self._data.get(key)
if e is None or e.is_expired(self._clock()):
if e is not None:
self._remove_entry(key) # lazy expiry
self._misses += 1
return None
self._policy.record_access(key)
self._hits += 1
return e.value
def put(self, key: K, value: V, ttl: Optional[float] = None) -> None:
"""ttl is in seconds; None means the entry never expires."""
if value is None:
raise ValueError("values may not be None")
if ttl is not None and ttl <= 0:
raise ValueError("ttl must be positive")
with self._lock:
now = self._clock()
expires_at = float("inf") if ttl is None else now + ttl
old = self._data.get(key)
if old is not None and not old.is_expired(now):
self._data[key] = _Entry(value, expires_at)
self._policy.record_access(key)
return
if old is not None:
self._remove_entry(key) # expired: start over as a new key
if len(self._data) == self._capacity:
self._evict_one()
self._data[key] = _Entry(value, expires_at)
self._policy.record_insert(key)
def remove(self, key: K) -> bool:
with self._lock:
return self._remove_entry(key)
def purge_expired(self) -> int:
with self._lock:
now = self._clock()
dead = [k for k, e in self._data.items() if e.is_expired(now)]
for k in dead:
self._remove_entry(k)
return len(dead)
def __len__(self) -> int:
with self._lock:
return len(self._data)
def stats(self) -> Stats:
with self._lock:
return Stats(self._hits, self._misses, self._evictions)
def check_invariants(self) -> None:
with self._lock:
if len(self._data) != len(self._policy):
raise AssertionError("map and policy disagree")
if len(self._data) > self._capacity:
raise AssertionError("over capacity")
# Internal helpers: the caller must hold the lock.
def _evict_one(self) -> Tuple[K, V]:
victim = self._policy.evict()
entry = self._data.pop(victim)
self._evictions += 1
return victim, entry.value
def _remove_entry(self, key: K) -> bool:
if self._data.pop(key, None) is None:
return False
self._policy.record_remove(key)
return True
def _stress(policy: EvictionPolicy[int]) -> None:
cache: Cache[int, int] = Cache(64, policy)
gets = [0] * 8
start = threading.Barrier(8)
def worker(seed: int) -> None:
r = random.Random(seed)
start.wait()
for _ in range(5_000):
k = r.randrange(200)
op = r.randrange(3)
if op == 0:
cache.put(k, k * 10)
elif op == 1:
gets[seed] += 1
v = cache.get(k)
assert v is None or v == k * 10, "wrong value"
else:
cache.remove(k)
threads = [threading.Thread(target=worker, args=(i,)) for i in range(8)]
for t in threads:
t.start()
for t in threads:
t.join()
cache.check_invariants()
s = cache.stats()
assert s.hits + s.misses == sum(gets), "lost stat updates"
def main() -> None:
clock = ManualClock()
lru: Cache[str, int] = Cache(2, LruPolicy(), clock)
lru.put("a", 1)
lru.put("b", 2)
lru.get("a")
lru.put("c", 3)
assert lru.get("b") is None and lru.get("a") == 1 and lru.get("c") == 3
lfu: Cache[str, int] = Cache(2, LfuPolicy(), clock)
lfu.put("x", 1)
lfu.put("y", 2)
lfu.put("z", 3) # x and y tie at freq 1, x is older
assert lfu.get("x") is None
lfu.get("y")
lfu.get("y")
lfu.put("w", 4) # z has freq 1, evicted
assert lfu.get("z") is None and lfu.get("y") == 2
p: LfuPolicy[str] = LfuPolicy()
for k in "abc":
p.record_insert(k)
p.record_access("b")
p.record_access("c")
p.record_access("c")
p.record_remove("a") # the only freq-1 key leaves
assert p.frequency("b") == 2
assert p.evict() == "b" and p.evict() == "c"
ttl: Cache[str, str] = Cache(10, LruPolicy(), clock)
ttl.put("session", "s1", ttl=1.0)
clock.advance(0.999)
assert ttl.get("session") == "s1"
clock.advance(0.001)
assert ttl.get("session") is None
for i in range(3):
ttl.put(f"t{i}", "v", ttl=0.1)
ttl.put("forever", "v")
clock.advance(0.1)
assert ttl.purge_expired() == 3 and len(ttl) == 1
_stress(LruPolicy())
_stress(LfuPolicy())
print("cache.py: all checks passed")
if __name__ == "__main__":
main()
// file: cache.ts
// Bounded cache with pluggable eviction (LRU, LFU) and per-entry TTL.
// Run directly: npx tsx cache.ts
export type Clock = () => number; // milliseconds
export class ManualClock {
private now = 0;
readonly read: Clock = () => this.now;
advance(ms: number): void { this.now += ms; }
}
export class ListNode<K> {
prev: ListNode<K> | null = null;
next: ListNode<K> | null = null;
constructor(readonly key: K) {}
}
export class DoublyLinkedList<K> {
// Sentinels never expose their key, so a typed placeholder is safe.
private readonly head = new ListNode<K>(undefined as unknown as K);
private readonly tail = new ListNode<K>(undefined as unknown as K);
size = 0;
constructor() {
this.head.next = this.tail;
this.tail.prev = this.head;
}
addFirst(n: ListNode<K>): void {
const first = this.head.next!;
n.prev = this.head;
n.next = first;
first.prev = n;
this.head.next = n;
this.size++;
}
unlink(n: ListNode<K>): void {
n.prev!.next = n.next;
n.next!.prev = n.prev;
n.prev = n.next = null;
this.size--;
}
removeLast(): ListNode<K> | null {
if (this.size === 0) return null;
const last = this.tail.prev!;
this.unlink(last);
return last;
}
}
export interface EvictionPolicy<K> {
recordInsert(key: K): void;
recordAccess(key: K): void;
recordRemove(key: K): void;
evict(): K;
size(): number;
}
export class LruPolicy<K> implements EvictionPolicy<K> {
private readonly nodes = new Map<K, ListNode<K>>();
private readonly order = new DoublyLinkedList<K>();
recordInsert(key: K): void {
const n = new ListNode(key);
this.nodes.set(key, n);
this.order.addFirst(n);
}
recordAccess(key: K): void {
const n = this.nodes.get(key)!;
this.order.unlink(n);
this.order.addFirst(n);
}
recordRemove(key: K): void {
const n = this.nodes.get(key);
if (!n) return;
this.nodes.delete(key);
this.order.unlink(n);
}
evict(): K {
const n = this.order.removeLast();
if (!n) throw new Error("nothing to evict");
this.nodes.delete(n.key);
return n.key;
}
size(): number { return this.nodes.size; }
}
class Bucket<K> {
readonly keys = new DoublyLinkedList<K>();
prev: Bucket<K> = this;
next: Bucket<K> = this;
constructor(readonly freq: number) {}
}
export class LfuPolicy<K> implements EvictionPolicy<K> {
private readonly nodes = new Map<K, ListNode<K>>();
private readonly bucketOf = new Map<K, Bucket<K>>();
private readonly head = new Bucket<K>(0); // sentinel, head.next = lowest frequency
private insertAfter(at: Bucket<K>, b: Bucket<K>): void {
b.prev = at;
b.next = at.next;
at.next.prev = b;
at.next = b;
}
private unlinkIfEmpty(b: Bucket<K>): void {
if (b.keys.size > 0) return;
b.prev.next = b.next;
b.next.prev = b.prev;
}
recordInsert(key: K): void {
let first = this.head.next;
if (first === this.head || first.freq !== 1) {
first = new Bucket<K>(1);
this.insertAfter(this.head, first);
}
const n = new ListNode(key);
first.keys.addFirst(n);
this.nodes.set(key, n);
this.bucketOf.set(key, first);
}
recordAccess(key: K): void {
const n = this.nodes.get(key)!;
const cur = this.bucketOf.get(key)!;
let next = cur.next;
if (next === this.head || next.freq !== cur.freq + 1) {
next = new Bucket<K>(cur.freq + 1);
this.insertAfter(cur, next);
}
cur.keys.unlink(n);
next.keys.addFirst(n);
this.bucketOf.set(key, next);
this.unlinkIfEmpty(cur);
}
recordRemove(key: K): void {
const n = this.nodes.get(key);
if (!n) return;
const b = this.bucketOf.get(key)!;
this.nodes.delete(key);
this.bucketOf.delete(key);
b.keys.unlink(n);
this.unlinkIfEmpty(b);
}
evict(): K {
const lowest = this.head.next;
if (lowest === this.head) throw new Error("nothing to evict");
const n = lowest.keys.removeLast()!;
this.nodes.delete(n.key);
this.bucketOf.delete(n.key);
this.unlinkIfEmpty(lowest);
return n.key;
}
frequency(key: K): number { return this.bucketOf.get(key)?.freq ?? 0; }
size(): number { return this.nodes.size; }
}
interface Entry<V> { readonly value: V; readonly expiresAt: number; }
export interface Stats { hits: number; misses: number; evictions: number; }
export class Cache<K, V> {
private readonly data = new Map<K, Entry<V>>();
private hits = 0;
private misses = 0;
private evictions = 0;
constructor(
private readonly capacity: number,
private readonly policy: EvictionPolicy<K>,
private readonly clock: Clock = Date.now,
) {
if (!Number.isInteger(capacity) || capacity < 1) throw new RangeError("capacity must be >= 1");
}
get(key: K): V | undefined {
const e = this.data.get(key);
if (!e || this.clock() >= e.expiresAt) {
if (e) this.removeEntry(key); // lazy expiry
this.misses++;
return undefined;
}
this.policy.recordAccess(key);
this.hits++;
return e.value;
}
/** ttlMs omitted means the entry never expires. */
put(key: K, value: V, ttlMs?: number): void {
if (value === undefined) throw new TypeError("values may not be undefined");
if (ttlMs !== undefined && !(ttlMs > 0)) throw new RangeError("ttl must be positive");
const now = this.clock();
const expiresAt = ttlMs === undefined ? Infinity : now + ttlMs;
const old = this.data.get(key);
if (old && now < old.expiresAt) {
this.data.set(key, { value, expiresAt });
this.policy.recordAccess(key);
return;
}
if (old) this.removeEntry(key); // expired: start over as a new key
if (this.data.size === this.capacity) this.evictOne();
this.data.set(key, { value, expiresAt });
this.policy.recordInsert(key);
}
remove(key: K): boolean { return this.removeEntry(key); }
purgeExpired(): number {
const now = this.clock();
const dead = [...this.data].filter(([, e]) => now >= e.expiresAt).map(([k]) => k);
dead.forEach((k) => this.removeEntry(k));
return dead.length;
}
get size(): number { return this.data.size; }
stats(): Stats { return { hits: this.hits, misses: this.misses, evictions: this.evictions }; }
checkInvariants(): void {
if (this.data.size !== this.policy.size()) throw new Error("map and policy disagree");
if (this.data.size > this.capacity) throw new Error("over capacity");
}
protected evictOne(): [K, V] {
const victim = this.policy.evict();
const entry = this.data.get(victim)!;
this.data.delete(victim);
this.evictions++;
return [victim, entry.value];
}
private removeEntry(key: K): boolean {
if (!this.data.delete(key)) return false;
this.policy.recordRemove(key);
return true;
}
}
function assert(cond: unknown, msg: string): asserts cond {
if (!cond) throw new Error(msg);
}
async function stress(policy: EvictionPolicy<number>): Promise<void> {
const cache = new Cache<number, number>(64, policy);
let gets = 0;
const worker = async (seed: number): Promise<void> => {
let x = seed + 1;
const rand = (n: number): number => { x = (x * 1103515245 + 12345) % 2147483648; return x % n; };
for (let i = 0; i < 5_000; i++) {
if (i % 100 === 0) await Promise.resolve(); // yield so workers interleave
const k = rand(200);
const op = rand(3);
if (op === 0) cache.put(k, k * 10);
else if (op === 1) {
gets++;
const v = cache.get(k);
assert(v === undefined || v === k * 10, "wrong value");
} else cache.remove(k);
}
};
await Promise.all(Array.from({ length: 8 }, (_, i) => worker(i)));
cache.checkInvariants();
const s = cache.stats();
assert(s.hits + s.misses === gets, "lost stat updates");
}
async function main(): Promise<void> {
const clock = new ManualClock();
const lru = new Cache<string, number>(2, new LruPolicy(), clock.read);
lru.put("a", 1);
lru.put("b", 2);
lru.get("a");
lru.put("c", 3);
assert(lru.get("b") === undefined && lru.get("a") === 1 && lru.get("c") === 3, "LRU order");
const lfu = new Cache<string, number>(2, new LfuPolicy(), clock.read);
lfu.put("x", 1);
lfu.put("y", 2);
lfu.put("z", 3);
assert(lfu.get("x") === undefined, "LFU tie goes to the older key");
lfu.get("y");
lfu.get("y");
lfu.put("w", 4);
assert(lfu.get("z") === undefined && lfu.get("y") === 2, "LFU frequency");
const p = new LfuPolicy<string>();
for (const k of ["a", "b", "c"]) p.recordInsert(k);
p.recordAccess("b");
p.recordAccess("c");
p.recordAccess("c");
p.recordRemove("a");
assert(p.frequency("b") === 2, "frequency");
assert(p.evict() === "b" && p.evict() === "c", "LFU after remove");
const ttl = new Cache<string, string>(10, new LruPolicy(), clock.read);
ttl.put("session", "s1", 1000);
clock.advance(999);
assert(ttl.get("session") === "s1", "still live");
clock.advance(1);
assert(ttl.get("session") === undefined, "expired at the boundary");
for (let i = 0; i < 3; i++) ttl.put(`t${i}`, "v", 100);
ttl.put("forever", "v");
clock.advance(100);
assert(ttl.purgeExpired() === 3 && ttl.size === 1, "purge");
await stress(new LruPolicy());
await stress(new LfuPolicy());
console.log("cache.ts: all checks passed");
}
if (require.main === module) {
main().catch((e) => { console.error(e); process.exit(1); });
}
Walking through the code
A few lines carry most of the design, and they're worth narrating in an interview.
put on an existing key counts as an access. Overwriting user:42 with a fresh value means somebody cares about it, so LRU moves it to the head and LFU bumps its frequency. That matches LeetCode's LFU problem and most production caches. A design could reasonably choose otherwise (for instance, a write-heavy key that nobody reads arguably shouldn't be protected). Whatever you pick, say it.
put on an expired key is a fresh insert. If we treated it as an update, an LFU entry that expired after ten thousand hits would come back with ten thousand hits of credit it didn't earn this time. Removing and reinserting resets it to frequency 1.
Eviction happens before insertion. This was covered in the sequence diagram. It's the reason LFU doesn't evict the newcomer.
get returns null / None / undefined for a miss, and values may not be null. That's a deliberate API contract. If nulls were allowed, get would need to return Optional<V> or a (found, value) pair. Both are fine. Mixing them is not.
size() can include expired entries. Lazy expiry means an expired entry still sits in the map until something touches it. If the interviewer wants size() to be exact, it costs a sweep. Most real caches document size() as approximate for exactly this reason.
7. Concurrency
What's shared
Everything: the key map, the policy's internal list or buckets, and the stat counters. The crucial observation is that get is a write. It moves a node in the LRU list or between LFU buckets. A read-write lock where get takes the read lock is broken: two readers would both unlink the same node and splice it in at the head, and the list would end up with a cycle or a lost node. This is the most common concurrency mistake on this problem.
Option 1: one lock around everything (what the listings do)
A single ReentrantLock (Java) or threading.Lock (Python) wraps every public method. Each operation is a handful of pointer writes, so the critical section is a few hundred nanoseconds. That's simple and obviously correct, and it's fine up to a fairly high request rate. Its ceiling is that every thread serializes through one lock, so throughput stops growing with core count.
Why not synchronized? It would work equally well here. ReentrantLock was chosen because it supports tryLock with a timeout, which some interviewers ask about ("what if a caller can't wait?"). Either is a defensible answer.
Why not a ConcurrentHashMap and no lock? Because the map and the policy must change together. A concurrent map makes each map operation atomic, but "remove from map and unlink from list" is two operations, and another thread can observe the state between them. The checkInvariants() call in the stress test exists to catch exactly that.
Option 2: lock striping (segmented cache)
Split the cache into N independent segments, each a full Cache with its own lock and capacity / N slots. A key always hashes to the same segment. Threads that touch different segments don't contend. This is how ConcurrentHashMap worked before Java 8, and how Guava's CacheBuilder still works.
// file: SegmentedCacheDemo.java
import java.util.*;
import java.util.concurrent.*;
import java.util.function.Supplier;
/** N independent caches, each with its own lock. A key always lands in the same segment. */
final class SegmentedCache<K, V> {
private final List<Cache<K, V>> segments = new ArrayList<>();
SegmentedCache(int capacity, int segmentCount, Supplier<EvictionPolicy<K>> policies, Clock clock) {
if (segmentCount < 1 || capacity < segmentCount) throw new IllegalArgumentException("bad sizing");
int base = capacity / segmentCount, extra = capacity % segmentCount;
for (int i = 0; i < segmentCount; i++) {
segments.add(new Cache<>(base + (i < extra ? 1 : 0), policies.get(), clock));
}
}
private Cache<K, V> segmentFor(K key) {
int h = key.hashCode();
h ^= (h >>> 16); // spread high bits so similar keys don't pile into one segment
return segments.get(Math.floorMod(h, segments.size()));
}
V get(K key) { return segmentFor(key).get(key); }
void put(K key, V value) { segmentFor(key).put(key, value); }
boolean remove(K key) { return segmentFor(key).remove(key); }
int size() { return segments.stream().mapToInt(Cache::size).sum(); }
void checkInvariants() { segments.forEach(Cache::checkInvariants); }
}
class SegmentedCacheDemo {
public static void main(String[] args) throws Exception {
SegmentedCache<Integer, Integer> cache =
new SegmentedCache<>(1000, 16, LruPolicy::new, Clock.SYSTEM);
ExecutorService pool = Executors.newFixedThreadPool(16);
List<Future<Object>> futures = new ArrayList<>();
for (int t = 0; t < 16; t++) {
final int seed = t;
futures.add(pool.submit(() -> {
Random r = new Random(seed);
for (int i = 0; i < 50_000; i++) {
int k = r.nextInt(5_000);
if (r.nextBoolean()) cache.put(k, -k);
else {
Integer v = cache.get(k);
if (v != null && v != -k) throw new AssertionError("wrong value");
}
}
return null;
}));
}
for (Future<Object> f : futures) f.get();
pool.shutdown();
cache.checkInvariants();
if (cache.size() > 1000) throw new AssertionError("over capacity");
System.out.println("SegmentedCacheDemo ok, size=" + cache.size());
}
}
The trade-off is precision. Eviction is now per segment: a segment can evict its least recently used key while another segment holds keys that are older globally. With a decent hash and enough keys this barely matters, but it means the cache is "approximately LRU", and you should say so. A hot segment (many popular keys hashing together) also gets less than its fair share of capacity.
Option 3: what production caches actually do
Caffeine (Java) avoids locking on reads entirely. A get reads a ConcurrentHashMap and appends a "this key was read" event to a striped, lossy ring buffer. A single thread drains those buffers in batches under a lock and replays them against the policy. Dropping a few read events under extreme load only makes the recency order slightly less exact, which is harmless. It's worth one sentence in an interview to show you know the frontier, but don't try to build it in 45 minutes.
Python and TypeScript
In CPython the GIL makes individual bytecodes atomic, but not your multi-step put. A thread can be preempted between self._data[key] = ... and self._policy.record_insert(key). The lock is still required, and the Python stress test checks the invariant. (Free-threaded Python 3.13+ removes the GIL, which makes the lock even more necessary.)
In TypeScript on Node, each synchronous method runs to completion without interruption, so the cache needs no lock. The TS stress test interleaves eight async workers with await and verifies nothing breaks. The danger in JavaScript appears when an operation spans an await, for example "on a miss, fetch from the database, then put". Two callers can both miss and both fetch. That's the single-flight problem, solved in Extension A below.
8. Extensions: "the interviewer adds X"
Extension A: "On a miss, load the value, and don't let 100 threads hit the database at once"
This is the cache stampede (or thundering herd) problem. The fix is single-flight: the first thread to miss a key registers a future for it, and later threads that miss the same key wait on that future instead of calling the loader. It's a wrapper (Decorator-shaped) around the existing cache, with no changes inside it.
// file: LoadingCacheDemo.java
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.Function;
/** Concurrent misses for one key trigger exactly one call to the loader. */
final class LoadingCache<K, V> {
private final Cache<K, V> cache;
private final Function<K, V> loader;
private final ConcurrentHashMap<K, CompletableFuture<V>> inFlight = new ConcurrentHashMap<>();
LoadingCache(Cache<K, V> cache, Function<K, V> loader) {
this.cache = cache;
this.loader = loader;
}
V get(K key) {
V cached = cache.get(key);
if (cached != null) return cached;
CompletableFuture<V> mine = new CompletableFuture<>();
CompletableFuture<V> existing = inFlight.putIfAbsent(key, mine);
if (existing != null) return existing.join(); // someone else is already loading
try {
V again = cache.get(key); // a load may have finished between our miss and putIfAbsent
V value = again != null ? again : loader.apply(key);
if (again == null) cache.put(key, value);
mine.complete(value);
return value;
} catch (RuntimeException ex) {
mine.completeExceptionally(ex); // waiters see the failure too, nothing is cached
throw ex;
} finally {
inFlight.remove(key, mine);
}
}
}
class LoadingCacheDemo {
public static void main(String[] args) throws Exception {
AtomicInteger loads = new AtomicInteger();
LoadingCache<String, String> cache = new LoadingCache<>(Cache.lru(100), key -> {
loads.incrementAndGet();
try { Thread.sleep(50); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
return "value-of-" + key;
});
int threads = 32;
ExecutorService pool = Executors.newFixedThreadPool(threads);
CountDownLatch start = new CountDownLatch(1);
List<Future<String>> results = new ArrayList<>();
for (int i = 0; i < threads; i++) {
results.add(pool.submit(() -> { start.await(); return cache.get("hot"); }));
}
start.countDown();
for (Future<String> f : results) {
if (!"value-of-hot".equals(f.get())) throw new AssertionError("wrong value");
}
pool.shutdown();
if (loads.get() != 1) throw new AssertionError("loader ran " + loads.get() + " times");
System.out.println("LoadingCacheDemo ok: 32 concurrent misses, 1 load");
}
}
Two subtle points. First, the re-check after winning putIfAbsent: without it, a thread that missed just before the previous loader finished could start a second load. Second, failures are not cached. The future completes exceptionally, waiters get the error, and the next caller retries. Negative caching (remembering "not found" for a short TTL) is a separate, deliberate choice.
Extension B: "Tell me when something is evicted, so I can write it back"
Eviction listeners are an Observer. The naive version calls the listener inside _evict_one, which runs while the cache lock is held. A slow listener, say one that writes to a database, would then block every other cache operation. Worse, a listener that calls back into the cache would deadlock on a non-reentrant lock.
The fix is to queue evictions under the lock and deliver them after the lock is released.
# file: ext_listener.py
"""Eviction listener: queue under the lock, notify after releasing it."""
from collections import deque
from typing import Callable, Deque, Tuple
from cache import Cache, LruPolicy, ManualClock
class ListeningCache(Cache):
def __init__(self, capacity, policy, clock, on_evict: Callable[[object, object], None]) -> None:
super().__init__(capacity, policy, clock)
self._on_evict = on_evict
self._pending: Deque[Tuple[object, object]] = deque()
def _evict_one(self):
key, value = super()._evict_one() # runs with the lock held
self._pending.append((key, value)) # cheap, no user code here
return key, value
def put(self, key, value, ttl=None) -> None:
super().put(key, value, ttl) # lock is released when this returns
self._drain()
def _drain(self) -> None:
while True:
try:
key, value = self._pending.popleft() # deque.popleft is thread-safe
except IndexError:
return
self._on_evict(key, value)
if __name__ == "__main__":
written_back = []
cache = ListeningCache(2, LruPolicy(), ManualClock(), on_evict=lambda k, v: written_back.append((k, v)))
def reentrant_listener_check(k, v):
written_back.append((k, v))
cache.get("b") # would deadlock if we were still holding the lock
cache._on_evict = reentrant_listener_check
cache.put("a", 1)
cache.put("b", 2)
cache.put("c", 3) # evicts a
cache.put("d", 4) # evicts c (b was just read by the listener)
assert written_back == [("a", 1), ("c", 3)], written_back
print("ext_listener.py ok:", written_back)
Production caches pass a cause along with the key and value (Caffeine's RemovalCause has SIZE, EXPIRED, EXPLICIT, REPLACED), because "write back on eviction" and "write back on expiry" are often different decisions.
Extension C: "A nightly batch job reads every key once and wipes out the hot set"
This is the weakness of plain LRU: a scan of keys that are used once pushes out keys that are used constantly. LFU resists scans but is slow to forget keys that were popular yesterday. A middle ground is Segmented LRU (SLRU): new keys enter a probation list, and only a second hit promotes them to a protected list. Eviction takes from probation first. A scan only churns probation, and the hot set stays protected.
Because eviction is a Strategy, SLRU is a new class and nothing else changes.
// file: slru.ts
import { Cache, DoublyLinkedList, EvictionPolicy, ListNode, LruPolicy } from "./cache";
/** Segmented LRU: first hit goes to probation, a second hit promotes to protected. */
export class SlruPolicy<K> implements EvictionPolicy<K> {
private readonly probation = new DoublyLinkedList<K>();
private readonly protectedList = new DoublyLinkedList<K>();
private readonly nodes = new Map<K, { node: ListNode<K>; isProtected: boolean }>();
constructor(private readonly protectedCapacity: number) {}
recordInsert(key: K): void {
const node = new ListNode(key);
this.probation.addFirst(node);
this.nodes.set(key, { node, isProtected: false });
}
recordAccess(key: K): void {
const e = this.nodes.get(key)!;
if (e.isProtected) {
this.protectedList.unlink(e.node);
this.protectedList.addFirst(e.node);
return;
}
this.probation.unlink(e.node);
this.protectedList.addFirst(e.node);
e.isProtected = true;
if (this.protectedList.size > this.protectedCapacity) {
const demoted = this.protectedList.removeLast()!; // overflow drops back to probation
this.probation.addFirst(demoted);
this.nodes.get(demoted.key)!.isProtected = false;
}
}
recordRemove(key: K): void {
const e = this.nodes.get(key);
if (!e) return;
(e.isProtected ? this.protectedList : this.probation).unlink(e.node);
this.nodes.delete(key);
}
evict(): K {
const victim = this.probation.removeLast() ?? this.protectedList.removeLast();
if (!victim) throw new Error("nothing to evict");
this.nodes.delete(victim.key);
return victim.key;
}
size(): number { return this.nodes.size; }
}
function survivesScan(policy: EvictionPolicy<string>): boolean {
const cache = new Cache<string, number>(4, policy);
cache.put("hot1", 1);
cache.put("hot2", 2);
cache.get("hot1");
cache.get("hot2"); // second touch
for (let i = 0; i < 10; i++) cache.put(`scan${i}`, i); // one-off batch reads
return cache.get("hot1") !== undefined && cache.get("hot2") !== undefined;
}
if (!survivesScan(new SlruPolicy<string>(2))) throw new Error("SLRU should protect the hot set");
if (survivesScan(new LruPolicy<string>())) throw new Error("plain LRU should lose the hot set");
console.log("slru.ts ok: hot keys survive a scan under SLRU, not under LRU");
Mention that this idea, in more refined form, is what W-TinyLFU (Caffeine) does: a small LRU "window" in front of an SLRU main space, plus a compact frequency sketch that decides whether a newcomer deserves to displace the current victim.
9. Testing
The demo main in each listing already checks the core behaviour. A proper suite is organised by behaviour, not by method, and it never sleeps. The manual clock makes TTL tests instant and exact.
What to cover:
- LRU order. A read protects a key, and the least recently touched key is evicted.
- LFU order and tie-break. The lowest frequency loses, and ties go to the least recent.
- LFU after out-of-order removal. This is the test that catches the
minFreqbug. - Update doesn't evict.
puton an existing key in a full cache must not evict anything. - TTL boundary. Live at
expiresAt - 1, gone atexpiresAt. Off-by-one here is common. - Expired key re-put starts fresh. For LFU, its frequency is back to 1.
- Capacity 1. Every new key evicts the previous one.
- Invalid arguments. Capacity 0 and negative TTL are rejected.
- Concurrency. A stress test with random operations, ending with
checkInvariants(). It won't prove absence of races, but it reliably catches a missing lock. Run it with the lock removed once, to confirm the test can fail.
// file: CacheTests.java
import java.util.function.Supplier;
class CacheTests {
static int passed;
static void test(String name, Runnable body) {
body.run();
passed++;
System.out.println(" ok " + name);
}
static void expectThrows(Runnable r) {
try { r.run(); } catch (IllegalArgumentException e) { return; }
throw new AssertionError("expected IllegalArgumentException");
}
public static void main(String[] args) {
test("update in a full cache does not evict", () -> {
Cache<String, Integer> c = new Cache<>(2, new LruPolicy<>(), new ManualClock());
c.put("a", 1); c.put("b", 2); c.put("a", 10);
CacheDemo.eq(10, c.get("a")); CacheDemo.eq(2, c.get("b"));
CacheDemo.eq(0L, c.stats().evictions());
});
test("capacity one keeps only the newest key", () -> {
Cache<String, Integer> c = new Cache<>(1, new LfuPolicy<>(), new ManualClock());
c.put("a", 1); c.get("a"); c.get("a"); c.put("b", 2);
CacheDemo.eq(null, c.get("a")); CacheDemo.eq(2, c.get("b"));
});
test("expired key re-put starts at frequency one", () -> {
ManualClock clock = new ManualClock();
LfuPolicy<String> policy = new LfuPolicy<>();
Cache<String, Integer> c = new Cache<>(5, policy, clock);
c.put("k", 1, 10); c.get("k"); c.get("k");
CacheDemo.eq(3, policy.frequency("k"));
clock.advance(10);
c.put("k", 2);
CacheDemo.eq(1, policy.frequency("k"));
});
test("stats count hits, misses and evictions", () -> {
Cache<Integer, Integer> c = new Cache<>(1, new LruPolicy<>(), new ManualClock());
c.put(1, 1); c.get(1); c.get(2); c.put(2, 2);
CacheDemo.eq(new Stats(1, 1, 1), c.stats());
});
test("invalid arguments are rejected", () -> {
Supplier<Cache<String, Integer>> ok = () -> new Cache<>(1, new LruPolicy<>(), new ManualClock());
expectThrows(() -> new Cache<String, Integer>(0, new LruPolicy<>(), new ManualClock()));
expectThrows(() -> ok.get().put("a", 1, -5));
});
System.out.println("CacheTests: " + passed + " passed");
}
}
# file: test_cache.py
import unittest
from cache import Cache, LfuPolicy, LruPolicy, ManualClock, Stats
class CacheTest(unittest.TestCase):
def test_update_in_full_cache_does_not_evict(self):
c = Cache(2, LruPolicy(), ManualClock())
c.put("a", 1)
c.put("b", 2)
c.put("a", 10)
self.assertEqual(c.get("a"), 10)
self.assertEqual(c.get("b"), 2)
self.assertEqual(c.stats().evictions, 0)
def test_ttl_boundary(self):
clock = ManualClock()
c = Cache(2, LruPolicy(), clock)
c.put("k", "v", ttl=5)
clock.advance(4.999)
self.assertEqual(c.get("k"), "v")
clock.advance(0.001)
self.assertIsNone(c.get("k"))
def test_lfu_survives_out_of_order_removal(self):
c = Cache(3, LfuPolicy(), ManualClock())
for k in "abc":
c.put(k, k)
c.get("b")
c.get("c")
c.get("c")
c.remove("a") # the only key at the lowest frequency
c.put("d", "d") # fills the slot
c.put("e", "e") # must evict d (freq 1), not b or c
self.assertIsNone(c.get("d"))
self.assertEqual([c.get(k) for k in "bce"], ["b", "c", "e"])
def test_stats(self):
c = Cache(1, LruPolicy(), ManualClock())
c.put(1, 1)
c.get(1)
c.get(2)
c.put(2, 2)
self.assertEqual(c.stats(), Stats(hits=1, misses=1, evictions=1))
def test_invalid_arguments(self):
with self.assertRaises(ValueError):
Cache(0, LruPolicy())
with self.assertRaises(ValueError):
Cache(1, LruPolicy()).put("a", 1, ttl=-1)
with self.assertRaises(ValueError):
Cache(1, LruPolicy()).put("a", None)
if __name__ == "__main__":
unittest.main(verbosity=2)
// file: cache.test.ts
import { test } from "node:test";
import assert from "node:assert/strict";
import { Cache, LfuPolicy, LruPolicy, ManualClock } from "./cache";
test("update in a full cache does not evict", () => {
const c = new Cache<string, number>(2, new LruPolicy(), new ManualClock().read);
c.put("a", 1);
c.put("b", 2);
c.put("a", 10);
assert.equal(c.get("a"), 10);
assert.equal(c.get("b"), 2);
assert.equal(c.stats().evictions, 0);
});
test("ttl boundary is exclusive", () => {
const clock = new ManualClock();
const c = new Cache<string, string>(2, new LruPolicy(), clock.read);
c.put("k", "v", 50);
clock.advance(49);
assert.equal(c.get("k"), "v");
clock.advance(1);
assert.equal(c.get("k"), undefined);
});
test("lfu survives out-of-order removal", () => {
const c = new Cache<string, string>(3, new LfuPolicy(), new ManualClock().read);
for (const k of ["a", "b", "c"]) c.put(k, k);
c.get("b");
c.get("c");
c.get("c");
c.remove("a");
c.put("d", "d");
c.put("e", "e"); // evicts d
assert.equal(c.get("d"), undefined);
assert.deepEqual(["b", "c", "e"].map((k) => c.get(k)), ["b", "c", "e"]);
});
test("invalid arguments are rejected", () => {
assert.throws(() => new Cache<string, number>(0, new LruPolicy()), RangeError);
assert.throws(() => new Cache<string, number>(1, new LruPolicy()).put("a", 1, -1), RangeError);
});
10. Common mistakes
- Using a built-in list and calling
remove(key).LinkedList.remove(Object)is O(n). The whole point is that the map stores a reference to the node, and the node unlinks itself. - A singly linked list. Unlinking needs the previous node. Without
prevyou're back to scanning. - No sentinels. You end up with four special cases in
unlinkand get one wrong under pressure. Two dummy nodes delete all of them. - Forgetting to update the map when evicting. The list drops the tail node, but the map still points at it. The next
getof that key "hits" a ghost. The node must store its key so eviction can find the map entry. - Inserting before evicting. For LFU this evicts the brand-new key. For both, the map briefly holds
capacity + 1entries, which breaks any invariant check. minFreqwith deletions. The LeetCode LFU trick silently breaks once TTL or explicit removal exists. Use the linked list of buckets, or rebuildminFreqlazily and admit it's not O(1).- A read-write lock with
getunder the read lock.getwrites to the recency structure. Two concurrent readers corrupt the list. - A
ConcurrentHashMapplus a separate list, each "thread-safe". Two thread-safe structures don't make a thread-safe pair. The compound update must be atomic. - Calling user callbacks under the lock. Listeners and loaders can be slow or re-enter the cache. Collect under the lock, call outside it.
- Sleeping in TTL tests. They become slow and flaky. Inject the clock.
- Using wall-clock time for TTL.
System.currentTimeMillis()can jump backwards when NTP corrects the clock. For pure in-process expiry, a monotonic source (System.nanoTime,time.monotonic,performance.now) is safer. The listings use wall-clock in Java and TS for readability. Mention the swap. - Over-patterning. A
CacheFactory, aCacheManagersingleton and an abstractAbstractCacheEntryadd nothing here. One interface (EvictionPolicy) earns its place because the requirements name two policies.
11. Interview follow-ups
"What's the time complexity of each operation, honestly?"
O(1) expected for get, put and remove under both policies. "Expected" because hash map operations are O(1) on average and O(n) in the pathological all-collide case (Java 8+ bounds that at O(log n) by turning a long bucket into a tree). purgeExpired is O(n) by design.
"How much memory does this use beyond the values?"
Per entry: one map entry for the data, one map entry in the policy, and a node with two pointers plus the key reference. LFU adds a second map entry (bucketOf) and amortized bucket objects. On the JVM that's roughly 100+ bytes of overhead per entry, which is why caches of millions of small values often switch to off-heap or open-addressing designs. You could merge the two maps by storing the node inside the entry, at the cost of coupling the cache to the policy's internals.
"Why does LFU need a recency tie-break at all?" Without it, the choice among equal-frequency keys is arbitrary and non-deterministic, which makes tests flaky. Recency is the natural tie-break because among equally popular keys, the one untouched longest is the least likely to be needed soon.
"LFU has a known weakness. What is it, and how would you fix it?" It never forgets. A key hit a million times during yesterday's launch stays forever even if nobody reads it again. Fixes include aging (periodically halving every frequency), windowed counts, or a TinyLFU-style sketch that decays. Redis's LFU mode uses a logarithmic counter that decays over time for exactly this reason.
"Why both lazy and active expiry?" Lazy expiry costs nothing until a key is touched, but a key that's never touched again stays in memory forever. Active expiry (a sweep) reclaims those, but a full sweep is O(n) and holds the lock. A good compromise is to sample: every 100 ms, check 20 random keys with a TTL and repeat if more than a quarter were expired. That's the approach Redis documents. A min-heap or timing wheel keyed by expiry time is the precise alternative, at the cost of O(log n) per insert.
"How would you make capacity based on bytes instead of entries?"
Accept a weigher: (K, V) -> int, track total weight, and on insert evict in a loop while totalWeight + newWeight > maxWeight. Reject single entries heavier than the whole cache. Updates must subtract the old weight. The policy interface doesn't change.
"Two threads put the same key at the same time. What happens?"
The lock serializes them. One insert wins, and the second becomes an update that overwrites the value and counts as an access. Last writer wins. If the caller needs "insert only if absent", add a putIfAbsent that checks and inserts under the same lock acquisition.
"Can get ever return a value that was already removed?"
Not with a single lock: remove and get are serialized. With the segmented version it's also safe, because a key always lives in exactly one segment. It can return a value that has been overwritten by the time the caller uses it, but that's inherent to any shared mutable cache.
"How would this change if the cache were shared by many servers?" It stops being an LLD problem. You'd move to a networked cache like Redis or Memcached, think about consistent hashing for sharding, replication and invalidation, and accept that LRU becomes approximate (Redis samples a handful of keys and evicts the oldest of the sample rather than maintaining a global list). The in-process cache may remain as an L1 in front of it.
"Is your Cache class doing too much?"
It owns the map, TTL, stats and the lock. One could extract Stats or a TtlPolicy. The test is whether those pieces vary independently. TTL is a property of entries that the map already holds, and splitting it out would mean a second structure that must stay consistent with the first. Keeping it together is a deliberate cohesion choice, and that's the argument to give.
Related
- Strategy: the pattern behind pluggable eviction.
- Decorator and Observer: the loading-cache and listener extensions.
- Thread-Safe Class Design and Concurrency Patterns in LLD: lock granularity, striping and single-flight in more depth.
- Design an In-Memory Key-Value Store: the next step up, adding TTL sweeps, transactions and a command parser.