Dictionary compositions

1. The absence

A dict is fast for two things: writing, and looking a value up when you already know the key. Both O(1).

What it will not do is store any relationship between the keys. That is the price of hashing being cheap: the whole point is to scatter keys so that no two of them are near each other.

So a dict is a function from key to value, and function evaluation is pointwise. Every question that needs two entries in the same breath is outside what it does:

• which key has the biggest value
• which key was inserted first, or touched least recently
• how many keys fall in this range
• what was the value at time t

None of those are answerable in less than O(n), because the only way to compare entries is to look at all of them.

The fix is always the same shape. Keep the dict, and put a second structure next to it that maintains the relationship the dict threw away. Two structures over the same data, two different access paths, O(n) memory. That is a composition.

There are three axes you might want to compare on, and one structure for each.

2. Comparing values → dict + heap

The question: which key has the biggest value, right now, while values keep changing.

The dict holds the current value per key. The heap holds (-value, key) tuples and answers “what is the largest.” Push on every write; peek to read.

class Scoreboard:
    def __init__(self):
        self.scores = {}
        self.heap = []

    def add_score(self, player, points):
        self.scores[player] = self.scores.get(player, 0) + points
        heapq.heappush(self.heap, (-self.scores[player], player))

    def top_player(self):
        while self.heap and -self.heap[0][0] != self.scores.get(self.heap[0][1]):
            heapq.heappop(self.heap)
        return self.heap[0][1] if self.heap else None

Two things carry the whole pattern.

The tuple is ordered by the axis you compare on. (-score, player), not the other way round. The score is what gets compared and the player rides along. Negated because Python’s heap is a min-heap and the question wants a max.

The dict is the source of truth and the heap is allowed to lie. Updating a player’s score leaves the old entry buried in the middle of the heap where it can’t be reached. So it stays there and is discarded when it surfaces.

2.1 Lazy deletion

Pop entries off the top while they disagree with the dict, then peek at the first one that agrees. Never pop the valid entry: a query called twice must return the same answer both times, and popping consumes it.

Two ways to detect a stale entry, and they answer different questions:

• Content staleness — does the value on the heap entry still match the dict? Enough when you only care that the number is current.
• Identity staleness — is this the same entry that was pushed? Needs a unique id or generation counter in the tuple, because two entries can carry the same value and still be different objects. The case that forces it: a score goes 5 → 8 → 5, and the original 5 entry now passes a content check it should fail.

2.2 Why the popping is affordable

A single query can pop a thousand stale entries and cost O(k log n). That call is genuinely slow, and per-call analysis has nothing useful to say about it.

The bound is over the sequence instead. Every push comes from a write, so total pops ≤ total pushes ≤ m operations. Spread across m operations that is O(log n) amortized, and it holds for the worst sequence an adversary could write, with no assumptions about distribution.

Which is the thing to notice about amortized analysis generally: you cannot reason about the cost inside the function, because the work one operation does was created by a different one.

2.3 When the heap alone is enough

Drop the dict when both are true: values never change after insertion, and the only question ever asked is about the top. Then nothing goes stale and there is nothing to reconcile.

Keep the dict as soon as either fails. Mutation means the heap needs a source of truth to be checked against, and lookup-by-key is something a heap cannot do at all.

2.4 When lazy deletion is not needed

The trigger is narrow: something has to be removed from the heap that is not at the top. Cancel an order sitting in the book, update a value already pushed, invalidate an entry from outside the heap’s ordering.

If every removal happens at the minimum, the heap never lies and you just pop. A parking garage handing out the lowest-numbered free spot is exactly this: spots leave through the top and come back as pushes, so there is no staleness anywhere.

The compressed test: does the data change after it enters the heap?

3. Comparing use order → dict + doubly linked list

The question: which key was touched least recently.

Insertion order alone doesn’t need a composition. Python dicts have preserved it since 3.7, and a plain deque of keys handles fixed-capacity eviction: append on write, popleft on overflow, delete the evicted key from the dict. O(1) throughout.

LRU is the harder one, because reading counts as touching. A key inserted first and then read a hundred times is the most recent, not the least. So every access has to move its key to the back, and that key is somewhere in the middle.

Nothing else does that move:

• a heap orders on value, which is the wrong axis entirely
• a deque is O(1) only at its ends; reaching into the middle is O(n) and there is no splice
• generation counters on a deque look like a rescue and aren’t: pushes would then happen on reads, so the structure grows with the number of operations rather than with the capacity, and the accounting that makes lazy deletion affordable breaks

A doubly linked list does it in four pointer writes. The dict maps key to node, so the node is reachable in O(1) without traversing.

class Node:
    def __init__(self, key, value):
        self.key = key          # a node must be able to name itself:
        self.value = value      # eviction hands you a node and you delete its dict entry
        self.prev = None
        self.next = None

Two sentinel nodes, permanent and empty, sit at the head and tail. They mean there is always something on both sides of a real node, so unlinking is unconditionally four assignments instead of four assignments plus two null checks. That is the empty-container bug killed structurally rather than guarded against.

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

def _add_to_tail(self, node):
    prev = self.tail.prev          # bind first: the next line destroys it
    prev.next = node
    node.prev = prev
    node.next = self.tail
    self.tail.prev = node

Write those two helpers before anything else. With them, get and put are three lines each; without them the same pointer surgery appears inline twice, which is where the bugs live.

Head end is least recent, tail end is most recent. get removes and re-adds at the tail. put on an existing key does the same after overwriting the value; on a new key at capacity it evicts head.next from both structures first.

Where the time goes. Nothing is saved, it is moved. A bare dict pays nothing on write and O(n) on eviction, because finding the least recently used means examining everything. The composition pays four pointer writes on every access so eviction is free, since the answer is always already at the head.

collections.OrderedDict is this pattern in the standard library, dict plus doubly linked list internally, with move_to_end and popitem(last=False). Which is why an interview asking for LRU will forbid it: using it skips the entire problem.

4. Comparing positions → dict + sorted list

The question: what was the value at time t, or how many entries fall in this range.

This family is shaped differently from the other two. In sections 2 and 3 a key has one current value and the second structure orders the keys against each other. Here each key accumulates many values over time, and the ordering being restored is within one key’s history rather than across keys. A version store keeps every value a key has held; a rate limiter keeps every timestamp a user has hit.

So the composition is nested rather than parallel. The dict maps key to its own sorted list, and binary search runs inside that list:

store = {"a": [(1, "v1"), (5, "v2")]}     # one timeline per key

Two lookups on two different axes: O(1) on the outer dict to find the key’s timeline, O(log n) inside that list to find the position within it.

Within a timeline, the entries are positions on a line rather than labels. A dict could tell you instantly whether timestamp 15 exists; it cannot tell you the closest timestamp below 15, because hashing destroyed adjacency on purpose. That is what the sorted list restores.

The list is sorted for free when data arrives in order, which it usually does for timestamps. You never sort and never shift, so insert is O(1) — an append. State that assumption out loud, because removing it is a standard part 2: out-of-order arrival makes insert bisect.insort, which is O(n).

Two queries, both off bisect:

• value as of t — bisect_right(times, t) - 1, the last entry at or below t. Guard the -1 case, which means nothing exists yet.
• count in a range — bisect_left(times, cutoff) gives the boundary, and len(times) - idx is the count. A boundary plus a length is a count; you never touch the elements.

5. Heap or sorted list

The two overlap enough to be worth separating. They are not competing on speed, they are competing on what they can answer.

A heap buys cheap inserts by refusing to maintain a full ordering. It surfaces the minimum and nothing else. A sorted list pays for the ordering up front and can then answer anything positional.

Two questions decide it, and neither needs a crossover computed:

1. Does the question name a rank, or a threshold?

Rank — “the max”, “top 10” — you chose k, it is small, the cost is bounded. Heap. This includes k = 1, which is the most common shape there is.

Threshold — “how many above X”, “everything before time t” — the data decides how many match, so a heap’s cost is unbounded and it may have to drain everything. Sorted list.

Most cases end here, because only one of the two can answer the question at all.

2. Only if it is a rank question and inserts are heavy: is the data already sorted?

If yes, the list costs nothing to maintain and answers strictly more. If no, the heap’s O(log n) insert against insort’s O(n) is a real difference.

5.1 Pay on the write or pay on the read

Every decision on this page is the same one underneath.

With w writes and q queries: a bare dict costs w + qn, since writes are free and every query scans. The composition costs w log n, since writes maintain the second structure and queries are amortized free.

n appears on both sides, but linearly on one and logarithmically on the other: the dict pays n per query, the composition pays log n per write. That gap is what makes the crossover arrive so fast. Many writes and almost no queries favours the plain dict, since a scan you rarely run is cheaper than an index you constantly maintain. Anything else favours the composition.

Counter is the same question in miniature. It is a plain dict with sugar and maintains no ranking, so most_common sorts at call time. Perfect for tally-then-ask-once; a trap when the max is queried repeatedly while counts change.

6. When none of this works

All three families precompute an ordering at write time. That only works if the ordering is fixed.

Dispatch the driver with the best rating - distance, where distance is measured from whoever is asking: the score cannot be computed at insertion, because the rider does not exist yet. Every query induces a different ordering over the same drivers, so there is nothing to maintain.

A heap fixes one ordering at insertion time. When the query defines the ordering, no heap survives.

The honest baseline is an O(n) scan of the dict, and it is the right thing to say first. A bound can prune it: walk in descending rating, keep the best actual score S, and stop at the first driver whose rating is ≤ S, since distance is never negative and no one below can beat it. That needs a structure you can iterate in order without destroying, which is a sorted list. Popping a heap and pushing everything back gets the same order and pays ~2k log n writes for it, which makes a read generate writes and is strictly worse.

Recognising that the previous part’s structure no longer fits is the point of a question like this. The trap is forcing the heap.

7. Mistakes

• Reaching for lazy deletion by reflex. It is for removals that are not at the top. Every exit through the minimum means the heap never lies.
• Popping the valid entry instead of peeking it. A query called twice must answer twice.
• Tuple ordered by the payload instead of the comparison axis. (score, player), never (player, score).
• Reading a defaultdict inside a validation check. The read inserts, so “removed” stops being detectable by absence. Four appearances in one week.
• Forgetting the second structure on eviction. popleft hands you a key; the dict entry has to go too.
• Not binding tail.prev before overwriting it. The old last node becomes unreachable and its next can never be fixed.
• Answering a threshold question with a heap. k is chosen by the data and can be all of n.