Design I — Composing for O(1)

Review boundary and corrected contracts

Python dicts do preserve insertion order, but do not expose O(1) arbitrary recency moves. OrderedDict already supplies move_to_end and popitem(last=False). The explicit linked-list cache is pedagogical; zero capacity drops writes safely and negative capacity is rejected.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Own LRU Cache completely, and extract the general technique: when no single data structure gives O(1) for every operation, compose two so each covers the other's weakness.

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

Why this session exists

LRU Cache is a useful design exercise because it forces lookup and recency ordering to stay synchronized. Aim to write the implementation from its invariants rather than memorize pointer assignments; the practice timings below are personal targets, not hiring-frequency evidence.

A Python dict gives expected O(1) lookup and preserves insertion order, but does not directly provide O(1) moves to arbitrary recency positions. The linked list provides explicit recency order and known-node rewiring; OrderedDict is a valid library alternative.

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 use a constant number of pointer assignments 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. At every public-method boundary the membership and node-identity invariants must hold. Moving an existing node changes links but not the map; insertion and eviction update both memberships.

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):
        if capacity < 0:
            raise ValueError("negative capacity")
        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:
        if self.cap == 0:
            return
        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. Their cost is two permanent nodes and initialization of their linking pointers.

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.

Insert Delete GetRandom keeps the same composition principle but changes what the second structure must provide. LRU needed a recency order, so its map pointed into a linked list. Uniform random selection needs a dense set of indexable slots, so this map points into an array instead. Order is now disposable: when deletion leaves a hole, move the last value into it and update that value's map entry. The shared invariant is still that both structures describe exactly the same members.

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.

Python's collections.OrderedDict has efficient move_to_end and popitem(last=False) operations for an expected-constant-time LRU under normal hashing assumptions. Know that it exists and say so — it shows you know the standard library. Then write the explicit version, because a reviewer is asking about the data structure, not about your import statements. Offering the shortcut and then doing the real work reads well; offering only the shortcut does not.

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. A dense array is a convenient way to give every stored member one equally likely index; it is not the only possible random-sampling representation.

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:

Plain dict alone. Insertion order exists, but moving arbitrary entries and efficiently removing the oldest must be analyzed for the chosen operations. OrderedDict explicitly supports recency moves and endpoint eviction.

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

OrderedDict. This standard-library combination already supports key lookup, move_to_end and popitem(last=False); it is a valid alternative to the explicit teaching implementation.

The plain map and list have different limitations; OrderedDict already combines the needed capabilities. 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 derive the public methods from their membership and recency obligations.

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. Sentinels keep those boundary cases on the same code path.

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: insertion and eviction update both memberships; a recency move rewires only the existing node. Verify the invariants after each complete public operation.

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.

Myth: Python's dict preserves insertion order since 3.7, so a plain dict is already an LRU cache — just delete and reinsert a key to mark it recent.

Why: A regular dict preserves insertion order, and deleting then reinserting a key can move it to the newest end. That observation is useful, not a myth to dismiss. It does not by itself give a documented efficient oldest-entry eviction primitive or an efficient move to the leftmost end. OrderedDict explicitly provides endpoint movement and FIFO popitem(last=False). The explicit list is for learning those mechanics; a library implementation is a valid choice when the task permits it. Neither design is automatically a thread-safe or TTL-aware production cache.

Steps 1: A hash map gives expected constant-time key lookup under the usual hashing assumptions. Python dict also preserves insertion order; lookup and recency maintenance are different operations.

Steps 2: LRU eviction needs the oldest access, not merely the oldest insertion. Reads and updates must explicitly change recency; the linked list makes both endpoints available.

Steps 3: Because a doubly-linked node stores both neighbours, unlinking it is a constant number of pointer writes given only the node itself.

Steps 4: Because the map can store node references as its values, obtaining the node for a key is O(1), which is exactly the precondition the unlink operation needs.

Steps 5: Because reordering is then unlink plus relink at the head, and both are constant, every cache operation is a constant number of map and pointer operations.

Steps 6: Check structural work, not identical latency: get and put perform a bounded number of map operations and link rewrites independent of capacity. Allocation, hash collisions, resizing and memory locality can still change observed timings.

Picture: A library where the hash map is the card catalogue and the linked list is a single long shelf. The catalogue tells you exactly which shelf slot a book is in, so you never walk the shelf looking. Once your hand is on the book you can pull it out and push it in at the front in one motion, because you can see both neighbours.

Trigger: Fires whenever a design spec demands O(1) for operations that individually suggest different data structures.

Name: Hash map plus explicit doubly-linked list

Gain: Exposes each pointer operation and the map/list invariant. Frequency or expiry policies need additional state and their own invariants; they do not follow automatically from LRU.

Cost: Roughly forty lines with sentinels; several places to introduce a pointer bug; you must remember that nodes carry their key

Name: OrderedDict with move_to_end

Gain: A concise standard-library implementation with explicit endpoint movement and FIFO eviction.

Cost: Hides the pointer mechanism being studied. LFU can use OrderedDict as each frequency bucket, but still needs a frequency map and minimum-frequency tracking.

Pick: Write the explicit map-plus-list version whenever the question is phrased as 'design' or 'implement', which is the signal that the mechanism is the subject. Use OrderedDict when a cache is incidental to a larger problem you are solving, or in real code where you want the shortest correct implementation.

Complexity

LRU get: expected O(1) — one map lookup and a constant number of link writes; a miss leaves recency unchanged.

LRU put: expected amortized O(1) under usual dictionary assumptions — lookup, optional eviction and insertion, and bounded link rewiring. Worst-case hash behavior and occasional resizing are not constant-time latency guarantees.

Space: O(capacity + 1) — one node and one map entry per cached key plus two sentinels. The node holds an additional reference to its key, not a copied key object; Python object and container overhead still matter.

RandomizedSet: expected amortized O(1) for insert and remove, using usual hash-table and dynamic-array assumptions. getRandom selects a uniform index from a nonempty dense list, so each member has probability 1/n. Space O(n) holds references in the array and map rather than duplicating each value object. Empty getRandom is outside the exercise contract and random.choice raises IndexError.

LFU: expected O(1) get and put with a key-to-node map, frequency-to-recency-list map, and running minimum frequency. Insertion starts at frequency 1 and resets the minimum to 1. Access removes the node from frequency f and inserts it at the most-recent end of f+1; if the old bucket empties and f was the minimum, increment the minimum. Eviction removes the least-recent node in the minimum-frequency bucket, resolving ties by LRU. This is a design sketch, not an executed LFU implementation; arbitrary deletion or expiry needs additional minimum-frequency logic.

Quiz

Self-check (answer follows each question).

Q: Why must LRU nodes store their key when the map is already keyed by key?

A: On eviction you start from the node at the tail and need to delete its map entry. Without the key stored in the node you would have to scan the map for a matching value, which is O(n) and defeats the design.

Q: Why a doubly-linked list rather than a singly-linked one?

A: Unlinking a node requires rewriting its predecessor's next pointer. A singly-linked list forces a walk from the head to find the predecessor, making removal O(n). The back pointer makes it O(1).

Q: What do the head and tail sentinel nodes buy you?

A: Every linked real node has both neighbors, even in an otherwise empty list, so unlink and insertion avoid separate endpoint null branches. The sentinels themselves are never removed. Exact line-count savings depend on the alternative implementation.

Q: In RandomizedSet.remove, what are the two map updates required and why?

A: Set the moved last element's index to the vacated position, and delete the removed value's entry. Forgetting the first leaves a stale index that only causes a failure on some later removal.

Q: Why does GetRandom require an array rather than working directly off a hash set?

A: A Python set has no constant-time positional-access API. The dense array gives each member exactly one slot, so a uniform index gives a uniform member. Converting a set to a list for every sample costs O(n); uniform sampling in general does not require this particular representation.

Q: Sketch what LFU needs beyond LRU, and why it is harder.

A: A key-to-node map, frequency-to-recency-list map and minimum frequency. On access move f to f+1; if the emptied f bucket was minimum, advance it to f+1. New keys enter at frequency 1. Evict the least-recent member of the minimum-frequency bucket. These transitions maintain both frequency priority and LRU tie-breaking; arbitrary deletion needs more bookkeeping.

Stretch: true

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.

• When no single structure gives O(1) for every required operation, compose two so each covers the other's weakness.

• LRU = hash map for O(1) lookup + doubly-linked list for O(1) reordering, with map values pointing at list nodes.

• Sentinel head and tail nodes eliminate every null check in the remove and insert helpers. Always use them.

• Nodes must store their key, because eviction starts from a node and needs to delete the corresponding map entry.

• GetRandom needs a dense array; deletion from the middle becomes O(1) via swap-with-last, and the moved element's index must be updated.

• Mention OrderedDict, then write the explicit version. The mechanism is what is being evaluated.

Corrective source notes

• collections — Python 3.14 documentation — endpoint reordering, dict emulation and FIFO eviction. Rechecked 2026-10-09.
• Mapping types — dict preserves insertion order (language guarantee since Python 3.7). Rechecked 2026-10-09.
• random.choice — chooses from a nonempty sequence; empty input raises IndexError. Rechecked 2026-10-09.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.