DSA LFU Cache

The problem: the LFU cache spec

An LFU cache is a fixed-size store that evicts its least frequently used entry when a new entry needs the space. LFU stands for least frequently used. Frequency means how many times an entry has been touched, and a touch is a get or a put.

A get returns the stored value, or -1 when the key is absent. A put stores a value, updating an existing key in place. Ties in frequency break by recency, so the least recently touched entry among the lowest-frequency entries leaves first.

script = [
    ("put(1, 10)", None),
    ("put(2, 20)", None),
    ("get(1)", 10),
    ("put(3, 30) evicts 2", None),
    ("get(2)", -1),
    ("get(3)", 30),
    ("put(4, 40) evicts 1", None),
    ("get(1)", -1),
    ("get(4)", 40),
]
print("capacity: 2")
for action, expected in script:
    if expected is None:
        print(action)
    else:
        print(action, "expected:", expected)

Key 1 earns a second touch early, so key 2 is the first victim. Key 3 then earns its own second touch, and key 1 becomes the second victim.

Intuition: keep counts in a dict and scan for the smallest

The first design stores each key with its value and its touch count in plain dicts. A get reads the dict and bumps the count. The design is correct, and eviction is where it pays.

An eviction must find the smallest count, and a tie inside that count must find the oldest touch. A plain dict holds no order for either job, so each eviction scans every entry.

vals = {1: 10, 2: 20, 3: 30, 4: 40, 5: 50}
freq = {1: 4, 2: 1, 3: 2, 4: 1, 5: 3}
scanned = 0
victim = None
for key in sorted(vals):
    scanned += 1
    if victim is None or freq[key] < freq[victim]:
        victim = key
print("entries scanned:", scanned, "victim:", victim, "with freq", freq[victim])

Five entries cost five inspections for one eviction, and the scan repeats on every eviction. The real design groups keys by frequency so the victim is always at a known place.

Brute force: the naive scanning cache, counted

The naive design is the intuition, written as a class. Recency is kept as a tick counter per key, so ties break correctly. A counter records the entries scanned across evictions.

class NaiveLFU:
    def __init__(self, cap):
        self.cap = cap
        self.vals = {}
        self.freq = {}
        self.tick = {}
        self.clock = 0
        self.scans = 0

    def _touch(self, key):
        self.clock += 1
        self.freq[key] = self.freq.get(key, 0) + 1
        self.tick[key] = self.clock

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

    def put(self, key, value):
        if self.cap == 0:
            return
        if key in self.vals:
            self.vals[key] = value
            self._touch(key)
            return
        if len(self.vals) == self.cap:
            victim = None
            for k in sorted(self.vals):
                self.scans += 1
                if victim is None or (self.freq[k], self.tick[k]) < (self.freq[victim], self.tick[victim]):
                    victim = k
            print("evict", victim, "after scanning", self.scans, "entries")
            self.scans = 0
            del self.vals[victim]
            del self.freq[victim]
            del self.tick[victim]
        self.vals[key] = value
        self._touch(key)

cache = NaiveLFU(2)
cache.put(1, 10)
cache.put(2, 20)
print("get(1) =", cache.get(1))
cache.put(3, 30)
print("get(2) =", cache.get(2))
print("get(3) =", cache.get(3))
cache.put(4, 40)
print("get(1) =", cache.get(1))
print("get(4) =", cache.get(4))

The answers match the script, evictions included. The scans stay small only because the capacity is 2. At capacity 100 each eviction inspects about 100 entries.

The optimal solution: one ordered group per frequency

The real design keeps one ordered dict per frequency, holding that group's keys in touch order, plus one number for the smallest live frequency. That grouping is the whole design.

An ordered dict remembers insertion order. A touch removes the key from its old group and appends it to the next group. The eviction victim is the first key of the minimum-frequency group, with no scan at all.

from collections import OrderedDict

class LFU:
    def __init__(self, cap):
        self.cap = cap
        self.vals = {}
        self.freq = {}
        self.groups = {}
        self.min_freq = 0

    def _touch(self, key):
        f = self.freq[key]
        group = self.groups[f]
        del group[key]
        if not group:
            del self.groups[f]
            if self.min_freq == f:
                self.min_freq = f + 1
        self.freq[key] = f + 1
        self.groups.setdefault(f + 1, OrderedDict())[key] = None

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

    def put(self, key, value):
        if self.cap == 0:
            return
        if key in self.vals:
            self.vals[key] = value
            self._touch(key)
            return
        if len(self.vals) == self.cap:
            group = self.groups[self.min_freq]
            victim, _ = group.popitem(last=False)
            print("evict", victim)
            del self.vals[victim]
            del self.freq[victim]
            if not group:
                del self.groups[self.min_freq]
        self.vals[key] = value
        self.freq[key] = 1
        self.groups.setdefault(1, OrderedDict())[key] = None
        self.min_freq = 1

    def state(self):
        parts = []
        for f in sorted(self.groups):
            parts.append(str(f) + ": " + str(list(self.groups[f].keys())))
        return "freq groups {" + ", ".join(parts) + "}"

cache = LFU(2)
cache.put(1, 10)
cache.put(2, 20)
print("get(1) =", cache.get(1))
cache.put(3, 30)
print("get(2) =", cache.get(2))
print("get(3) =", cache.get(3))
cache.put(4, 40)
print("get(1) =", cache.get(1))
print("get(4) =", cache.get(4))

Every line matches the script from the first section. The evictions print in the same places as the naive run, and no scan counter exists because no scan happens.

Walkthrough: the script, step by step

The walk reruns the script and prints the frequency groups after each step. Group keys print in touch order, oldest first. The minimum frequency prints beside them.

from collections import OrderedDict

class LFU:
    def __init__(self, cap):
        self.cap = cap
        self.vals = {}
        self.freq = {}
        self.groups = {}
        self.min_freq = 0

    def _touch(self, key):
        f = self.freq[key]
        group = self.groups[f]
        del group[key]
        if not group:
            del self.groups[f]
            if self.min_freq == f:
                self.min_freq = f + 1
        self.freq[key] = f + 1
        self.groups.setdefault(f + 1, OrderedDict())[key] = None

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

    def put(self, key, value):
        if self.cap == 0:
            return
        if key in self.vals:
            self.vals[key] = value
            self._touch(key)
            return
        if len(self.vals) == self.cap:
            group = self.groups[self.min_freq]
            victim, _ = group.popitem(last=False)
            print("evict", victim)
            del self.vals[victim]
            del self.freq[victim]
            if not group:
                del self.groups[self.min_freq]
        self.vals[key] = value
        self.freq[key] = 1
        self.groups.setdefault(1, OrderedDict())[key] = None
        self.min_freq = 1

    def state(self):
        parts = []
        for f in sorted(self.groups):
            parts.append(str(f) + ": " + str(list(self.groups[f].keys())))
        return "freq groups {" + ", ".join(parts) + "}"

cache = LFU(2)
def show(action, result=None):
    if result is None:
        print(action, "->", cache.state(), "| min_freq", cache.min_freq)
    else:
        print(action, "=", result, "->", cache.state(), "| min_freq", cache.min_freq)

cache.put(1, 10)
show("put(1, 10)")
cache.put(2, 20)
show("put(2, 20)")
show("get(1)", cache.get(1))
cache.put(3, 30)
show("put(3, 30)")
show("get(3)", cache.get(3))
cache.put(4, 40)
show("put(4, 40)")
show("get(4)", cache.get(4))

After get(1), key 1 sits alone at frequency 2 and key 2 sits alone at frequency 1. The next put reads its victim straight off the frequency 1 group. When that group empties on a touch, the minimum frequency climbs by one.

Complexity

A get and a put each do a fixed set of dict operations, so their time is O(1) at any capacity. The store holds one entry per key plus one group slot per key, so its space is O(capacity).

for cap in [10, 50, 100]:
    print("capacity", cap, "- naive scans per eviction:", cap, " real design scans per eviction: 0")

The naive scan grows in a straight line with the capacity. The real design replaces the scan with a direct read of one group's first key.

Edge cases and pitfalls

A cache of capacity zero stores nothing and every get misses. A put on an existing key updates the value and counts as a touch, and it evicts nothing. A get on a missing key returns -1 and touches nothing.

The classic pitfall forgets the minimum frequency when a group empties. A stale minimum points at a group that no longer exists. The touch code raises the minimum exactly when its group empties, and the reset to 1 on each fresh insert keeps it honest.

from collections import OrderedDict

class LFU:
    def __init__(self, cap):
        self.cap = cap
        self.vals = {}
        self.freq = {}
        self.groups = {}
        self.min_freq = 0

    def _touch(self, key):
        f = self.freq[key]
        group = self.groups[f]
        del group[key]
        if not group:
            del self.groups[f]
            if self.min_freq == f:
                self.min_freq = f + 1
        self.freq[key] = f + 1
        self.groups.setdefault(f + 1, OrderedDict())[key] = None

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

    def put(self, key, value):
        if self.cap == 0:
            return
        if key in self.vals:
            self.vals[key] = value
            self._touch(key)
            return
        if len(self.vals) == self.cap:
            group = self.groups[self.min_freq]
            victim, _ = group.popitem(last=False)
            print("evict", victim)
            del self.vals[victim]
            del self.freq[victim]
            if not group:
                del self.groups[self.min_freq]
        self.vals[key] = value
        self.freq[key] = 1
        self.groups.setdefault(1, OrderedDict())[key] = None
        self.min_freq = 1

    def state(self):
        parts = []
        for f in sorted(self.groups):
            parts.append(str(f) + ": " + str(list(self.groups[f].keys())))
        return "freq groups {" + ", ".join(parts) + "}"

zero = LFU(0)
zero.put(1, 10)
print("capacity 0 get:", zero.get(1))
cache = LFU(2)
cache.put(1, 10)
cache.put(2, 20)
cache.put(1, 99)
print("update in place, size:", len(cache.vals), "get(1):", cache.get(1))
print("missing get:", cache.get(9), "state:", cache.state())
tie = LFU(2)
tie.put(1, 10)
tie.put(2, 20)
tie.put(3, 30)
print("tie victim was 1, get(1):", tie.get(1), "get(2):", tie.get(2), "get(3):", tie.get(3))

The tie row evicts key 1, the older of the two frequency 1 keys. Frequency decides first, and arrival order inside the group breaks the tie.