LFU Cache

Start from brute force

Store each key’s value, use count and the time of its last use, and on eviction scan every key for the smallest (count, last_used) pair. Gets and updates are O(1), and the scan always finds the right victim, because that tuple order is exactly “least frequent, then least recent”. But each eviction costs O(capacity) time, so a workload where every put misses a full cache pays it on every operation; space is O(capacity). A heap keyed by (count, last_used) cuts eviction to O(log n), but every use changes a key’s priority, so it needs lazy deletion of stale entries, and it is still not the O(1) the problem demands.

The approach

Group keys by frequency, and keep each group in use order. The reference lfu_ops holds val (key to value), freq (key to use count), buckets, a defaultdict(OrderedDict) from each count to its keys oldest-use first, and min_freq, the smallest non-empty count. The helper use(k) deletes k from buckets[f], drops that bucket if it emptied (raising min_freq to f + 1 if it was the minimum), and appends k to the end of buckets[f + 1], the most recent position.

A get hit records the value and calls use; a put on an existing key updates the value and calls use. A new key arriving at a full cache evicts with buckets[min_freq].popitem(last=False), the least recently used of the least frequently used, then enters at count 1 with min_freq = 1. No scan is ever needed: a use raises the minimum by at most one, an insert resets it to 1, and nothing else changes it. The TypeScript version uses one Map per bucket, since a Map iterates in insertion order.

Walk through an example

On the first example, key 1 earns a second use before key 3 arrives, so the eviction falls on key 2.

Complexity

Every operation is O(1) on average: a constant number of dict and OrderedDict lookups, inserts and deletes, plus at most one popitem. Space is O(capacity), since each key sits in val, freq and exactly one bucket. The scan-on-evict design is O(1) for hits but O(capacity) per eviction, with the same O(capacity) space.

Edge cases to test

• cap = 2: put 1, put 2, put 3, get 2, get 3 → [2, 3]. Keys 1 and 2 tie at count 1, so the least recently used, key 1, is evicted.
• cap = 2: put 1, put 2, put 1 (value 9), put 3, get 2, get 1 → [-1, 9]. Updating key 1 counts as a use, so key 2 is the victim.
• cap = 1: put 1, get 1, put 2, get 1, get 2 → [1, -1, 2]. With one slot, a key used twice is still evicted by any new key.
• cap = 2: put 1, get 1, get 1, put 2, put 3, get 2 → [1, 1, -1]. Key 2 entered at count 1, under key 1’s count of 3, so it was the next victim; a new key is always the most exposed.
• cap = 2: put 1, put 2, get 1, get 2, put 3, get 1 → [1, 2, -1]. Both keys reached count 2 and bucket 1 emptied, so min_freq moved to 2 and the oldest key there, key 1, was evicted.
• A get of a missing key returns -1 and changes nothing: a miss is not a use. The reference also skips every put when cap is 0.

Common mistakes

• Scanning the whole cache for the least-frequent victim — O(n) per eviction.
• Not breaking frequency ties by recency, so eviction is ambiguous.
• Forgetting to bump the frequency (and move the entry to the next bucket) on a read.

Follow-ups an interviewer asks next

Add delete(key) without losing O(1).

Deleting a key can empty the minimum bucket and leave no way to find the next minimum without a scan, because the minimum may jump by more than one. The classic O(1) LFU design fixes this by linking the frequency buckets themselves in a doubly linked list ordered by count, so the head is always the minimum and removing an empty bucket is an O(1) unlink.

Keys that were popular once never leave. How do you age frequencies?

Plain LFU lets a key that was hot last week outrank everything new. Common fixes decay the counts, such as halving every count after a fixed number of operations, or count only recent activity. W-TinyLFU, the policy in the Java caching library Caffeine, estimates frequencies with a compact sketch, halves them periodically, and passes new keys through a small LRU window first.

Make it safe for concurrent use.

A get is a write here, because it bumps a count and moves the key between buckets, so a read-write lock buys nothing; the simple answer is one mutex around every operation. To cut contention, shard the key space into several independent caches by key hash, accepting that eviction becomes per-shard LFU rather than global.

Where this shows up

LFU suits caches where popularity is stable — a hot set that stays hot, like CDN edges or some database buffer pools. The choice between LFU (frequency) and LRU (recency) comes down to which better predicts the next access for your workload; getting O(1) on either is the textbook data-structure win.

Reference solution

from collections import OrderedDict, defaultdict

def lfu_ops(cap, ops):
    val = {}                              # key -> value
    freq = {}                             # key -> use count
    buckets = defaultdict(OrderedDict)    # freq -> {key: None} in use order
    min_freq = 0
    out = []

    def use(k):                           # bump k's frequency by one
        nonlocal min_freq
        f = freq[k]
        del buckets[f][k]
        if not buckets[f]:
            del buckets[f]
            if min_freq == f:
                min_freq = f + 1
        freq[k] = f + 1
        buckets[f + 1][k] = None

    for op in ops:
        if op[0] == "put":
            k, v = op[1], op[2]
            if cap <= 0:
                continue
            if k in val:                  # update + count as a use
                val[k] = v
                use(k)
                continue
            if len(val) >= cap:           # evict LFU (ties: LRU)
                ek, _ = buckets[min_freq].popitem(last=False)
                del val[ek]
                del freq[ek]
            val[k] = v
            freq[k] = 1
            buckets[1][k] = None
            min_freq = 1
        else:                             # get
            k = op[1]
            if k in val:
                out.append(val[k])
                use(k)
            else:
                out.append(-1)
    return out


print(lfu_ops(2, [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["get",3]]))  # -> [1, -1, 3]

function lfuOps(cap: number, ops: any[][]): number[] {
  const val = new Map<number, number>();          // key -> value
  const freq = new Map<number, number>();          // key -> use count
  const buckets = new Map<number, Map<number, true>>(); // freq -> ordered keys
  let minFreq = 0;
  const out: number[] = [];

  function bucket(f: number): Map<number, true> {
    if (!buckets.has(f)) buckets.set(f, new Map());
    return buckets.get(f)!;
  }
  function use(k: number): void {                  // bump frequency by one
    const f = freq.get(k)!;
    bucket(f).delete(k);
    if (bucket(f).size === 0) {
      buckets.delete(f);
      if (minFreq === f) minFreq = f + 1;
    }
    freq.set(k, f + 1);
    bucket(f + 1).set(k, true);
  }

  for (const op of ops) {
    if (op[0] === "put") {
      const k = op[1] as number, v = op[2] as number;
      if (cap <= 0) continue;
      if (val.has(k)) { val.set(k, v); use(k); continue; }
      if (val.size >= cap) {                        // evict LFU (ties: LRU)
        const b = bucket(minFreq);
        const ek = b.keys().next().value as number; // oldest in the bucket
        b.delete(ek); val.delete(ek); freq.delete(ek);
      }
      val.set(k, v); freq.set(k, 1); bucket(1).set(k, true); minFreq = 1;
    } else {                                        // get
      const k = op[1] as number;
      if (val.has(k)) { out.push(val.get(k)!); use(k); }
      else out.push(-1);
    }
  }
  return out;
}

console.log(lfuOps(2, [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["get",3]])); // -> [1,-1,3]