Shelf · DSA Patterns · Chapter 3

Chapter 3: The data-structure toolkit

A pattern is only as fast as the structure under it, so this chapter gives you six structures and the one question that picks between them, which is how things leave. By the end you can state the cost of each core operation with its assumption attached, and name the structure before you write the loop.

Difficulty
Priority
dsa-03-01Card 1 of 6

Arrays and dynamic-array operation costs

EasyP1 · Must knowKnow cold8 min
arraylistamortizedslicingshallow-copy

Why you care

Every Python ETL job you have written is built on list, so you already use a dynamic array daily and probably cannot say which operations are cheap. That gap shows up as a job that takes four minutes on 50,000 rows and four hours on 5 million, because somebody wrote rows = rows[1000:] in a loop or batch.pop(0) to "consume" a batch. Interviewers ask about append cost, middle insertion and slicing to separate people who count work from people who count lines. This card comes first because every later structure is compared against the array.

Explain like I'm 5

Picture a row of numbered lockers in a corridor. Opening locker 417 is instant because you walk straight to the number. Adding a locker at the far end is easy while there is spare wall; when the wall runs out, the school builds a longer corridor and moves everything across once. Adding a locker at the front shifts every other locker one slot down. Copying "lockers 100 to 200" means carrying 100 items to a new row.

Core concept

A list is a contiguous block of references with a length and spare capacity, so position is a direct jump.

  • Index read/write xs[i]: O(1).
  • Scan (in, index, count, max): O(n). in on a list is a scan, not a lookup.
  • append / pop() at the end: amortized O(1). Most calls use spare capacity; an occasional call reallocates and copies all n references. The claim is about the total over many calls, not each call.
  • insert(i, v) / pop(i) / del xs[i]: O(n - i), because the tail shifts. Front operations are O(n).
  • Slice xs[a:b]: O(k), k = b - a, and it allocates a new list. Slicing in a loop is a hidden quadratic.
  • Copy xs[:], list(xs): O(n) and shallow. The new list holds the same element objects.

Say the assumption with the cost: "append is amortized O(1) under geometric over-allocation". Use Complexity and amortization if pushed: n appends total O(n), so the average per call is O(1).

Decision rule: use a list when you read by position, append and remove at the end, or sort in place. Switch when you remove from the front (deque, Stacks, queues and deques), test membership repeatedly (set, Hash maps and sets under stated assumptions), or repeatedly want the smallest (heap, Heaps as partial order).

Minimal example Alias, copy and the repeated-row trap

Pythonruns
a = [1, 2, 3]
b = a
c = a[:]
a.append(4)
print(b, c)
grid = [[0] * 2] * 2
grid[0][0] = 1
print(grid)
rows = [[0] * 2 for _ in range(2)]
rows[0][0] = 1
print(rows)
Output
[1, 2, 3, 4] [1, 2, 3]
[[1, 0], [1, 0]]
[[1, 0], [0, 0]]

In production Catalogue batches, resize counting and shallow snapshots

Pythonruns
import sys
import time

def count_resizes(n):
    xs, last, changes = [], sys.getsizeof([]), 0
    for i in range(n):
        xs.append(i)
        size = sys.getsizeof(xs)
        if size != last:
            changes, last = changes + 1, size
    return changes

def elapsed(fn):
    start = time.perf_counter()
    fn()
    return time.perf_counter() - start

N = 20_000
print("resizes under 1% of appends:", count_resizes(N) < N // 100)

def tail_appends():
    xs = []
    for i in range(N):
        xs.append(i)

def head_inserts():
    xs = []
    for i in range(N):
        xs.insert(0, i)

print("head insert slower than append:", elapsed(head_inserts) > elapsed(tail_appends))

catalogue = [["SKU1", 100], ["SKU2", 250]]
snapshot = catalogue[:]
catalogue[0][1] = 90
print("shallow snapshot sees price:", snapshot[0][1])
deep = [row[:] for row in catalogue]
catalogue[1][1] = 200
print("row-copy snapshot keeps price:", deep[1][1])
try:
    [].pop()
except IndexError as exc:
    print(f"IndexError: {exc}")
Output
resizes under 1% of appends: True
head insert slower than append: True
shallow snapshot sees price: 90
row-copy snapshot keeps price: 250
IndexError: pop from empty list
Scenario A

In your world

The situation

Your nightly Jenkins job reads a 300,000-row price file from S3 into a list, then loads it into Postgres in batches of 1,000. To "take the next batch" you wrote batch = rows[:1000] then rows = rows[1000:]. It passed every test with 5,000 rows.

What actually breaks

Each rows = rows[1000:] copies the remaining list: 300 batches × 150,000 average remaining = 45 million reference copies, slow but green. Finance then sends a 4.8-million-row backfill: 4,800 × 2.4M = 11.5 billion copies. Jenkins kills the job at 61% loaded, and the audit table says RUNNING with no end time.

What you'd do on Monday

Never rebuild the list to consume it. Walk with an offset, so each slice is O(batch) and total work is O(n).

Python
for start in range(0, len(rows), BATCH):
    batch = rows[start:start + BATCH]   # O(BATCH), source untouched
    load(batch)
    audit.write(batch_no=start // BATCH, rows=len(batch))
Scenario B

Imagine you work at Nykaa

2.4M SKU price rows per hourly sync

The numbers

2.4M rows, batches of 1,000, so 2,400 slices. Rebuilding the list copies about 1.2M references per slice on average: 2,400 × 1.2M ≈ 2.9 billion pointer copies, roughly 23 GB of memmove at 8 bytes each, every hour.

What the Scenario-A answer does here

The Scenario A offset loop still works and its cost is flat. What breaks is the rest: 2.4M row dicts at an assumed 300 bytes is about 720 MB resident, and a rows[:] rollback snapshot shares every dict, so a later price edit corrupts it.

What flips at this scale

Stop materialising the whole list. Stream the file, build one batch of 1,000 at a time and checkpoint per batch in the audit table.

The trade-off you'd defend

I would defend a streamed batch loop over a full in-memory list, trading random access to any row for a flat memory ceiling and restartable batches.

Illustrative sizes and row counts; not Nykaa-published. The 300 bytes per row is an assumption.

Gotchas

Multiplying a list of lists

Symptom

Setting grid[0][0] = 1 changes every row; the printed grid shows the same value in each.

Cause

[[0] * m] * n repeats references to one inner list.

Fix

[[0] * m for _ in range(n)].

Shallow copy that shares inner rows

Symptom

A backup made with xs[:] shows the new price after an in-place edit to an inner list.

Cause

Slicing copies only the outer references.

Fix

[row[:] for row in xs].

Tricky questions

Is list.append O(1)?
Most people say

Yes, always constant time.

Actually

Amortized O(1). A call that triggers a reallocation costs O(n); the claim holds over a sequence of appends.

Scenario question

You're handed a function that removes processed records from the front of a 2-million-element list with pop(0) and is "mysteriously slow".

Model answer

I'd say each pop(0) shifts the remaining elements, so draining n items costs about n²/2 moves, around 2 trillion for 2 million. If order is FIFO I'd switch to a deque and popleft; if I only read once I'd iterate with an index. The trade-off is that a deque gives up cheap middle indexing.

Interview corner

CommonWhat are the costs of append, insert(0, x) and x in xs?
“I'd say append is amortized O(1) because of geometric over-allocation, insert(0, x) is O(n) because everything shifts, and in is an O(n) scan.”
TrickYou copy with ys = xs[:]. Are xs and ys independent?
“I'd say the lists are independent but the elements are not. It's a shallow O(n) copy, so if I'm going to mutate inner rows I copy at that level.”
Experience checkWhere has quadratic list work hit you?
“I'd cite a loader that re-sliced the remaining rows every batch. An offset loop made it linear.”

Memory hook

A corridor of numbered lockers: jump to any number, add at the far end, never at the front, and never carry a slice you can walk past.

If you remember only one thing:

Count how many elements move; the tail is cheap, the front and the copy are not.

Self-check

  1. Which list operations are O(n) but look like O(1)?

    insert(0, x), pop(0), x in xs, and xs[a:b] (O(b - a)).

  2. What does xs[:] share with xs?

    The element objects. Only the outer array is new.

  3. What does amortized O(1) append not promise?

    That every call is constant.

Prove it

Run the production block, then add a timing of xs.pop() n times versus xs.pop(0) n times for N = 20,000 and 40,000. Paste the four timings.

dsa-03-02Card 2 of 6

Hash maps and sets under stated assumptions

EasyP1 · Must knowKnow cold7 min
hash-mapsetcounterdefaultdictcollisions

Why you care

Most "make it fast" fixes in ETL code are one fix: replace a scan with a dict or set. Looking up an id in a list of 200,000 ids is a scan per row; in a set it is one hash and a probe. That swap turns hours into seconds, and it is also the source of sneaky bugs, because a dict silently creates, keeps or reorders things you assumed it would not. Interviewers ask because the real question is whether you know the cost is average and conditional on cheap hashing and well-spread keys.

Explain like I'm 5

Think of a coat-check desk with 64 numbered hooks. A clerk turns your ticket text into a hook number by a fixed rule, and later goes straight to that hook. Sometimes two tickets land on one hook, so the clerk checks a short chain. If the rule sends every ticket to hook 1, the desk is just a pile.

Core concept

A hash table turns a key into an integer, picks a slot, and compares keys in the slot to resolve collisions.

  • Insert, lookup, delete, membership on dict and set: average O(1), worst case O(n) when many keys collide. A constant __hash__ makes n inserts O(n²), because every key probes past all earlier ones.
  • Resizing: when the table fills, one insert rebuilds every entry, O(n); the sequence is amortized O(1).
  • Hashable keys are immutable: int, str, tuple of hashables. A list raises TypeError: unhashable type.
  • Order versus equality: a dict iterates in insertion order (3.7+), but == ignores order. A set has no order to rely on.
  • Counter: a missing key reads as 0 without inserting; a count decremented to 0 stays as a key.
  • defaultdict: reading a missing key creates it, so d[k] as a "check" mutates the map.

Decision rule: a set for "seen before?", a dict when you need a value, Counter for frequencies, defaultdict for grouping. Do not use hashing when you need sorted order, ranges or nearest neighbours; use sorted data with binary search or a tree (Trees and tries by key structure).

Minimal example Counter and defaultdict mutate on read

Pythonruns
from collections import Counter, defaultdict
c = Counter("banana")
print(c["z"], "z" in c)
c["a"] -= 3
print(c["a"], "a" in c, len(c))
g = defaultdict(list)
if g["missing"] == []:
    print("lookup created key:", "missing" in g)
print({"a": 1, "b": 2} == {"b": 2, "a": 1})
Output
0 False
0 True 3
lookup created key: True
True

In production Settlement dedupe, grouping and a degenerate hash

Pythonruns
from collections import Counter, defaultdict

class BadKey:
    calls = 0
    def __init__(self, v):
        self.v = v
    def __hash__(self):
        return 1
    def __eq__(self, other):
        BadKey.calls += 1
        return self.v == other.v

def probes(n):
    BadKey.calls = 0
    table = {}
    for i in range(n):
        table[BadKey(i)] = i
    return BadKey.calls

print("200 colliding keys do over 10x the work of 20:", probes(200) > 10 * probes(20))

rows = [
    ("S1", "m1", 500),
    ("S2", "m2", 300),
    ("S1", "m1", 500),
    ("S3", "m1", 200),
]
seen = set()
by_merchant = defaultdict(int)
dups = Counter()
for settlement_id, merchant, amount in rows:
    if settlement_id in seen:
        dups[settlement_id] += 1
        continue
    seen.add(settlement_id)
    by_merchant[merchant] += amount
print(dict(by_merchant), dict(dups))

try:
    seen.add(["S9"])
except TypeError as exc:
    print(f"TypeError: {exc}")
Output
200 colliding keys do over 10x the work of 20: True
{'m1': 700, 'm2': 300} {'S1': 1}
TypeError: unhashable type: 'list'
Scenario A

In your world

The situation

Your settlement loader reads a day of rows from S3 and skips any settlement_id already loaded. You wrote if sid in loaded_ids, where loaded_ids is a list pulled from Postgres, 1.8 million ids long.

What actually breaks

Each row scans up to 1.8M ids. With 400,000 new rows that is up to 400,000 × 1.8M = 720 billion comparisons. On Jenkins it runs six hours and gets killed, leaving the audit row at 212,044 rows loaded, a total that matches nothing finance has.

What you'd do on Monday

Make membership a hash lookup and normalise the key.

Python
loaded = set(row[0] for row in cur.execute("select settlement_id from settlements"))
new_rows = []
for row in rows:
    sid = row.settlement_id.strip()
    if sid in loaded:
        continue
    loaded.add(sid)                 # also dedupes inside today's file
    new_rows.append(row)

Building the set is O(n) once; each check is then average O(1). The strip() matters: "S1 " and "S1" are different keys.

Scenario B

Imagine you work at PhonePe

2,000 payment events per second, 24 h dedupe window

The numbers

2,000 events/s × 86,400 s = 172.8M idempotency keys per 24 h window. At an assumed 100 bytes per key, 172.8M × 100 B ≈ 17 GB in one in-process set.

What the Scenario-A answer does here

The Scenario A set still gives O(1) lookups and is correct for one process. What breaks is residence: 17 GB exceeds a normal worker, a restart empties the set so retries pass as new, and two workers each hold half the truth.

What flips at this scale

Move dedupe state out of the process and partition it. Hash each key to one of 16 shards, so each owner holds 172.8M ÷ 16 ≈ 10.8M keys, about 1.1 GB, and expire entries leaving the 24 h window. A key always routes to one owner, so the check stays one lookup.

The trade-off you'd defend

I would defend a sharded, expiring key store over one big in-memory set, trading a network hop and a fixed dedupe window for bounded memory and restart safety.

Illustrative rates and sizes; not PhonePe-published.

Gotchas

Reading a defaultdict to test presence

Symptom

len(d) grows after you only "checked" keys, and later loops see empty entries.

Cause

d[k] on a defaultdict inserts the default.

Fix

Use k in d or d.get(k) for tests.

Hashable but collidable keys

Symptom

Inserts slow as the table grows, with CPU time in __eq__ and no error.

Cause

A constant or low-entropy __hash__ voids the average O(1) assumption.

Fix

Key on a compact immutable value such as an id.

Tricky questions

Are dict lookups O(1)?
Most people say

Always, regardless of keys.

Actually

Average O(1) given constant-time hashing and well-spread keys. Worst case is O(n), and hashing a long string costs O(length).

Scenario question

You're handed a job that checks if key in seen_list per record and asked to speed it up without changing output order.

Model answer

I'd iterate the input in order and swap seen_list for a set, turning each check from O(n) into average O(1). The trade-off is memory: a set costs more per element than a list, so if it outgrows RAM I'd shard or externalise it.

Interview corner

CommonHow does a hash map get O(1) lookup, and when does it not?
“I'd say it hashes the key to a slot and compares keys there, so lookups are average O(1). It degrades toward O(n) under heavy collisions, and one insert can pay for a resize.”
TrickCan a dict key be mutable if I promise not to change it?
“I'd say no, because Python needs a stable hash and a list or dict is rejected as unhashable. I'd use a tuple, since a hash that changes after insertion strands the entry.”
Experience checkWhere did a set rescue a slow job?
“I'd cite a loader that scanned a list of loaded ids per row. One set built up front cut hours to seconds.”

Memory hook

A coat-check desk: ticket text picks the hook, a collision means a short chain, and a desk that sends everything to hook 1 is just a pile.

If you remember only one thing:

Hash lookups are average O(1) under cheap, well-spread keys, and a map has no sorted order to lean on.

Self-check

  1. Does counter["missing"] insert the key?

    No, it returns 0. A defaultdict read does insert.

  2. Which key types raise unhashable type?

    Mutable containers such as list, dict and set.

  3. Do dicts with equal items but different insertion order compare equal?

    Yes.

Prove it

Run the production block, then change __hash__ to return hash(self.v) and print BadKey.calls after probes(200) and probes(20) for both versions. Paste the counts: the colliding version should be 19,900 and 190, the fixed one near 0.

dsa-03-03Card 3 of 6

Stacks, queues and deques

EasyP1 · Must knowKnow cold8 min
stackqueuedequemaxlenfifolifo

Why you care

Stacks and queues are the same data with a different exit rule, and the wrong exit rule is how pipelines process the newest record first or let a "temporary" backlog eat RAM. In Python the classic mistake is a list used as a queue: pop(0) looks harmless and costs O(n). The opposite mistake is a bounded deque that quietly throws away work when full. Interviewers ask because it tests whether you choose by removal order, and because DFS is a stack and BFS is a queue.

Explain like I'm 5

A stack is a pile of plates: you add on top and take from the top. A queue is a ticket line: join at the back, the person at the front is served. A deque is a corridor open at both ends. A bounded deque is the same corridor with a fixed number of spaces, where a new arrival pushes the person at the far end into the street without telling anyone.

Core concept

Decide by who leaves first.

  • Stack (LIFO): list append and pop(), amortized O(1). Use it for undo and "resolve the most recent pending thing".
  • Queue (FIFO): collections.deque with append and popleft(), O(1). Use it for work in arrival order.
  • list.pop(0) / insert(0, x): O(n). A list is a bad FIFO.
  • Deque indexing: O(1) at the ends, O(n) in the middle.
  • maxlen: once full, an append discards an item from the opposite end silently. Correct for "keep the last N log lines", dangerous for work you must not lose.
  • queue.Queue is the thread-safe, blocking version with Full and Empty; it adds locking cost, so use it across threads only.

Decision rule: newest first means stack; oldest first or both ends means deque. If losing an item is a bug, do not set maxlen; check the length yourself and reject, block or spill to disk. If you need the smallest key rather than the oldest, use a heap (Heaps as partial order).

Minimal example Pop order and silent eviction

Pythonruns
from collections import deque
stack = [1, 2, 3]
print(stack.pop())
q = deque([1, 2, 3])
print(q.popleft())
frontier = deque(maxlen=2)
for node in "abc":
    frontier.append(node)
print(list(frontier))
Output
3
1
['b', 'c']

In production Ride-request backlog, bounded with an explicit reject

Pythonruns
import time
from collections import deque

def drain(container, pop, n):
    start = time.perf_counter()
    for _ in range(n):
        pop(container)
    return time.perf_counter() - start

N = 20_000
t_list = drain(list(range(N)), lambda c: c.pop(0), N)
t_deque = drain(deque(range(N)), lambda c: c.popleft(), N)
print("list.pop(0) slower than popleft:", t_list > t_deque)

class BoundedQueue:
    def __init__(self, capacity):
        self.items = deque()
        self.capacity = capacity

    def put(self, item):
        if len(self.items) >= self.capacity:
            raise OverflowError(f"queue full at {self.capacity}, rejected {item!r}")
        self.items.append(item)

    def get(self):
        return self.items.popleft()

backlog = BoundedQueue(2)
for ride in ("r1", "r2", "r3"):
    try:
        backlog.put(ride)
    except OverflowError as exc:
        print(f"OverflowError: {exc}")
print(backlog.get(), len(backlog.items))

applied = []
for step in ("load", "clean", "dedupe"):
    applied.append(step)
while applied:
    print("undo", applied.pop())
Output
list.pop(0) slower than popleft: True
OverflowError: queue full at 2, rejected 'r3'
r1 1
undo dedupe
undo clean
undo load

See it happen A bounded deque drops work without a sound

deque(maxlen=3)bcd
  1. The deque starts empty with room for three items.
  2. Items a, b and c are appended and the deque is now full.
  3. Item d arrives at the right end of a full deque.
  4. Item a is discarded from the left with no exception and no log line.
  5. Anything that still needed a is now lost, and the program continues as if nothing happened.
Notice: the loss happens on the opposite end from the append, and nothing signals it.
Scenario A

In your world

The situation

Your Jenkins job reads file keys from S3 into a list pending and processes oldest-first with key = pending.pop(0). Other code appends newly discovered keys at the end.

What actually breaks

With 3,000 keys nobody notices. In a backfill week the list holds 900,000 keys and each pop(0) shifts up to 900,000 pointers, about 405 billion moves over the drain; the build runs eleven hours. A colleague "fixes" memory with deque(maxlen=50_000), and now the 850,000 oldest keys vanish at enqueue time while the audit table shows 50,000 processed and status SUCCESS.

What you'd do on Monday

Use an unbounded deque for FIFO and enforce the limit yourself so rejection is loud.

Python
from collections import deque
pending = deque(initial_keys)
while pending:
    key = pending.popleft()          # O(1)
    for child in discover(key):
        pending.append(child)
    if len(pending) > MAX_BACKLOG:
        raise RuntimeError(f"backlog {len(pending)} exceeds {MAX_BACKLOG}")
Scenario B

Imagine you work at Uber

500 ride requests per second in one city at peak

The numbers

Arrival 500/s; matching clears 400/s, so the backlog grows 100/s. A deque(maxlen=10_000) fills in 10,000 ÷ 100 = 100 seconds. After that, 100 requests/s are dropped, which is 6,000 per minute with no error and no metric.

What the Scenario-A answer does here

The Scenario A fix still gives FIFO order and O(1) popleft at any size. What breaks is policy: an unbounded deque at 100 extra items/s grows 360,000 requests per hour, and the maxlen shortcut turns a capacity problem into silent loss of the longest-waiting riders.

What flips at this scale

Make capacity an explicit decision. Reject or shed at admission with a counted error, export queue length and age of the oldest item as metrics, and push back upstream. Order stays FIFO, but the bound becomes visible policy, not a side effect of a container option.

The trade-off you'd defend

I would defend an explicit bounded queue with counted rejections over maxlen eviction, trading a visible failure and an alert for the comfort of a job that never raises.

Illustrative rates; not Uber-published.

Gotchas

Bounded deque dropping the frontier

Symptom

A traversal or worker loop finishes "successfully" having processed fewer items than were enqueued, with no exception.

Cause

deque(maxlen=N) discards from the opposite end when full.

Fix

Use an unbounded deque and check len(d) yourself, raising or rejecting at the limit.

Using a list as a queue

Symptom

Run time grows with the square of backlog size; CPU is busy in list.pop, memory is flat.

Cause

pop(0) shifts all remaining elements.

Fix

deque.popleft().

Tricky questions

deque(maxlen=3) is full. What does append do?
Most people say

It raises an error or blocks, like a bounded queue.

Actually

It silently drops an item from the opposite end. For raising or blocking use queue.Queue(maxsize=N) or check the length yourself.

Scenario question

You're handed a worker loop built on deque(maxlen=1000) where records occasionally "disappear".

Model answer

I'd suspect maxlen eviction: when producers outrun the consumer, the deque discards the oldest unprocessed record with no error. I'd confirm by logging length at each append, then use an unbounded deque with an explicit limit that raises and increments a counter. The trade-off is that failures become visible and noisy, which is right for work that must not be lost.

Interview corner

CommonWhen would you use a stack versus a queue?
“I'd choose by removal order. Most recent first, like undo or nested state, is a stack; oldest first, like jobs, is a queue. In Python that's a list and a deque.”
TrickWhy not use list.pop(0) for a queue?
“I'd say it shifts every remaining element, so each pop is O(n) and draining n items is quadratic. I'd use deque.popleft(), which is O(1).”
Experience checkHave you lost data from a bounded buffer?
“I had a bounded deque that silently dropped old items under load. I replaced it with an explicit capacity check that rejected and counted overflow, so it became an alert instead of a gap in the data.”

Memory hook

Plates pile up top-first, a ticket line serves the front, and a bounded corridor pushes the far person into the street without telling you.

If you remember only one thing:

Choose by who leaves first, and never let a container silently decide to lose work.

Self-check

  1. Which operation makes a list a poor queue?

    pop(0) (and insert(0, x)), both O(n).

  2. What does deque(maxlen=2) do on a third append?

    It discards the item at the opposite end, with no error.

  3. Which structure does DFS use, and which does BFS use?

    DFS uses a stack; BFS uses a queue.

Prove it

Time pop(0) on a list versus popleft() on a deque for N = 20,000 and 40,000 and paste all four numbers. Then run deque(range(5), maxlen=3) and paste the result to show the eviction.

dsa-03-04Card 4 of 6

Heaps as partial order

MediumP2 · Very likelyKnow cold7 min
heappriority-queueheapqtie-breakerpartial-order

Why you care

Whenever a job says "process the earliest due", "give me the cheapest" or "keep the K largest", a sort is the wrong tool and a heap is the right one. A heap keeps just enough order to hand you the minimum quickly while items keep arriving. Interviewers ask because the failure modes are checkable: the orientation is min by default, equal priorities can raise TypeError, and heapq has no decrease-key.

Explain like I'm 5

Imagine a tournament bracket on a whiteboard, where the winner of each small match sits above the two players beneath. You can always see the champion at the top without ranking everyone. A new player climbs only while they beat the one above; when the champion leaves, the last player moves up top and sinks. You never know who is third best; you pay for a partial order only.

Core concept

A binary heap stored in a list keeps each parent no larger than its children. It guarantees the smallest item at index 0 and nothing more.

  • Peek h[0]: O(1). heappush and heappop: O(log n).
  • heapify(list): O(n) in place, cheaper than n pushes. Arbitrary search is O(n).
  • Min-heap only in older Pythons: negate numeric priorities for max behaviour. Python 3.14 adds heappush_max, heappop_max and heapify_max; check the runtime before using them.
  • heapreplace(h, x) pops first, then pushes, so it can return a value larger than x. heappushpop(h, x) pushes first, then pops, so a smaller x comes straight back.
  • No decrease-key. Push a fresh entry and skip the stale one when it surfaces (lazy deletion).

Equal priorities then compare the payload, and dicts or custom objects raise TypeError. Add a unique tie-breaker: (priority, seq, payload). The sequence also keeps FIFO order among ties.

Decision rule: use a heap when you repeatedly need the smallest or largest of a changing collection, or the best K of a stream. Sort once if the set never changes. Use a sorted index (Trees and tries by key structure) if you need ordered iteration or neighbours.

Minimal example Heapify, pop and the heapreplace difference

Pythonruns
import heapq
h = [5, 1, 4]
heapq.heapify(h)
print(h[0])
heapq.heappush(h, 0)
print(heapq.heappop(h), heapq.heappop(h))
print(heapq.heapreplace([1, 5], 9), heapq.heappushpop([1, 5], 0))
Output
1
0 1
1 0

In production Retry scheduler with tie-breakers and lazy re-prioritising

Pythonruns
import heapq
import itertools

try:
    clash = []
    heapq.heappush(clash, (1, {"job": "a"}))
    heapq.heappush(clash, (1, {"job": "b"}))
except TypeError as exc:
    print(f"TypeError: {exc}")

class RetryQueue:
    def __init__(self):
        self.heap = []
        self.counter = itertools.count()
        self.live = {}

    def schedule(self, job, due):
        entry = (due, next(self.counter), job)
        self.live[job] = entry
        heapq.heappush(self.heap, entry)

    def pop_due(self, now):
        out = []
        while self.heap and self.heap[0][0] <= now:
            entry = heapq.heappop(self.heap)
            if self.live.get(entry[2]) is entry:
                del self.live[entry[2]]
                out.append(entry[2])
        return out

q = RetryQueue()
q.schedule("charge-1", 50)
q.schedule("charge-2", 20)
q.schedule("charge-3", 20)
q.schedule("charge-1", 10)
print(q.pop_due(25))
print(q.pop_due(100))
print(len(q.heap))
Output
TypeError: '<' not supported between instances of 'dict' and 'dict'
['charge-1', 'charge-2', 'charge-3']
[]
0

See it happen A heap pop keeps the invariant, not a sorted list

heap array (min at index 0)2347
  1. The array [1, 3, 2, 7, 4] satisfies the invariant: each parent is no larger than its children.
  2. A pop removes the minimum at index 0 and moves the last item, 4, into its place.
  3. 4 is larger than its smaller child 2, so they swap.
  4. 4 has no children left to beat, so it stops and the root is the new minimum.
  5. The array carries no order between siblings or cousins, so it is not sorted in general.
Notice: only the path from the root to a leaf is touched, which is why a pop costs O(log n).
Scenario A

In your world

The situation

Your pipeline has a Postgres retry table of failed settlement files with a next_attempt_at time. Every minute a Jenkins job loads all pending rows into a Python list and calls pending.sort() to find what is due.

What actually breaks

After an outage there are 600,000 rows, and each minute sorts them at about 600,000 × 19 ≈ 11.4 million comparisons to find perhaps 40 due items. The run overlaps the next one, two jobs pick the same file, and the audit table shows 40 files loaded twice.

What you'd do on Monday

Query the database for due rows with an index, or, if you hold them in memory, use a heap keyed on (due, seq, file).

Python
import heapq
heap = [(due, i, f) for i, (f, due) in enumerate(rows)]
heapq.heapify(heap)                      # O(n) once
while heap and heap[0][0] <= now:        # peek is O(1)
    due, _, f = heapq.heappop(heap)      # O(log n)
    process(f)

Add a unique-lock row before processing so overlapping runs cannot take the same file.

Scenario B

Imagine you work at Stripe

20M scheduled retries across a webhook fleet

The numbers

20M pending retries over 24 h. 20M pushes cost about 20M × 24.3 ≈ 486M comparisons worst case; heapify is near 2n = 40M. All 20M in one process at an assumed 120 bytes per tuple is 2.4 GB.

What the Scenario-A answer does here

The Scenario A heap is still right for "what is due next". What breaks is holding every pending retry in one process: 2.4 GB of tuples, a restart that loses the schedule.

What flips at this scale

Keep the full schedule in a durable store indexed by due time and hold only a short horizon in memory. With even spread, a 5-minute horizon is 20M × 300 ÷ 86,400 ≈ 69,444 entries, about 8 MB, with log2 ≈ 16 per operation.

The trade-off you'd defend

I would defend a durable time index with a small in-memory heap over a global in-memory heap, trading a refill query for restart safety and bounded memory.

Illustrative volumes and entry size; not Stripe-published.

Gotchas

Equal priorities compare the payload

Symptom

TypeError: '<' not supported between instances of 'dict' and 'dict' appears only when two tasks share a priority, so tests with distinct priorities pass.

Cause

Tuple comparison falls through to the next element on a tie.

Fix

Insert a unique sequence number: (priority, next(counter), payload).

Expecting a sorted list

Symptom

Printing the heap shows a non-ascending order.

Cause

A heap guarantees only parent-child order.

Fix

Pop repeatedly, or sorted(h) a copy.

Tricky questions

Is heapify O(n log n), since it does n sifts?
Most people say

Yes, building a heap from n items costs n log n.

Actually

It is O(n). Most nodes sit near the leaves and sift only a short distance, so the total converges to a linear bound.

Scenario question

You're handed a scheduler whose tasks occasionally crash with a TypeError inside heappush, only under load.

Model answer

I'd suspect equal priorities: under load two tasks tie on the first tuple element and Python compares the dict payloads. I'd change entries to (priority, seq, payload) with an itertools.count() sequence. The trade-off is one extra element per entry, a small memory cost for deterministic behaviour.

Interview corner

CommonWhat are the complexities of heappush, heappop and heapify?
“I'd say push and pop are O(log n), peek is O(1) and heapify is O(n). A heap is a partial order, so searching for an arbitrary element is still O(n).”
TrickWhy does heapq sometimes raise TypeError on equal priorities?
“I'd explain that equal first elements make tuple comparison fall through to the payload, which may be unorderable. I add a unique counter as the second element so the payload is never compared.”
DesignHow would you keep the 100 largest values from a stream?
“I'd keep a min-heap of size 100 and replace the root when a value beats it. That's O(log 100) per item and O(100) memory.”

Memory hook

A tournament bracket: the champion sits on top, newcomers climb only while they win, and nobody promises second place.

If you remember only one thing:

A heap gives the minimum fast and nothing else, and equal priorities need a unique tie-breaker.

Self-check

  1. Difference between heapreplace and heappushpop?

    heapreplace pops first then pushes, so it may return a value larger than the new item; heappushpop pushes first then pops, so it returns the smaller of the two.

  2. Does heapq support decrease-key?

    No; push a fresh entry and use lazy deletion.

  3. Why add a counter to heap entries?

    It breaks ties so payloads are never compared.

Prove it

Run the production block, then print len(q.heap) right after the four schedule calls and again after pop_due(100). Paste both numbers: 4, then 0.

dsa-03-05Card 5 of 6

Trees and tries by key structure

MediumP2 · Very likelyTalk about it8 min
treebsttrieprefixordered-mapheight

Why you care

Hash maps answer "is this key present?" and nothing about neighbours. The moment a requirement says "all paths starting with this prefix", "next higher id" or "keys between two bounds", a hash map has no answer except scanning everything. Trees and tries are built for those queries. Interviewers ask because the follow-up is always about shape: a binary search tree is O(log n) only when balanced, and a trie costs by key length, not item count.

Explain like I'm 5

A binary search tree is twenty questions: at each signpost go left for smaller or right for larger, so you walk only the height of the tree. If the signposts were built from already-sorted input they all point right, and the tree is just a long road. A trie is a filing cabinet with drawers labelled by letter: to find "docs/a.txt" you open one drawer per character, and everything sharing a prefix shares drawers.

Core concept

  • Traversal visiting every node: O(n), in any order.
  • BST search, insert, delete: O(height). A balanced tree has height about log₂ n, so O(log n). A skewed tree, such as one built by inserting sorted keys into a plain BST, has height n, so O(n).
  • Self-balancing trees (AVL, red-black, B-tree) keep height logarithmic. Python's standard library ships none.
  • A plain dict is not an ordered map. It remembers insertion order, not key order, and has no range or successor query. For sorted keys keep a sorted list with bisect (O(n) insertion) or use a database index.
  • Trie insert and lookup: O(L) for key length L, assuming constant-time child lookup. The cost does not depend on how many keys are stored.
  • Prefix reporting: walking to the prefix node is O(L); collecting matches costs O(output size plus nodes visited below), so a short prefix on a large trie is expensive.
  • Storage grows with total stored characters, reduced by shared prefixes; a dict per node is heavy in Python.

Decision rule: hash for exact membership; balanced tree or sorted index for order, ranges and neighbours; trie when queries are by prefix and keys share long prefixes. Do not use an unbalanced BST on data that may arrive sorted, and do not build a Python-object trie for millions of long keys without measuring memory.

Minimal example Same keys, two shapes, two depths

Pythonruns
def depth(keys):
    kids, deepest = {}, 0
    for k in keys[1:]:
        cur, d = keys[0], 1
        while (cur, k < cur) in kids:
            cur, d = kids[(cur, k < cur)], d + 1
        kids[(cur, k < cur)] = k
        deepest = max(deepest, d)
    return deepest
print(depth([1, 2, 3, 4, 5, 6, 7]), depth([4, 2, 6, 1, 3, 5, 7]))
Output
6 2

In production Path-prefix index with an explicit end marker

Pythonruns
END = object()

class Trie:
    def __init__(self):
        self.root = {}
        self.nodes = 1

    def insert(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur:
                cur[ch] = {}
                self.nodes += 1
            cur = cur[ch]
        cur[END] = True

    def with_prefix(self, prefix):
        cur = self.root
        for ch in prefix:
            if ch not in cur:
                return []
            cur = cur[ch]
        found, stack = [], [(cur, prefix)]
        while stack:
            node, text = stack.pop()
            for key, child in node.items():
                if key is END:
                    found.append(text)
                else:
                    stack.append((child, text + key))
        return sorted(found)

paths = ["docs/a.txt", "docs/b.txt", "docs/sub/c.txt", "photos/x.jpg"]
trie = Trie()
for p in paths:
    trie.insert(p)
print(trie.with_prefix("docs/"))
print(trie.with_prefix("zzz"))
print("nodes fewer than characters:", trie.nodes < sum(len(p) for p in paths) + 1)

d = {"b": 1, "a": 2}
print("dict iterates in key order:", list(d) == sorted(d))
print(list(d))
Output
['docs/a.txt', 'docs/b.txt', 'docs/sub/c.txt']
[]
nodes fewer than characters: True
dict iterates in key order: False
['b', 'a']
Scenario A

In your world

The situation

Your S3 ingest has a manifest of 1.2 million object keys such as raw/2025/03/14/orders_0001.csv. A reconciliation step needs every key under a prefix, and you wrote [k for k in keys if k.startswith(prefix)] once per partition, for 31 partitions.

What actually breaks

Each scan is O(n) over 1.2M keys, 31 times: 37.2M startswith calls, tolerable. Then the same code runs per tenant: 4,000 tenants × 1.2M = 4.8 billion calls, and the Jenkins stage is killed with zero reconciliation rows written.

What you'd do on Monday

Sort the keys once and answer each prefix with a range, using binary search at both boundaries.

Python
import bisect
keys.sort()                                    # O(n log n) once
lo = bisect.bisect_left(keys, prefix)
hi = bisect.bisect_left(keys, prefix + "\U0010ffff")
matches = keys[lo:hi]                          # O(log n + k)
Scenario B

Imagine you work at Dropbox

10M file paths in one namespace

The numbers

10M paths × 60 characters = 600M characters. A trie sharing prefixes by an assumed factor of 5 still holds 120M nodes; at an assumed 200 bytes per dict node that is about 24 GB. A sorted index answers a prefix query in log2(10M) ≈ 23.3 comparisons per boundary plus k results.

What the Scenario-A answer does here

The Scenario A sorted-keys range scan is the right shape. What breaks is keeping a 10M-element Python list per process: every new file inserted mid-list costs an O(n) shift, and re-sorting per batch costs O(n log n).

What flips at this scale

Push ordering into a persistent ordered index, such as a B-tree-backed table keyed by path, so a prefix is a key-range scan with O(log n) seek and O(k) read. Keep an in-memory trie only for a small, hot, prefix-heavy set such as autocomplete.

The trade-off you'd defend

I would defend a disk-backed ordered index over an in-memory trie, trading nanosecond lookups on a small set for bounded memory and cheap inserts at tens of millions of keys.

Illustrative counts; not Dropbox-published.

Gotchas

Sorted input into a plain BST

Symptom

Lookups crawl, and recursive code raises RecursionError: maximum recursion depth exceeded.

Cause

Sorted inserts always go one direction, producing height n.

Fix

Use a self-balancing structure or a sorted index, and iterate instead of recursing.

Trie memory blow-up

Symptom

A trie of a few million keys exhausts RAM though the raw strings fit.

Cause

Every node is a Python dict with hundreds of bytes of overhead.

Fix

Measure per-node memory, or move the index into a database.

Tricky questions

Is a BST lookup O(log n)?
Most people say

Yes, that is the definition of a binary search tree.

Actually

It is O(height): O(log n) only when balanced, O(n) when skewed.

Scenario question

You're handed a requirement to return all customer ids starting with a prefix, over millions of ids at many queries per second.

Model answer

I'd first ask how often ids change. If mostly static I'd keep them sorted and answer with two binary searches, O(log n + k), batching rebuilds for inserts. If they change constantly I'd use a database range scan. I'd build a trie only for a small, hot set, accepting its memory overhead for faster per-character walks.

Interview corner

CommonWhat is the difference between a BST and a balanced BST?
“I'd say a plain BST costs O(height), which is O(n) when it degenerates, for example on sorted inserts. A balanced one rotates or splits to keep height near log n.”
TrickWhy is trie lookup not O(1)?
“I'd say it's O(L), the key length, because you follow one edge per character. It doesn't depend on the number of keys, which is the advantage, but it isn't constant.”
DesignHow would you serve prefix search over 10 million paths?
“I'd use an ordered persistent index with range scans, not an in-memory trie, trading raw lookup speed for bounded memory.”

Memory hook

A filing cabinet with one drawer per character: the walk is as long as the word, and a signpost tree built from sorted input is just a road.

If you remember only one thing:

Tree cost is height, trie cost is key length, and neither is a dict.

Self-check

  1. What decides BST search cost?

    The height: log n if balanced, n if skewed.

  2. What is trie insert cost?

    O(L) for key length L, assuming constant-time child lookup.

  3. Does a dict support range queries?

    No; it has insertion order only.

Prove it

Run the minimal block's depth on list(range(1000)) and on the same keys shuffled with random.Random(0).shuffle, and paste both depths. The sorted one is 999; the shuffled one is far smaller.

dsa-03-06Card 6 of 6

Graphs, union-find and the which-one table

MediumP3 · Role-dependentTalk about it8 min
graphadjacency-listunion-findconnectivitydecision-table

Why you care

Anything shaped like "A is linked to B" is a graph: accounts sharing a device, tables depending on tables. Two choices decide whether it survives scale: how you store the links and how you answer "are these two connected?". Interviewers ask about union-find because people state its cost wrongly as O(1). This card closes the chapter with one table mapping every structure to its need.

Explain like I'm 5

An adjacency list is an address book where each person lists only their friends. An adjacency matrix is a giant grid with a cell for every possible pair, mostly empty. Union-find is a set of club rosters with a leader each. To check whether two people share a club, walk each up to their leader and compare, pointing everyone you passed at the leader so the next walk is short.

Core concept

Graph storage (V vertices, E edges):

  • Adjacency list: O(V + E) storage; neighbour scan O(degree); one edge test O(degree) unless neighbours sit in sets.
  • Adjacency matrix: O(V²) storage; edge test O(1); neighbour scan O(V).

Union-find answers connectivity under merges: make a set per element (O(V) initialisation and storage), find(x) returns the root, union(a, b) links two roots. With path compression plus union by size or rank, m operations cost O(m α(V)), with α the inverse Ackermann function. That is amortized, not per-call O(1).

Which-one table

NeedStructureCore cost
Position access, end appendslistO(1), append amortized O(1)
Membership, counts, groupingdict / setaverage O(1)
Oldest or newest firstdeque / list stackO(1) at ends
Smallest or largest repeatedlyheappeek O(1), push/pop O(log n)
Sorted keys, ranges, neighboursbalanced tree / sorted indexO(log n)
Prefix queriestrie / sorted indexO(L) / O(log n + k)
Links between itemsadjacency listO(V + E), scan O(degree)
"Same group?" under mergesunion-findamortized O(α(V)), no splits

Decision rule: ask how items leave, how they are found, and whether order or connectivity matters. Use union-find when edges only arrive and you ask "connected?"; traverse when you need the route or must handle deletions.

Minimal example Compression and components

Pythonruns
parent = list(range(6))

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

def union(a, b):
    parent[find(a)] = find(b)

union(0, 1); union(1, 2); union(4, 5)
print(find(0) == find(2), find(0) == find(4), len({find(i) for i in range(6)}))
Output
True False 3

In production Linked-account groups with union by size

Pythonruns
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

accounts = ["a0", "a1", "a2", "a3", "a4", "a5", "a6", "a7"]
index = {name: i for i, name in enumerate(accounts)}
dsu = DSU(len(accounts))
links = [("a0", "a1"), ("a1", "a2"), ("a2", "a0"), ("a5", "a6")]
for left, right in links:
    print(left, right, "merged" if dsu.union(index[left], index[right]) else "already linked")
print("components:", dsu.components)
print("a0 and a2 together:", dsu.find(0) == dsu.find(2))

V, E = 2000, 3000
print("matrix cells:", V * V, "list entries:", 2 * E)
try:
    dsu.find(99)
except IndexError as exc:
    print(f"IndexError: {exc}")
Output
a0 a1 merged
a1 a2 merged
a2 a0 already linked
a5 a6 merged
components: 5
a0 and a2 together: True
matrix cells: 4000000 list entries: 6000
IndexError: list index out of range

See it happen Union by size and path compression on a parent array

parent[0..4]00004
  1. Every element starts as its own root, so parent[i] equals i.
  2. union(0, 1) links root 1 under root 0, so parent[1] becomes 0.
  3. union(2, 3) links root 3 under root 2.
  4. union(1, 3) finds roots 0 and 2 and links the equal-sized root 2 under root 0.
  5. find(3) walks 3, then 2, then 0, and repoints parent[3] straight at the root.
  6. A later find(3) is one step; element 4 is still its own component.
Notice: compression happens on the walk, so the cost of a long path is paid once and then removed.
Scenario A

In your world

The situation

Your nightly job flags customers who share a bank account or phone with another customer and writes "household ids" to Postgres. You search all other customers for connections and merge groups held in a list of sets.

What actually breaks

With 5,000 customers it finishes in seconds. With 800,000, the search alone is 800,000² = 640 billion comparisons, and each merge scans every set to find the right ones. Jenkins times out, and reruns give different household ids because set order changed: 211,904 households one night, 212,033 the next.

What you'd do on Monday

Stream the edges once into union-find, then derive a stable id from the root.

Python
dsu = DSU(len(customers))
for a, b in shared_identifier_pairs:      # one pass, amortized alpha(V) each
    dsu.union(index[a], index[b])
household = {c: min_member[dsu.find(i)] for c, i in index.items()}

Use the smallest customer id per group as the household id so reruns agree.

Scenario B

Imagine you work at CRED

50M users, 120M link events per day

The numbers

A Python list of 50M elements is 400 MB of slots, plus about 28 bytes per distinct int above 256: 50M × 28 B = 1.4 GB, so about 1.8 GB. A typed array('I') costs 4 bytes per element, 50M × 4 B = 200 MB.

What the Scenario-A answer does here

The Scenario A DSU still gives right answers. What breaks is representation: a boxed-int list near 1.8 GB, a nightly rebuild, and a per-process structure that cannot absorb events from several workers.

What flips at this scale

Store parent and size in compact typed arrays or an external graph store, persist them, and apply each day's links incrementally. Union-find cannot undo a merge, so revoked links need a scheduled full recomputation.

The trade-off you'd defend

I would defend an incrementally updated, compact union-find with a scheduled full rebuild over a nightly traversal, trading the inability to split groups for near-linear time on a large edge stream.

Illustrative user and event counts and per-object sizes; not CRED-published.

Gotchas

Calling union-find "O(1)"

Symptom

A design review accepts O(1) per operation, then a profile shows long find walks on a union-heavy batch.

Cause

Amortized O(α(V)) needs both optimisations, plus O(V) initialisation.

Fix

Say "amortized near-constant, O(V) to initialise", and use both optimisations.

Adjacency matrix for a sparse graph

Symptom

MemoryError building a V×V grid though few edges exist.

Cause

A matrix needs V² cells; 100,000 vertices is 10 billion.

Fix

Use dict[node, list] at O(V + E).

Tricky questions

Does path compression alone make find O(1)?
Most people say

Yes, after compression every path has length 1.

Actually

Only for compressed nodes. The bound is amortized, and α(V) needs union by size or rank too.

Scenario question

You're handed a stream of "these two accounts are linked" events and asked to answer "are X and Y in the same group?" at any moment.

Model answer

I'd use union-find with union by size and path compression: each event is a union, each question two finds, amortized near-constant, O(V) memory. The trade-off is that it can't split groups or return the path, so if links can be revoked I'd keep an adjacency list and traverse.

Interview corner

CommonAdjacency list or matrix, and why?
“I'd default to an adjacency list: O(V + E) space and O(degree) neighbour scans. I'd use a matrix only for small dense graphs where O(1) edge tests matter more than O(V²) memory.”
TrickWhat is the complexity of union-find operations?
“I'd say amortized O(α(V)) per operation with both path compression and union by size or rank, plus O(V) to initialise. I avoid calling it O(1), because a single find can still walk a long path.”
Experience checkWhen have you grouped records by shared attributes?
“I'd cite grouping customers by shared identifiers. A pairwise scan was quadratic, so I streamed edges into union-find with the smallest member id as group id.”

Memory hook

An address book lists only friends; a club roster points everyone at the leader, and walking up the roster flattens it for next time.

If you remember only one thing:

Pick the structure by how items leave and are found, and call union-find amortized near-constant, never plain O(1).

Self-check

  1. Storage cost of an adjacency list versus matrix?

    O(V + E) versus O(V²).

  2. What two optimisations give union-find its α(V) bound?

    Path compression and union by size or rank.

  3. Can union-find split a group?

    No.

Prove it

Extend the production block: build a DSU of 200,000 elements, run 200,000 unions on pairs from random.Random(1), and print dsu.components and the elapsed seconds. Paste both.