L51 · Design I — Composing for O(1)

Series: LeetCode — From Basics to Interview-Ready · Session 51 / 65 · Phase 3 · Advanced & specialised

Why this session exists

LRU Cache is possibly the most-asked design-coding question there is. Own it completely — not "I remember it uses a linked list" but able to write the whole thing, dummy nodes included, in eight minutes without hesitating. It is asked so often that fumbling it reads as unprepared in a way that fumbling a hard DP does not.

But memorising one problem is a poor use of a session. The transferable idea is composition. A hash map gives O(1) lookup by key and no notion of order. A doubly-linked list gives O(1) removal and insertion at a known node but O(n) search. Neither alone gives you an LRU cache. Together they do, because the hash map's values are pointers directly into the list — so the map supplies the "where" and the list supplies the "reorder cheaply".

Once you see that move, Insert Delete GetRandom falls out immediately. A hash set gives O(1) membership but no way to sample uniformly. An array gives O(1) random sampling but O(n) deletion. Compose them — array of values, map from value to its index — and delete becomes swap-with-last-then-pop, which is O(1). Same move, different pair.

LFU is the third instance and it is genuinely harder, because it needs a frequency dimension on top. I will sketch it but not dwell; the return on LFU is much lower than on LRU.

The question to ask when a design problem demands O(1) for operations that seem to conflict: which structure gives me each operation cheaply, and can I keep both in sync?

Blank-file warm-up

Five minutes, empty file, no notes. Write the doubly-linked list core:

1. A node with key, value, prev, next.
2. _remove(node) — unlink a node given only the node itself.
3. _add_front(node) — insert immediately after the head sentinel.

Both helpers should be three lines each and contain no conditionals. If you find yourself writing if node.prev is None, you have not used sentinel nodes, and adding them is the fix.

Pattern anatomy

The shape that summons this pattern: a design problem stating O(1) average time for a set of operations that no single structure provides together.

The invariant for LRU: the map and the list contain exactly the same keys at all times, the map's value for a key is the list node holding that key, and the list is ordered by recency with the most recent adjacent to the head sentinel.

That "exactly the same keys" clause is where bugs live. Every mutation must touch both structures or neither.

class Node:
    __slots__ = ("key", "val", "prev", "next")
    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 = {}                       # key -> Node
        self.head = Node()                  # sentinel: most recent side
        self.tail = Node()                  # sentinel: least recent side
        self.head.next = self.tail
        self.tail.prev = self.head
 
    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
 
    def _add_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
 
    def get(self, key: int) -> int:
        node = self.map.get(key)
        if node is None:
            return -1
        self._remove(node)                  # touch: move to front
        self._add_front(node)
        return node.val
 
    def put(self, key: int, value: int) -> None:
        node = self.map.get(key)
        if node:
            node.val = value
            self._remove(node)
            self._add_front(node)
            return
        if len(self.map) == self.cap:
            lru = self.tail.prev            # least recently used
            self._remove(lru)
            del self.map[lru.key]           # needs lru.key — this is WHY nodes store keys
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)

Two details carry the whole design.

The sentinels. head and tail are permanent dummy nodes that are never removed and never hold data. Because of them, every real node always has a non-null prev and next, so _remove and _add_front need no null checks at all. Without sentinels those helpers grow four conditionals each and the empty-list and single-element cases become separate code paths. Sentinels are two extra lines in the constructor that delete roughly twenty lines of branching.

Nodes store their key. This looks redundant since the map is keyed by key. It is not. On eviction you have a node — the one before the tail sentinel — and you must remove its entry from the map. Without node.key you would have to search the map for the matching value, which is O(n) and destroys the whole design. This is the single most common omission.

And the second composition, Insert Delete GetRandom:

import random
 
class RandomizedSet:
    def __init__(self):
        self.items = []                     # dense array for uniform sampling
        self.index = {}                     # value -> position in items
 
    def insert(self, val: int) -> bool:
        if val in self.index:
            return False
        self.index[val] = len(self.items)
        self.items.append(val)
        return True
 
    def remove(self, val: int) -> bool:
        i = self.index.get(val)
        if i is None:
            return False
        last = self.items[-1]
        self.items[i] = last                # move last into the hole
        self.index[last] = i
        self.items.pop()
        del self.index[val]
        return True
 
    def getRandom(self) -> int:
        return random.choice(self.items)

The swap-with-last trick is the key: removing from the middle of an array is O(n), but if order does not matter you can overwrite the hole with the last element and pop, which is O(1). The map must be updated for the moved element, and forgetting that line is the standard bug.

The cue

You are looking at a composition-design problem when the statement contains these tells:

1. "O(1) average time for all operations" stated explicitly, with a set of operations that no single structure handles. This is the loudest tell in the session.
2. The word "Design" or "Implement" followed by a class specification. You are being asked for a data structure, not an algorithm.
3. Operations that pull in different directions — fast lookup by key and an ordering, or fast membership and uniform random sampling. The tension is the whole problem.
4. An eviction or expiry policy — least recently used, least frequently used, time-to-live. Policies need auxiliary ordering that the primary index does not provide.
5. "Get a random element" alongside insert and delete. This specifically means a dense array, because uniform sampling requires contiguous indices.

Tell 3 is the generalisable one. When you notice two required operations that seem to demand incompatible structures, stop looking for one clever structure and start looking for two ordinary ones plus a synchronisation discipline.

Guided solve

LRU Cache — implement get(key) and put(key, value), both O(1) average. When capacity is exceeded, evict the least recently used entry.

Start by listing what each operation needs, because that list dictates the design:

• get needs to find a value by key: hash map.
• get also counts as a use, so it must mark the entry as most recent: some ordering structure.
• put on an existing key updates and marks as recent.
• put on a new key at capacity must find and remove the least recent: the ordering structure must expose its tail cheaply.

Now consider each single structure and watch it fail:

Hash map alone. Lookup is O(1) but there is no order, so finding the least recently used means scanning everything. O(n) eviction.

Array or list alone. Order is natural but finding a key is O(n).

Ordered dict / linked list alone. Order is natural and the ends are cheap, but locating an arbitrary key requires a walk. O(n).

Each fails on a different operation, and that is the signal. Compose the hash map with a doubly-linked list, and make the map's values be the list nodes. Now finding a key is O(1) via the map, and once you have the node, unlinking it is O(1) because a doubly-linked node knows both neighbours.

Why doubly and not singly linked? To unlink a node in a singly-linked list you need its predecessor, which requires a walk from the head — O(n). The backward pointer is exactly what buys O(1) removal, and that is the reason the "doubly" is not incidental.

Why a linked list rather than an array? Because moving an element to the front of an array shifts everything after it, which is O(n). Linked-list nodes move by pointer rewiring, independent of position.

The two helpers, _remove and _add_front, are the whole implementation. Every public operation is a combination of them plus a map update. Write the helpers first, verify them mentally on a two-element list, then the public methods become three lines each.

The eviction path is where the design's details converge. At capacity you take self.tail.prev, which is the least recently used real node. You unlink it. Then you must delete its map entry, and for that you need its key — which is why nodes store keys. Then insert the new node at the front and add its map entry.

Trace a capacity-2 cache: put(1,1), put(2,2), get(1), put(3,3). After the first two puts the list is head -> 2 -> 1 -> tail. get(1) moves node 1 to the front: head -> 1 -> 2 -> tail, returns 1. put(3,3) is at capacity, so evict tail.prev which is node 2, delete key 2 from the map, insert 3 at front: head -> 3 -> 1 -> tail. A subsequent get(2) correctly returns -1.

Solo timed

Fifteen minutes each, timer running, no editorial until it fires.

• LRU Cache — the full explicit implementation with sentinels. Target eight minutes. If it takes longer, that is the finding, and it is worth a second attempt tomorrow rather than moving on.
• Insert Delete GetRandom O(1) — array plus index map, swap-with-last on removal. The trap is forgetting to update the moved element's index.

If both land early, sketch LFU Cache. Do not aim to finish it; aim to identify the three structures it needs and how they interact.

Common failure modes

Nodes not storing their key. Eviction then requires searching the map by value, which is O(n) and defeats the entire design. This is the most common single error.

No sentinel nodes. Every helper gains null checks, and the empty-list and one-element cases become separate branches. The code roughly triples in size and the bug rate with it.

Forgetting that get is a use. A cache where reads do not update recency is not an LRU cache. Easy to omit, and the failing test looks mysterious.

Map and list drifting out of sync. Removing a node without deleting the map entry, or adding a map entry without linking the node. Discipline: every mutation touches both, in adjacent lines, never separated by other logic.

Not updating the moved element's index in RandomizedSet.remove. After items[i] = last, the map still says last lives at the end. One line, always forgotten, and the failure only appears on a later removal.

Using a singly-linked list. Removal needs the predecessor. Without a back pointer you walk, and O(1) becomes O(n).

Capacity of zero. An edge case worth one guard line if the constraints permit it.

Complexity

LRU get: O(1) — one hash lookup, one unlink, one relink. All constant.

LRU put: O(1) — one hash lookup, optionally one eviction which is a constant number of pointer writes plus one map delete, then one insert.

Space: O(capacity) — one node and one map entry per cached key. Nodes carry the key redundantly with the map, which roughly doubles the per-entry key storage; that is the price of O(1) eviction and it is worth paying.

RandomizedSet: O(1) for all three operations. Insert appends and writes one map entry. Remove does a constant number of array and map writes thanks to swap-with-last. GetRandom is one random index into a dense array. Space O(n) with each element stored twice — once in the array, once as a map key.

LFU: O(1) for get and put as well, but it needs three structures — a key-to-node map, a frequency-to-list map, and a running minimum frequency. Each entry moves between frequency lists on access. It is a real step up in bookkeeping and the constant factor is noticeably worse.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Make an exception for LRU Cache: review it every 30 days regardless of status. It is asked often enough that the marginal cost of over-reviewing it is smaller than the cost of fumbling it once.