Knowledge Guide
Home › Hands-On Builds › LLD Katas

Design an LFU Cache

Design an LFU Cache

Every candidate who has done the LRU cache kata walks into "now make it LFU" thinking it's the same problem with a different comparison. It is not. LRU's ordering signal (recency) only ever needs a move-to-front, so a doubly-linked list alone gets you O(1). LFU's ordering signal is a frequency count that changes for one key at a time while every other key's count stays put — there is no single list you can slide one node along and have the rest fall into the right order for free. The obvious instinct is to store the count next to the value and, on eviction, scan for the minimum. That works — and it is the reason this is rated the harder of the two caches in every interview loop: the fix is not "add a slightly smarter list," it's a genuinely different data-structure decomposition. This kata makes you build both the naive version and the true O(1) design, in Java and Go, and puts a stopwatch on the difference.

Play with it first

Before coding, use the debugger below — it runs one access trace through LRU, LFU, and FIFO side by side. Switch the workload, and on every full-cache miss predict which key each policy evicts before revealing it. Pay attention to the traces where LRU and LFU disagree — that disagreement is the entire reason this kata exists.

The Trap

Say you're building a per-node cache for a product-recommendation service: capacity 2,000 hot SKUs, and the eviction policy is LFU because popularity, not recency, is what should decide what stays. The "just make it work" version is one map: key -> (value, count). get bumps the count and returns the value — O(1), no problem. put, when the cache is full, has to find the minimum-count entry among all 2,000 live keys before it can evict — there's no way around inspecting every one of them, because nothing about the map tells you where the minimum lives. So every evicting put costs O(capacity), not O(1).

At small capacity this is invisible. It stops being invisible the moment the workload is eviction-heavy — a burst of new, never-seen-before SKUs (a flash sale, a fresh catalog import) where nearly every put is a miss that has to evict. Run 20,000 such puts against a capacity-2,000 cache and the naive scan does roughly capacity work on nearly every one of them — on the order of tens of millions of comparisons total. Measured later in this kata: that turns into roughly 20× slower in Java and roughly 170× slower in Go than the O(1) design, on identical input. Same bug, an order of magnitude apart depending on how the two runtimes iterate a hash map — but both are the same shape of trap.

There's a second, sneakier version of the trap that has nothing to do with speed. Suppose three keys — A, B, C — are all sitting at frequency 1 (each was inserted once, none has been touched since), and a fourth key arrives, forcing an eviction. All three tie on frequency. The correct rule (LeetCode 460's own spec, and every real LFU) is: among a frequency tie, evict the one that has gone longest without being touched — the true LRU-within-that-frequency-bucket. It is very easy to write the tie-break logic backwards — to compare "who was touched most recently" and keep that one instead, because "recently touched" intuitively sounds like it should be protected. It shouldn't, not on its own: recency without a frequency bump is exactly what put this key in the tied group to begin with. Get that comparison's direction wrong and your cache evicts the key you just used and hangs onto true dead weight — a silent correctness bug, not a crash, that only shows up as "why does the cache feel worse than no cache" days later.

Scope it like a senior

Before touching a data structure, pin the contract down out loud:

Answer: get/put both O(1), frequency bumps on every touch, ties broken by recency-within-frequency, fixed capacity with a 0-capacity guard, thread-safety as milestone 4.

Reason to the design

Simplest thing that could work: one map, key -> (value, freq). get and the "update an existing key" path of put are trivially O(1) — look up, bump the count, done. The entire cost lives in eviction: find the minimum freq across every live key. With one map and no auxiliary ordering, that's a full scan — O(n) in the current cache size. That's the naive design from the Trap above, and it's a real O(1)-looking-but-isn't bug: the individual map operations are O(1), but the policy's actual job — deciding who to evict — is not.

First fix attempt: keep the keys in a structure ordered by frequency. A min-heap keyed on freq turns "find the minimum" into O(1) peek — but every frequency bump is now a change to an already-heapified key, which standard heaps don't support without extra bookkeeping (an indexable / "decrease-key" heap, tracking each key's position). Even with that machinery, a heap update is O(log n), and a heap alone still doesn't solve the tie-break: two keys with equal frequency sit at arbitrary relative positions, not ordered by recency. You'd need a secondary comparator inside the heap ordering, which is more code for a data structure that's still not O(1). This is a real, legitimate design (some caches do use a variant of it) — it's just strictly worse than what's achievable here, and worth naming out loud as the road not taken.

The insight that unlocks O(1): frequency doesn't need a general-purpose ordered structure at all, because it only ever changes in one very restricted way — it starts at 1 and increases by exactly 1, one key at a time, on a touch. That means at any instant, the live keys partition cleanly into a small number of exact-integer frequency groups: "all keys currently at frequency 3," "all keys at frequency 7," and so on. Grouping by an exact integer is a hash-map lookup, not a comparison — O(1). And within one frequency group, all you need is "oldest untouched" vs "just touched," which is exactly what a doubly-linked list gives you for free (the same head/tail recency trick the LRU kata used, just scoped to one frequency instead of the whole cache).

So the design is three structures working together:

On a touch (get, or put on an existing key): unlink the node from freqMap[freq], and if that bucket is now empty and it was the current minFreq, bump minFreq up by one (the old minimum bucket just went extinct, so the next integer up is now guaranteed to be the new floor — frequencies only ever move up by exactly one, so there's no gap to search for). Then increment the node's frequency and push it to the front of freqMap[freq+1] — front, because it was just touched, which is also exactly the tie-break rule for free.

On eviction: go straight to freqMap[minFreq] and drop its tail — the node in the minimum-frequency group that has gone longest without a touch. No scan, ever.

Trace it with real numbers, capacity 3: put(1,100), put(2,200), put(3,300) — all three land at freq 1, oldest-to-newest order in that bucket is [1, 2, 3] tail-to-head. get(2): unlink 2 from bucket[1] (bucket[1] is now [1, 3], still non-empty so minFreq stays 1), push 2 to the front of bucket[2]. Now put(4,400) needs to evict: minFreq is still 1, bucket[1]'s tail is key 1 — drop it. Key 1 goes, not key 3, even though both were "equally idle" at freq 1 for a while — key 1 is strictly older in that bucket because it was inserted first and never touched again. That's the tie-break, mechanically, with no comparison logic anywhere — it falls out of "push new/touched nodes to the front."

Build it — milestones

Attempt-first: build against the contract get(key) -> value|miss, put(key, value), both O(1), ties broken by recency-within-frequency. Try each milestone yourself before reading the reference implementation below.

Reference implementation — Java

Three files. LFUCache.java is the M3/M4 answer: the real O(1) design. Save it, then compile it together with the naive version and the tests below — all three are plain (package-private) classes in the default package, so javac *.java just works.

import java.util.HashMap;
import java.util.Map;

/** A node in one frequency bucket's doubly-linked list. */
final class LfuNode {
    final int key;
    int value;
    int freq;
    LfuNode prev, next;
    LfuNode(int key, int value) { this.key = key; this.value = value; this.freq = 1; }
}

/**
 * A doubly-linked list of nodes that all currently share ONE frequency.
 * addFirst() marks a node as the most-recently-touched WITHIN this frequency;
 * removeLast() peels off the least-recently-touched -- the tie-break victim.
 * Sentinel head/tail nodes avoid null checks at the ends.
 */
final class FreqList {
    private final LfuNode head = new LfuNode(-1, -1);
    private final LfuNode tail = new LfuNode(-1, -1);
    int size = 0;

    FreqList() { head.next = tail; tail.prev = head; }

    void addFirst(LfuNode n) {
        n.prev = head; n.next = head.next;
        head.next.prev = n; head.next = n;
        size++;
    }
    void remove(LfuNode n) {
        n.prev.next = n.next; n.next.prev = n.prev;
        size--;
    }
    LfuNode removeLast() {                 // the LRU-within-this-frequency victim
        if (size == 0) return null;
        LfuNode victim = tail.prev;
        remove(victim);
        return victim;
    }
}

/**
 * O(1) get/put LFU cache. Three structures do the whole trick:
 *  - keyMap:  key -> node                        (O(1) lookup)
 *  - freqMap: frequency -> FreqList of its keys   (O(1) bucket membership)
 *  - minFreq: the smallest frequency that still has at least one key
 * On a hit, a key's node moves from bucket[f] to bucket[f+1] -- O(1) unlink + O(1) insert.
 * On eviction, drop the tail of bucket[minFreq] -- never a scan.
 */
final class LFUCache {
    private final int capacity;
    private int minFreq = 0;
    private final Map<Integer, LfuNode> keyMap = new HashMap<>();
    private final Map<Integer, FreqList> freqMap = new HashMap<>();

    LFUCache(int capacity) { this.capacity = capacity; }

    int get(int key) {
        LfuNode n = keyMap.get(key);
        if (n == null) return -1;
        touch(n);
        return n.value;
    }

    void put(int key, int value) {
        if (capacity <= 0) return;
        LfuNode n = keyMap.get(key);
        if (n != null) {
            n.value = value;
            touch(n);
            return;
        }
        if (keyMap.size() >= capacity) {
            FreqList victims = freqMap.get(minFreq);
            LfuNode evicted = victims.removeLast();     // O(1): tail of the min-frequency bucket
            keyMap.remove(evicted.key);
        }
        LfuNode fresh = new LfuNode(key, value);
        keyMap.put(key, fresh);
        freqMap.computeIfAbsent(1, f -> new FreqList()).addFirst(fresh);
        minFreq = 1;                                     // a brand-new key always starts the new minimum
    }

    /** Moves a node from bucket[freq] to bucket[freq+1], advancing minFreq if its old bucket emptied. */
    private void touch(LfuNode n) {
        FreqList oldBucket = freqMap.get(n.freq);
        oldBucket.remove(n);
        if (oldBucket.size == 0 && n.freq == minFreq) minFreq++;
        n.freq++;
        freqMap.computeIfAbsent(n.freq, f -> new FreqList()).addFirst(n);
    }
}

Reference implementation — Go

Same three-structure shape. Save as lfucache.go in a module named lfucache (go mod init lfucache).

module lfucache

go 1.21

// Package lfucache is the reference implementation for the "Design an LFU
// Cache" LLD kata: O(1) Get/Put via a key->node map, a frequency->doubly
// linked-list map, and a minFreq pointer.
package lfucache

// node sits in exactly one frequency bucket's doubly-linked list at a time.
type node struct {
	key, value int
	freq       int
	prev, next *node
}

// freqList is a doubly-linked list of nodes that all currently share ONE
// frequency. pushFront marks a node as the most-recently-touched WITHIN this
// frequency; popBack peels off the least-recently-touched -- the tie-break
// victim. Sentinel head/tail nodes avoid nil checks at the ends.
type freqList struct {
	head, tail *node
	size       int
}

func newFreqList() *freqList {
	h, t := &node{}, &node{}
	h.next, t.prev = t, h
	return &freqList{head: h, tail: t}
}

func (l *freqList) pushFront(n *node) {
	n.prev = l.head
	n.next = l.head.next
	l.head.next.prev = n
	l.head.next = n
	l.size++
}

func (l *freqList) remove(n *node) {
	n.prev.next = n.next
	n.next.prev = n.prev
	l.size--
}

func (l *freqList) popBack() *node { // the LRU-within-this-frequency victim
	if l.size == 0 {
		return nil
	}
	victim := l.tail.prev
	l.remove(victim)
	return victim
}

// LFUCache gives O(1) Get/Put. Three structures do the whole trick:
//   - keyMap:  key -> node                       (O(1) lookup)
//   - freqMap: frequency -> freqList of its keys  (O(1) bucket membership)
//   - minFreq: the smallest frequency that still has at least one key
//
// On a hit, a key's node moves from bucket[f] to bucket[f+1] -- O(1) unlink
// + O(1) insert. On eviction, drop the tail of bucket[minFreq] -- never a scan.
type LFUCache struct {
	capacity int
	minFreq  int
	keyMap   map[int]*node
	freqMap  map[int]*freqList
}

func New(capacity int) *LFUCache {
	return &LFUCache{
		capacity: capacity,
		keyMap:   make(map[int]*node),
		freqMap:  make(map[int]*freqList),
	}
}

func (c *LFUCache) Get(key int) (int, bool) {
	n, ok := c.keyMap[key]
	if !ok {
		return 0, false
	}
	c.touch(n)
	return n.value, true
}

func (c *LFUCache) Put(key, value int) {
	if c.capacity <= 0 {
		return
	}
	if n, ok := c.keyMap[key]; ok {
		n.value = value
		c.touch(n)
		return
	}
	if len(c.keyMap) >= c.capacity {
		victims := c.freqMap[c.minFreq]
		evicted := victims.popBack() // O(1): tail of the min-frequency bucket
		delete(c.keyMap, evicted.key)
	}
	fresh := &node{key: key, value: value, freq: 1}
	c.keyMap[key] = fresh
	if c.freqMap[1] == nil {
		c.freqMap[1] = newFreqList()
	}
	c.freqMap[1].pushFront(fresh)
	c.minFreq = 1 // a brand-new key always starts the new minimum
}

// touch moves a node from bucket[freq] to bucket[freq+1], advancing minFreq
// if its old bucket emptied out.
func (c *LFUCache) touch(n *node) {
	oldBucket := c.freqMap[n.freq]
	oldBucket.remove(n)
	if oldBucket.size == 0 && n.freq == c.minFreq {
		c.minFreq++
	}
	n.freq++
	if c.freqMap[n.freq] == nil {
		c.freqMap[n.freq] = newFreqList()
	}
	c.freqMap[n.freq].pushFront(n)
}

Note the sentinel head/tail nodes in freqList — exactly the same trick the LRU kata used, just one list per frequency instead of one list for the whole cache. That's the entire conceptual leap: LFU is "LRU, run once per frequency, plus a pointer to the currently-smallest frequency."

Break it

Both failures from the Trap live in one deliberately-wrong class, NaiveLFUCache — kept only so the tests below can reproduce them against the real LFUCache on identical input. Never use it for anything else.

import java.util.HashMap;
import java.util.Map;

/**
 * THE TRAP: a "just make it work" LFU. Correct-looking on paper, wrong in two
 * concrete ways this page's break-it tests reproduce:
 *  1. Eviction SCANS every live key to find the minimum frequency -- O(n)
 *     per evicting put, not O(1).
 *  2. Its tie-break among equal-frequency keys is backwards: it means to
 *     prefer evicting the LEAST-recently-touched candidate, but the
 *     comparison got inverted, so among ties it keeps the true LRU and
 *     evicts whichever key was touched MOST recently instead -- an easy,
 *     realistic bug to write by accident.
 * Kept here ONLY so the break-it section can demonstrate both failures
 * against the real O(1) LFUCache above. Never use this in real code.
 */
final class NaiveLFUCache {
    private final int capacity;
    private long clock = 0;
    private final Map<Integer, Integer> values = new HashMap<>();
    private final Map<Integer, Integer> freqs = new HashMap<>();
    private final Map<Integer, Long> lastTouched = new HashMap<>();

    NaiveLFUCache(int capacity) { this.capacity = capacity; }

    int get(int key) {
        if (!values.containsKey(key)) return -1;
        freqs.merge(key, 1, Integer::sum);
        lastTouched.put(key, ++clock);
        return values.get(key);
    }

    void put(int key, int value) {
        if (capacity <= 0) return;
        if (values.containsKey(key)) {
            values.put(key, value);
            freqs.merge(key, 1, Integer::sum);
            lastTouched.put(key, ++clock);
            return;
        }
        if (values.size() >= capacity) {
            Integer victim = null;
            int victimFreq = Integer.MAX_VALUE;
            long victimTouch = -1;
            // BUG 1: walks every live key on EVERY evicting put -- O(n).
            for (int k : values.keySet()) {
                int f = freqs.get(k);
                long t = lastTouched.get(k);
                // BUG 2: tie-break inverted -- should prefer the SMALLER t
                // (older = true LRU). ">" instead of "<" means among equal
                // frequencies it keeps overwriting `victim` with whichever
                // key was touched MOST recently -- it evicts the just-used
                // key and spares the actual least-recently-used one.
                if (f < victimFreq || (f == victimFreq && t > victimTouch)) {
                    victim = k; victimFreq = f; victimTouch = t;
                }
            }
            values.remove(victim);
            freqs.remove(victim);
            lastTouched.remove(victim);
        }
        values.put(key, value);
        freqs.put(key, 1);
        lastTouched.put(key, ++clock);
    }
}

Compile and run all three Java files together (javac LFUCache.java NaiveLFUCache.java LFUCacheTests.java && java LFUCacheTests):

public final class LFUCacheTests {

    static int pass = 0, fail = 0;

    static void check(String name, boolean cond) {
        if (cond) { pass++; System.out.println("PASS: " + name); }
        else      { fail++; System.out.println("FAIL: " + name); }
    }

    public static void main(String[] args) {

        // --- M1: capacity + basic eviction (the classic LeetCode 460 trace) ---
        {
            LFUCache c = new LFUCache(2);
            c.put(1, 1);                 // cache: {1:1(f1)}
            c.put(2, 2);                 // cache: {1:1(f1), 2:2(f1)}
            check("get(1) hits", c.get(1) == 1);           // 1 -> freq 2
            c.put(3, 3);                 // capacity full, evict min-freq: key 2 (freq1) vs key1(freq2) -> evict 2
            check("after put(3), key 2 was evicted (lowest freq)", c.get(2) == -1);
            check("key 1 survived (freq bumped by the earlier get)", c.get(1) == 1);
            check("key 3 present", c.get(3) == 3);
        }

        // --- M2: frequency actually protects a hot key under repeated pressure ---
        {
            LFUCache c = new LFUCache(2);
            c.put(1, 10);
            c.put(2, 20);
            c.get(1); c.get(1); c.get(1);           // key 1 freq = 4, well ahead
            c.put(3, 30);                            // evicts key 2 (freq 1), not key 1
            check("hot key 1 survives eviction pressure", c.get(1) == 10);
            check("cold key 2 was evicted", c.get(2) == -1);
            check("new key 3 present", c.get(3) == 30);
        }

        // --- M3: tie-break within a frequency is LRU (oldest untouched key), on the O(1) cache ---
        {
            LFUCache c = new LFUCache(3);
            c.put(1, 100);   // freq=1, oldest
            c.put(2, 200);   // freq=1
            c.put(3, 300);   // freq=1, newest
            // all three are still at freq=1 -- a tie. Correct LFU tie-breaks by
            // recency-within-frequency and evicts the OLDEST untouched one: key 1.
            c.put(4, 400);
            check("tie-break (correct): true LRU-among-ties (key 1) was evicted", c.get(1) == -1);
            check("tie-break (correct): key 2 (untouched, newer than 1) survives", c.get(2) == 200);
            check("tie-break (correct): key 3 (untouched, newest) survives", c.get(3) == 300);
        }

        // --- Break-it #1: same tie-break scenario on the NAIVE cache -- wrong victim ---
        {
            NaiveLFUCache c = new NaiveLFUCache(3);
            c.put(1, 100);   // freq=1, oldest
            c.put(2, 200);   // freq=1
            c.put(3, 300);   // freq=1, newest / just-used
            c.put(4, 400);   // triggers eviction among the freq=1 tie
            // THE BUG: NaiveLFUCache's inverted tie-break evicts the MOST
            // recently touched key among ties (key 3) instead of the true
            // LRU (key 1). This is "break it": the naive cache throws away
            // the item you JUST used and keeps the one nobody has touched
            // since it was inserted.
            boolean evictedTheJustUsedKey = (c.get(3) == -1);
            boolean keptTheTrueStaleKey   = (c.get(1) == 100);
            check("break-it: naive cache evicts the JUST-USED key 3 (wrong)", evictedTheJustUsedKey);
            check("break-it: naive cache KEEPS the true-stale key 1 (wrong)", keptTheTrueStaleKey);
            System.out.println("       -> contrast with M3 above: the O(1) LFUCache evicts key 1 (right),");
            System.out.println("          the naive cache evicts key 3 (wrong) -- same input, opposite victim.");
        }

        // --- Break-it #2: the O(n) scan under load -- measure the latency, don't just assert it ---
        {
            final int capacity = 2000;
            final int ops = 20_000;   // every key is unique -> every put past warm-up evicts

            LFUCache fast = new LFUCache(capacity);
            long t0 = System.nanoTime();
            for (int i = 0; i < ops; i++) fast.put(i, i);
            long fastNanos = System.nanoTime() - t0;

            NaiveLFUCache slow = new NaiveLFUCache(capacity);
            long t1 = System.nanoTime();
            for (int i = 0; i < ops; i++) slow.put(i, i);
            long slowNanos = System.nanoTime() - t1;

            double fastMs = fastNanos / 1_000_000.0;
            double slowMs = slowNanos / 1_000_000.0;
            double ratio = slowMs / fastMs;

            System.out.println();
            System.out.printf("       O(1) LFUCache:      %,d unique puts (capacity %,d) in %.2f ms%n", ops, capacity, fastMs);
            System.out.printf("       O(n) NaiveLFUCache:  %,d unique puts (capacity %,d) in %.2f ms%n", ops, capacity, slowMs);
            System.out.printf("       naive / O(1) ratio:  %.1fx slower%n", ratio);

            // A loose bound, not a tight one -- JIT/GC noise varies run to run,
            // but the O(n) scan must be substantially, measurably slower.
            check("break-it: naive O(n) scan is at least 3x slower under eviction pressure", ratio > 3.0);
        }

        System.out.println();
        System.out.println(pass + " passed, " + fail + " failed");
        if (fail > 0) System.exit(1);
    }
}

Measured in this session: all 13/13 assertions pass. The two break-it assertions are the whole point:

Go tells the same story with a much sharper gap. The Go twin of the same trap — save as naive_lfucache.go, same lfucache package as lfucache.go above:

package lfucache

// NaiveLFUCache is THE TRAP: a "just make it work" LFU. Correct-looking on
// paper, wrong in two concrete ways this page's break-it tests reproduce:
//  1. Eviction SCANS every live key to find the minimum frequency -- O(n)
//     per evicting Put, not O(1).
//  2. Its tie-break among equal-frequency keys is backwards: it means to
//     prefer evicting the LEAST-recently-touched candidate, but the
//     comparison got inverted, so among ties it keeps the true LRU and
//     evicts whichever key was touched MOST recently instead -- an easy,
//     realistic bug to write by accident.
//
// Kept here ONLY so the break-it section can demonstrate both failures
// against the real O(1) LFUCache above. Never use this in real code.
type NaiveLFUCache struct {
	capacity    int
	clock       int64
	values      map[int]int
	freqs       map[int]int
	lastTouched map[int]int64
}

func NewNaive(capacity int) *NaiveLFUCache {
	return &NaiveLFUCache{
		capacity:    capacity,
		values:      make(map[int]int),
		freqs:       make(map[int]int),
		lastTouched: make(map[int]int64),
	}
}

func (c *NaiveLFUCache) Get(key int) (int, bool) {
	v, ok := c.values[key]
	if !ok {
		return 0, false
	}
	c.freqs[key]++
	c.clock++
	c.lastTouched[key] = c.clock
	return v, true
}

func (c *NaiveLFUCache) Put(key, value int) {
	if c.capacity <= 0 {
		return
	}
	if _, ok := c.values[key]; ok {
		c.values[key] = value
		c.freqs[key]++
		c.clock++
		c.lastTouched[key] = c.clock
		return
	}
	if len(c.values) >= c.capacity {
		victim := -1
		victimFreq := int(^uint(0) >> 1) // max int
		var victimTouch int64 = -1
		// BUG 1: walks every live key on EVERY evicting Put -- O(n).
		for k := range c.values {
			f := c.freqs[k]
			t := c.lastTouched[k]
			// BUG 2: tie-break inverted -- should prefer the SMALLER t
			// (older = true LRU). ">" instead of "<" means among equal
			// frequencies it keeps overwriting `victim` with whichever key
			// was touched MOST recently -- it evicts the just-used key and
			// spares the actual least-recently-used one.
			if f < victimFreq || (f == victimFreq && t > victimTouch) {
				victim, victimFreq, victimTouch = k, f, t
			}
		}
		delete(c.values, victim)
		delete(c.freqs, victim)
		delete(c.lastTouched, victim)
	}
	c.values[key] = value
	c.freqs[key] = 1
	c.clock++
	c.lastTouched[key] = c.clock
}

Add this test file next to both (package lfucache) and run go test -race ./...:

package lfucache

import "testing"

// TestBasicEvictionByFrequency reproduces the classic LeetCode 460 trace.
func TestBasicEvictionByFrequency(t *testing.T) {
	c := New(2)
	c.Put(1, 1) // cache: {1:1(f1)}
	c.Put(2, 2) // cache: {1:1(f1), 2:2(f1)}
	if v, ok := c.Get(1); !ok || v != 1 {
		t.Fatalf("get(1) = %d,%v want 1,true", v, ok)
	} // key 1 -> freq 2
	c.Put(3, 3) // full: evict min-freq key 2 (freq1), key 1 is freq2
	if _, ok := c.Get(2); ok {
		t.Errorf("key 2 should have been evicted (lowest freq)")
	}
	if v, ok := c.Get(1); !ok || v != 1 {
		t.Errorf("key 1 should survive (freq bumped by the earlier get), got %d,%v", v, ok)
	}
	if v, ok := c.Get(3); !ok || v != 3 {
		t.Errorf("key 3 should be present, got %d,%v", v, ok)
	}
}

// TestHotKeySurvivesPressure proves frequency, not recency, decides eviction.
func TestHotKeySurvivesPressure(t *testing.T) {
	c := New(2)
	c.Put(1, 10)
	c.Put(2, 20)
	c.Get(1)
	c.Get(1)
	c.Get(1) // key 1 freq = 4, well ahead
	c.Put(3, 30) // evicts key 2 (freq 1), not key 1
	if v, ok := c.Get(1); !ok || v != 10 {
		t.Errorf("hot key 1 should survive eviction pressure, got %d,%v", v, ok)
	}
	if _, ok := c.Get(2); ok {
		t.Errorf("cold key 2 should have been evicted")
	}
}

// TestTieBreakIsLRUWithinFrequency is the correctness case break-it #1 contrasts with.
func TestTieBreakIsLRUWithinFrequency(t *testing.T) {
	c := New(3)
	c.Put(1, 100) // freq=1, oldest
	c.Put(2, 200) // freq=1
	c.Put(3, 300) // freq=1, newest
	// all three tied at freq=1 -- correct LFU tie-breaks by recency-within-
	// frequency and evicts the OLDEST untouched one: key 1.
	c.Put(4, 400)
	if _, ok := c.Get(1); ok {
		t.Errorf("tie-break: true LRU-among-ties (key 1) should have been evicted")
	}
	if v, ok := c.Get(2); !ok || v != 200 {
		t.Errorf("tie-break: key 2 should survive, got %d,%v", v, ok)
	}
	if v, ok := c.Get(3); !ok || v != 300 {
		t.Errorf("tie-break: key 3 should survive, got %d,%v", v, ok)
	}
}

// TestBreakIt_NaiveTieBreakEvictsJustUsedKey is the failure lesson: run the
// IDENTICAL scenario as TestTieBreakIsLRUWithinFrequency against the naive,
// O(n)/inverted-tie-break cache and show it picks the OPPOSITE, wrong victim.
func TestBreakIt_NaiveTieBreakEvictsJustUsedKey(t *testing.T) {
	c := NewNaive(3)
	c.Put(1, 100) // freq=1, oldest
	c.Put(2, 200) // freq=1
	c.Put(3, 300) // freq=1, newest / just-used
	c.Put(4, 400) // triggers eviction among the freq=1 tie

	_, key3Present := c.Get(3)
	_, key1Present := c.Get(1)
	if key3Present {
		t.Errorf("break-it: expected the naive cache's inverted tie-break to evict key 3 (the just-used key), but it is still present")
	}
	if !key1Present {
		t.Errorf("break-it: expected the naive cache to WRONGLY keep key 1 (the true LRU), but it was evicted")
	}
	t.Logf("break-it confirmed: naive cache evicted key 3 (just-used) and kept key 1 (true LRU) -- backwards from TestTieBreakIsLRUWithinFrequency")
}

Measured in this session: go build ./... and go vet ./... are clean; go test ./... passes 4/4, and go test -race ./... reports zero races. TestBreakIt_NaiveTieBreakEvictsJustUsedKey reproduces the exact same wrong-victim bug as the Java version, on the identical scenario.

For the latency half of the break-it, a small standalone program times both caches head-to-head — put it at cmd/breakit/main.go in the same module:

// Command breakit measures the O(n)-scan trap for real: it hammers both the
// O(1) LFUCache and the O(n) NaiveLFUCache with the same eviction-heavy
// workload (every key unique, so every put past warm-up evicts) and prints
// the wall-clock gap.
//
//	go run ./cmd/breakit
package main

import (
	"fmt"
	"time"

	"lfucache"
)

func main() {
	const capacity = 2000
	const ops = 20_000 // every key is unique -> every put past warm-up evicts

	fast := lfucache.New(capacity)
	t0 := time.Now()
	for i := 0; i < ops; i++ {
		fast.Put(i, i)
	}
	fastDur := time.Since(t0)

	slow := lfucache.NewNaive(capacity)
	t1 := time.Now()
	for i := 0; i < ops; i++ {
		slow.Put(i, i)
	}
	slowDur := time.Since(t1)

	ratio := float64(slowDur) / float64(fastDur)

	fmt.Printf("O(1)  LFUCache:      %d unique puts (capacity %d) in %v\n", ops, capacity, fastDur)
	fmt.Printf("O(n)  NaiveLFUCache: %d unique puts (capacity %d) in %v\n", ops, capacity, slowDur)
	fmt.Printf("naive / O(1) ratio:  %.1fx slower\n", ratio)

	if ratio < 3.0 {
		fmt.Printf("UNEXPECTED: ratio %.1fx is below the 3x floor this break-it demo expects\n", ratio)
	}
}

Measured in this session (go run ./cmd/breakit, run twice): the O(1) LFUCache did the 20,000-put eviction-heavy workload in ~3.8–4.1 ms; the O(n) NaiveLFUCache took ~700–702 ms — a ~170–183× slower naive path. The gap is far larger than Java's ~20× on the exact same algorithmic difference — a good reminder that "same big-O gap" doesn't mean "same wall-clock gap": Go's plain map iteration for the O(n) scan carries more per-key overhead than Java's HashMap iteration does, so the identical O(n) mistake costs noticeably more here. The lesson is the same either way — O(n) eviction is a real, measurable tax that gets worse as capacity grows, not a theoretical footnote.

Optimise — with trade-offs

DecisionOption AOption BWhen A winsWhen B wins
Eviction signalLFU (evict lowest access count)LRU (evict least-recently-touched)Popularity is genuinely stable — a fixed hot set (a handful of celebrity profiles, top-selling SKUs, hot config rows) that keeps getting re-requested; frequency predicts future reuse better than "was it touched in the last N requests"Access patterns are recency-driven — a user's working set shifts over a session, a scan walks through data once. LRU is also simpler: no counters, no tie-break logic, and it doesn't suffer LFU's core weakness below
Handling stale popularityClassic LFU (counts never decay)LFU-with-aging (counts decay over time, e.g. halved every N ops or by an exponential time-weighted formula)The workload has no "yesterday's viral item" problem — popularity, once earned, genuinely stays relevant (e.g. reference/config data that really is permanently hot)Cache pollution is the classic LFU failure mode: an item that was extremely popular once (say frequency 10,000 from a one-day traffic spike) but hasn't been touched since is immortal under classic LFU — nothing ever lowers its count, so it permanently outranks every currently-trending item in the min-frequency comparison and can never be evicted on its own merits. Aging fixes this by periodically deflating counts so old fame fades and the bucket structure reflects recent popularity, not all-time popularity. Cost: one more tuning knob (decay rate) — too aggressive and you've reinvented LRU with extra steps; too slow and pollution still happens, just later
Counting mechanism at scaleExact per-key counts (this kata's freqMap, real LFU)Approximate sketch-based counts (a Count-Min Sketch, as used by Caffeine)The key space is bounded and modest — the exact design here, or a LeetCode-460-style interview answer, where correctness and auditability of the count matter and memory for one integer per live key is cheapThe cache has seen (and evicted) far more distinct keys over its lifetime than it currently holds — exact counts either grow unboundedly (if you never forget evicted keys' history) or lose all history the instant a key is evicted (if you do). A fixed-size probabilistic sketch approximates "how often has this key ever been seen," in constant memory, independent of how many distinct keys have ever passed through
Overall policyPure single-signal policy (plain LFU or plain LRU, this kata's LFUCache)W-TinyLFU (Caffeine's admission-filter hybrid)You need to reason about and defend one clean mechanism — simplicity is worth more than squeezing out the last few points of hit ratio, and you control the whole workload shape (this is exactly why it's the right kata/interview answer)You're building a general-purpose, high-throughput cache library that has to behave well under any workload, including adversarial ones. See below — W-TinyLFU adds a frequency-based admission gate in front of an LRU-based eviction policy, getting near-optimal hit ratios in small, constant memory and resisting one-off scan pollution that plain LRU can't

How Caffeine's W-TinyLFU actually improves on classic LFU

It is not "LFU, but faster" — it's a genuinely different architecture that borrows LFU's signal (frequency) without inheriting its bookkeeping cost or its pollution problem:

Defend under drilling

You can now defend

Re-authored/Deepened for this guide. Related theory: Cache Replacement — How Each Policy Actually Works. Reference implementations (Java + Go) compiled and tested in-session: javac clean, 13/13 assertions pass (including both deliberately-adversarial break-it assertions — the wrong-tie-break demonstration and the O(n)-vs-O(1) latency measurement, ~20–23× slower for the naive scan across repeated runs); go build + go vet + go test -race clean, 4/4 tests pass with zero races, and the separate cmd/breakit benchmark measured ~170–183× slower for the naive O(n) scan across repeated runs.

🤖 Don't fully get this? Learn it with Claude

Stuck on Design an LFU Cache? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Design an LFU Cache** (Hands-On Builds) and want to truly understand it. Explain Design an LFU Cache from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Design an LFU Cache** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Design an LFU Cache** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Design an LFU Cache** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Design a Deck of Cards & BlackjackDesign Tic-Tac-Toe →