Designing a data structure

A design question — "implement an LRU cache", "insert, delete and get-random in constant time" — is not asking for a clever idea. It is handing you a contract: a list of operations, each with a required complexity, all of which must hold simultaneously. Candidates lose these questions by picking a structure first and discovering on the third operation that it cannot meet the third line.

Write the contract before the code

For an LRU cache the contract is four lines, and writing them down takes twenty seconds:

Operation	Requirement
get(key)	return the value, O(1)
put(key, value)	insert or overwrite, O(1)
every access	mark that key as most recently used, O(1)
at capacity	evict the least recently used key, O(1)

Now test each candidate structure against all four lines, not the first one.

A hash map alone passes lines 1 and 2 — O(1) average, which is the weaker of the two guarantees pulled apart in queues and amortised cost — and fails 3 and 4: it has no order, so finding the least recently used key means scanning every entry. At a capacity of 10,000, that scan is 10,000 pointer chases at roughly 100 ns each ≈ 1 ms per eviction — slower than the 0.5 ms datacenter round trip and the 100 µs SSD read the cache exists to avoid. A cache that is slower than its origin is not a cache.

An array of keys in recency order passes 3 and 4 and fails 1 and 2: finding a key is a linear scan, and moving one to the front shifts everything behind it.

A doubly linked list in recency order passes 3 and 4 outright — unlinking a node and splicing it to the front is six pointer writes, two to close the gap the node left behind and four to seat it after the head, O(1) no matter where in the list it sits — but only if you already hold the node. Finding it means walking the list, and pointer chasing is the slow direction, as pointer surgery covers.

Nothing single-structure satisfies all four. That is the answer, not a dead end: the map supplies the address, the list supplies the order.

An LRU cache built from a hash map for O(1) lookup and a doubly linked list for O(1) recency, kept in sync on every eviction100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

The implementation, and the one line people forget

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

class LRUCache:
    def __init__(self, capacity):
        self.cap, self.map = capacity, {}
        self.head, self.tail = Node(), Node()      # sentinels
        self.head.next, self.tail.prev = self.tail, self.head

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

    def _push_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return -1
        self._unlink(node)
        self._push_front(node)
        return node.val

    def put(self, key, val):
        if key in self.map:
            node = self.map[key]
            node.val = val
            self._unlink(node)
            self._push_front(node)
            return
        if len(self.map) == self.cap:
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]          # the line people forget
        node = Node(key, val)
        self.map[key] = node
        self._push_front(node)

The two sentinel nodes are the dummy-head habit again: with a permanent head and tail, _unlink never has to ask whether a node is first or last, and there is no empty-list branch anywhere.

del self.map[lru.key] is why a node stores its key as well as its value. The list knows which node to evict; only the key tells the map which entry to remove. Omit it and the map grows without bound while handing out nodes that were unlinked minutes ago — a lookup that returns a value the cache no longer holds, and a memory leak, from one missing line.

The general move, and what it costs you

When no single structure meets every line of the contract, use two, and give each one the job it is good at. The pattern recurs:

• Insert, delete and get-random in O(1): an array for uniform random choice by index, plus a map from value to its index. Deleting swaps the doomed element with the last one, pops, and fixes that one index in the map.
• A stack with min() in O(1): the values stack, plus a second stack whose top is always the minimum so far. Both are pushed and popped together, which is the sync obligation made trivial.
• LFU: a map from key to entry, plus a map from frequency to a list of keys at that frequency, plus a running minimum frequency.

The cost is always the same, and it is worth stating before an interviewer finds it: two structures mean one invariant that code, not the language, has to maintain. For the LRU cache it is exactly this — the keys in the map are precisely the keys of the nodes in the list, and the map's value for a key is the node currently holding it. Every mutation must restore that invariant before it returns. Every bug in this class of problem is a path that leaves it broken: an eviction that skips the map, an overwrite that creates a second node for a key, an unlink without a re-link.

So write the pairs down as pairs. Never del self.map[k] on one line and the unlink three lines later behind a branch — put them in one helper and call the helper. The complexity is the easy part; the synchronisation is where the implementation actually fails.

In an interview

Open with the contract, out loud, before writing anything: "get is O(1), put is O(1), and eviction has to find the least recently used key in O(1). A map gives me the first two but no ordering, so I will pair it with a doubly linked list." That is the whole answer, stated in thirty seconds, and everything after it is transcription.

Then declare the invariant, and again when you write the eviction. Interviewers running this question watch for exactly one thing after the code compiles: does the candidate delete the key from the map. Saying it before you write it is worth more than fixing it after they ask.

The mistake that loses points is reaching for OrderedDict or functools.lru_cache as the answer. It is the right production choice and the wrong interview answer, because the question is asking how those are built. Say that you would use the library in real code, then build it.

Check yourself

Why does a hash map plus a singly linked list not satisfy the contract?

Eviction and move-to-front both need to unlink a node, which needs its predecessor. In a singly linked list finding the predecessor is an O(n) walk from the head, so line 3 of the contract fails. The prev pointer is what buys O(1).

On eviction you unlink the tail node but forget del self.map[lru.key]. Describe the first two symptoms.

The map keeps growing past capacity, so memory rises without bound; and a later get on the evicted key finds a node that is no longer in the list, returning a value the cache has already thrown away — and moving that orphan to the front corrupts the list.

A cache holds 10,000 entries and you scan the map to find the least recently used one. Why is that not merely "a bit slower"?

10,000 scattered reads at roughly 100 ns each is about 1 ms per eviction, which is longer than the 0.5 ms datacenter round trip and the 100 µs SSD read that the cache was added to avoid. The cache would cost more than the fetch it replaces.