Shelf · DSA Patterns · Chapter 5

Chapter 5: Search & ordering patterns

Searching and ordering questions look different on the surface and collapse into six reusable shapes underneath. This chapter gives you the invariant, the edge cases and the cost statement for each, so you can write them without improvising and defend them aloud.

Difficulty
Priority
dsa-05-01Card 1 of 6

Binary search with a boundary invariant

MediumP2 · Very likelyKnow cold8 min
binary-searchbisectinvariantboundaries

Why you care

Most binary search bugs are boundary bugs: an off-by-one that loops forever, or an answer one slot too far left. In ETL work the same code appears as "first row at or after the watermark" or "how many events fall in this hour" on a sorted extract. Get the boundary wrong and you double-load one row or drop one, silently. Interviewers ask for binary search because it is short enough to write in five minutes and strict enough that a missing invariant shows at once.

Explain like I'm 5

You want the first page of a phone book where surnames reach "Mehta" or later. Open the middle. If that page is still before "Mehta", throw away the left half. If it is "Mehta" or later, it might be your answer, so keep it and discard only what lies to its right. Every opening discards at least one page, never one that could still be the answer.

Core concept

Write the question as one sentence first: find the first index whose element satisfies a condition that flips from false to true once. For plain search the condition is xs[i] >= target.

  • Use a half-open interval [lo, hi) with hi = len(xs), so "insert at the end" is a legal answer.
  • Loop while lo < hi; mid = (lo + hi) // 2 is always < hi, so xs[mid] is safe.
  • Fails the condition: lo = mid + 1. Passes: hi = mid. Both shrink the interval, so it terminates; everything left of lo fails and everything from hi passes.
  • Lower bound (bisect_left) is the first x >= t; upper bound (bisect_right) is the first x > t. Their difference counts copies of t.
  • Exact match is search plus a post-check: i < len(xs) and xs[i] == t.

Use it when data is sorted (or the condition is monotone) and you need a position, a range count or an insertion point. Do not use it on unsorted data, and do not call insort in a hot loop: the search is O(log n) comparisons but the list shift is O(n). bisect accepts key= from Python 3.10, applied to list elements, not to the value you search for.

Minimal example Left versus right, and the end slot

PythonThe insertion point can equal len(a)runs
from bisect import bisect_left, bisect_right
a = [1, 3, 3, 3, 7]
print(bisect_left(a, 3), bisect_right(a, 3))
print(bisect_left(a, 9), len(a))
print(bisect_left(a, 0))
i = bisect_left(a, 4)
print(i, i < len(a) and a[i] == 4)
Output
1 4
5 5
0
4 False

In production Hand-written lower bound checked against bisect

The sorted guard matters: binary search on unsorted input returns a confident wrong number, not an error.

PythonCount events in [start, end) over a sorted extractruns
from bisect import bisect_left


def lower_bound(xs, target):
    """First index i with xs[i] >= target, or len(xs). Search space is [lo, hi)."""
    lo, hi = 0, len(xs)
    while lo < hi:
        mid = (lo + hi) // 2
        if xs[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def count_in_window(ts, start, end):
    """Events with start <= t < end, two boundary searches and a subtraction."""
    if any(a > b for a, b in zip(ts, ts[1:])):
        raise ValueError("timestamps must be sorted ascending")
    return lower_bound(ts, end) - lower_bound(ts, start)


def find_exact(xs, t):
    i = lower_bound(xs, t)
    return i if i < len(xs) and xs[i] == t else -1


settled = [100, 100, 130, 130, 130, 175, 200, 200, 260]
for t in range(90, 270):
    assert lower_bound(settled, t) == bisect_left(settled, t), t
print("matches bisect_left on 180 targets")
print(count_in_window(settled, 100, 200))
print(count_in_window(settled, 130, 131))
print(count_in_window(settled, 261, 300))
print(count_in_window(settled, 0, 10**9))
print(find_exact(settled, 175), find_exact(settled, 176), find_exact(settled, 999))
try:
    count_in_window([5, 3, 9], 0, 10)
except ValueError as e:
    print(f"ValueError: {e}")
Output
matches bisect_left on 180 targets
6
3
0
9
5 -1 -1
ValueError: timestamps must be sorted ascending

See it happen The interval shrinks, hi never passes the answer

xs, target 3 (last cell = end slot)13337endpointerslo=hi
  1. Start with lo=0 and hi=5, one past the last item, so the search space is [0, 5).
  2. mid=2 holds 3, which is not below the target, so it may be the answer and hi moves onto it.
  3. mid=1 holds 3 again, so hi moves left to 1 and the duplicate to its right is discarded safely.
  4. mid=0 holds 1, below the target, so lo steps past it to 1.
  5. lo equals hi at 1: that is the first element that is 3 or more, and the post-check xs[1] == 3 confirms a match.
Notice: hi only lands on a slot that passed the test, so the leftmost duplicate is never lost.
Scenario A

In your world

The situation

Your Jenkins job loads incremental extracts from S3, sorted by updated_at, and must start at the first row at or after the last watermark. Today it reads everything and filters in a Python loop.

What actually breaks

A teammate hand-rolls a search with hi = len(rows) - 1 and while lo < hi. When the watermark equals the last timestamp it lands one slot early and one row loads twice. Counts drift by 1 per file until finance notices.

What you'd do on Monday

Use bisect_left on a key list and test three edges: watermark before, at and after the last row.

PythonResume from the watermark (needs a real file per run)
from bisect import bisect_left

stamps = [r["updated_at"] for r in rows]          # sorted by contract
start = bisect_left(stamps, watermark)            # first row >= watermark
new_rows = rows[start:]                           # len(rows) means "nothing new"
Scenario B

Imagine you work at Microsoft

2B sorted telemetry keys

The numbers

Illustrative: 2,000,000,000 keys × 16 bytes ≈ 32 GB. A linear scan at ~1 GB/s costs ≈ 32 s per lookup. Binary search needs ⌈log2(2×10^9)⌉ = 31 probes; at ~100 µs per random SSD read that is 31 × 100 µs ≈ 3.1 ms.

What the Scenario-A answer does here

The Scenario A fix works while the array fits in RAM. At 32 GB each of the 31 probes is a cold page read.

What flips at this scale

Make the top of the search permanent. Keep one key per 4 KB page in memory: 32 GB ÷ 4 KB = 8M pages × 16 B ≈ 128 MB. Search that index in RAM, then do one page read and a local search. The same invariant now runs at two levels.

The trade-off you'd defend

I would defend a sparse in-memory index plus one page read over pure on-disk bisection, trading 128 MB of RAM and a rebuild on writes for about 30x fewer random reads.

Illustrative numbers chosen to show the arithmetic; not Microsoft-published figures.

Gotchas

Search loops forever or skips the answer

Symptom

The call never returns, or returns an index one slot too small on exact-boundary inputs.

Cause

Closed bounds (hi = n - 1) mixed with half-open moves (hi = mid), or lo = mid without + 1, so the interval stops shrinking.

Fix

Pick half-open [lo, hi) once; use only lo = mid + 1 or hi = mid.

Insertion point read as a match

Symptom

IndexError: list index out of range on xs[i], or "found" for an absent value.

Cause

bisect_left returns len(xs) past the end.

Fix

Post-check i < len(xs) and xs[i] == target.

Tricky questions

Which returns the count of a value, bisect_left or bisect_right?
Most people say

Either one, since both find where the value is.

Actually

Neither alone. The count is bisect_right(a, t) - bisect_left(a, t).

Scenario question

You're handed 50 million sorted order timestamps and asked for the order count in each of 24 hourly windows.

Model answer

I would do two bisect_left calls per window: about 24 × 2 × 26 ≈ 1,250 comparisons instead of 24 scans of 50 million rows. The trade-off is that I depend on the sort contract; if upstream delivers unsorted data the counts are silently wrong, so I would sample-assert at load.

Interview corner

CommonWrite binary search and state your invariant.
“I'd use a half-open interval, so hi starts at len(xs). Everything left of lo is below the target and everything from hi on is at or above it. Both updates shrink the interval, so it terminates with lo as the answer.”
TrickWhat does bisect_left return if the target exceeds everything?
“I get len(a) back, the insertion point at the end, so I always post-check i < len(a) before indexing.”
Experience checkWhere have you used sorted data to avoid a scan?
“I resumed an incremental load from a watermark with bisect_left instead of filtering every row, and I tested watermark before, inside and after the data.”

Memory hook

A phone book where you only throw away pages that cannot be the answer.

If you remember only one thing:

Define the false-to-true boundary first, keep [lo, hi) half-open, and post-check an exact match.

Self-check

  1. What does bisect_right(a, t) - bisect_left(a, t) give?

    The number of occurrences of t.

  2. Why start hi at len(xs)?

    The answer may be the end slot, and half-open intervals make that normal.

  3. What does insort cost, and why?

    O(n): the search is O(log n) but the list shift is linear.

Prove it

Compare your lower_bound and upper_bound with bisect_left and bisect_right on 10,000 seeded random sorted lists with duplicates, for every target from min - 1 to max + 1. Paste the zero-mismatch line.

dsa-05-02Card 2 of 6

Binary search on the answer

HardP3 · Role-dependentKnow cold7 min
binary-searchmonotonefeasibilityanswer-space

Why you care

Sometimes there is no sorted array, only a number you must choose: a batch size, worker count or timeout. If you can test "does this value work?" and the answers run no, no, no, yes, yes, yes, you find the boundary in a few dozen tests instead of thousands, and the number becomes defensible instead of folklore. Interviewers ask it to see whether you spot search structure where sorting is never mentioned. The failure mode, a non-monotone predicate, is silent.

Explain like I'm 5

You want the lowest oven temperature that cooks a loaf through. Try 200: raw. Try 250: cooked. Try 225: cooked. Hotter never un-cooks a loaf, so a "cooked" at 225 means everything above is cooked too, and you only explore below. The loaf is the predicate and the dial is the sorted array you never wrote down.

Core concept

This is binary search (Binary search with a boundary invariant) with a function in place of the array.

  • Pick an ordered integer candidate domain [lo, hi] with proven bounds.
  • Write a feasibility predicate ok(x) that is monotone: False…False True…True.
  • First feasible value: if ok(mid), hi = mid; else lo = mid + 1.
  • Check ok(hi) once up front and fail loudly, otherwise an impossible problem returns the sentinel.
  • Cost: ⌈log2(domain size)⌉ predicate calls times the cost of one call.

Use it for "smallest x such that…" questions where the test is cheap enough to run 20 to 40 times and you can argue monotonicity in one sentence. Do not use it when bigger can break feasibility (a U-shaped cost) or when a formula gives the answer. For real-valued answers, run a fixed number of iterations instead of comparing floats.

Under the hood

Termination is the integer detail. With lo < hi and mid = (lo + hi) // 2, floor division gives lo <= mid < hi. So hi = mid strictly lowers hi and lo = mid + 1 strictly raises lo; the gap falls every round. The "last feasible" variant with lo = mid leaves mid == lo when the gap is 1 and loops forever, so it needs the rounded-up (lo + hi + 1) // 2. The loop exits with lo == hi, which is the answer only if ok(hi) was true at the start.

Minimal example The same template, and what a bumpy predicate does

PythonMonotone works; an island predicate returns the end sentinelruns
def first_true(lo, hi, ok):
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


print(first_true(0, 100, lambda x: x * x >= 50))
print(first_true(0, 100, lambda x: 20 <= x <= 30))
print(first_true(0, 100, lambda x: x >= 20))
Output
8
100
20

In production First feasible value with checked bounds

The predicate asks whether a worker pool clears a nightly load inside its window.

PythonSmallest worker count that fits the windowruns
def first_true(lo, hi, ok):
    """Smallest x in [lo, hi] with ok(x) True; ok must be False...False True...True."""
    if not ok(hi):
        raise ValueError(f"infeasible even at upper bound {hi}")
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


def make_feasible(rows, rows_per_sec, window_sec, calls):
    def ok(workers):
        calls.append(workers)
        return workers * rows_per_sec * window_sec >= rows
    return ok


calls = []
ok = make_feasible(7_200_000, 2_500, 900, calls)
best = first_true(1, 7_200_000, ok)
print(best, ok(best), ok(best - 1))
print("predicate calls:", len(calls) - 2)

try:
    first_true(1, 3, make_feasible(7_200_000, 2_500, 900, []))
except ValueError as e:
    print(f"ValueError: {e}")


def u_ok(w):  # more workers help, then coordination overhead hurts
    return 1000 / w + 5 * w <= 150


feasible = [w for w in range(1, 41) if u_ok(w)]
print(feasible[0], feasible[-1])
try:
    first_true(1, 40, u_ok)
except ValueError as e:
    print(f"ValueError: {e}")
Output
4 True False
predicate calls: 24
ValueError: infeasible even at upper bound 3
10 20
ValueError: infeasible even at upper bound 40
Scenario A

In your world

The situation

Your Jenkins ETL has BATCH_SIZE = 5000, picked three years ago. Nobody knows if it is right, and the nightly run sometimes overruns its window.

What actually breaks

You tune by trial (2,000, 10,000, 50,000), each a 40-minute run. After four runs you hold a number nobody can defend, and one run died on a Postgres statement-size limit.

What you'd do on Monday

Write a cheap fits_window(x) from row counts and measured per-row cost, argue monotonicity, search it, then run the real job once.

PythonCalibrate against measured throughput (needs your own timings)
def fits_window(workers):
    return total_rows / (workers * measured_rows_per_sec) <= WINDOW_SECONDS

workers = first_true(1, MAX_WORKERS, fits_window)   # ~log2(MAX_WORKERS) cheap calls
Scenario B

Imagine you work at Myntra

40M sale-night events, replay predicate

The numbers

Illustrative: find the smallest shard count (1 to 4,096) that replays 40M events in 20 minutes. ⌈log2(4,096)⌉ = 12 probes. A full replay predicate costs ~40 s, so 12 × 40 s = 480 s (8 min). A linear scan costs 4,096 × 40 s ≈ 45.5 hours.

What the Scenario-A answer does here

The Scenario A idea still holds; what breaks is cost per probe. At 40 s a call, tuning ten similar knobs takes over an hour on a shared cluster.

What flips at this scale

Make the predicate cheap, not the search smarter. Pre-aggregate the replay into 1,440 per-minute counts once, then test each candidate against those in about 1 ms. Twelve probes cost ~12 ms. The predicate is now a model, so validate it against one real replay.

The trade-off you'd defend

I would defend a cheap validated model over repeated full replays, trading a measured model error for milliseconds instead of a tuning day.

Illustrative figures for the arithmetic; not Myntra-published.

Gotchas

Non-monotone predicate returns a plausible wrong answer

Symptom

The search returns hi or a passing value while a smaller passing value exists, with no error.

Cause

Feasible values form an island (such as 20 <= x <= 30) and the probes fall outside it.

Fix

Argue "if x works, x+1 works" in one sentence before coding; assert ok(hi) first.

Hang on the last-feasible variant

Symptom

The loop never ends with lo and hi one apart.

Cause

lo = mid with floor mid leaves mid == lo.

Fix

Use mid = (lo + hi + 1) // 2 there.

Tricky questions

The predicate is True at mid, so return it immediately.
Most people say

Return the first mid where ok(mid) holds, to save iterations.

Actually

That is a feasible value, not the smallest. Keep going with hi = mid.

Scenario question

You're handed a nightly job that must finish in 90 minutes, a parallelism knob from 1 to 64, and 25 minutes per measurement trial.

Model answer

I would not bisect with real runs. I would measure per-row cost once, bisect a predicate "estimated time at parallelism p ≤ 90 minutes" in about 6 calls, then verify with one real run. The trade-off is model risk: if lock contention breaks linear scaling the predicate is not monotone, so I would check two values near the boundary.

Interview corner

CommonHow do you binary search when there is no sorted array?
“I look for a monotone yes/no question about the answer, then search the range for the first true with proven bounds. Cost is log of the domain size times one predicate call.”
TrickWhat breaks if the predicate is not monotone?
“I'd expect the search to discard the region holding the answer and still return a confident wrong value, so I state the monotonicity argument aloud and assert the upper bound is feasible.”
DesignThe predicate costs 30 seconds. What now?
“I'd cut the predicate cost before touching the search: sample, pre-aggregate or cache. Twelve probes at 30 s is 6 minutes; a millisecond model makes it free, at the price of validating the model once.”

Memory hook

Don't bake at every temperature: hotter never un-cooks the loaf, so one cooked result tells you which half to forget.

If you remember only one thing:

Search only works if feasibility never flips back, so prove that and check ok(hi) first.

Self-check

  1. What shape must the predicate have?

    False…False True…True, so a single boundary exists.

  2. What is the cost formula?

    ⌈log2(domain size)⌉ predicate calls times the cost of one call.

  3. Why check ok(hi) before looping?

    Otherwise an infeasible problem returns hi as if it were an answer.

Prove it

Run first_true over a domain of one million with a call counter and paste the count (about 20). Then use a predicate true only on [300, 400] and paste the wrong result.

dsa-05-03Card 3 of 6

Sort then scan without losing the contract

MediumP2 · Very likelyKnow cold7 min
sortingscantiesstabilitymutation

Why you care

A large share of ETL logic is "sort, then walk adjacent rows": deduplicate, sessionise, find gaps. Sorting turns a nested loop into one pass, the O(n²) to O(n log n) jump interviewers want named. The production risk is the contract: you reorder the caller's list, lose original row numbers, or get a different output order per rerun because equal keys came out arbitrarily. Interviewers probe ties and indices for that reason.

Explain like I'm 5

Finding two receipts from the same shop in a messy pile means comparing every pair. Sort by shop and date and twins touch, so you flip through once, comparing each receipt only with its neighbour. Sorting shuffles arrival order, so write the arrival number on each slip first.

Core concept

Two phases: order the data so related items are neighbours, then make one pass that only compares neighbours.

  • Cost: sort O(n log n) plus scan O(n), assuming O(1) comparisons. Long string or tuple keys make comparisons dearer; say so.
  • Python's sort is stable: equal keys keep input order.
  • Use a deterministic tie key such as (group, time, original_index) so output is identical on every run.
  • To keep original positions, sort the indices (sorted(range(n), key=...)) and report them.
  • list.sort() mutates in place and returns None; sorted() returns a new list. Both need O(n) temporary space; sorted allocates a new pointer array (about 8 bytes per row) and shares the element objects.
  • A neighbour-only scan is right only when the relation holds between adjacent sorted items. "Any two within distance d" may need look-ahead.

Sort first when you need grouping, adjacency or deterministic order. Use a hash map (Hash maps and sets under stated assumptions) when you only need membership or counts: O(n) and no order needed. If the data is already sorted by contract, assert that instead of sorting.

Minimal example sort versus sorted, and stable ties

PythonNone, copies and stable orderruns
rows = [("b", 2), ("a", 2), ("c", 1)]
print(rows.sort())
print(rows)
data = [3, 1, 2]
out = sorted(data)
print(data, out)
print(sorted([("b", 2), ("a", 2), ("c", 1)], key=lambda r: r[1]))
Output
None
[('a', 2), ('b', 2), ('c', 1)]
[3, 1, 2] [1, 2, 3]
[('c', 1), ('b', 2), ('a', 2)]

In production Flag repeated charges, report original row numbers

The key (account, amount, ts, i) puts events that can repeat next to each other: sorting by time first would let a different-amount row sit between a real pair. The final i makes output reproducible.

PythonAdjacent-after-sort duplicate detectorruns
def suspect_repeats(events, window=60):
    """Adjacent-after-sort check; returns pairs of ORIGINAL indices. Input untouched."""
    if any(len(e) != 3 for e in events):
        raise ValueError("expected (account, ts, amount) tuples")
    order = sorted(range(len(events)),
                   key=lambda i: (events[i][0], events[i][2], events[i][1], i))
    flagged = []
    for prev, cur in zip(order, order[1:]):
        a, b = events[prev], events[cur]
        if a[0] == b[0] and a[2] == b[2] and b[1] - a[1] <= window:
            flagged.append((prev, cur))
    return flagged


events = [("acc2", 500, 40), ("acc1", 100, 10), ("acc1", 130, 10),
          ("acc2", 480, 40), ("acc1", 400, 25), ("acc1", 100, 10)]
snapshot = list(events)
print(suspect_repeats(events))
print(suspect_repeats([("acc1", 100, 10), ("acc1", 110, 25), ("acc1", 120, 10)]))
print("input unchanged:", events == snapshot)
try:
    suspect_repeats([("acc1", 100)])
except ValueError as e:
    print(f"ValueError: {e}")
Output
[(1, 5), (5, 2), (3, 0)]
[(0, 2)]
input unchanged: True
ValueError: expected (account, ts, amount) tuples
Scenario A

In your world

The situation

Your job reads payments.csv from S3 and must flag customers charged the same amount twice within a minute. The current code compares every row with every other row.

What actually breaks

At 20,000 rows it takes 4 seconds. At 2 million month-end rows it runs about 11 hours (4 s × 100² = 40,000 s) and trips the Jenkins timeout. A quick fix calls rows.sort() in place, and the audit step, which expected arrival order, now reports row numbers that no longer match the source file.

What you'd do on Monday

Sort a list of indices, scan neighbours, report original row numbers, never mutate the shared list.

PythonSort indices, keep the original rows intact
order = sorted(range(len(rows)), key=lambda i: (rows[i]["customer"], rows[i]["amount"], rows[i]["ts"], i))
flagged = [(a, b) for a, b in zip(order, order[1:]) if is_repeat(rows[a], rows[b])]
Scenario B

Imagine you work at Airbnb

120M calendar rows per nightly run

The numbers

Illustrative: 120M listing-night rows × ~100 B ≈ 12 GB. Sorting costs 120M × log2(120M) ≈ 120M × 27 ≈ 3.2 billion comparisons. Tuples, strings and floats inflate 12 GB roughly 6x, so about 72 GB of objects, plus ~1 GB for the pointer array sorted() allocates (120M × 8 B) and ~4 GB for an index list (120M × ~36 B).

What the Scenario-A answer does here

The Scenario A algorithm is still right. One process is what fails: 72 + 1 + 4 ≈ 77 GB exceeds a 64 GB worker and the OOM killer ends the job.

What flips at this scale

The scan only needs neighbours within one listing, so global order is never required. Hash-partition by listing_id into 256 shards (12 GB ÷ 256 ≈ 47 MB each), sort and scan each independently, and run shards in parallel. Per shard: 470k rows × 19 ≈ 9M comparisons. The contract becomes "sorted within a key".

The trade-off you'd defend

I would defend per-key partition-then-sort over a global external sort, trading a shuffle step and no cross-key ordering for bounded memory per task and trivial parallelism.

Illustrative sizes and counts for the arithmetic; not Airbnb-published figures.

Gotchas

rows = rows.sort() makes rows None

Symptom

TypeError: 'NoneType' object is not iterable on the next line.

Cause

list.sort() sorts in place and returns None.

Fix

Call rows.sort() alone, or write rows = sorted(rows).

Mixed types blow up the sort

Symptom

TypeError: '<' not supported between instances of 'NoneType' and 'int'.

Cause

One null in a key column; Python 3 does not order None against numbers.

Fix

Encode null placement in the key: key=lambda r: (r["ts"] is None, r["ts"] or 0).

Tricky questions

Does the order of two successive sorts matter?
Most people say

Sort by time then by account; the order of the two sorts is irrelevant.

Actually

Stability makes the last sort the primary key. Time then account gives account-major order. A tuple key says it more clearly.

Scenario question

You're handed a 3 GB event export and told to find, per user, any two events less than 30 seconds apart. Memory is 8 GB.

Model answer

I would hash-partition by user into shards that fit in memory, sort each by (user, ts, row_index) and scan neighbours: O(n log n) with bounded memory. The trade-off is a pass to write shards, which I accept because a global sort of 3 GB at roughly 3x object overhead is near my limit.

Interview corner

CommonWhy sort first instead of comparing all pairs?
“I sort so related items become adjacent, so one linear pass replaces a quadratic one. The total is O(n log n), dominated by the sort, assuming constant-cost comparisons.”
TrickWhat is the difference between sorted and list.sort?
“I remember that sort mutates and returns None, while sorted returns a new list. If other code holds my list I don't mutate it, so I use sorted or sort indices and accept the memory.”
Experience checkHave you hit a nondeterministic report order?
“I have: reruns reordered equal-key rows. I added the original index as the last sort key, which makes the order a pure function of the data.”

Memory hook

Sort the receipts so twins sit together, but write the arrival number on each slip first.

If you remember only one thing:

Sort, compare neighbours only, end the key with the original index, and never mutate the input.

Self-check

  1. What does rows.sort() return?

    None; it sorts in place.

  2. Why end the sort key with the original index?

    It makes ties deterministic and preserves original positions.

  3. What is the total cost of sort-then-scan?

    O(n log n) for the sort plus O(n) for the pass, with O(1) comparisons.

Prove it

Generate 100,000 seeded (account, ts, amount) events with duplicates. Check the neighbour scan against a brute-force O(n²) checker on the first 2,000 and paste the agreement line and both timings.

dsa-05-04Card 4 of 6

Top-K with bounded heaps

MediumP2 · Very likelyKnow cold7 min
heaptop-kheapqselection

Why you care

"Top 10 slowest endpoints" sits inside almost every dashboard and alert. The bounded-heap version keeps O(K) memory while data streams past, so it survives a billion rows. Interviewers like it because it checks whether you know the orientation is backwards (the largest K live in a min-heap), size it correctly and survive ties. The TypeError on equal priorities is a classic production failure.

Explain like I'm 5

A podium has three spots. A runner arrives; if there is space they step on. Otherwise compare them with the slowest person on the podium, who would be knocked off first. If the newcomer is faster, the slowest steps down; if not, the newcomer leaves. You only ever look at one person.

Core concept

To keep the K largest, keep a min-heap of at most K items. The root heap[0] is the weakest keeper, the only one you compare with.

  • Fill: push while len(heap) < k.
  • Admit: once full, a newcomer enters only if it beats heap[0]; heapreplace swaps in one step. Otherwise reject.
  • Cost: O(n log K) time, O(K) space. Sorting the K results for display adds O(K log K).
  • Orientation: K smallest needs a max-heap. heapq is min-only before 3.14, which adds heappush_max, heappop_max, heapify_max, heappushpop_max and heapreplace_max; on older runtimes negate numbers.
  • Ties: (score, payload) compares payloads on equal scores, raising TypeError for dicts or custom objects. Use (score, -seq, payload).
  • Edges: K=0 returns empty, K greater than n returns everything, K<0 is an input error.

Use a bounded heap when n is large, K is small and data streams. Sort when n is small or K is near n. heapq.nlargest does this for you, though its docs say it suits small K. For only the K-th value, see Quickselect as rank partitioning.

Minimal example Equal scores trigger a payload comparison

PythonThe tie-break that heapq needs from youruns
import heapq
heap = [(1, {"id": "a"})]
try:
    heapq.heappush(heap, (1, {"id": "b"}))
except TypeError as e:
    print(f"TypeError: {e}")
heap = [(1, 0, {"id": "a"})]
heapq.heappush(heap, (1, 1, {"id": "b"}))
print(heap[0][2])
Output
TypeError: '<' not supported between instances of 'dict' and 'dict'
{'id': 'a'}

In production Streaming top-K with deterministic ties

Earlier arrival wins on equal scores via the negative sequence number. It accepts any iterable, including a generator.

PythonBounded heap over a one-shot streamruns
import heapq
from itertools import count


def top_k(items, k, score):
    """K highest scores; on equal score the earlier arrival wins. O(n log(k+1)) time, O(k) space."""
    if k < 0:
        raise ValueError("k must be >= 0")
    if k == 0:
        return []
    heap, seq = [], count()            # min-heap: heap[0] is the weakest keeper
    for item in items:
        entry = (score(item), -next(seq), item)   # later arrival ranks lower on ties
        if len(heap) < k:
            heapq.heappush(heap, entry)
        elif entry > heap[0]:
            heapq.heapreplace(heap, entry)
    return [e[2] for e in sorted(heap, reverse=True)]


tickets = [{"id": "t1", "n": 5}, {"id": "t2", "n": 9}, {"id": "t3", "n": 9},
           {"id": "t4", "n": 2}, {"id": "t5", "n": 7}, {"id": "t6", "n": 9}]
score = lambda t: t["n"]
print([t["id"] for t in top_k(tickets, 2, score)])
print([t["id"] for t in top_k(tickets, 0, score)])
print(len(top_k(tickets, 50, score)))
print([t["id"] for t in heapq.nlargest(2, tickets, key=score)])
try:
    top_k(tickets, -1, score)
except ValueError as e:
    print(f"ValueError: {e}")
print(len(top_k((t for t in tickets), 2, score)), "from a one-shot stream")
Output
['t2', 't3']
[]
6
['t2', 't3']
ValueError: k must be >= 0
2 from a one-shot stream

See it happen The podium of three

arrivals (scores)592791min-heap array, K=3799
  1. Score 5 arrives and the heap has room, so it is pushed.
  2. Score 9 arrives, still room, so it is pushed below the root; the root stays the minimum 5.
  3. Score 2 arrives, the heap fills to size 3, and 2 sifts up to become the root because it is now the smallest.
  4. Score 7 beats the root 2, so heapreplace evicts 2 and the heap settles with 5 on top.
  5. The second 9 beats the root 5, so 5 is evicted; the sequence number decides the tie in the earlier 9's favour.
  6. Score 1 is below the root 7, so it is rejected after one comparison and the heap is unchanged.
Notice: the heap never grows past three, and the rejected arrival costs one comparison against the root.
Scenario A

In your world

The situation

Your reporting script loads 8 million support-ticket rows into a list and calls sorted(rows, key=lambda r: r["age_hours"], reverse=True)[:10] to email the ten oldest open tickets.

What actually breaks

After a backfill the list reaches 40 million rows and the Jenkins agent is killed with exit code 137 (out of memory). A bigger agent doubled the cost and the job still takes 11 minutes for a ten-line report.

What you'd do on Monday

Stream rows with a generator and keep a bounded heap of ten with a sequence tie-breaker. Memory is constant and the job is one pass.

PythonConstant memory over a streamed S3 read (needs boto3 + real object)
oldest = top_k(iter_ticket_rows(s3_body), 10, score=lambda r: r["age_hours"])
for t in oldest:
    print(t["id"], t["age_hours"])
Scenario B

Imagine you work at Freshworks

500M ticket events a day, top 20 per tenant

The numbers

Illustrative: 500M events ÷ 20,000 tenants = 25,000 events per tenant. Heap top-20: 25,000 × log2(21) ≈ 25,000 × 4.4 ≈ 110k comparisons per tenant, 2.2B overall. Full sort per tenant: 25,000 × 14.6 ≈ 365k, 7.3B overall, holding 25,000 rows instead of 20.

What the Scenario-A answer does here

The Scenario A function works for one tenant on one machine. It breaks when a tenant's events are spread over 64 partitions: a global top-20 needs every event in one place, a shuffle of 500M rows.

What flips at this scale

A top-K heap is a mergeable partial result. Each of 64 partitions keeps 20 per tenant; the combine step merges 64 × 20 = 1,280 candidates per tenant. Network data falls from 500M rows to 20,000 × 1,280 = 25.6M candidates, about 20x less, and live state is 400k entries (20,000 × 20) per partition.

The trade-off you'd defend

I would defend local top-K plus merge over a global sort, trading a careful merge (one total order for ties everywhere) for a 20x smaller shuffle.

Illustrative volumes for the arithmetic; not Freshworks-published.

Gotchas

TypeError on equal priorities

Symptom

TypeError: '<' not supported between instances of 'dict' and 'dict' inside heappush.

Cause

Equal scores make tuple comparison fall through to the payload, which has no ordering.

Fix

Use (score, seq, payload) with a unique sequence number.

Largest K needs a min-heap

Symptom

The "top 5" returned are the 5 smallest, or the wrong item is evicted.

Cause

heapq is a min-heap, so heap[0] is the smallest; max-orientation needs negation or the 3.14 *_max functions.

Fix

Hold the K largest in a min-heap and compare against heap[0].

Tricky questions

Which heap holds the K smallest?
Most people say

A min-heap, since you want small values.

Actually

A bounded heap needs the eviction candidate at the root. For K smallest you evict the largest, so you need a max-heap.

Scenario question

You're handed a stream of 1 billion (endpoint, latency_ms) records and asked for the 50 slowest requests on a 2 GB machine.

Model answer

I would stream into a size-50 min-heap with a sequence tie-breaker: most records cost one comparison, admitted ones about log2(51) ≈ 6 steps, memory is 50 entries. The trade-off is no history beyond the top 50; if percentiles are wanted later I would keep a histogram alongside.

Interview corner

CommonFind the K largest in a stream.
“I keep a min-heap of at most K items. If it's full and the new value beats the root I replace the root. That is O(n log K) time and O(K) memory.”
TrickWhy a min-heap for the largest K?
“I need to evict the smallest quickly, and the root of a min-heap is the smallest. A max-heap would hand me the best item, which I never need to remove.”
DesignWhen do you choose sort over a heap?
“I sort if n is small or K is close to n: it is simpler and the heap saves nothing. I reach for the heap when the stream is large or unbounded and K is small.”

Memory hook

A podium with three spots: you only compare the newcomer with whoever would be knocked off first.

If you remember only one thing:

Keep the K best in a min-heap, compare to the root, and never let the payload be compared on a tie.

Self-check

  1. What is the heap's space cost?

    O(K), regardless of n.

  2. What happens when K = 0?

    Return empty before touching the heap.

  3. Why does the largest-K heap use a min-heap?

    Its root is the weakest keeper, the one you compare and evict.

Prove it

Run top_k on 2 million seeded scores with K=10, check against sorted(...)[-10:], and use tracemalloc to paste heap_peak < sort_peak as a boolean.

dsa-05-05Card 5 of 6

Quickselect as rank partitioning

HardP4 · DifferentiatorTalk about it8 min
quickselectpartitionselectionrandomization

Why you care

Sometimes you need exactly one rank: the median or the 95th percentile. Sorting does far more work than that needs. Quickselect answers in expected linear time by partitioning and discarding the side that cannot hold the rank. Interviewers test partition invariants and whether you honestly state the worst case: O(n²), not O(n).

Explain like I'm 5

You want the exam paper ranked 30th. Pick a random paper as a divider: lower marks left, higher right, equal in the middle. If the left pile has 40 papers, rank 30 is in it, so repeat inside that pile only. You never sort the stack.

Core concept

Quickselect is quicksort's partition step, recursing into one side only.

  • Rank translation: fix a zero-based target k first. Median is (n - 1) // 2; a percentile is ceil(p × n) - 1.
  • Partition the active range around a pivot into three zones: < pivot, == pivot, > pivot. Equal values need their own zone or the range may never shrink.
  • Invariant during the scan: a[lo:lt] < p, a[lt:i] == p, a[gt+1:hi+1] > p, with a[i:gt+1] unexamined.
  • Then: k < lt keep the left zone; k > gt keep the right zone; otherwise a[k] equals the pivot.
  • Cost: expected O(n) with a random pivot; worst O(n²) if pivots are consistently extreme. Randomness makes the worst case improbable, not impossible.
  • It works in place and guarantees only the k-th value, not a sorted array.

Use it for one rank on in-memory data you may reorder or copy. Use a bounded heap (Top-K with bounded heaps) for streams or K items, a sort for many ranks. Do not claim worst-case O(n) without naming a deterministic method such as median of medians.

Under the hood

A random pivot lands in the middle half of the range with probability 1/2, leaving at most 3/4 of the data, so work is a geometric series: n + (3/4)n + (9/16)n + … ≤ 4n. A fixed "first element" pivot on sorted input peels off one element per round: n + (n-1) + … = O(n²). A seeded random.Random gives reproducible tests; the loop here is iterative, so recursion limits do not apply.

Minimal example One partition pass, three zones

PythonDutch-flag partition around pivot 4runs
a = [9, 4, 7, 4, 1, 8, 4]
p = 4
lt, i, gt = 0, 0, len(a) - 1
while i <= gt:
    if a[i] < p:
        a[lt], a[i] = a[i], a[lt]
        lt += 1
        i += 1
    elif a[i] > p:
        a[i], a[gt] = a[gt], a[i]
        gt -= 1
    else:
        i += 1
print(a, lt, gt)
Output
[1, 4, 4, 4, 8, 7, 9] 1 3

In production In-place quickselect with a randomised pivot

It mutates its argument by design. The 300-case check uses heavy duplicates, where weak partitions fail.

PythonRank selection verified against sorted()runs
import random


def quickselect(a, k, rng):
    """Value that would sit at index k if a were sorted. Reorders a in place."""
    if not 0 <= k < len(a):
        raise IndexError(f"rank {k} outside 0..{len(a) - 1}")
    lo, hi = 0, len(a) - 1
    while lo < hi:
        p = a[rng.randint(lo, hi)]
        lt, i, gt = lo, lo, hi
        while i <= gt:                 # a[lo:lt] < p, a[lt:i] == p, a[gt+1:hi+1] > p
            if a[i] < p:
                a[lt], a[i] = a[i], a[lt]
                lt += 1
                i += 1
            elif a[i] > p:
                a[i], a[gt] = a[gt], a[i]
                gt -= 1
            else:
                i += 1
        if k < lt:
            hi = lt - 1
        elif k > gt:
            lo = gt + 1
        else:
            return p
    return a[k]

rng = random.Random(7)
for _ in range(300):
    xs = [rng.randint(0, 12) for _ in range(rng.randint(1, 40))]
    k = rng.randrange(len(xs))
    assert quickselect(list(xs), k, rng) == sorted(xs)[k]
print("300 random arrays with heavy duplicates agree with sorted()")
lat = [212, 95, 340, 101, 98, 180, 95, 2200, 130, 101]
rank = -(-95 * len(lat) // 100) - 1          # ceil(0.95 * n) - 1, zero-based
before = list(lat)
print(rank, quickselect(lat, rank, rng), sorted(before)[rank])
print("input reordered:", lat != before, "| fully sorted:", lat == sorted(lat))
try:
    quickselect([], 0, rng)
except IndexError as e:
    print(f"IndexError: {e}")
Output
300 random arrays with heavy duplicates agree with sorted()
9 2200 2200
input reordered: True | fully sorted: False
IndexError: rank 0 outside 0..-1

See it happen Partition, then keep one zone

a, pivot 41444879zones<===>>>
  1. Start: lt=0, i=0, gt=6 and nothing has been examined; the pivot value is 4.
  2. The 9 is greater than the pivot, so it is swapped to the right end and gt shrinks to 5; i stays because the incoming value is unexamined.
  3. The next two values equal the pivot, so i walks over them while lt stays put, which builds the middle zone.
  4. 7 and then 8 are both greater than the pivot and are swapped to the right end, so gt falls to 3.
  5. 1 is below the pivot, so it swaps with the first 4 at lt and both lt and i advance.
  6. The scan ends with lt=1 and gt=3: rank 0 is in the left zone, ranks 1 to 3 equal 4, and ranks 4 to 6 are in the right zone.
Notice: the array is only partly ordered, yet each rank's zone relative to the pivot is known, which is all selection needs.
Scenario A

In your world

The situation

Your nightly job computes the 95th-percentile response time of 6 million API calls for an SLA line. It does sorted(latencies)[int(0.95 * len(latencies))] on a list read from S3.

What actually breaks

It takes 9 seconds and about 1.1 GB, mostly the 6 million float objects in the loaded list. Someone writes a "faster" first-element-pivot version; the next file arrives already sorted and the job runs 6 hours until Jenkins kills it. The percentile was also off, because int() truncated instead of using the ceiling rank.

What you'd do on Monday

Translate the percentile into a zero-based rank, use a random pivot, and work on your own copy.

PythonPercentile via quickselect on a private copy
import math, random
k = math.ceil(0.95 * len(latencies)) - 1
p95 = quickselect(list(latencies), k, random.Random())
Scenario B

Imagine you work at Postman

10M response-time samples per hour per region

The numbers

Illustrative: 10M floats ≈ 40 bytes each in a Python list (32 B object + 8 B pointer) ≈ 400 MB per region-hour. Sorting costs 10M × log2(10M) ≈ 233M comparisons. Quickselect costs about 2n to 4n = 20M to 40M, roughly 6x to 12x fewer.

What the Scenario-A answer does here

The Scenario A fix works for one region. Across 12 regions a global p95 needs all 120M samples in one place (≈ 4.8 GB of objects).

What flips at this scale

Stop selecting from raw samples. Each region ships a fixed-bucket histogram (2,000 log-spaced counters) instead of 10M floats, and the aggregator sums them and walks cumulative counts to the target rank. Quickselect stays for exact answers inside one shard.

The trade-off you'd defend

I would defend histograms across regions and quickselect for the exact local answer, trading a stated bucket error for a payload that falls from ~400 MB to ~16 KB per region.

Illustrative sample counts and sizes for the arithmetic; not Postman-published.

Gotchas

O(n²) on sorted input with a fixed pivot

Symptom

A job fast on random data takes hours on data that arrives sorted or reversed.

Cause

First- or last-element pivots on ordered data split off one value per round.

Fix

Random pivot, and state that the worst case is still O(n²).

Hangs on many equal values

Symptom

The call spins on an all-identical array.

Cause

A two-way partition puts equal values on one side, so the range may not shrink.

Fix

Use the three-zone partition and exclude the equal zone from the next round.

Tricky questions

After quickselect returns, is the prefix sorted?
Most people say

The first k+1 elements are the k+1 smallest, in order.

Actually

They are the k+1 smallest as a set, unordered. Only a[k] is guaranteed.

Scenario question

You're handed an in-memory list of 5 million order values and asked for the median in a report that runs once a night.

Model answer

I would call statistics.median: 5 million values sort in seconds and the code is obviously correct. Only a profile would move me to quickselect on a private copy. The trade-off is readable code versus a speedup nobody asked for.

Interview corner

CommonFind the median without fully sorting.
“I'd translate the median to a zero-based rank and quickselect: partition around a random pivot into less, equal and greater, then keep only the zone holding the rank. Expected O(n), worst O(n²), and it reorders the array in place.”
TrickIs quickselect O(n)?
“I'd say expected O(n) with a random pivot, worst case O(n²), and state both. A guaranteed linear method exists, but I wouldn't write it unless asked.”
TrickWhat happens with lots of duplicate values?
“I use a three-way partition, because a two-way one can stall. The equal zone is excluded from the next round, so the range always shrinks.”

Memory hook

Pick a divider paper, split the stack, and keep only the pile that can hold rank 30.

If you remember only one thing:

Convert to a zero-based rank, partition into three zones around a random pivot, and keep only the zone containing the rank.

Self-check

  1. What are the expected and worst-case costs?

    Expected O(n) with a random pivot; worst case O(n²).

  2. Does quickselect leave the array sorted?

    No: only the k-th element is guaranteed to be in its sorted position.

  3. Why three zones instead of two?

    Equal values need their own zone so the range always shrinks, even on all-duplicate input.

Prove it

Count comparisons in quickselect on 100,000 sorted integers with random pivots and with a first-element pivot variant. Paste both counts.

dsa-05-06Card 6 of 6

Monotonic stacks and queues

MediumP3 · Role-dependentKnow cold7 min
monotonic-stackmonotonic-dequesliding-windowamortized

Why you care

Two recurring needs: "nearest greater value to the right" and "rolling extremum over an expiring window". The obvious loops are O(n²) and O(n × window). A monotonic stack or deque does both in O(n) by discarding candidates that can never win again. Interviewers use it to see whether you can prove a nested loop is still linear and handle ties and expiry correctly.

Explain like I'm 5

A line of people for a photo where the tallest must be visible. A newcomer taller than those just in front makes them irrelevant forever, so the shorter ones at the back go home. If the person at the front has waited past the allowed time, they leave from the front. The line stays ordered tallest to shortest.

Core concept

Both structures keep candidates in monotone order and discard anything that cannot win.

  • Monotonic stack ("next greater to the right"): hold indices of items still waiting, values decreasing bottom to top. A new value pops every waiting item it beats; those answers are the new index.
  • Monotonic deque (sliding maximum): hold indices with values decreasing front to back. Pop the back while dominated by the new value, push the new index, pop the front while its index left the window. The front is the maximum.
  • Ties: pop on <= and values are strictly decreasing, because an older equal value can never beat the newer one that lives longer. Pop on < and equals stay. State your rule.
  • Stale entries expire by index, so store indices and test dq[0] <= i - w.
  • Cost: each index is pushed once and popped at most once, so inner iterations total at most n: O(n) amortised (Complexity and amortization). Space is O(n) for the stack, O(w) for the deque.

Use a stack for one-sided nearest-greater/smaller, a deque when old items expire, a heap with lazy deletion for non-monotone scores. If w is tiny, plain max(window) is fine.

Minimal example Nearest greater to the right, by index

PythonEach index is pushed once and popped onceruns
vals = [2, 1, 5, 3, 4, 6]
nxt = [-1] * len(vals)
stack = []
for i, v in enumerate(vals):
    while stack and vals[stack[-1]] < v:
        nxt[stack.pop()] = i
    stack.append(i)
print(nxt, stack)
Output
[2, 2, 5, 4, 5, -1] [5]

In production Rolling maximum with expiring indices

This is the reusable template for any expiring-window extremum; a brute-force comparison guards the tie and window edges.

PythonReusable rolling-extremum template, O(n)runs
from collections import deque


def window_max(xs, w):
    """Max of every length-w window. Deque holds indices, values strictly decreasing."""
    if w < 1:
        raise ValueError("w must be >= 1")
    dq, out = deque(), []
    for i, x in enumerate(xs):
        while dq and xs[dq[-1]] <= x:   # <= : an equal older value can never win again
            dq.pop()
        dq.append(i)
        if dq[0] <= i - w:              # front index has left the window
            dq.popleft()
        if i >= w - 1:
            out.append(xs[dq[0]])
    return out


lat = [4, 2, 12, 3, 8, 8, 1, 7, 7, 7]
print(window_max(lat, 3))
brute = [max(lat[i:i + 3]) for i in range(len(lat) - 2)]
print(window_max(lat, 3) == brute)
print(window_max(lat, 1) == lat, window_max(lat, 10), window_max(lat, 11))
try:
    window_max(lat, 0)
except ValueError as e:
    print(f"ValueError: {e}")
Output
[12, 12, 12, 8, 8, 8, 7, 7]
True
True [12] []
ValueError: w must be >= 1

See it happen The deque discards dominated candidates

stream, window 34212388deque (values, front to back)8
  1. 4 arrives into an empty deque and becomes the only candidate.
  2. 2 is smaller than 4, so it stays behind it as a future candidate once 4 expires.
  3. 12 beats both 2 and 4, so both are popped from the back and 12 is the sole candidate; the first window's maximum is 12.
  4. 3 joins behind 12 and the maximum is still 12 because index 2 is inside the window.
  5. 8 pops the 3 it beats and queues behind 12, whose index is still within the window, so the maximum is 12.
  6. The second 8 pops the first one (equal values are dropped) and the front 12 has expired, so the maximum becomes 8.
Notice: nothing in the deque is smaller than something behind it, so the front is always the answer.
Scenario A

In your world

The situation

Your monitoring job computes a rolling 5-minute maximum of per-second CPU samples for 3,000 hosts, calling max(samples[i-299:i+1]) for every second.

What actually breaks

3,000 hosts × 86,400 seconds × 300 comparisons ≈ 78 billion a day. The nightly job crawls to 3 hours, someone shrinks the window to 60 seconds "to make it pass", and the alert now misses 4-minute spikes without any error.

What you'd do on Monday

One deque of indices per host, so each sample is pushed and popped once. Keep the window honest and test against brute-force max.

PythonOne deque per host, fed by a streaming reader (needs real data)
maxes = {host: deque() for host in hosts}
for host, i, cpu in samples:
    dq = maxes[host]
    while dq and series[host][dq[-1]] <= cpu:
        dq.pop()
    dq.append(i)
Scenario B

Imagine you work at Grab

500k geohash cells, rolling 5-minute surge maximum

The numbers

Illustrative: 500,000 cells × 1 update/s = 500,000 events/s. Brute-force max over 300 s is 500,000 × 300 = 150M comparisons per second. A deque does at most 2 operations per event, about 1M per second: 150x fewer.

What the Scenario-A answer does here

The Scenario A fix works per host. At 500k cells a steadily falling surge fills every deque with 300 entries: 500,000 × 300 = 150M entries, about 2.4 GB at 16 bytes each.

What flips at this scale

Coarsen time. Collapse each cell's updates into 10-second bucket maxima and run the deque over 30 buckets, not 300 samples. Worst-case state falls to 500,000 × 30 = 15M entries (about 240 MB), exact at 10-second granularity. Shard cells by geohash prefix so each worker owns its deques.

The trade-off you'd defend

I would defend bucketed maxima over per-second deques, trading 10-second timing resolution for a 10x cut in worst-case state.

Illustrative rates and sizes for the arithmetic; not Grab-published.

Gotchas

Off-by-one in the expiry test

Symptom

A window result includes a value from outside the window.

Cause

dq[0] < i - w instead of dq[0] <= i - w keeps a window of length w+1.

Fix

Test dq[0] <= i - w and compare to a brute-force result on small input.

Popping on the wrong tie rule

Symptom

A "next strictly greater" answer returns an equal value, or the deque fills with duplicates.

Cause

< used where <= was needed, or the reverse.

Fix

Write the rule in a comment and test with all-equal input.

Tricky questions

Does the inner while inside the for make it O(n²)?
Most people say

Nested loops mean quadratic time.

Actually

Each index is appended once and popped at most once, so inner iterations total at most n. Count pushes and pops.

Scenario question

You're handed a stream of per-second latency values and asked to maintain a rolling 1-minute extremum, updated every second, with minimal memory.

Model answer

I would use a deque of indices with <= on the back and an expiry check on the front: each sample is touched at most twice and memory is at most 60 entries. The trade-off is that it answers only that window shape; arbitrary ranges or percentiles would need another structure.

Interview corner

CommonHow do you keep a rolling extremum over an expiring window in linear time?
“I keep a deque of indices with decreasing values. New values pop dominated entries from the back, expired indices pop from the front, and the front is the maximum. Each index enters and leaves once, so it's O(n).”
TrickIt has a while inside a for. Why isn't that quadratic?
“I count pushes and pops: the pops are paid for by the pushes. Every index is pushed once and popped at most once, so inner iterations are bounded by n in total.”
Experience checkWhere have you replaced a rolling max?
“I replaced max(slice) per row in a metrics job with a deque and verified it against the brute force on a sample. I had to decide explicitly how ties behave.”

Memory hook

A photo line where anyone shorter than the newcomer goes home, and the person at the front leaves when their time is up.

If you remember only one thing:

Keep indices in monotone order, pop dominated ones from the back, expire stale ones from the front, and touch each index once.

Self-check

  1. Why store indices instead of values?

    So you can expire old entries from the front by position.

  2. Why is it O(n) despite the nested loop?

    Each index is pushed once and popped at most once.

  3. What does popping on <= instead of < do?

    It removes equal older values, keeping the deque strictly decreasing.

Prove it

Run window_max on 200,000 seeded integers with w=1,000, compare with brute-force max(slice) on the first 5,000 windows, and paste the equality result and total pop count (at most n).