LFU Cache

HARD✓ CHIP-TIMEDLC #460 — FULL STATEMENT ↗

The drill: A fixed-capacity cache that evicts by usage count first — the item touched the fewest times goes, and only a tie in that count falls back to least-recently-used — where both get and put count as a touch.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

This cache holds a fixed number of key-value pairs and supports get and put, same interface as any cache — but the eviction rule cares about how often a key gets touched, not just how recently.

When a put would exceed capacity, the key with the smallest usage count is the one that goes. If more than one key shares that smallest count, the least recently used among them breaks the tie.

Every get and every put on an existing key counts as a touch and bumps that key's usage count by one; a put on a brand-new key starts its count at one and may itself trigger an eviction if the cache was already full.

EX 01

LFUCache(2)

put(100, 1)

put(200, 2)

get(100) → 1

put(300, 3)

get(200) → -1

get(300) → 3

put(400, 4)

get(100) → -1

get(300) → 3

get(400) → 4

FREQUENCY TIES BROKEN BY RECENCY ACROSS TWO EVICTIONS

EX 02

LFUCache(0)

put(1, 100)

get(1) → -1

put(2, 200)

get(2) → -1

CAPACITY ZERO ACCEPTS NOTHING

EX 03

LFUCache(1)

put(5, 50)

get(5) → 50

put(5, 55)

get(5) → 55

put(6, 60)

get(5) → -1

CAPACITY ONE, REPEATED PUTS ON THE RESIDENT KEY

capacity is fixed at construction; capacity 0 accepts nothing
keys and values are plain integers
get and put must both run in O(1)
ties in usage count break by least-recently-used

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Tracking a running count per key and scanning for the smallest count — breaking ties by age — is correct and simple, but that scan costs you the whole cache on every eviction.

HINT 2 THE STRUCTURE

Grouping keys by their current frequency turns 'find the minimum frequency' into 'look at the bucket you're already tracking as the smallest,' instead of scanning everything.

HINT 3 ONE STEP FROM THE ANSWER

Keep a hashmap from frequency to a recency-ordered doubly linked list of keys at that frequency, plus a running minimum frequency; a touch moves a key from its bucket to the next one up, and eviction pops the back of the minimum bucket.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE FREQUENCY BUCKETSPATTERN · FREQUENCY BUCKETScapacity 2 · put1,put2,get1×3,put3,get1,get2

new(2)

put1,11

put2,22

get1

put3,33

get1

get2

MIN-FREQUENCY BUCKET

min_freq → 0

buckets → (empty)

STEP 1

Capacity-2 LFU cache — evicts by usage count first, ties broken by recency. Buckets start empty.

STEP 1 / 9 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/lfu-cache.py — RACE PACE

LANG ▸

PACE ▸

class _Node:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        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 remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1

    def insert_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
        self.size += 1

    def pop_lru(self):
        if self.size == 0:
            return None
        node = self.tail.prev
        self.remove(node)
        return node


class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.key_node = {}
        self.freq_list = {}  # frequency -> _DLL, most recently touched at the front

    def _touch(self, node):
        freq = node.freq
        self.freq_list[freq].remove(node)
        if self.freq_list[freq].size == 0 and self.min_freq == freq:
            self.min_freq += 1
        node.freq += 1
        if node.freq not in self.freq_list:
            self.freq_list[node.freq] = _DLL()
        self.freq_list[node.freq].insert_front(node)

    def get(self, key: int) -> int:
        if key not in self.key_node:
            return -1
        node = self.key_node[key]
        self._touch(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        if key in self.key_node:
            node = self.key_node[key]
            node.val = value
            self._touch(node)
            return
        if len(self.key_node) == self.capacity:
            lru = self.freq_list[self.min_freq].pop_lru()
            del self.key_node[lru.key]
        node = _Node(key, value)
        self.key_node[key] = node
        self.min_freq = 1
        if 1 not in self.freq_list:
            self.freq_list[1] = _DLL()
        self.freq_list[1].insert_front(node)

TIME O(1) ALL OPSSPACE O(CAPACITY)PYTHON · RACE PACE · 78 LN

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.values = {}
        self.freqs = {}
        self.times = {}
        self.tick = 0

    def get(self, key: int) -> int:
        if key not in self.values:
            return -1
        self.freqs[key] += 1
        self.tick += 1
        self.times[key] = self.tick
        return self.values[key]

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        if key in self.values:
            self.values[key] = value
            self.freqs[key] += 1
            self.tick += 1
            self.times[key] = self.tick
            return
        if len(self.values) == self.capacity:
            evict_key = min(self.values.keys(), key=lambda k: (self.freqs[k], self.times[k]))
            del self.values[evict_key]
            del self.freqs[evict_key]
            del self.times[evict_key]
        self.values[key] = value
        self.freqs[key] = 1
        self.tick += 1
        self.times[key] = self.tick

TIME O(N) PER EVICTIONSPACE O(N)PYTHON · TRAINING PACE · 34 LN

class LFUCache {
    private static class Node {
        int key, val, freq = 1;
        Node prev, next;

        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private static class DLL {
        Node head = new Node(0, 0);
        Node tail = new Node(0, 0);
        int size = 0;

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

        void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            size--;
        }

        void insertFront(Node node) {
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
            size++;
        }

        Node popLru() {
            if (size == 0) return null;
            Node node = tail.prev;
            remove(node);
            return node;
        }
    }

    private final int capacity;
    private int minFreq = 0;
    private final Map<Integer, Node> keyNode = new HashMap<>();
    private final Map<Integer, DLL> freqList = new HashMap<>();

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

    private void touch(Node node) {
        int freq = node.freq;
        freqList.get(freq).remove(node);
        if (freqList.get(freq).size == 0 && minFreq == freq) minFreq++;
        node.freq++;
        freqList.computeIfAbsent(node.freq, f -> new DLL()).insertFront(node);
    }

    public int get(int key) {
        if (!keyNode.containsKey(key)) return -1;
        Node node = keyNode.get(key);
        touch(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        if (keyNode.containsKey(key)) {
            Node node = keyNode.get(key);
            node.val = value;
            touch(node);
            return;
        }
        if (keyNode.size() == capacity) {
            Node lru = freqList.get(minFreq).popLru();
            keyNode.remove(lru.key);
        }
        Node node = new Node(key, value);
        keyNode.put(key, node);
        minFreq = 1;
        freqList.computeIfAbsent(1, f -> new DLL()).insertFront(node);
    }
}

TIME O(1) ALL OPSSPACE O(CAPACITY)JAVA · RACE PACE · 85 LN

class LFUCache {
    private final int capacity;
    private final Map<Integer, Integer> values = new HashMap<>();
    private final Map<Integer, Integer> freqs = new HashMap<>();
    private final Map<Integer, Integer> times = new HashMap<>();
    private int tick = 0;

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

    public int get(int key) {
        if (!values.containsKey(key)) return -1;
        freqs.put(key, freqs.get(key) + 1);
        times.put(key, ++tick);
        return values.get(key);
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        if (values.containsKey(key)) {
            values.put(key, value);
            freqs.put(key, freqs.get(key) + 1);
            times.put(key, ++tick);
            return;
        }
        if (values.size() == capacity) {
            int evictKey = -1;
            int bestFreq = Integer.MAX_VALUE;
            int bestTime = Integer.MAX_VALUE;
            for (int k : values.keySet()) {
                int f = freqs.get(k);
                int t = times.get(k);
                if (f < bestFreq || (f == bestFreq && t < bestTime)) {
                    bestFreq = f;
                    bestTime = t;
                    evictKey = k;
                }
            }
            values.remove(evictKey);
            freqs.remove(evictKey);
            times.remove(evictKey);
        }
        values.put(key, value);
        freqs.put(key, 1);
        times.put(key, ++tick);
    }
}

TIME O(N) PER EVICTIONSPACE O(N)JAVA · TRAINING PACE · 48 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED