On this page
Cache with Eviction Policies (LRU / LFU)
Last reviewed 14 Oct 2026
Problem
Design an in-memory key-value cache with a fixed capacity. When it’s full, adding a new key evicts one existing key chosen by an eviction policy. The policy must be swappable: LRU today, LFU tomorrow. get and put should be O(1).
Requirements
get(key)returns the value orundefined; it counts as an access.put(key, value)inserts or updates; updating counts as an access; inserting into a full cache evicts first.delete(key),size.- Policies: LRU (evict least recently used) and LFU (evict least frequently used; ties broken by least recently used).
- Capacity ≥ 1.
Entities and class diagram
classDiagram
class Cache {
-capacity: number
-store: Map
-policy: EvictionPolicy
+get(key) V
+put(key, value)
+delete(key) boolean
}
class EvictionPolicy {
<<interface>>
+onAccess(key)
+onInsert(key)
+onRemove(key)
+victim() K
}
class LRUPolicy {
-nodes: Map
-head: Node
-tail: Node
}
class LFUPolicy {
-freq: Map
-buckets: Map
-minFreq: number
}
Cache o-- EvictionPolicy
EvictionPolicy <|.. LRUPolicy
EvictionPolicy <|.. LFUPolicy
Design decisions
- Split storage from policy.
Cacheowns the values and capacity; the policy only tracks keys and answers “which key should go?”. That’s the Strategy pattern, and it means each policy is tested on its own. - LRU in O(1): a hash map from key to a node in a doubly linked list ordered by recency. Access → unlink the node and move it to the front. Evict → the tail. Sentinel head/tail nodes remove null checks.
- LFU in O(1):
freq[key], andbuckets[f]= keys with frequency f in recency order (a JSSetkeeps insertion order, so deleting and re-adding moves a key to the end). TrackminFreq; the victim is the oldest key inbuckets[minFreq]. A new key always resetsminFreqto 1. - Interview note: in JavaScript, a
Mapalone gives a valid LRU (delete and re-set to move a key to the end; the first key is the oldest). Show the linked list anyway — it’s what the interviewer is checking, and it’s the answer in Java (LinkedHashMapwith access order does it for you).
Final code
interface EvictionPolicy<K> { onAccess(key: K): void; onInsert(key: K): void; onRemove(key: K): void; victim(): K | undefined;}
class ListNode<K> { prev: ListNode<K> | null = null; next: ListNode<K> | null = null; constructor(readonly key: K | null) {}}
/** Most recent at the head, least recent at the tail. */class LRUPolicy<K> implements EvictionPolicy<K> { private nodes = new Map<K, ListNode<K>>(); private head = new ListNode<K>(null); private tail = new ListNode<K>(null);
constructor() { this.head.next = this.tail; this.tail.prev = this.head; }
onInsert(key: K): void { const node = new ListNode(key); this.nodes.set(key, node); this.addFront(node); }
onAccess(key: K): void { const node = this.nodes.get(key); if (!node) return; this.unlink(node); this.addFront(node); }
onRemove(key: K): void { const node = this.nodes.get(key); if (!node) return; this.unlink(node); this.nodes.delete(key); }
victim(): K | undefined { const last = this.tail.prev!; return last === this.head ? undefined : (last.key as K); }
private addFront(node: ListNode<K>): void { node.prev = this.head; node.next = this.head.next; this.head.next!.prev = node; this.head.next = node; }
private unlink(node: ListNode<K>): void { node.prev!.next = node.next; node.next!.prev = node.prev; node.prev = node.next = null; }}
/** Least frequently used; ties go to the least recently used within that frequency. */class LFUPolicy<K> implements EvictionPolicy<K> { private freq = new Map<K, number>(); private buckets = new Map<number, Set<K>>(); private minFreq = 0;
onInsert(key: K): void { this.freq.set(key, 1); this.bucket(1).add(key); this.minFreq = 1; }
onAccess(key: K): void { const f = this.freq.get(key); if (f === undefined) return; const old = this.bucket(f); old.delete(key); if (old.size === 0) { this.buckets.delete(f); if (this.minFreq === f) this.minFreq = f + 1; } this.freq.set(key, f + 1); this.bucket(f + 1).add(key); }
onRemove(key: K): void { const f = this.freq.get(key); if (f === undefined) return; const b = this.bucket(f); b.delete(key); if (b.size === 0) this.buckets.delete(f); this.freq.delete(key); if (this.freq.size === 0) this.minFreq = 0; else if (f === this.minFreq && !this.buckets.has(f)) this.minFreq = Math.min(...this.buckets.keys()); }
victim(): K | undefined { const b = this.buckets.get(this.minFreq); return b?.values().next().value; }
private bucket(f: number): Set<K> { let b = this.buckets.get(f); if (!b) this.buckets.set(f, (b = new Set())); return b; }}
class Cache<K, V> { private store = new Map<K, V>();
constructor(private capacity: number, private policy: EvictionPolicy<K> = new LRUPolicy<K>()) { if (!Number.isInteger(capacity) || capacity < 1) throw new Error('Capacity must be a positive integer'); }
get size(): number { return this.store.size; }
get(key: K): V | undefined { if (!this.store.has(key)) return undefined; this.policy.onAccess(key); return this.store.get(key); }
put(key: K, value: V): void { if (this.store.has(key)) { this.store.set(key, value); this.policy.onAccess(key); return; } if (this.store.size >= this.capacity) { const victim = this.policy.victim()!; this.store.delete(victim); this.policy.onRemove(victim); } this.store.set(key, value); this.policy.onInsert(key); }
delete(key: K): boolean { if (!this.store.delete(key)) return false; this.policy.onRemove(key); return true; }}Edge cases
- Capacity 1 → every new key evicts the previous one.
- Updating an existing key never evicts; it counts as an access.
getof a missing key doesn’t touch the policy.- LFU tie → the least recently used among the least frequent keys goes.
- Deleting the only key at the minimum frequency →
minFreqmoves to the next frequency present.
Extensions
- TTL — store
expiresAtwith each value; treat expired entries as missing onget(lazy expiry) plus a periodic sweep. - FIFO / random policies — new
EvictionPolicyclasses, no change toCache. - Thread safety — Java: a
ReentrantReadWriteLock, or segment the cache into N shards each with its own lock (like oldConcurrentHashMap). Note thatgetmutates LRU order, so it needs the write lock — a reason real caches (Caffeine) buffer access events instead. - Eviction listener — Observer callback when a key is evicted (write-back caches).
- Distributed — see Distributed Cache.
Interview follow-ups
- “Why a doubly linked list and not an array?” — Removing an arbitrary node is O(1) with prev/next pointers; an array shift is O(n).
- “Why does LRU
getneed a write lock?” — It reorders the list. - “LRU vs LFU — when is each better?” — LRU adapts to changing access patterns; LFU keeps long-term popular items but can hold stale ones (frequency aging fixes that).
- “How do you add a new policy?” — Implement
EvictionPolicy; inject it.