LRU / LFU Cache

LRU and LFU Cache Design

Caches are everywhere in systems design, and interviewers love asking you to implement them from scratch. The two most common eviction policies are Least Recently Used (LRU) and Least Frequently Used (LFU). Both require $O(1)$ get and put operations, which rules out any naive approach involving sorting or linear scans.

The LRU Problem

LeetCode 146 presents the core challenge: an LRU cache has a fixed capacity. When it's full and you need to insert a new key, you evict whichever key was accessed least recently. This requires two things simultaneously: fast key lookup, and the ability to track and update access order cheaply.

The key insight is that you need a data structure that remembers insertion/access order and lets you move elements around in $O(1)$. Python's OrderedDict is exactly that.

The OrderedDict Approach

Python's collections.OrderedDict maintains insertion order and exposes two critical methods: move_to_end(key) promotes a key to the "most recent" end, and popitem(last=False) evicts the "least recent" entry from the front. Both run in $O(1)$.

Here is the full LRU implementation:

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.cap = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)   # mark as most recently used
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)  # evict least recently used

Walked Example

Start with capacity 2. The cache is empty.

• put(1, 10): cache: {1: 10}
• put(2, 20): cache: {1: 10, 2: 20}
• get(1): moves key 1 to the end; cache order: {2: 20, 1: 10}; returns 10
• put(3, 30): cache is full; evict the front (key 2, the LRU); insert 3; cache: {1: 10, 3: 30}
• get(2): key 2 was evicted; returns -1

Every operation is $O(1)$ because OrderedDict uses a doubly-linked list under the hood.

The From-Scratch Approach

Interviewers often want you to implement this without OrderedDict. The canonical approach is a doubly-linked list combined with a hashmap. The DLL stores nodes in access order (most recent at the tail, least recent at the head). The hashmap maps each key to its node, enabling $O(1)$ lookup. On every get or put, you detach the node and reattach it at the tail. On eviction, you remove from the head.

class Node:
    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}
        # sentinel head (LRU end) and tail (MRU end)
        self.head, self.tail = Node(), Node()
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_to_tail(self, node):
        node.prev, node.next = self.tail.prev, self.tail
        self.tail.prev.next = self.tail.prev = node

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_to_tail(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, value)
        self._add_to_tail(node)
        self.map[key] = node
        if len(self.map) > self.cap:
            lru = self.head.next
            self._remove(lru)
            del self.map[lru.key]

Sentinel head and tail nodes eliminate all null checks on boundary operations, a small trick that makes the code much cleaner.

LFU Cache

LeetCode 460 raises the difficulty. LFU is harder. Instead of evicting the least recently used key, you evict the least frequently used one, breaking ties by recency (i.e., among keys with the same minimum frequency, evict the least recently used).

Frequency Buckets

The key data structure is a hashmap that maps each frequency count to an OrderedDict of keys at that frequency. You also keep a min_freq variable tracking the current minimum. On every access (get or put), you move the key from its current frequency bucket to the next one. When you need to evict, you pull from the front of the min_freq bucket.

from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.key_val = {}          # key -> value
        self.key_freq = {}         # key -> frequency
        self.freq_keys = defaultdict(OrderedDict)  # freq -> OrderedDict of keys
        self.min_freq = 0

    def _update(self, key):
        freq = self.key_freq[key]
        del self.freq_keys[freq][key]
        if not self.freq_keys[freq] and freq == self.min_freq:
            self.min_freq += 1
        self.key_freq[key] = freq + 1
        self.freq_keys[freq + 1][key] = None

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

    def put(self, key: int, value: int) -> None:
        if self.cap == 0:
            return
        if key in self.key_val:
            self._update(key)
            self.key_val[key] = value
        else:
            if len(self.key_val) == self.cap:
                evict_key, _ = self.freq_keys[self.min_freq].popitem(last=False)
                del self.key_val[evict_key]
                del self.key_freq[evict_key]
            self.key_val[key] = value
            self.key_freq[key] = 1
            self.freq_keys[1][key] = None
            self.min_freq = 1

When a new key is inserted, min_freq resets to 1 because the new key has frequency 1 and is always a candidate for eviction. When the min-frequency bucket becomes empty after an update and its frequency equals min_freq, increment min_freq. This is the only time you need to update it on access.

Complexity

Both LRU and LFU achieve $O(1)$ amortized time for all operations. Space is $O(capacity)$ for LRU, and $O(capacity)$ for LFU as well, since the frequency maps only hold as many entries as the cache allows.

Recognizing this pattern

You're probably looking at LRU/LFU cache design when:

• The problem says "design a cache with a fixed capacity" and an explicit eviction policy.
• You need O(1) get and O(1) put on a key-value store with bounded size.
• Eviction is governed by recency (least recently used) or frequency (least frequently used).
• A hashmap alone is not enough: you also need ordered access to "which key goes next."

Common templates:

• LRU via hashmap + doubly linked list: list orders by recency; map gives O(1) node lookup. Example: LRU Cache.
• LRU via OrderedDict: Python's OrderedDict.move_to_end and popitem(last=False) collapse the implementation. Example: LRU Cache.
• LFU via frequency-bucketed lists: map keys to nodes, map frequencies to doubly linked lists of nodes; track the current minimum frequency. Example: LFU Cache.
• First Unique Number stream: same hashmap-plus-linked-list idea adapted to "first key with count 1." Example: First Unique Number.