Implementing LFU Cache in O(1) Time: A Hands-on Breakdown

The flash sale that LRU evicted by mistake

A product detail API caches responses in memory to spare Postgres. Black Friday hits. One SKU gets hammered: tens of thousands of reads per minute. The cache is full at 10,000 entries.

LRU evicts the least recently touched key. A burst of new product IDs arrives (long-tail catalog browsing). The hot SKU has not been requested in the last 200 milliseconds because the handler was busy serving other keys. LRU drops the bestseller to make room for a product page that will be viewed once.

The next request for the hot SKU misses cache. Postgres takes the hit. Connection pool pressure spikes. p99 latency jumps on checkout because the database is shared.

LFU (Least Frequently Used) answers a different question: not “what did I touch last?” but “what do callers actually want?” Evict the key with the lowest hit count. Tie-break with LRU inside the same frequency bucket.

That policy is easy to describe. Implementing it in O(1) per get and put is where interview questions and production caches diverge.

Why the naive version fails

The slow approach keeps a HashMap of key to value and a HashMap of key to frequency. On eviction, scan all keys to find the minimum frequency. That is O(n) per eviction.

At n = 10,000 entries, one eviction scans 10,000 integers. Under write-heavy traffic, eviction runs often. The “cache” spends CPU walking memory while requests wait. You traded database I/O for a different bottleneck: a linear scan in the request path.

The fix is to invert the index. Do not search for min frequency. Track where min frequency lives and which keys sit there.

The O(1) shape: two maps and a list per frequency

You need four pieces:

1. keyToNode: HashMap<K, Node> for O(1) lookup by key
2. freqToBucket: HashMap<Integer, DoublyLinkedList> where each bucket holds all keys with that hit count
3. minFreq: integer pointing at the current lowest frequency in the cache
4. Doubly linked lists inside each bucket for O(1) insert/remove and LRU order within the same frequency

Each Node stores key, value, frequency, and prev/next pointers for its bucket list.

flowchart TB
  KEY["keyToNode HashMap"] --> NODE["Node: key, value, freq, prev, next"]
  FREQ["freqToBucket HashMap"] --> B1["freq=1 doubly linked list"]
  FREQ --> B2["freq=2 doubly linked list"]
  FREQ --> B3["freq=5 doubly linked list"]
  MIN["minFreq pointer"] --> B1
  NODE -.-> B2

Think of frequency buckets like lanes in a parking garage. Keys with freq 1 sit in lane 1. When a key is accessed, it moves to lane 2. Eviction always removes from the back of minFreq’s lane (least recently used among the least popular keys).

get(key) in O(1)

1. Look up keyToNode. Miss: return null (or -1 in LeetCode terms).
2. Read current frequency f from the node.
3. Remove the node from freqToBucket.get(f) (unlink from doubly linked list).
4. If that bucket is now empty and f == minFreq, increment minFreq (the next eviction must come from freq f + 1 or higher).
5. Increment node frequency to f + 1.
6. Insert node at the front of freqToBucket.get(f + 1) (most recently used within that frequency).
7. Return the value.

Every step is a constant number of pointer updates and hash map lookups. No scan across all keys.

sequenceDiagram
  participant API as get(key)
  participant Map as keyToNode
  participant Bucket as freqToBucket
  participant Min as minFreq

  API->>Map: lookup key
  Map-->>API: Node freq=f
  API->>Bucket: unlink from bucket f
  alt bucket f empty and f == minFreq
    API->>Min: minFreq = f + 1
  end
  API->>Bucket: insert front of bucket f+1
  API-->>API: return value

put(key, value) in O(1)

Two cases.

Key already exists: update value, then run the same frequency bump logic as get (a repeat access).

New key:

1. If at capacity, evict one entry: remove the tail of freqToBucket.get(minFreq) (LRU among least frequent keys). Delete from keyToNode.
2. Create a new node with frequency 1.
3. Insert at front of freqToBucket.get(1). Set minFreq = 1.
4. Add to keyToNode.

Eviction never scans the full map. It touches only the tail of one bucket.

// Java sketch: eviction removes tail of minFreq bucket
private void evictOne() {
    DoublyLinkedList bucket = freqToBucket.get(minFreq);
    Node victim = bucket.removeTail();
    keyToNode.remove(victim.key);
}

private void bumpFrequency(Node node) {
    int f = node.freq;
    freqToBucket.get(f).remove(node);
    if (freqToBucket.get(f).isEmpty() && f == minFreq) {
        minFreq++;
    }
    node.freq++;
    freqToBucket.computeIfAbsent(node.freq, k -> new DoublyLinkedList())
                .addToHead(node);
}

What this costs at runtime

Each get and put does two to four hash map lookups and a handful of pointer writes. In Java, HashMap get is O(1) average but allocates nothing on the hot path if you reuse node objects.

The mechanical cost is memory locality, not arithmetic. Each access jumps through:

• keyToNode bucket chain (pointer chase)
• bucket list head/tail (another chase)
• node object fields scattered in the heap

A 10,000 entry LFU cache with 200 distinct frequency buckets means 200 linked lists plus 10,000 node objects. L3 cache helps on hot keys (the freq 500 bucket for your bestseller SKU). Cold long-tail keys sit in freq 1 buckets and get evicted first, which is the intended behavior.

Compare to Redis: production systems often use approximate LFU (Redis volatile-lfu, allkeys-lfu) because exact per-key counters are expensive at millions of keys. The hand-rolled in-process LFU is for bounded local caches (10k to 100k entries) in front of a database, not for replacing Redis.

Python version of the same idea

The structure is identical. collections.OrderedDict per frequency bucket is a pragmatic shortcut in Python (OrderedDict popitem last = LRU within bucket):

from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.min_freq = 0
        self.key_to_val = {}
        self.key_to_freq = {}
        self.freq_to_keys = defaultdict(OrderedDict)

    def _touch(self, key: int) -> None:
        freq = self.key_to_freq[key]
        self.freq_to_keys[freq].pop(key)
        if not self.freq_to_keys[freq] and freq == self.min_freq:
            self.min_freq += 1
        self.key_to_freq[key] = freq + 1
        self.freq_to_keys[freq + 1][key] = None
        self.freq_to_keys[freq + 1].move_to_end(key, last=False)

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

    def put(self, key: int, value: int) -> None:
        if self.cap == 0:
            return
        if key in self.key_to_val:
            self.key_to_val[key] = value
            self._touch(key)
            return
        if len(self.key_to_val) == self.cap:
            evict_key, _ = self.freq_to_keys[self.min_freq].popitem(last=True)
            del self.key_to_val[evict_key]
            del self.key_to_freq[evict_key]
        self.key_to_val[key] = value
        self.key_to_freq[key] = 1
        self.freq_to_keys[1][key] = None
        self.freq_to_keys[1].move_to_end(key, last=False)
        self.min_freq = 1

Python hides the doubly linked list. Java makes the pointers explicit. The algorithm is the same.

Where this shows up in real backends

Exact LFU in O(1) is less common as a standalone service and more common as a local guard in application memory:

• Recommendation service caching feature vectors for top products
• Pricing service caching hot SKU price rows during promotions
• API gateway caching OAuth introspection results for high-volume clients

The pattern: bounded memory, skewed access, expensive miss path (database or remote call). LFU protects the keys that matter under burst traffic. LRU protects keys that were touched recently but might not matter statistically.

Do not reach for LFU because it sounds smarter. Reach for it when metrics show a small key set dominates hit rate and LRU evicts them during bursts of cold keys.

The implementation lesson

LFU O(1) is a standard systems interview problem because it compresses several ideas engineers use daily:

• Index inversion (track min instead of scanning)
• Multiple maps for different access patterns
• Linked structures for O(1) move and evict
• Policy choice (frequency vs recency) tied to business traffic shape

Build it once in Java or Python with println debugging on minFreq transitions. Watch the hot key climb frequency buckets during a simulated flash sale. Watch long-tail keys pile up in freq 1 and get evicted first.

That beats memorizing the LeetCode solution. You feel why the double map exists the first time you try to evict without scanning.