Generated by Codex with GPT-5

Quick facts

• Difficulty: HARD
• Problem: LFU Cache
• Topics: Hash Table, Linked List, Design, Doubly-Linked List

Problem gist

Design a cache with a fixed capacity that supports two operations:

• get(key): return the value for key, or -1 if the key is absent.
• put(key, value): insert or update a key-value pair.

When the cache is full, it must evict the least frequently used key. If multiple keys have the same lowest frequency, it evicts the least recently used key among them.

Every successful get counts as a use. Updating an existing key with put also counts as a use. The challenge is to make both operations run in constant time, including the eviction decision.

Optimal design

The cache has two separate ordering rules:

The LFU rule needs to find the smallest frequency currently present in the cache.

The LRU tie-breaker needs to find, among keys with that frequency, the oldest key by recent access.

A single heap can seem tempting, but it either leaves stale entries behind or costs extra time to update a key’s frequency. The clean O(1) design separates lookup, frequency grouping, and recency ordering:

• A hash map from key to the key’s node.
• A hash map from frequency to a doubly linked list of all nodes with that frequency.
• A minimum_frequency integer that points to the lowest non-empty frequency bucket.

Each frequency bucket is an LRU list. Newly used nodes move to the front of the next frequency bucket. Eviction removes from the back of the minimum_frequency bucket, because that is the least recently used node among the least frequently used nodes.

How to derive it

Start with the requirement that get(key) must be O(1). That implies a hash map from key to the cache entry.

Then notice what happens after every hit: the entry’s frequency increases by one. If entries are grouped by frequency, moving an entry means removing it from one group and inserting it into the next group. To make that O(1), each group must support O(1) removal of a known node and O(1) insertion at the most-recent end. A doubly linked list gives exactly that.

The final missing piece is eviction. Scanning for the smallest frequency would be too slow, so the cache maintains minimum_frequency. Whenever the last node leaves the current minimum bucket, the minimum rises by one. Whenever a brand-new key is inserted, the minimum resets to one.

Python solution

from typing import Optional


class CacheNode:
    __slots__ = ("key", "value", "frequency", "previous", "next")

    def __init__(self, key: int, value: int) -> None:
        self.key = key
        self.value = value
        self.frequency = 1
        self.previous: Optional["CacheNode"] = None
        self.next: Optional["CacheNode"] = None


class FrequencyBucket:
    """Doubly linked list ordered from most recent to least recent."""

    def __init__(self) -> None:
        self.head = CacheNode(0, 0)
        self.tail = CacheNode(0, 0)
        self.head.next = self.tail
        self.tail.previous = self.head
        self.size = 0

    def add_most_recent(self, node: CacheNode) -> None:
        first_real_node = self.head.next

        node.previous = self.head
        node.next = first_real_node
        self.head.next = node
        first_real_node.previous = node
        self.size += 1

    def remove(self, node: CacheNode) -> None:
        previous_node = node.previous
        next_node = node.next

        previous_node.next = next_node
        next_node.previous = previous_node

        node.previous = None
        node.next = None
        self.size -= 1

    def pop_least_recent(self) -> CacheNode:
        node_to_remove = self.tail.previous
        self.remove(node_to_remove)
        return node_to_remove

    def is_empty(self) -> bool:
        return self.size == 0


class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.nodes_by_key: dict[int, CacheNode] = {}
        self.buckets_by_frequency: dict[int, FrequencyBucket] = {}
        self.minimum_frequency = 0

    def get(self, key: int) -> int:
        if key not in self.nodes_by_key:
            return -1

        node = self.nodes_by_key[key]
        self._increase_frequency(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0:
            return

        if key in self.nodes_by_key:
            node = self.nodes_by_key[key]
            node.value = value
            self._increase_frequency(node)
            return

        if len(self.nodes_by_key) == self.capacity:
            self._evict_least_frequent()

        new_node = CacheNode(key, value)
        self.nodes_by_key[key] = new_node
        self.buckets_by_frequency.setdefault(1, FrequencyBucket()).add_most_recent(
            new_node,
        )
        self.minimum_frequency = 1

    def _increase_frequency(self, node: CacheNode) -> None:
        old_frequency = node.frequency
        old_bucket = self.buckets_by_frequency[old_frequency]
        old_bucket.remove(node)

        if old_bucket.is_empty():
            del self.buckets_by_frequency[old_frequency]
            if self.minimum_frequency == old_frequency:
                self.minimum_frequency += 1

        node.frequency += 1
        self.buckets_by_frequency.setdefault(
            node.frequency,
            FrequencyBucket(),
        ).add_most_recent(node)

    def _evict_least_frequent(self) -> None:
        bucket = self.buckets_by_frequency[self.minimum_frequency]
        node_to_evict = bucket.pop_least_recent()
        del self.nodes_by_key[node_to_evict.key]

        if bucket.is_empty():
            del self.buckets_by_frequency[self.minimum_frequency]

Correctness sketch

Every cached key has exactly one CacheNode, and nodes_by_key points directly to it. Therefore get can find present keys and reject absent keys correctly.

Every node is stored in the bucket matching its current frequency. A successful get or update removes the node from its old frequency bucket, increments its frequency, and inserts it at the most-recent end of the new bucket. This preserves both the frequency count and the recency order within each frequency group.

minimum_frequency always names the lowest non-empty bucket. New keys enter with frequency one, so the minimum becomes one. If a node leaves the current minimum bucket and that bucket becomes empty, no remaining node has that old frequency, so the minimum increases to the next possible frequency. During eviction, removing the least-recent node from the minimum_frequency bucket exactly applies LFU first and LRU as the tie-breaker.

Complexity

get is O(1) because it performs one hash lookup and a constant number of linked-list pointer updates.

put is O(1) for both updates and insertions. Eviction is also O(1) because the cache knows the minimum frequency and each bucket can remove its least-recent node directly.

The space cost is O(capacity), with one node per cached key and one bucket for each frequency currently represented in the cache.

Interview follow-ups

Why not use a heap?

A heap can find the smallest frequency, but updating a key’s frequency in place is not O(1). Most heap-based approaches push a new entry and leave the old entry as stale. That can work for relaxed systems, but strict LeetCode-style LFU requires every operation to be O(1), including repeated accesses and evictions. The bucketed linked-list design avoids stale entries because each key has one node that moves directly between lists.

Can this be implemented with OrderedDict?

Yes. In Python, each frequency bucket can be an OrderedDict from key to value or key to node. Moving a key to a new frequency removes it from one ordered dictionary and inserts it into another. Eviction uses popitem(last=False) from the minimum-frequency bucket. This is shorter and practical in production Python, but the custom linked-list version is more portable and shows the underlying data-structure reasoning clearly.

What if frequency counts grow very large?

The basic algorithm lets frequencies increase without bound. That is acceptable for the usual constraints because there are only as many live nodes as the cache capacity. In a long-running service, very large counters may become awkward for observability or memory locality. A practical system can periodically age the cache by scaling frequencies down, or use a bounded approximation such as windowed LFU. The tradeoff is that aging improves adaptability to new traffic patterns but no longer represents exact all-time LFU behavior.

How would this change in a concurrent cache?

The data structure has several shared pieces that must change together: the key map, the frequency map, the linked-list pointers, and minimum_frequency. A thread-safe version should guard each operation with a lock, or use sharded caches where each shard has its own lock and LFU state. A single lock is simple and preserves correctness, but limits throughput. Sharding improves concurrency, though eviction becomes local to a shard rather than globally perfect across the whole cache.

What if the interviewer asks for time-based expiration too?

Expiration adds another eviction dimension. The usual approach is to keep the LFU structure for capacity eviction and add an expiration index, such as a min-heap keyed by expiry time. Before get or put, the cache removes expired entries from both structures. This makes cleanup cost depend on how many expired entries are removed at that moment, so the design is no longer strict O(1) in the worst case, but it is often the right practical tradeoff for real cache systems.