LFU Cache Design: O(1) Get and Put with Frequency Lists (Java)
To design an LFU cache in O(1), keep three things: a map from key to node, a map from each use count to a doubly linked list of the keys with that count, and minFreq, the lowest count in use. A get or put moves a key from the list for count f to the list for f + 1. When the cache is full, evict from the back of the minFreq list, which is the least recently used key among the least used.
Where it shows up
The harder sibling of the LRU cache question. LeetCode 460, LFU Cache, is the coding form: get and put in O(1) average time, with ties broken by least recently used. In a design round it usually follows the LRU question: now evict the least used key instead.
Two courses by the author of this page:
770 lessons · 18 free to read
₹499 in India · $49 elsewhere, once
Get System DesignYou own this course
204 lessons · 10 free to read
₹999 in India · $49 elsewhere, once
Get AI EngineeringYou own this course
Spec sheetLFU Cache
- 01Core classes
- LFUCache, Node, Bucket, SlowLFU
- 02Design patterns
- Bucketing by count, LRU inside each bucket, Sentinel nodes, Test against a slow reference
- 03Key methods
- 3 signatures, with the code skeleton
worked through below, with the maths
Why this is asked
A cache is a small, fast store that keeps copies of data you will likely need again. When it is full, it must throw something out. LFU, least frequently used, throws out the key with the fewest uses. A hash map stores key and value pairs and finds a key in one step. A doubly linked list is a chain of nodes that link both ways, so a node can be unlinked in one step. The naive version keeps a count per key and searches for the smallest count on every eviction. That is O(n), where n is the number of keys. A heap, a tree that keeps the smallest item on top, brings it to O(log n). The question asks for O(1), meaning the time does not grow with the number of keys. Getting there needs one insight: a count only ever goes up by 1, so a key only moves to the next list. The question also tests whether you handle ties, keep minFreq right, and know where LFU goes wrong.
Requirements
Functional
- get(key) returns the value, or null if the key is missing. A hit adds 1 to the key's use count.
- put(key, value) adds a key with use count 1, or updates the value of an existing key and adds 1 to its count.
- When the cache is full and a new key arrives, evict the key with the lowest use count.
- If several keys share the lowest count, evict the one used longest ago (the least recently used).
- Capacity is fixed when the cache is made, and must be at least 1.
Constraints & non-functional
- get and put each take O(1) time on average.
- Memory grows in step with the number of keys.
- No searching on eviction: the victim must be found directly.
- On random operations, the program must match a slow version that is plainly correct.
Core classes & entities
LFUCache
The class callers use. It keeps the key map, the count-to-list map and minFreq in step on every get and put.
attrs: capacity: int, nodes: HashMap<K, Node>, buckets: HashMap<Integer, Bucket>, minFreq: int
methods: get(key): V, put(key, value), touch(node), size(): int
Node
One cached key: its value, its use count, and links to its neighbours in its count's list. It stores the key so an evicted node can be deleted from the key map.
attrs: key, value, freq, prev, next
Bucket
A doubly linked list of every key with one use count, most recently used at the front. Two dummy end nodes mean adding and removing never deal with an empty list.
attrs: head, tail: Node (dummy ends), size: int
methods: addFront(node), unlink(node), removeLast(): Node
SlowLFU
The reference used only in the checks. It stores each key's count and last-use time, and scans every key to pick a victim. Slow, but easy to see that it is right.
attrs: m: HashMap<K, Entry>, tick: long
methods: get(key): V, put(key, value)
Relationships
- LFUCache → composition → Node. The cache makes and owns every node. The key map and one bucket both point at each node.
- LFUCache → composition → Bucket. One bucket per use count that has at least one key. An empty bucket is removed.
- Bucket → aggregation → Node. A bucket links the nodes with its count. A node moves to the next bucket on each use.
Design patterns used
Bucketing by count in buckets: count to list
Grouping keys by use count turns find the smallest count into a direct lookup, as long as minFreq is kept right.
LRU inside each bucket in Bucket.addFront and Bucket.removeLast
A used key goes to the front of its new bucket, so the back of each bucket is the least recently used key with that count. Ties are then broken with no extra data.
Sentinel nodes in The dummy head and tail of each bucket
Every real node always has neighbours, so unlinking needs no checks for an empty list.
Test against a slow reference in SlowLFU in the program
The fast version has many moving parts. A slow version that scans everything is easy to trust. Random operations run against both, and any difference shows a bug.
Key API / methods
V get(K key)Look up the node. On a miss, return null and change nothing. On a hit, call touch(node) and return the value. O(1).
void put(K key, V value)If the key exists, set the value and touch it. If it is new and the cache is full, remove the last node of the minFreq bucket and delete its key. Then add the new node to bucket 1 and set minFreq to 1. O(1).
private void touch(Node n)Unlink n from bucket n.freq. If that bucket is now empty, remove it, and if it was the minFreq bucket, add 1 to minFreq. Add 1 to n.freq and add n to the front of that bucket. O(1).
Code skeleton
import java.util.*;
// ---------- The O(1) LFU cache ----------
// Three parts:
// nodes: key -> node (value + use count), to find any key at once
// buckets: use count -> doubly linked list of the keys with that count, most recent at the front
// minFreq: the smallest use count that has any key, so the victim is found without searching
// Ties: inside one bucket, the key at the back was used longest ago, so it goes first (LRU).
final class LFUCache<K, V> {
private static final class Node<K, V> {
final K key; V value; int freq = 1; Node<K, V> prev, next;
Node(K key, V value) { this.key = key; this.value = value; }
}
private static final class Bucket<K, V> {
final Node<K, V> head = new Node<>(null, null), tail = new Node<>(null, null); int size;
Bucket() { head.next = tail; tail.prev = head; }
void addFront(Node<K, V> n) { n.prev = head; n.next = head.next; head.next.prev = n; head.next = n; size++; }
void unlink(Node<K, V> n) { n.prev.next = n.next; n.next.prev = n.prev; n.prev = n.next = null; size--; }
Node<K, V> removeLast() { Node<K, V> n = tail.prev; unlink(n); return n; }
}
private final int capacity;
private final Map<K, Node<K, V>> nodes = new HashMap<>();
private final Map<Integer, Bucket<K, V>> buckets = new HashMap<>();
private int minFreq;
final List<K> evicted = new ArrayList<>();
LFUCache(int capacity) { if (capacity <= 0) throw new IllegalArgumentException("capacity must be at least 1"); this.capacity = capacity; }
V get(K key) {
Node<K, V> n = nodes.get(key);
if (n == null) return null;
touch(n);
return n.value;
}
void put(K key, V value) {
Node<K, V> n = nodes.get(key);
if (n != null) { n.value = value; touch(n); return; } // update counts as a use
if (nodes.size() == capacity) {
Bucket<K, V> lowest = buckets.get(minFreq);
Node<K, V> victim = lowest.removeLast(); // fewest uses, and of those, least recent
if (lowest.size == 0) buckets.remove(minFreq);
nodes.remove(victim.key);
evicted.add(victim.key);
}
n = new Node<>(key, value);
nodes.put(key, n);
buckets.computeIfAbsent(1, f -> new Bucket<>()).addFront(n);
minFreq = 1; // a new key always has the lowest count
}
// move a node from bucket f to bucket f + 1
private void touch(Node<K, V> n) {
Bucket<K, V> from = buckets.get(n.freq);
from.unlink(n);
if (from.size == 0) { buckets.remove(n.freq); if (minFreq == n.freq) minFreq++; }
n.freq++;
buckets.computeIfAbsent(n.freq, f -> new Bucket<>()).addFront(n);
}
int size() { return nodes.size(); }
int minFreq() { return minFreq; }
// e.g. "1: [E] 2: [D] 3: [A]", most recent first inside each bucket
String describe() {
StringBuilder sb = new StringBuilder();
for (int f : new TreeSet<>(buckets.keySet())) {
List<String> ks = new ArrayList<>();
for (Node<K, V> n = buckets.get(f).head.next; n != buckets.get(f).tail; n = n.next) ks.add(String.valueOf(n.key));
sb.append(f).append(": ").append(ks).append(" ");
}
return sb.toString().trim();
}
Map<K, Integer> counts() { Map<K, Integer> m = new HashMap<>(); nodes.forEach((k, n) -> m.put(k, n.freq)); return m; }
}
// ---------- A slow reference: obviously correct, scans everything to evict ----------
final class SlowLFU<K, V> {
private record Entry<V>(V value, int freq, long lastUse) {}
private final int capacity; private final Map<K, Entry<V>> m = new HashMap<>(); private long tick;
SlowLFU(int capacity) { this.capacity = capacity; }
V get(K k) { Entry<V> e = m.get(k); if (e == null) return null; m.put(k, new Entry<>(e.value(), e.freq() + 1, ++tick)); return e.value(); }
void put(K k, V v) {
Entry<V> e = m.get(k);
if (e != null) { m.put(k, new Entry<>(v, e.freq() + 1, ++tick)); return; }
if (m.size() == capacity) {
K victim = null; Entry<V> best = null;
for (var x : m.entrySet()) {
Entry<V> c = x.getValue();
if (best == null || c.freq() < best.freq() || (c.freq() == best.freq() && c.lastUse() < best.lastUse())) { best = c; victim = x.getKey(); }
}
m.remove(victim);
}
m.put(k, new Entry<>(v, 1, ++tick));
}
Map<K, Integer> counts() { Map<K, Integer> r = new HashMap<>(); m.forEach((k, e) -> r.put(k, e.freq())); return r; }
}
public class LFUCacheDemo {
public static void main(String[] args) {
System.out.println("1. A sequence of operations, capacity 3 (use count: keys, most recent first)");
LFUCache<String, Integer> c = new LFUCache<>(3);
run(c, "put A", () -> c.put("A", 1));
run(c, "put B", () -> c.put("B", 2));
run(c, "put C", () -> c.put("C", 3));
run(c, "get A", () -> c.get("A"));
run(c, "get A", () -> c.get("A"));
run(c, "get B", () -> c.get("B"));
run(c, "put D (full: evicts C)", () -> c.put("D", 4));
run(c, "get D", () -> c.get("D"));
run(c, "put E (full: evicts B)", () -> c.put("E", 5));
check(c.evicted.equals(List.of("C", "B")) && c.describe().equals("1: [E] 2: [D] 3: [A]"),
"C goes first (count 1). Then B and D both have count 2, and B was used longer ago, so B goes");
System.out.println("2. The LeetCode 460 example");
LFUCache<Integer, Integer> lc = new LFUCache<>(2);
List<Integer> got = new ArrayList<>();
lc.put(1, 1); lc.put(2, 2); got.add(lc.get(1)); lc.put(3, 3); got.add(lc.get(2)); got.add(lc.get(3));
lc.put(4, 4); got.add(lc.get(1)); got.add(lc.get(3)); got.add(lc.get(4));
check(got.equals(Arrays.asList(1, null, 3, null, 3, 4)), "gets return 1, miss, 3, miss, 3, 4 (the problem's expected output, with -1 as a miss)");
System.out.println("3. Same answers as a slow reference that scans every key");
Random rnd = new Random(7);
long ops = 0, gets = 0, mismatches = 0;
for (int cap : new int[] { 1, 2, 3, 8, 32 }) {
LFUCache<Integer, Integer> fast = new LFUCache<>(cap);
SlowLFU<Integer, Integer> slow = new SlowLFU<>(cap);
for (int i = 0; i < 40_000; i++, ops++) {
int k = (int) Math.min(cap * 4L, Math.abs((long) (rnd.nextGaussian() * cap * 1.5))); // some keys hotter than others
if (rnd.nextInt(3) > 0) { gets++; if (!Objects.equals(fast.get(k), slow.get(k))) mismatches++; }
else { int v = rnd.nextInt(); fast.put(k, v); slow.put(k, v); }
if (i % 1000 == 0 && !fast.counts().equals(slow.counts())) mismatches++;
}
if (!fast.counts().equals(slow.counts())) mismatches++;
}
check(mismatches == 0, String.format("%,d random operations at capacities 1, 2, 3, 8 and 32: all %,d gets, every use count and every eviction match", ops, gets));
System.out.println("4. minFreq after a get empties the lowest bucket");
LFUCache<String, Integer> m = new LFUCache<>(2);
m.put("x", 1); m.put("y", 2); m.get("x"); m.get("y");
check(m.minFreq() == 2, "x and y both move to count 2, bucket 1 is empty, so minFreq becomes 2");
m.put("z", 3);
check(m.minFreq() == 1 && m.evicted.equals(List.of("x")), "put z evicts x (count 2, used before y) and minFreq resets to 1");
System.out.println("5. The weak spot: an old favourite never leaves");
LFUCache<String, Integer> lfu = new LFUCache<>(4);
Map<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true) { // a plain LRU of the same size, to compare
private static final long serialVersionUID = 1L;
@Override protected boolean removeEldestEntry(Map.Entry<String, Integer> e) { return size() > 4; }
};
lfu.put("old", 0); lru.put("old", 0);
for (int i = 0; i < 100; i++) { lfu.get("old"); lru.get("old"); } // popular yesterday
int lfuHits = 0, lruHits = 0, reads = 0;
for (int round = 0; round < 200; round++, reads++) { // today: 4 new keys, read in turn
String k = "new" + (round % 4);
if (lfu.get(k) != null) lfuHits++; else lfu.put(k, round);
if (lru.get(k) != null) lruHits++; else lru.put(k, round);
}
check(lfu.counts().get("old") == 101 && lfuHits == 0 && lruHits == reads - 4,
String.format("today's 4 keys, read %d times: LFU keeps 'old' (count 101) and hits %d times; LRU drops 'old' and hits %d times", reads, lfuHits, lruHits));
System.out.println("all checks passed");
}
static void run(LFUCache<String, Integer> c, String what, Runnable r) {
r.run();
System.out.printf(" %-24s %s%n", what, c.describe());
}
static void check(boolean ok, String what) { System.out.println((ok ? " ok " : " FAIL ") + what); if (!ok) System.exit(1); }
}
/* Output of this exact program (javac + java 21, 2026-10-07):
* 1. A sequence of operations, capacity 3 (use count: keys, most recent first)
* put A 1: [A]
* put B 1: [B, A]
* put C 1: [C, B, A]
* get A 1: [C, B] 2: [A]
* get A 1: [C, B] 3: [A]
* get B 1: [C] 2: [B] 3: [A]
* put D (full: evicts C) 1: [D] 2: [B] 3: [A]
* get D 2: [D, B] 3: [A]
* put E (full: evicts B) 1: [E] 2: [D] 3: [A]
* ok C goes first (count 1). Then B and D both have count 2, and B was used longer ago, so B goes
* 2. The LeetCode 460 example
* ok gets return 1, miss, 3, miss, 3, 4 (the problem's expected output, with -1 as a miss)
* 3. Same answers as a slow reference that scans every key
* ok 200,000 random operations at capacities 1, 2, 3, 8 and 32: all 133,424 gets, every use count and every eviction match
* 4. minFreq after a get empties the lowest bucket
* ok x and y both move to count 2, bucket 1 is empty, so minFreq becomes 2
* ok put z evicts x (count 2, used before y) and minFreq resets to 1
* 5. The weak spot: an old favourite never leaves
* ok today's 4 keys, read 200 times: LFU keeps 'old' (count 101) and hits 0 times; LRU drops 'old' and hits 196 times
* all checks passed
*/How it works
Start with why the simple ways are slow. Keep a count per key and, on eviction, search for the smallest. That is O(n). Keep the keys in a heap ordered by count, and each use must fix the heap. That is O(log n). The paper by Matani, Shah and Mitra, An O(1) algorithm for implementing the LFU cache eviction scheme, shows that hash tables and doubly linked lists bring every operation to O(1). The version below follows that idea, in the form most interviewers expect.
The insight is that a count only goes up by 1 at a time. So group keys by their count. buckets maps each count to a doubly linked list of the keys with that count. A use moves a key from list f to list f + 1, which is an unlink and an add, both O(1). nodes maps each key to its node, so any key is found at once.
The victim must be found without searching. Keep minFreq, the lowest count that has any key. The victim is the last node of the minFreq list. Inside each list, a used key goes to the front, so the last node is the one used longest ago. That breaks ties by LRU for free.
minFreq stays right with two rules. A new key has count 1, so after a put of a new key, minFreq is 1. After a use, if the key's old list is now empty and it was the minFreq list, minFreq goes up by 1, because that key now sits at the next count. Nothing else can change the lowest count.
The figure above follows the program with capacity 3. After A is read twice and B once, the lists are 1: C, 2: B, 3: A. put D is a new key in a full cache. minFreq is 1, so C goes. A read of D moves D to count 2, and list 1 is now empty, so minFreq becomes 2. put E evicts from list 2. B and D both have count 2, B was used longer ago, so B goes. The end state is 1: E, 2: D, 3: A.
The program then runs 200,000 random operations, at 5 cache sizes, against a slow version that scans every key. Every get, every use count and every eviction matches. It also passes the LeetCode 460 example.
Plain LFU has one weak spot, and the program measures it. A key read 100 times keeps its high count after it stops being useful. When a new set of 4 keys is read in turn, the old key holds 1 of the 4 slots. The 4 new keys fight over the other 3 and keep evicting each other, so LFU gets 0 hits in 200 reads. An LRU with room for 4 drops the old key and hits 196 times. The fix is aging: make old counts count for less over time. The FAQ covers how Redis and Caffeine do it.
Edge cases & gotchas
- A tie at the lowest count. Evict the key used longest ago. The program's run evicts B over D: both have count 2, and D was used more recently.
- minFreq after a get. If the get empties the lowest bucket, minFreq goes up by exactly 1, because the key moved to the next count. It can never jump further.
- minFreq after a put of a new key. It always resets to 1.
- Updating an existing key counts as a use. LeetCode 460 counts both get and put. Say which rule you use.
- A new key is the easiest to evict, since its count is 1. In a full cache, a key that arrives and is never read again is the next to go. That keeps one-off keys from pushing out popular ones. It also means a new key that will become popular has to survive its first few uses.
- An old favourite never leaves. A key read 100 times last week still has count 101, and a key read twice today cannot beat it. The program shows plain LFU missing all 200 reads of a new working set, where LRU hits 196 times. Fix it with aging, covered in the FAQ.
- Counts can overflow in a cache that runs for years. Aging also fixes this, since counts are halved before they grow large.
- Threads: get changes the buckets, so get and put need one shared lock, as with LRU.
FAQ
Master LLD and system design interviews
770 interactive lessons and 90 real systems taken apart. One payment, lifetime access, no subscription.
course 1
System Design Masterclass
From absolute beginner to principal engineer, drawn step by step.
- 770 interactive lessons
- Step-by-step system design diagrams
- Live code editors
- Quizzes with instant feedback
- Progress tracking and streaks
- Lifetime access and all future lessons