LFU Cache — Interview Preparation¶

Tiered questions (Junior → Middle → Senior → Professional) followed by the canonical coding challenge: LeetCode 460 — O(1) LFU Cache in Go, Java, and Python. Cross-references: LRU cache · ARC / 2Q · Count-Min Sketch.

Junior Questions¶

Middle Questions¶

Senior Questions¶

Professional Questions¶

Trace-Reading Drills¶

Interviewers love asking you to predict the eviction victim. Practice these (capacity in parentheses).

Drill A (capacity 2): put(1,1) put(2,2) get(1) put(3,3) — who is evicted?

Key 2. After get(1), freqs are {1:2, 2:1}. put(3) overflows; minFreq=1 holds only key 2.

Drill B (capacity 2): put(1,1) put(2,2) get(2) get(1) get(2) put(3,3) — who is evicted?

Key 1. Freqs: 1:2, 2:3. minFreq=2 holds only key 1. (Frequency, not recency, decides here — key 1 was touched recently but is less frequent.)

Drill C (capacity 3): put(1,1) put(2,2) put(3,3) get(1) get(2) put(4,4) — who is evicted?

Key 3. Freqs: 1:2, 2:2, 3:1. minFreq=1 holds only key 3.

Drill D — the tie (capacity 2): put(1,1) put(2,2) get(1) get(2) put(3,3) — who is evicted?

Key 1. Freqs tie at 1:2, 2:2; minFreq=2 bucket is ordered by recency [2(newest), 1(oldest)]; the back (oldest) is key 1. Recency breaks the tie.

The pattern: frequency first, recency only on ties. If you can explain Drill D out loud you understand the policy.

Rapid-Fire Round (Mixed)¶

Whiteboard Diagnostic: Spot the Bug¶

Interviewers often hand you broken LFU code. Train on these:

Coding Challenge: LeetCode 460 — LFU Cache (O(1))¶

Problem. Design and implement an LFU cache supporting: - LFUCache(int capacity) — initialize with positive capacity. - get(key) — return the value if present (and increment its use count), else -1. - put(key, value) — insert/update; on overflow, evict the least frequently used key, breaking ties by least recently used.

Both get and put must run in O(1) average time.

Design. keyMap: key → node, freqMap: freq → doubly linked list (recency-ordered), and a minFreq integer. Promotion (on every use) moves a node up one frequency bucket; eviction removes the back of the minFreq bucket.

Test cases¶

LFUCache c = new LFUCache(2)
c.put(1,1)            // cache {1:1}
c.put(2,2)            // cache {1:1, 2:2}
c.get(1)   -> 1       // freq: 1->2 ; cache {1, 2}
c.put(3,3)            // evict key 2 (freq 1) ; cache {1, 3}
c.get(2)   -> -1      // not found
c.get(3)   -> 3       // freq: 3->2
c.put(4,4)            // tie freq=2 between 1 and 3; 1 is LRU -> evict 1 ; cache {3, 4}
c.get(1)   -> -1
c.get(3)   -> 3
c.get(4)   -> 4

Go¶

package main

import "fmt"

type node struct {
    key, value, freq int
    prev, next       *node
}

type dll struct {
    head, tail *node
    size       int
}

func newDLL() *dll {
    h, t := &node{}, &node{}
    h.next, t.prev = t, h
    return &dll{head: h, tail: t}
}
func (l *dll) pushFront(n *node) {
    n.prev, n.next = l.head, l.head.next
    l.head.next.prev = n
    l.head.next = n
    l.size++
}
func (l *dll) remove(n *node) {
    n.prev.next = n.next
    n.next.prev = n.prev
    l.size--
}
func (l *dll) popBack() *node { n := l.tail.prev; l.remove(n); return n }

type LFUCache struct {
    capacity, minFreq int
    keyMap            map[int]*node
    freqMap           map[int]*dll
}

func Constructor(capacity int) LFUCache {
    return LFUCache{
        capacity: capacity,
        keyMap:   make(map[int]*node),
        freqMap:  make(map[int]*dll),
    }
}

func (c *LFUCache) promote(n *node) {
    f := n.freq
    c.freqMap[f].remove(n)
    if c.freqMap[f].size == 0 {
        delete(c.freqMap, f)
        if c.minFreq == f {
            c.minFreq = f + 1
        }
    }
    n.freq++
    if c.freqMap[n.freq] == nil {
        c.freqMap[n.freq] = newDLL()
    }
    c.freqMap[n.freq].pushFront(n)
}

func (c *LFUCache) Get(key int) int {
    n, ok := c.keyMap[key]
    if !ok {
        return -1
    }
    c.promote(n)
    return n.value
}

func (c *LFUCache) Put(key, value int) {
    if c.capacity == 0 {
        return
    }
    if n, ok := c.keyMap[key]; ok {
        n.value = value
        c.promote(n)
        return
    }
    if len(c.keyMap) >= c.capacity {
        victim := c.freqMap[c.minFreq].popBack()
        delete(c.keyMap, victim.key)
    }
    n := &node{key: key, value: value, freq: 1}
    c.keyMap[key] = n
    if c.freqMap[1] == nil {
        c.freqMap[1] = newDLL()
    }
    c.freqMap[1].pushFront(n)
    c.minFreq = 1
}

func main() {
    c := Constructor(2)
    c.Put(1, 1)
    c.Put(2, 2)
    fmt.Println(c.Get(1)) // 1
    c.Put(3, 3)           // evict 2
    fmt.Println(c.Get(2)) // -1
    fmt.Println(c.Get(3)) // 3
    c.Put(4, 4)           // evict 1
    fmt.Println(c.Get(1)) // -1
    fmt.Println(c.Get(3)) // 3
    fmt.Println(c.Get(4)) // 4
}

Java¶

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

public class Solution {

    static class Node {
        int key, value, freq = 1;
        Node prev, next;
        Node() {}
        Node(int k, int v) { key = k; value = v; }
    }

    static class DLL {
        final Node head = new Node(), tail = new Node();
        int size = 0;
        DLL() { head.next = tail; tail.prev = head; }
        void pushFront(Node n) {
            n.prev = head; n.next = head.next;
            head.next.prev = n; head.next = n; size++;
        }
        void remove(Node n) { n.prev.next = n.next; n.next.prev = n.prev; size--; }
        Node popBack() { Node n = tail.prev; remove(n); return n; }
    }

    static class LFUCache {
        final int capacity;
        int minFreq = 0;
        final Map<Integer, Node> keyMap = new HashMap<>();
        final Map<Integer, DLL> freqMap = new HashMap<>();

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

        void promote(Node n) {
            int f = n.freq;
            DLL list = freqMap.get(f);
            list.remove(n);
            if (list.size == 0) {
                freqMap.remove(f);
                if (minFreq == f) minFreq = f + 1;
            }
            n.freq++;
            freqMap.computeIfAbsent(n.freq, k -> new DLL()).pushFront(n);
        }

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

        void put(int key, int value) {
            if (capacity == 0) return;
            Node n = keyMap.get(key);
            if (n != null) { n.value = value; promote(n); return; }
            if (keyMap.size() >= capacity) {
                Node victim = freqMap.get(minFreq).popBack();
                keyMap.remove(victim.key);
            }
            Node fresh = new Node(key, value);
            keyMap.put(key, fresh);
            freqMap.computeIfAbsent(1, k -> new DLL()).pushFront(fresh);
            minFreq = 1;
        }
    }

    public static void main(String[] args) {
        LFUCache c = new LFUCache(2);
        c.put(1, 1);
        c.put(2, 2);
        System.out.println(c.get(1)); // 1
        c.put(3, 3);                   // evict 2
        System.out.println(c.get(2)); // -1
        System.out.println(c.get(3)); // 3
        c.put(4, 4);                   // evict 1
        System.out.println(c.get(1)); // -1
        System.out.println(c.get(3)); // 3
        System.out.println(c.get(4)); // 4
    }
}

Python¶

class Node:
    __slots__ = ("key", "value", "freq", "prev", "next")

    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.freq = 1
        self.prev = None
        self.next = None


class DLL:
    def __init__(self):
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def push_front(self, n):
        n.prev, n.next = self.head, self.head.next
        self.head.next.prev = n
        self.head.next = n
        self.size += 1

    def remove(self, n):
        n.prev.next = n.next
        n.next.prev = n.prev
        self.size -= 1

    def pop_back(self):
        n = self.tail.prev
        self.remove(n)
        return n


class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.key_map: dict[int, Node] = {}
        self.freq_map: dict[int, DLL] = {}

    def _promote(self, n: Node) -> None:
        f = n.freq
        self.freq_map[f].remove(n)
        if self.freq_map[f].size == 0:
            del self.freq_map[f]
            if self.min_freq == f:
                self.min_freq = f + 1
        n.freq += 1
        self.freq_map.setdefault(n.freq, DLL()).push_front(n)

    def get(self, key: int) -> int:
        n = self.key_map.get(key)
        if n is None:
            return -1
        self._promote(n)
        return n.value

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        n = self.key_map.get(key)
        if n is not None:
            n.value = value
            self._promote(n)
            return
        if len(self.key_map) >= self.capacity:
            victim = self.freq_map[self.min_freq].pop_back()
            del self.key_map[victim.key]
        fresh = Node(key, value)
        self.key_map[key] = fresh
        self.freq_map.setdefault(1, DLL()).push_front(fresh)
        self.min_freq = 1


if __name__ == "__main__":
    c = LFUCache(2)
    c.put(1, 1)
    c.put(2, 2)
    print(c.get(1))  # 1
    c.put(3, 3)      # evict 2
    print(c.get(2))  # -1
    print(c.get(3))  # 3
    c.put(4, 4)      # evict 1
    print(c.get(1))  # -1
    print(c.get(3))  # 3
    print(c.get(4))  # 4

Follow-up questions an interviewer may ask¶

Model Answers to the Hardest Questions¶

These four questions separate strong candidates. Here is how to answer them in full.

"Walk me through why every operation is O(1)."¶

"Both get and put reduce to three primitives, each O(1). Lookup is a single hash-map access. Promotion unlinks a node from its current frequency bucket (a constant number of pointer rewires on a doubly linked list), increments its frequency, and pushes it to the front of the next bucket — no loop. Eviction removes the back node of the minFreq bucket and deletes one map entry. The only thing that could cost more is recomputing minFreq, but it never needs a search: on insert it resets to 1 because a freq-1 key now exists, and on a promotion that empties the min bucket it rises by exactly 1 because the promoted node landed in minFreq + 1. So the minimum moves in unit steps or snaps to 1 — never searched. Hash operations are O(1) expected, the pointer work is O(1) worst-case, so the whole thing is O(1) expected."

"Why is LFU sometimes worse than LRU?"¶

"The aging problem. Frequencies only ever increase; they never forget. A key that was hammered in the past keeps a huge count forever, so it can never be the minimum — it squats a cache slot even after it goes completely cold, while currently-hot keys thrash in and out. Formally, pure non-decaying LFU has an unbounded competitive ratio: an adversary inflates one key's count, then loops a working set, and LFU's hit ratio degrades without bound versus the offline optimum. LRU adapts to shifting popularity within O(k) accesses. The cure is decay — periodically halving counts, or decaying by elapsed time on access — which turns 'least frequently used ever' into 'least frequently used recently.'"

"When would you actually choose LFU?"¶

"When the access distribution is stable and skewed — a small set of keys is reliably hot and stays hot. Under the Independent Reference Model with a fixed Zipfian distribution, exact LFU provably converges to caching the top-k most popular keys, the optimal contents. It is also scan-resistant: a one-time sequential scan creates freq-1 keys that get evicted first, protecting the hot set — exactly where LRU collapses. In practice I'd reach for a decaying or approximate LFU (or W-TinyLFU) rather than exact LFU, to keep the frequency benefit while fixing aging."

"Design the eviction for a CDN edge cache."¶

"Frequency matters more than recency at the edge because catalogs are heavily Zipfian and full of one-time tail requests. I'd use a frequency-aware policy with three additions: (1) decay, so a release that's hot this week fades next week; (2) admission filtering (TinyLFU-style) so singletons and crawler traffic don't displace the hot head; and (3) size/cost weighting — evict by frequency × fetch_cost / size (GreedyDual-Size-Frequency) so one giant cold video doesn't crowd out thousands of hot thumbnails, optimizing byte hit ratio, not just object hit ratio. W-TinyLFU plus size weighting is a strong concrete choice, validated by replaying real edge traces."

Complexity & Policy Reference (for the whiteboard)¶

Memorize this grid — interviewers expect instant recall.

Note: all "O(1)" entries are average/amortized (the hash map's worst case is O(n) on pathological collisions; the linked-list and bucket work is always O(1)).

Two-sentence policy pitches (for "compare X vs Y")¶

• LFU vs LRU: LFU evicts by how often a key is used and is scan-resistant and IRM-optimal on stable skewed loads, but suffers aging. LRU evicts by how recently a key is used and adapts to shifting popularity, but is flushed by sequential scans.
• Exact LFU vs Redis LFU: Exact LFU keeps a precise count and a freq-bucket structure (tens of bytes/key, no decay). Redis uses a ~1-byte logarithmic Morris counter with time-decay and sampled eviction — approximate ranking, tiny memory, no aging.
• LFU vs W-TinyLFU: Plain LFU evicts the global minimum and ages badly. W-TinyLFU uses a frequency sketch to gate admission plus a small LRU window, getting frequency-awareness, scan-resistance, and adaptivity at ~10 bits/entry — the best general-purpose policy.

Quick-Reference Cheat Sheet¶