SyntaxPilot
Courses/Low-Level Design/Lesson 66
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Low-Level Design · Lesson 66 of 90

Design an LFU cache and a pluggable cache library

LFUfrequency mapminimum frequency trackingtie-breaking by recencyEvictionPolicy interfaceStorage interfacepluggable policieswrite-through vs write-backcache statisticsTTL support

These are the notes for Low-Level Design (LLD) episode 66. Last episode's LRU cache has one weak spot: a scan. Today we watch one reader empty an LRU cache, invent the LFU (least frequently used) cache with a frequency map and minimum frequency tracking, see the crash you get when you forget one line, and settle ties with tie-breaking by recency. Then we turn it into a small cache library: an EvictionPolicy interface and a Storage interface so policies are pluggable, cache statistics, write-through vs write-back, and TTL support.

How the code was run: every program was saved as Main.java in a fresh folder and run with javac Main.java && java -cp . Main on OpenJDK 21. Every output below is the real output, pasted exactly. The news app, pages and numbers are made up for teaching.

1. The problem: one reader empties the cache

A news app caches 3 pages. All day thousands of readers open the same three: home, cricket, weather. Then one reader opens three old pages from the archive, each once. A scan means going through many items one time each.

import java.util.*;
public class Main {
    static Map<String, String> lru = new LinkedHashMap<>(16, 0.75f, true) {     // last episode's LRU
        protected boolean removeEldestEntry(Map.Entry<String, String> e) { return size() > 3; } };
    static int misses = 0;
    static void visit(List<String> pages) {
        for (String page : pages)
            if (lru.get(page) == null) { misses++;  lru.put(page, "<html of " + page + ">"); }
    }
    public static void main(String[] args) {
        List<String> favourites = List.of("home", "cricket", "weather");
        for (int i = 0; i < 5; i++) visit(favourites);                  // read all day, 5 times each
        visit(List.of("old1", "old2", "old3"));                         // ONE reader scans the archive, once
        System.out.println("after the scan: " + lru.keySet());
        misses = 0;  visit(favourites);
        System.out.println("favourites again: " + misses + " misses out of 3");
    }
}

Real output:

after the scan: [old1, old2, old3]
favourites again: 3 misses out of 3

Why it failed: LRU remembers only when each page was used, never how often. The scan made three one-off pages the most recent, so they pushed out every favourite. The next readers all missed.

2. LFU: least frequently used

  • Frequency: how many times a key has been used (each get hit or put adds one).
  • LFU (Least Frequently Used): when full, evict the key with the smallest frequency.
  • Tie-breaking by recency: when several keys share the smallest frequency, evict the least recently used of them.

The obvious LFU walks all keys to find the smallest count: O(n) per eviction. We want O(1).

3. LFU in O(1): the frequency map, buckets and minFreq

Three maps and one number:

Structure Holds Example
vals key → value home → <html>
freq (the frequency map) key → uses home → 5
byFreq (buckets) uses → keys with that many uses, oldest first (LinkedHashSet) 5 → [home, cricket, weather]
minFreq the smallest frequency present 5
capacity 3, after the favourites (5 uses each):

  vals    {home, cricket, weather}
  freq    {home=5, cricket=5, weather=5}
  byFreq  5 → [home, cricket, weather]     oldest first
  minFreq 5

put(old1):  full → victim = byFreq[minFreq].first() = home
            old1 is new → freq 1, byFreq 1 → [old1]
            minFreq = 1   ← a new key is ALWAYS the least used

Minimum frequency tracking:

  • Evict: the victim is the first key in byFreq[minFreq]: no search, O(1). Because each bucket keeps insertion order, the first key is the one that reached this frequency earliest: that's the tie-break by recency.
  • Use (bump): move the key from bucket f to f + 1; if bucket f was the minimum and is now empty, minFreq++.
  • Insert a new key: frequency 1, so minFreq = 1 (nothing can be smaller).

4. The forgotten line

The same LFUCache without minFreq = 1 on insert:

import java.util.*;
class LFUCache<K, V> {
    private final int capacity;  private int minFreq = 0;
    private final Map<K, V> vals = new HashMap<>();
    private final Map<K, Integer> freq = new HashMap<>();                     // key → how many uses
    private final Map<Integer, LinkedHashSet<K>> byFreq = new HashMap<>();    // uses → keys, oldest first
    LFUCache(int capacity) { this.capacity = capacity; }
    private void bump(K key) {                                                // one more use
        int f = freq.get(key);  freq.put(key, f + 1);  byFreq.get(f).remove(key);
        if (f == minFreq && byFreq.get(f).isEmpty()) minFreq++;
        byFreq.computeIfAbsent(f + 1, x -> new LinkedHashSet<>()).add(key); }
    V get(K key) { if (!vals.containsKey(key)) return null;  bump(key);  return vals.get(key); }
    void put(K key, V val) {
        if (vals.containsKey(key)) { vals.put(key, val);  bump(key);  return; }
        if (vals.size() == capacity) {
            K victim = byFreq.get(minFreq).iterator().next();                 // least used; tie → oldest
            byFreq.get(minFreq).remove(victim);  vals.remove(victim);  freq.remove(victim);
            System.out.println("  evict " + victim + " (used " + minFreq + "x)"); }
        vals.put(key, val);  freq.put(key, 1);                                // a new key: used once
        byFreq.computeIfAbsent(1, x -> new LinkedHashSet<>()).add(key); }
    public String toString() { return "uses " + freq; } }
public class Main { public static void main(String[] args) {
    LFUCache<String, String> c = new LFUCache<>(3);  int misses = 0;
    List<String> fav = List.of("home", "cricket", "weather");
    for (int i = 0; i < 5; i++) for (String p : fav) if (c.get(p) == null) c.put(p, p);
    for (String p : List.of("old1", "old2", "old3")) if (c.get(p) == null) c.put(p, p);
    for (String p : fav) if (c.get(p) == null) misses++;
    System.out.println(c + "\nfavourites again: " + misses + " misses out of 3"); }}

Real output:

Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.util.LinkedHashSet.iterator()" because the return value of "java.util.Map.get(Object)" is null
    at LFUCache.put(Main.java:16)
    at Main.main(Main.java:26)

minFreq was still 0, there is no bucket 0, so byFreq.get(0) returned null and .iterator() threw a NullPointerException on the first eviction.

5. LFU fixed

import java.util.*;
class LFUCache<K, V> {
    private final int capacity;  private int minFreq = 0;
    private final Map<K, V> vals = new HashMap<>();
    private final Map<K, Integer> freq = new HashMap<>();                     // key → how many uses
    private final Map<Integer, LinkedHashSet<K>> byFreq = new HashMap<>();    // uses → keys, oldest first
    LFUCache(int capacity) { this.capacity = capacity; }
    private void bump(K key) {                                                // one more use
        int f = freq.get(key);  freq.put(key, f + 1);  byFreq.get(f).remove(key);
        if (f == minFreq && byFreq.get(f).isEmpty()) minFreq++;
        byFreq.computeIfAbsent(f + 1, x -> new LinkedHashSet<>()).add(key); }
    V get(K key) { if (!vals.containsKey(key)) return null;  bump(key);  return vals.get(key); }
    void put(K key, V val) {
        if (vals.containsKey(key)) { vals.put(key, val);  bump(key);  return; }
        if (vals.size() == capacity) {
            K victim = byFreq.get(minFreq).iterator().next();                 // least used; tie → oldest
            byFreq.get(minFreq).remove(victim);  vals.remove(victim);  freq.remove(victim);
            System.out.println("  evict " + victim + " (used " + minFreq + "x)"); }
        vals.put(key, val);  freq.put(key, 1);  minFreq = 1;                  // a new key: used once
        byFreq.computeIfAbsent(1, x -> new LinkedHashSet<>()).add(key); }
    public String toString() { return "uses " + freq; } }
public class Main { public static void main(String[] args) {
    LFUCache<String, String> c = new LFUCache<>(3);  int misses = 0;
    List<String> fav = List.of("home", "cricket", "weather");
    for (int i = 0; i < 5; i++) for (String p : fav) if (c.get(p) == null) c.put(p, p);
    for (String p : List.of("old1", "old2", "old3")) if (c.get(p) == null) c.put(p, p);
    for (String p : fav) if (c.get(p) == null) misses++;
    System.out.println(c + "\nfavourites again: " + misses + " misses out of 3"); }}

Real output:

  evict home (used 5x)
  evict old1 (used 1x)
  evict old2 (used 1x)
uses {cricket=6, weather=6, old3=1}
favourites again: 1 misses out of 3
  • evict home (used 5x): all three favourites had 5 uses (a tie); home reached 5 first, so it is the least recent of them.
  • old1 and old2 (1 use each) then evict each other: the one-off pages fight among themselves.
  • Favourites again: 1 miss out of 3 instead of 3 out of 3.
Operation Steps Cost
get vals lookup + bump O(1)
put existing update + bump O(1)
put new, full first of byFreq[minFreq] → remove from 3 maps → insert with freq 1, minFreq = 1 O(1)

6. A pluggable cache library

Two caches (LRU, LFU) meant two copies of almost the same get/put. So we pull out what changes:

  • EvictionPolicy interface: used(k) on every use, removed(k), and victim(): who leaves?
  • Storage interface: where values live: get, put, remove, size. A HashMap today; a file, or a remote server tomorrow.
  • Pluggable policies: the cache is given a policy (and a storage) from outside; swapping one never changes the cache. This is the Strategy pattern (episode 34) plus dependency injection (episode 16).
  • Cache statistics: counters for hits, misses and evictions; hit rate = hits ÷ (hits + misses).
import java.util.*;
interface Storage<K, V> { V get(K k);  void put(K k, V v);  void remove(K k);  int size(); }
class MapStorage<K, V> implements Storage<K, V> {  private final Map<K, V> m = new HashMap<>();
    public V get(K k) { return m.get(k); }     public void put(K k, V v) { m.put(k, v); }
    public void remove(K k) { m.remove(k); }   public int size() { return m.size(); } }
interface EvictionPolicy<K> { void used(K k);  void removed(K k);  K victim(); }
class LRUPolicy<K> implements EvictionPolicy<K> {  private final LinkedHashSet<K> order = new LinkedHashSet<>();
    public void used(K k) { order.remove(k);  order.add(k); }   public void removed(K k) { order.remove(k); }
    public K victim() { return order.iterator().next(); } }                   // least recently used
class LFUPolicy<K> implements EvictionPolicy<K> {  private final Map<K, Integer> uses = new LinkedHashMap<>();
    public void used(K k) { uses.merge(k, 1, Integer::sum); }   public void removed(K k) { uses.remove(k); }
    public K victim() { return Collections.min(uses.entrySet(), Map.Entry.comparingByValue()).getKey(); } }
class Cache<K, V> {  final Storage<K, V> store;  final EvictionPolicy<K> policy;  final int cap;  // library
    int hits, misses, evictions;
    Cache(int c, Storage<K, V> s, EvictionPolicy<K> e) { cap = c;  store = s;  policy = e; }
    V get(K k) { V v = store.get(k);  if (v == null) misses++;  else { hits++;  policy.used(k); }  return v; }
    void put(K k, V v) {
        if (store.get(k) == null && store.size() == cap) {
            K out = policy.victim();  store.remove(out);  policy.removed(out);  evictions++; }
        store.put(k, v);  policy.used(k); }
    String stats() { return "hits " + hits + ", misses " + misses + ", evictions " + evictions; } }
public class Main { public static void main(String[] args) {
    String fav = "home cricket weather ";                                    // same day as before
    List<String> day = List.of((fav.repeat(5) + "old1 old2 old3 " + fav).split(" "));
    for (EvictionPolicy<String> p : List.<EvictionPolicy<String>>of(new LRUPolicy<>(), new LFUPolicy<>())) {
        Cache<String, String> c = new Cache<>(3, new MapStorage<>(), p);          // plug in a policy
        for (String page : day) if (c.get(page) == null) c.put(page, "<" + page + ">");
        System.out.println(p.getClass().getSimpleName() + ": " + c.stats()); } }}

Real output:

LRUPolicy: hits 12, misses 9, evictions 6
LFUPolicy: hits 14, misses 7, evictions 4

Same Cache class, one argument changed. The statistics show LFU fits this workload better. (This simple LFUPolicy finds its victim with Collections.min, which is O(n); the mini project plugs in the O(1) bucket version.)

7. Write-through vs write-back, and TTL support

  • Write-through: every write goes to the cache and the database at once. Always safe; every write pays the slow database.
  • Write-back (also "write-behind"): write only the cache and mark the key dirty (changed but not yet saved). A flush later writes all dirty keys. Fast, and five quick updates become one database write, but a crash before the flush loses the dirty data.
  • TTL (time to live): each entry gets expiresAt = now + ttl; at or after that time, get treats it as a miss.
  • Clock injection: the cache asks a LongSupplier (a function returning a long) for the time, so a test can move time by hand instead of sleeping.
Write-through Write-back
Database writes for 5 quick updates 5 1 (at flush)
Speed of a write Slow (waits for the DB) Fast (memory only)
Crash before flush Nothing lost Dirty data lost
Good for Money, orders Counters, likes, views
import java.util.*;
import java.util.function.LongSupplier;
class Db { final Map<String, Integer> rows = new HashMap<>();  int writes = 0;
    void save(String k, int v) { rows.put(k, v);  writes++; } }
class WriteCache {  record Entry(int value, long expiresAt) {}     // a cache that also takes WRITES
    final Map<String, Entry> map = new HashMap<>();  final Set<String> dirty = new HashSet<>();
    final Db db;  final boolean writeBack;  final long ttl;  final LongSupplier clock;
    WriteCache(Db db, boolean writeBack, long ttl, LongSupplier clock) {
        this.db = db;  this.writeBack = writeBack;  this.ttl = ttl;  this.clock = clock; }
    void put(String k, int v) {
        map.put(k, new Entry(v, clock.getAsLong() + ttl));
        if (writeBack) dirty.add(k);                // write-back: the database later
        else db.save(k, v); }                       // write-through: the database now
    void flush() { for (String k : dirty) db.save(k, map.get(k).value());  dirty.clear(); }
    Integer get(String k) { Entry e = map.get(k);
        if (e == null || clock.getAsLong() >= e.expiresAt()) return null;   // TTL: too old = a miss
        return e.value(); } }
public class Main { public static void main(String[] args) {
    long[] now = {0};  Db a = new Db(), b = new Db();      // a fake clock we can move by hand
    WriteCache through = new WriteCache(a, false, 60, () -> now[0]);  // TTL 60 seconds
    WriteCache back = new WriteCache(b, true, 60, () -> now[0]);
    for (int i = 1; i <= 5; i++) { through.put("likes", i);  back.put("likes", i); }   // 5 quick updates
    System.out.println("write-through: " + a.writes + " db writes, db " + a.rows);
    System.out.println("write-back:    " + b.writes + " db writes, db " + b.rows + "  <- crash now = lost");
    back.flush();  System.out.println("after flush:   " + b.writes + " db write,  db " + b.rows);
    through.put("score", 42);
    now[0] = 59;  System.out.println("at 59 s: score " + through.get("score"));
    now[0] = 60;  System.out.println("at 60 s: score " + through.get("score") + "  (TTL 60 s: expired)"); }}

Real output:

write-through: 5 db writes, db {likes=5}
write-back:    0 db writes, db {}  <- crash now = lost
after flush:   1 db write,  db {likes=5}
at 59 s: score 42
at 60 s: score null  (TTL 60 s: expired)

8. The class diagram

Cache<K, V>  (the library)
 ├─has──▶ Storage<K, V>        get · put · remove · size   (MapStorage, a file, Redis-like...)
 ├─has──▶ EvictionPolicy<K>    used · removed · victim     (LRUPolicy, LFUPolicy, FIFO...)
 ├─has──▶ stats                hits · misses · evictions → hit rate
 ├─has──▶ TTL + clock          expiresAt = now + ttl; too old = a miss
 └─has──▶ write mode           write-through (db now) · write-back (dirty → flush)
LFUCache:  vals + freq + byFreq (freq → LinkedHashSet) + minFreq   O(1)

9. Interview follow-ups

Follow-up Answer
A page popular last year keeps a huge count forever Aging: halve every count now and then, so old popularity fades
Keep LRU but survive scans Two lists: a new item must be used twice before it joins the main list (the idea behind "2Q" / segmented LRU)
Thread safety One lock for get and put, or shards with a lock each
Write-back durability Flush on a timer and on shutdown (practice 4); for critical data use write-through
Expired entries nobody reads again A background sweep removes them
Code wants to know when items leave An eviction listener: the Observer pattern (episode 35)

10. Common mistakes

Mistake What you see (real) Why Fix
LRU for scan-heavy traffic favourites again: 3 misses out of 3 Recency only LFU, or a scan-resistant LRU
minFreq not reset on a new key NullPointerException: Cannot invoke "java.util.LinkedHashSet.iterator()" because the return value of "java.util.Map.get(Object)" is null Bucket 0 doesn't exist minFreq = 1 on insert
Scanning all keys for the minimum O(n) on every eviction No buckets freq → LinkedHashSet + minFreq
Policy code written inside the cache A copy of get/put per policy No interface EvictionPolicy plugged in
Write-back with no flush 0 db writes, db {} Dirty data only in memory Flush on a timer and on shutdown
Reading the real clock in tests Tests must sleep 60 s Hidden dependency on time Inject a LongSupplier clock

Mini project: the complete cache library

Three policies (FIFO, LRU, and the O(1) LFU as a plug-in), storage behind an interface, statistics, TTL and an injected clock, thread-safe methods.

import java.util.*;
import java.util.function.LongSupplier;

// ---------- Storage: where values live ----------
interface Storage<K, V> { V get(K k);  void put(K k, V v);  void remove(K k);  int size(); }
class MapStorage<K, V> implements Storage<K, V> {
    private final Map<K, V> m = new HashMap<>();
    public V get(K k) { return m.get(k); }   public void put(K k, V v) { m.put(k, v); }
    public void remove(K k) { m.remove(k); } public int size() { return m.size(); }
}

// ---------- Eviction policies: who leaves ----------
interface EvictionPolicy<K> { void used(K k);  void removed(K k);  K victim(); }
class FIFOPolicy<K> implements EvictionPolicy<K> {                    // order of first arrival
    private final LinkedHashSet<K> order = new LinkedHashSet<>();
    public void used(K k) { order.add(k); }                           // add() keeps the old position
    public void removed(K k) { order.remove(k); }
    public K victim() { return order.iterator().next(); }
}
class LRUPolicy<K> implements EvictionPolicy<K> {
    private final LinkedHashSet<K> order = new LinkedHashSet<>();
    public void used(K k) { order.remove(k);  order.add(k); }
    public void removed(K k) { order.remove(k); }
    public K victim() { return order.iterator().next(); }
}
class LFUPolicy<K> implements EvictionPolicy<K> {                     // O(1): buckets + minFreq
    private final Map<K, Integer> freq = new HashMap<>();
    private final Map<Integer, LinkedHashSet<K>> byFreq = new HashMap<>();
    private int minFreq = 0;
    public void used(K k) {
        Integer f = freq.get(k);
        if (f == null) { freq.put(k, 1);  bucket(1).add(k);  minFreq = 1;  return; }
        freq.put(k, f + 1);  bucket(f).remove(k);
        if (f == minFreq && bucket(f).isEmpty()) minFreq++;
        bucket(f + 1).add(k);
    }
    public void removed(K k) {
        Integer f = freq.remove(k);
        if (f != null) bucket(f).remove(k);
    }
    public K victim() {
        while (bucket(minFreq).isEmpty()) minFreq++;                  // after removals the min may move up
        return bucket(minFreq).iterator().next();
    }
    private LinkedHashSet<K> bucket(int f) { return byFreq.computeIfAbsent(f, x -> new LinkedHashSet<>()); }
}

// ---------- The library ----------
class Cache<K, V> {
    private record Entry<V>(V value, long expiresAt) {}
    private final Storage<K, Entry<V>> store;  private final EvictionPolicy<K> policy;
    private final int capacity;  private final long ttl;  private final LongSupplier clock;
    private long hits, misses, evictions, expired;
    Cache(int capacity, Storage<K, Entry<V>> store, EvictionPolicy<K> policy, long ttl, LongSupplier clock) {
        this.capacity = capacity;  this.store = store;  this.policy = policy;  this.ttl = ttl;  this.clock = clock;
    }
    static <K, V> Cache<K, V> of(int capacity, EvictionPolicy<K> policy, long ttl, LongSupplier clock) {
        return new Cache<>(capacity, new MapStorage<>(), policy, ttl, clock);
    }
    synchronized Optional<V> get(K k) {
        Entry<V> e = store.get(k);
        if (e != null && clock.getAsLong() >= e.expiresAt()) { store.remove(k);  policy.removed(k);  expired++;  e = null; }
        if (e == null) { misses++;  return Optional.empty(); }
        hits++;  policy.used(k);
        return Optional.of(e.value());
    }
    synchronized void put(K k, V v) {
        if (store.get(k) == null && store.size() == capacity) {
            K out = policy.victim();  store.remove(out);  policy.removed(out);  evictions++;
        }
        store.put(k, new Entry<>(v, clock.getAsLong() + ttl));  policy.used(k);
    }
    synchronized String stats() {
        return String.format("hits %d, misses %d, evictions %d, expired %d, hit rate %.0f%%",
                             hits, misses, evictions, expired, 100.0 * hits / Math.max(1, hits + misses));
    }
}

public class Main {
    public static void main(String[] args) {
        long[] now = {0};
        String fav = "home cricket weather ";
        List<String> day = List.of((fav.repeat(5) + "old1 old2 old3 " + fav).split(" "));
        List<EvictionPolicy<String>> policies = List.of(new FIFOPolicy<>(), new LRUPolicy<>(), new LFUPolicy<>());
        for (EvictionPolicy<String> p : policies) {
            Cache<String, String> c = Cache.of(3, p, 1_000, () -> now[0]);
            for (String page : day) if (c.get(page).isEmpty()) c.put(page, "<" + page + ">");
            System.out.printf("%-10s %s%n", p.getClass().getSimpleName(), c.stats());
        }
        Cache<String, String> c = Cache.of(3, new LFUPolicy<>(), 60, () -> now[0]);
        c.put("score", "42");
        now[0] = 30;  System.out.println("t=30 " + c.get("score"));
        now[0] = 90;  System.out.println("t=90 " + c.get("score") + "  " + c.stats());
    }
}

Real output:

FIFOPolicy hits 12, misses 9, evictions 6, expired 0, hit rate 57%
LRUPolicy  hits 12, misses 9, evictions 6, expired 0, hit rate 57%
LFUPolicy  hits 14, misses 7, evictions 4, expired 0, hit rate 67%
t=30 Optional[42]
t=90 Optional.empty  hits 1, misses 1, evictions 0, expired 1, hit rate 50%

On this workload FIFO and LRU behave the same (the favourites are always the oldest and least recent before the scan), and LFU wins. The TTL entry is a hit at t = 30 and expired at t = 90.

Practice

1. Plug the O(1) LFU in as a policy. 2. Add a FIFO policy. 3. Add TTL to the library Cache.

Answer (1, 2 and 3)

All three are in the mini project: LFUPolicy with buckets and minFreq (note victim() moves minFreq up past buckets emptied by removals), FIFOPolicy where used() is just add() (a LinkedHashSet keeps the first position), and Entry(value, expiresAt) with the injected clock. Real output above.

4. Make a write-back cache flush every 200 ms, and once more on shutdown.

Answer
import java.util.*;
import java.util.concurrent.*;

// Practice: a write-back cache that flushes every 200 ms and once more on shutdown.
class WriteBackCache {
    private final Map<String, Integer> map = new HashMap<>(), db = new HashMap<>();
    private final Set<String> dirty = new HashSet<>();
    private int dbWrites = 0;
    private final ScheduledExecutorService timer = Executors.newSingleThreadScheduledExecutor();
    WriteBackCache() { timer.scheduleAtFixedRate(this::flush, 200, 200, TimeUnit.MILLISECONDS); }
    synchronized void put(String k, int v) { map.put(k, v);  dirty.add(k); }
    synchronized void flush() { for (String k : dirty) { db.put(k, map.get(k));  dbWrites++; }  dirty.clear(); }
    synchronized String db() { return dbWrites + " db writes, db " + db; }
    void shutdown() { timer.shutdown();  flush(); }                     // never lose the last changes
}
public class Main {
    public static void main(String[] args) throws InterruptedException {
        WriteBackCache c = new WriteBackCache();
        for (int i = 1; i <= 1000; i++) c.put("likes", i);             // 1000 quick updates
        System.out.println("right away: " + c.db());
        Thread.sleep(300);                                            // the timer flushed once
        System.out.println("after 300 ms: " + c.db());
        c.put("likes", 1001);  c.put("views", 7);
        c.shutdown();
        System.out.println("after shutdown: " + c.db());
    }
}

Real output:

right away: 0 db writes, db {}
after 300 ms: 1 db writes, db {likes=1000}
after shutdown: 3 db writes, db {views=7, likes=1001}

1000 updates became one database write. The shutdown flush saved the last two changes, which would otherwise be lost.

5. Why does LFU need LinkedHashSet buckets, not HashSet?

Answer

To break ties by recency. A LinkedHashSet remembers insertion order, so the first key in a bucket is the one that reached that frequency earliest. A HashSet has no order, so the "victim" would be arbitrary.

Quick quiz

LFU cache, capacity 2: put(a) put(b) get(a) get(b) put(c). Which key is evicted? (a) a (b) b (c) c (d) nobody

Answer

(a) a. Both have 2 uses, a tie; a reached 2 first, so it's first in bucket 2. Real LFUCache run:

  evict a (used 2x)
uses {b=2, c=1}

Interview questions

  1. Design an LFU cache with O(1) get and put. vals, freq, byFreq (frequency → LinkedHashSet), and minFreq; victim = first of byFreq[minFreq]; new key → freq 1, minFreq = 1.
  2. How are ties broken? By recency within the same frequency: the bucket keeps insertion order.
  3. When is LFU better than LRU, and when worse? Better with stable popular items and scans; worse when popularity shifts, because old counts linger (fix: aging).
  4. How would you make the eviction policy pluggable? An EvictionPolicy interface (used, removed, victim) injected into the cache: the Strategy pattern.
  5. Why a Storage interface? So the same cache logic can sit on memory, disk or a remote store, and tests can use a fake.
  6. Write-through or write-back? Write-through for data you can't lose; write-back for high write rates where losing a few updates is acceptable, with regular flushes.
  7. How do you implement TTL? Store expiresAt per entry; check on get (lazy expiry), plus an optional background sweep.
  8. How do you test TTL without waiting? Inject the clock.
  9. What statistics would you expose? Hits, misses, evictions, expirations, hit rate, load time.
  10. How do you make the library thread-safe? Synchronize get/put (policies change state on every use), or shard.

Glossary

Term Meaning, with an example
Scan Going through many items once each: three archive pages read one time
Frequency How many times a key was used: home → 5
LFU Least frequently used: evict the key with the fewest uses
Frequency map key → use count: freq
Frequency bucket All keys with the same count: byFreq[5] = [home, cricket, weather]
Minimum frequency tracking Keeping minFreq, the smallest count present, so the victim is found in O(1)
minFreq The smallest frequency in the cache; reset to 1 on every new key
Tie-breaking by recency Among equal counts, evict the least recently used
LinkedHashSet A set that remembers insertion order
NullPointerException Calling a method on null: byFreq.get(0).iterator()
Eviction policy The rule that picks who leaves
EvictionPolicy interface used(k), removed(k), victim(): one class per policy
Storage interface get, put, remove, size: where values live
Pluggable policies Passing a policy object in, so swapping it never changes the cache
Strategy pattern A family of interchangeable algorithms behind one interface (episode 34)
Dependency injection Giving an object its collaborators from outside (episode 16)
Cache statistics Counters: hits, misses, evictions, expirations
Hit rate hits ÷ (hits + misses): 14 of 21 = 67%
Write-through Write the cache and the database at once
Write-back Write the cache, mark dirty, save to the database later
Write-through vs write-back Safe and slow vs fast with a risk of losing dirty data
Dirty Changed in the cache but not yet saved to the database
Flush Write all dirty entries to the database
TTL Time to live: an entry expires ttl after it was written
TTL support expiresAt = now + ttl; expired entries are misses
Clock injection Passing in the time source (LongSupplier) so tests can move time
LongSupplier A function that takes nothing and returns a long: () -> now[0]
Aging Periodically shrinking counts so old popularity fades
Eviction listener A callback told whenever an item leaves (Observer)

Summary

  • One scan emptied the LRU cache: [old1, old2, old3], 3 misses out of 3.
  • LFU evicts the least frequently used; ties go to the least recent.
  • O(1) LFU: vals + frequency map + buckets (LinkedHashSet) + minFreq; a new key sets minFreq = 1, or the first eviction throws a NullPointerException.
  • A library: EvictionPolicy and Storage interfaces make policies pluggable; statistics compare them (LRU 12 hits vs LFU 14).
  • Write-through (safe) vs write-back (fast, flush or lose); TTL with an injected clock.

Next episode: Design a logging framework: loggers, log levels, appenders, formatters and asynchronous logging.