Problem 68 · Object & System Design

LFU Cache in O(1)

HardClassic DSA & systems

01Problem

Implement an LFU cache with get and put in O(1). On eviction remove the least-frequently-used key; break ties by least-recently-used.

02Key insight

Bucket keys by frequency, each bucket an insertion-ordered set (LRU within frequency), and track min_freq. A hit moves a key from bucket f to f+1; min_freq only changes on that move or reset to 1 on insert.

03Solution

solution.pypython45 lines

from collections import defaultdict


class LFUCache:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.vals: dict[int, int] = {}
        self.freq: dict[int, int] = {}
        # dict preserves insertion order -> O(1) LRU within a frequency bucket
        self.buckets: defaultdict[int, dict[int, None]] = defaultdict(dict)
        self.min_freq = 0

    def _touch(self, key: int) -> None:
        f = self.freq[key]
        del self.buckets[f][key]
        if not self.buckets[f]:
            del self.buckets[f]
            if self.min_freq == f:
                self.min_freq = f + 1
        self.freq[key] = f + 1
        self.buckets[f + 1][key] = None

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

    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return
        if key in self.vals:
            self.vals[key] = value
            self._touch(key)
            return
        if len(self.vals) == self.capacity:
            bucket = self.buckets[self.min_freq]
            victim = next(iter(bucket))
            del bucket[victim]
            if not bucket:
                del self.buckets[self.min_freq]
            del self.vals[victim], self.freq[victim]
        self.vals[key], self.freq[key] = value, 1
        self.buckets[1][key] = None
        self.min_freq = 1

Try it first.

TimeO(1) per op

SpaceO(capacity)

tests.py · 4 passing

tests.pypython9 lines

c = LFUCache(2)
c.put(1, 1); c.put(2, 2)
assert c.get(1) == 1
c.put(3, 3)            # evicts 2 (freq 1)
assert c.get(2) == -1 and c.get(3) == 3
c.put(4, 4)            # 1 and 3 both freq 2 -> evict LRU = 1
assert c.get(1) == -1 and c.get(3) == 3 and c.get(4) == 4
z = LFUCache(0); z.put(1, 1)
assert z.get(1) == -1

04Staff-level follow-up

Pure LFU never forgets old hot keys. Fix: frequency aging/decay (halve counts periodically) or W-TinyLFU (Caffeine) with a count-min sketch admission filter.