Shelf · DSA Patterns · Chapter 1

Chapter 1: Reading a problem → naming the pattern

Most failed coding rounds are lost in the first two minutes, by solving a problem the interviewer did not ask. This chapter gives you a repeatable front end for any problem: pin the contract, read the signals, check the budget, state the invariant.

Difficulty
Priority
dsa-01-01Card 1 of 6

Clarify the input and output contract

EasyP1 · Must knowKnow cold7 min
contractclarifying-questionsconstraints
Needs: nothing. Start here.

Why you care

The expensive bugs on the job are contract bugs: the feed has duplicates, the "sorted" file is sorted per partition only, downstream needed original row positions. A coding round is the same thing in miniature, and the interviewer watches whether you notice. Employer guides tell candidates to clarify before coding; none publishes a checklist, so this list is editorial. This card is first because every later pattern has a precondition, and preconditions are facts about the input.

Explain like I'm 5

A tailor who cuts cloth before asking who the suit is for will cut something lovely that does not fit. A good tailor measures, repeats the numbers back ("forty-two chest, needed Friday?") and only then picks the cloth. The measurements are the contract; the cloth is the pattern.

Core concept

The rule: restate the input and output contract in your own words before you name a pattern.

  • Size and value bounds set the cost budget (Translate constraints into feasible complexity).
  • Order: sorted by what key, for the whole input?
  • Duplicates and empties: can values repeat; can the input be empty?
  • Mutation: may you modify the input? In-place patterns need permission.
  • Output shape: which order, positions or values? If positions matter, sorting first destroys the answer unless indices travel along.
  • Exact or approximate, streaming or batch: each can change the whole design.

Decision rule: ask if one answer would make you pick or reject an algorithm; skip if you can state a default ("I'll assume 32-bit values and read-only input"). Four to six questions is normal. Ten with no restatement is stalling; silence then code is guessing. Finish with a two-sentence restatement including one duplicate example and one empty case.

Minimal example Sorting first loses positions

PythonPositions do not survive a sortruns
vals = [30, 10, 20, 10]
srt = sorted(vals)
print(srt, srt.index(30), vals.index(30))
print(sorted(enumerate(vals), key=lambda p: p[1]))
print(len(set(vals)), len(vals))
Output
[10, 10, 20, 30] 3 0
[(1, 10), (3, 10), (2, 20), (0, 30)]
3 4

The 30 moves from index 0 to 3. Pairs keep the original index. The set collapsed 4 elements into 3.

In production A contract you can interrogate

Write the contract as data. Unanswered fields are the questions you have not asked. The domain is a batch of settlement amounts; nothing is solved, only the front end.

PythonContract object with open questions and an input checkerruns
from dataclasses import dataclass, fields


@dataclass
class Contract:
    max_n: int | None = None
    value_range: tuple | None = None
    sorted_input: bool | None = None
    duplicates: bool | None = None
    empty_ok: bool | None = None
    may_mutate: bool | None = None
    keep_indices: bool | None = None
    exact: bool | None = None
    streaming: bool | None = None


def open_questions(c):
    return [f.name for f in fields(c) if getattr(c, f.name) is None]


def check_input(c, data):
    problems = []
    if not data and c.empty_ok is False:
        problems.append("empty input")
    if c.max_n is not None and len(data) > c.max_n:
        problems.append(f"n={len(data)} exceeds {c.max_n}")
    if c.value_range is not None:
        lo, hi = c.value_range
        if any(not lo <= x <= hi for x in data):
            problems.append(f"value outside {lo}..{hi}")
    if c.sorted_input and any(a > b for a, b in zip(data, data[1:])):
        problems.append("not sorted")
    if c.duplicates is False and len(set(data)) != len(data):
        problems.append("duplicates")
    return problems


c = Contract(max_n=5, value_range=(0, 1000), sorted_input=True,
             duplicates=False, empty_ok=False)
print(open_questions(c))
for batch in ([], [5, 9, 9], [1, 2, 3, 4, 5, 6], [10, 5], [3, -1]):
    print(batch, check_input(c, batch) or "ok")
partial = Contract(max_n=5)
print(check_input(partial, [1, 2, 3]) or "ok", check_input(partial, []) or "ok")
Output
['may_mutate', 'keep_indices', 'exact', 'streaming']
[] ['empty input']
[5, 9, 9] ['duplicates']
[1, 2, 3, 4, 5, 6] ['n=6 exceeds 5']
[10, 5] ['not sorted']
[3, -1] ['value outside 0..1000', 'not sorted']
ok ok

Four fields are still None: four questions unasked. A partly filled contract checks only what you have answered, so the last line prints ok ok.

Scenario A

In your world

The situation

Your nightly job reads settlements.csv from S3. A ticket says "dedupe the merchant rows", so you write a set() pass and Jenkins goes green.

What actually breaks

Nobody asked whether reconciliation needs one row per merchant or per merchant per day. The set collapsed 48,213 rows into 9,870 and finance's variance report was off by 38,343 rows for a week.

What you'd do on Monday

Put the contract in the ticket as five lines (key, order, empties, mutability, expected output count), then assert it on the first run:

PythonRow-count contract on the job (needs the real S3 file)
expected_out = len({(r["merchant_id"], r["day"]) for r in rows})
assert len(result) == expected_out, f"contract says {expected_out}, got {len(result)}"
Scenario B

Imagine you work at Razorpay

4M payment events/hour, streaming

The numbers

4,000,000 events/hour ÷ 3,600 s ≈ 1,111 events/s. "Distinct paying customers today" means up to 96M events and, say, 20M distinct ids. An exact Python set of 20M string ids is about 20M × ~100 bytes ≈ 2 GB per worker.

What the Scenario-A answer does here

Writing the contract down still works. What breaks is the batch reading of "distinct" (collect everything, then set()): the contract never said whether the answer must be exact or live.

What flips at this scale

Exact versus approximate and streaming versus batch now choose the design. If a small error is fine, an approximate counter with kilobytes of state replaces 2 GB. If it must be exact, shard by customer-id hash: 8 shards × 2.5M ids ≈ 250 MB each.

The trade-off you'd defend

I would ask exact-or-approximate first and, if approximate is acceptable, defend the small sketch over the exact set, trading a bounded error for state that survives restarts.

Illustrative figures; not Razorpay-published numbers.

Gotchas

Sorting before checking position requirements

Symptom

Your values are right, but the expected output wanted original positions and yours differ.

Cause

sorted() reorders elements, so positions come from the sorted copy.

Fix

Ask "positions or values?" first. If positions matter, sort enumerate(vals) or avoid sorting.

A set silently drops duplicates

Symptom

len(set(xs)) is 3 where len(xs) is 4 and your result count is low, with no error.

Cause

A set keeps one copy per equal key, which is wrong if the contract counts duplicates separately.

Fix

Ask whether duplicates are meaningful; use collections.Counter when multiplicity matters.

Tricky questions

You asked ten clarifying questions. Is more always better?
Most people say

Yes, a thorough candidate leaves nothing open.

Actually

Only questions that change the algorithm are worth asking. State defaults for the rest. Ten questions with no restatement look like stalling.

Scenario question

You're handed: "Given a list of numbers, report the two biggest values." You have thirty seconds before you code. What do you ask?

Model answer

I would ask four things. How large can the list be? Can it have fewer than two elements, and what do I return? Do two equal 9s count as the two biggest? Is it in memory or a stream? Then I restate the contract aloud. The trade-off is half a minute against building the wrong design.

Interview corner

CommonWhat do you do first when given a coding problem?
“I restate it in my own words, then ask about size, ordering, duplicates, empty input and mutation. Those answers decide which approaches are legal.”
TrickThe input says "sorted". What else do you check?
“I'd ask sorted by what, and whether that holds for the whole input or only per chunk. I'd also ask about duplicates, because they change boundary handling.”
Experience checkTell me about a time an assumption about data broke a job.
“I deduplicated a settlements file by merchant id, but the key was merchant id plus day, and we lost tens of thousands of rows. Now I put the key and expected output count in the ticket and assert it.”

Memory hook

Measure the customer before you cut the cloth.

If you remember only one thing:

Say the contract back before you name any pattern.

Self-check

  1. Name three contract answers that can make a pattern illegal.

    Sortedness, mutation permission and index preservation.

  2. Why carry (index, value) pairs when sorting?

    A sort moves elements, so original positions are lost unless stored beside each value.

  3. When may you skip a clarifying question?

    When you can state a default and every plausible answer leads to the same algorithm.

Prove it

Invent three one-line problem statements from your ETL work. Fill all nine Contract fields for each and write inputs that break the answered ones. Paste the contracts and the check_input output. About 20 minutes.

dsa-01-02Card 2 of 6

Sequence signals and competing patterns

MediumP2 · Very likelyKnow cold7 min
sequencessignalswindowstwo-pointers

Why you care

A few cues cover most sequence problems: sorted ends, a contiguous range, overlapping spans, values that double as indexes. Each suggests a pattern, and each pattern fails under a specific precondition. The usual mistake is learning the cue and forgetting the rejecting condition, so you shrink a window over negatives and return a confident wrong answer.

Explain like I'm 5

A conveyor belt of parcels. Need any stretch of consecutive parcels: slide a frame along the belt. Each trick needs the belt to be a certain way; a frame that shrinks when the load is heavy only works if removing a parcel never makes the load heavier.

Core concept

The rule: read the cue, name the candidate, test the rejecting precondition before you commit.

CueCandidateRejecting precondition
Sorted input, pair or endsTwo pointersUnsorted, and sorting would lose indices
Contiguous range with a boundVariable windowNegatives: shrinking can raise the sum
Contiguous range, fixed lengthFixed windowAggregate not O(1) to update
Many range sums, or negativesPrefix sumsAggregate has no inverse (max)
Overlapping spansMerge intervalsMalformed spans (start > end)
Values in 1..n, n elementsCyclic sortRead-only input; duplicates without a guard

Define monotone validity: once a window is invalid, growing it keeps it invalid.

Decision rule: take the first pattern whose preconditions all hold and say the precondition aloud. If none hold, the cue was a decoy.

Minimal example A window that looks right and is not

PythonShrinking window versus exhaustive checkruns
def window_best(a, limit):
    lo = total = best = 0
    for hi, x in enumerate(a):
        total += x
        while total > limit and lo <= hi:
            total -= a[lo]
            lo += 1
        best = max(best, hi - lo + 1)
    return best
def brute(a, limit):
    spans = [j - i for i in range(len(a)) for j in range(i + 1, len(a) + 1) if sum(a[i:j]) <= limit]
    return max(spans, default=0)
for a in ([2, 1, 3, 1], [-3, 1, 4, 4, -3]):
    print(a, window_best(a, 3), brute(a, 3))
Output
[2, 1, 3, 1] 2 2
[-3, 1, 4, 4, -3] 3 5

With nonnegative values the window agrees with brute force. With negatives it reports 3, but the whole array sums to 3 and is a valid run of length 5.

In production A cue router with rejection reasons

The table as data. suggest returns USE or REJECT with the reason, so the logic is testable and doubles as your mental checklist.

PythonSignal table with rejecting preconditionsruns
RULES = [
    ("two pointers", "ordered_pair",
     lambda f: f["sorted"] or f["may_sort"], "unsorted and order or indices must survive"),
    ("variable window", "contiguous_bound",
     lambda f: f["nonneg"], "negatives break monotone validity"),
    ("prefix sums", "contiguous_sum",
     lambda f: True, ""),
    ("merge intervals", "overlap",
     lambda f: f["start_le_end"], "malformed intervals (start > end)"),
    ("cyclic sort", "values_1_to_n",
     lambda f: f["may_mutate"] and f["in_range"], "needs mutation and values inside 1..n"),
]


def suggest(cues, facts):
    out = []
    for name, cue, ok, why in RULES:
        if cue not in cues:
            continue
        out.append(f"USE {name}" if ok(facts) else f"REJECT {name}: {why}")
    return out


facts = dict(sorted=False, may_sort=False, nonneg=False, start_le_end=True,
             may_mutate=False, in_range=True)
cases = {
    "pair in unsorted feed, keep indices": {"ordered_pair"},
    "longest span under a bound, signed deltas": {"contiguous_bound", "contiguous_sum"},
    "overlapping maintenance slots": {"overlap"},
    "ids 1..n, input is read-only": {"values_1_to_n"},
}
for label, cues in cases.items():
    print(label, "->", suggest(cues, facts))
Output
pair in unsorted feed, keep indices -> ['REJECT two pointers: unsorted and order or indices must survive']
longest span under a bound, signed deltas -> ['REJECT variable window: negatives break monotone validity', 'USE prefix sums']
overlapping maintenance slots -> ['USE merge intervals']
ids 1..n, input is read-only -> ['REJECT cyclic sort: needs mutation and values inside 1..n']

The second case restates the minimal example: the cue fires and the precondition fails. Prefix sums survive and make each range check O(1), but finding the longest span still needs all pairs or an extra structure.

See it happen Why the shrinking window loses a valid start

values (bound = 3)-3144-3inside windowin
  1. Indices 0 to 2 are in the window; the sum is 2, within the bound.
  2. Adding index 3 makes the sum 6, so the window shrinks from the left.
  3. Dropping index 0 removes a negative, so the sum rises to 9.
  4. The loop keeps dropping from the left until the window is empty, so the leading -3, which made a long span valid, is gone.
  5. Index 4 is added to an empty window, so the length-3 best was set earlier, but the whole array sums to 3 and is valid at length 5.
Notice: dropping the left element made the sum bigger, which is the broken precondition.
Scenario A

In your world

The situation

Your Jenkins job scans hourly_orders.csv for the longest consecutive stretch of hours whose summed amount stays at or under a cap. Refunds are negative.

What actually breaks

You ship "longest stretch under a bound means sliding window". It passes last month's file but on month-end data reports 3 hours where the true answer is 5, understating safe stretches by 40 percent.

What you'd do on Monday

Check the precondition first; if any amount can be negative, take the prefix-sum path:

PythonGuard the window precondition
if any(x < 0 for x in amounts):
    raise ValueError("variable window needs nonnegative amounts; use the prefix-sum path")
Scenario B

Imagine you work at Swiggy

80,000 order events/min

The numbers

80,000 events/min across 4,000 restaurants is 20 events/min each. A day has 1,440 minutes. Brute force over every start and end is 1,440² / 2 ≈ 1.04M range sums per restaurant, × 4,000 ≈ 4.1 billion.

What the Scenario-A answer does here

The nonnegativity guard still works. What breaks is the signed-data fallback over all (i, j) pairs: 4.1 billion checks a day. Even at O(1) per check and an assumed 10M Python steps/s, that is about 410 s, roughly 7 minutes, per day on one worker.

What flips at this scale

Order counts are nonnegative, so one window pass is 1,440 steps per restaurant ≈ 5.8M total, about 700 times less. For signed adjustments, prefix sums make each range check O(1), but the longest-span search still needs pairs or an extra structure such as a monotonic stack over prefix minima.

The trade-off you'd defend

I would defend a nonnegativity check at ingest plus a window over a quadratic fallback, trading a quarantine path for signed rows against a roughly 700-times cheaper scan.

Illustrative numbers; not Swiggy-published figures.

Gotchas

A stretch cue without monotone validity

Symptom

The window result is shorter than brute force on the same small input (3 versus 5).

Cause

Shrinking assumes a valid window stays valid; negatives break that.

Fix

State the validity rule, assert nonnegativity, and cross-check against brute force.

Cyclic placement that never terminates

Symptom

The loop spins at 100 percent CPU on input with a repeated value.

Cause

The target slot already holds an equal value, so each swap exchanges equal values.

Fix

Skip the swap when the target slot already holds an equal value.

Tricky questions

Sorted input always means two pointers?
Most people say

Sorted means two pointers or binary search; anything else wastes the guarantee.

Actually

Sorted is a cue, not a command. A single membership check wants a set; check whether the output needs positions.

Scenario question

You're handed per-minute queue-length deltas (can be negative) and asked for the longest consecutive stretch whose sum stays at or under a cap. A teammate proposes a sliding window. What do you say?

Model answer

I would say the window is wrong and give a three-element counterexample where a later negative makes a discarded start valid again. Prefix sums make each sum check O(1), but the longest-span search still needs all pairs or an extra structure, so I would write the quadratic reference first. The trade-off is slower code against correctness; I would not trade correctness for the simpler template.

Interview corner

CommonHow do you choose between a sliding window and prefix sums?
“I'd check the values first. Nonnegative with a monotone condition gives a window in O(n) time and O(1) space. Negatives or many range queries mean prefix sums, paying O(n) extra space.”
TrickWhy can't you shrink a window when the array has negative numbers?
“I'd explain that removing an element can raise the sum, so shrinking stops moving toward validity and may discard a start a later negative would rescue.”
Experience checkWhen did you reach for a pattern and find it didn't fit?
“I used a window on refund-adjusted totals and it undercounted at month end because refunds are negative. I now assert the precondition.”

Memory hook

A conveyor belt only allows the trick it was built for: check the belt, then pick the trick.

If you remember only one thing:

Every cue has a rejecting precondition; say it aloud before you commit.

Self-check

  1. What precondition must a variable-size window have?

    A monotone validity rule, usually nonnegative values.

  2. Which pattern survives a range-sum problem with negatives?

    Prefix sums: a range total is a difference of two prefix values.

  3. What guarantees termination in cyclic placement?

    A guard that skips the swap when the target slot already holds an equal value.

Prove it

Run window_best and brute on 200 lists of length 6 from random.Random(1), values -3 to 4, and count disagreements. Repeat with values 0 to 4. Paste both counts (nonzero, then zero). About 25 minutes.

dsa-01-03Card 3 of 6

Search, rank and frontier signals

MediumP2 · Very likelyKnow cold7 min
binary-searchheapsmonotonic-stackgraphs

Why you care

The second family of cues is about finding things: a boundary in sorted data, the best k, the next larger element, reachability. Each has a quiet precondition candidates skip. The binary-search cue that matters is not "sorted array" but "a yes/no predicate that flips exactly once". In Python the cue-to-tool step is often one import, because bisect and heapq ship in the standard library.

Explain like I'm 5

Finding a name in a phone book is a boundary search: open in the middle, see whether you are before or after, discard half. That works only because the book is in order. Finding the three heaviest parcels on an unsorted pile is different: keep a shelf of the current top three and swap one out when something heavier appears.

Core concept

The rule: name what you can discard, then check the discard is always safe.

CueCandidateReject if
Sorted data, boundaryBinary search (bisect)Data unsorted
Smallest value that is feasibleBinary search on the answerFeasibility flips back
Top-k, unorderedSize-k heap or quickselectk near n: sort
Next greater or smallerMonotonic stackYou need every element
Moving-window extremumMonotonic dequeNo fixed expiry
Reachability; fewest hopsDFS or BFS (BFS for hops)Edges have weights
Cheapest pathDijkstraAny negative weight

Define monotone feasibility: false up to some point, true afterwards, never flipping back. bisect has had key since 3.10; heapq is a min-heap on 3.12 (public max-heap helpers arrive in 3.14), so negate priorities or use nlargest. Neither module checks sortedness.

Decision rule: for order cues ask whether order is guaranteed; for rank cues whether you need all ranks or the top k; for graph cues whether edges carry costs.

Minimal example Bisect on the wrong data

Pythonbisect needs sorted input, heapq does notruns
from bisect import bisect_left, bisect_right
import heapq

s = [1, 3, 3, 3, 8]
print(bisect_left(s, 3), bisect_right(s, 3))
u = [8, 1, 3, 3, 3]
print(bisect_left(u, 1), u.index(1))
print(heapq.nlargest(2, u), sorted(u)[-2:])
Output
1 4
0 1
[8, 3] [3, 8]

The two bisects bracket the run of 3s. On unsorted data bisect_left returns 0 for a value at index 1, with no error.

In production A guarded boundary search on the answer

Bisection over a candidate range needs monotone feasibility, so this template checks it on a sample first. The domain is the smallest per-partition drain rate that empties an order backlog within a window.

PythonBinary search on feasibility with a monotonicity checkruns
import math


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):
        return None
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


def is_monotone(lo, hi, ok):
    flags = [ok(x) for x in range(lo, hi + 1)]
    return flags == sorted(flags)


backlog = [30, 11, 23, 4, 20]          # orders waiting per partition
window_s = 7                           # drain window in seconds


def drains(rate):
    return sum(math.ceil(q / rate) for q in backlog) <= window_s


def flaky(rate):
    return rate % 4 != 0 and rate > 4


print(first_true(1, max(backlog), drains), is_monotone(1, 30, drains))
print(first_true(1, 30, flaky), is_monotone(1, 30, flaky))
Output
20 True
13 False

The second line returns 13 though 5 is feasible: flaky flips back to False at 8, so the search discards a half it should keep. The check is a linear scan, so use it in tests.

Scenario A

In your world

The situation

A Jenkins job must pick the largest batch size that loads orders.csv into Postgres inside a 60-second timeout. You try 100, 200, 300 by hand.

What actually breaks

Twelve full-load trials of up to 60 s each take up to 12 minutes of pipeline time and are accurate only to the nearest hundred. At one size a lock spike makes a larger size faster, so the hand-picked size fails on busy days.

What you'd do on Monday

Test monotonicity on a sample range first. If it holds, search the boundary in about 12 dry-run trials with first_true from the production example (the answer is one below the first too-slow size):

PythonSearch with a dry-run predicate (needs a Postgres connection)
too_slow = lambda size: load_dry_run(size) > 60.0
assert is_monotone(100, 400, too_slow), "timing not monotone: do not trust bisection"
best = first_true(100, 5000, too_slow) - 1
Scenario B

Imagine you work at Zerodha

50M tick records per trading session

The numbers

A 6.25-hour session is 22,500 s. 50M ticks ÷ 22,500 ≈ 2,222 ticks/s. Sorting 50M items is about 50M × log2(50M) ≈ 50M × 25.6 ≈ 1.3 billion comparisons; a size-20 heap costs 50M × log2(20) ≈ 216M.

What the Scenario-A answer does here

Checking the precondition first still holds. What breaks is "collect everything, then sort": 50M tuples at ~100 bytes ≈ 5 GB, and the answer arrives after the session ends.

What flips at this scale

Ranking becomes incremental. Keep a count per instrument (a few thousand keys, not 50M) and run nlargest over the counters periodically. That fits in megabytes and answers live.

The trade-off you'd defend

I would defend a keyed counter plus periodic top-k over a full sort, trading per-event ordering nobody needs for constant memory.

Illustrative session length and rates; not Zerodha-published figures.

Gotchas

bisect on data that is not actually sorted

Symptom

bisect_left returns a plausible index, no exception, yet a[i] != target.

Cause

The module assumes sorted input and never verifies it.

Fix

Assert sortedness in tests, sort first when allowed, or use a hash map.

Bisection on a non-monotone predicate

Symptom

The threshold is not the smallest feasible value (13 versus 5 in the example).

Cause

Bisection assumes the predicate flips once; lock contention or cache effects can break that.

Fix

Sample the predicate with is_monotone; if it flips, scan instead.

Tricky questions

Find the k-th largest. Always a size-k heap?
Most people say

Yes, a heap of size k is O(n log k), so it always wins.

Actually

When k is near n, sorting is cheaper; for a single rank on in-memory data, quickselect gives expected O(n). The heap wins when k is small and data streams.

Scenario question

You're handed a service that reports the 10 slowest endpoints every minute from millions of latency samples an hour. Someone suggests storing all samples and sorting each minute. What do you say?

Model answer

I would not store raw samples. The unit of ranking is the endpoint, so I keep a running aggregate per endpoint and run nlargest(10, ...) over those each minute. Memory scales with endpoints, not samples. The trade-off is losing per-sample detail; for percentiles I would add a separate bounded structure.

Interview corner

CommonWhen do you use binary search outside a sorted array?
“I'd use it when the answer lives in a range and feasibility is monotone. I check that first, because if it flips back, halving discards valid answers.”
TrickWhat is the difference between bisect_left and bisect_right?
“I'd say that with duplicates, bisect_left returns the first insertion point and bisect_right the one after the last equal item.”
DesignWhich structure finds the 'next greater element to the right'?
“I'd use a monotonic stack and scan once, popping smaller items because they can never answer for anyone later. That's O(n).”

Memory hook

A phone book, a shelf of three, a queue of people: boundary, rank and nearest, each with something safe to throw away.

If you remember only one thing:

Name what you can safely discard, and confirm the rule holds.

Self-check

  1. What must a predicate satisfy for binary search on the answer?

    It must be monotone: false up to a point, true afterwards.

  2. Why does nlargest work on unsorted input but bisect does not?

    nlargest examines every item; bisect assumes sorted order.

  3. What gets popped in a monotonic stack for "next greater"?

    Values smaller than or equal to the current one.

Prove it

Build three predicates for first_true: one monotone, two that flip back. Print the bisection answer, the linear-scan answer and the is_monotone flag for each. Paste the table. About 25 minutes.

dsa-01-04Card 4 of 6

Dependency and repeated-state signals

MediumP3 · Role-dependentTalk about it7 min
dependenciesgraphsdpbacktracking

Why you care

Some problems are about structure rather than sequence: hierarchy, dependencies, merging groups, branching choices, repeated work. The failure mode here is naming a heavy pattern too early; a dynamic-programming label on a problem with no repeated state wastes the round. This card treats recognition as a hypothesis with one fast check that can kill it. How much of this a loop probes depends on the company.

Explain like I'm 5

A building site has tasks that depend on each other: you cannot paint before plastering. A legal order is a topological order, and a loop in the dependencies means the plan is impossible. In a maze with many forks, if you keep rewalking the same corridor from the same junction, write the answer on the wall the first time. That is memoisation.

Core concept

The rule: a cue gives a hypothesis; test the one fact that would kill it before building anything.

CueHypothesisCheck that can falsify it
Parent/childTree traversalA node with two parents
Prefix lookupTrieExact match only: use a set
Connected? with mergesUnion-findEdges get removed
"X before Y"Topological sortAny cycle
All valid arrangementsBacktrackingYou need only the best
Best or count over choicesDPCalls equal distinct states

Define overlapping subproblems: the same state is reached by different paths. The state is the minimal set of values that decides the future, such as (stage, mode). For DP, count calls against distinct states; if nearly equal, there is nothing to cache. For ordering, the falsifier is a cycle, which graphlib reports.

Decision rule: pick the structure the cue suggests, test its killer fact before coding, and if it fails return to the contract (Clarify the input and output contract).

Minimal example A dependency hypothesis that fails

PythonOrdering works until a cycle appearsruns
from graphlib import TopologicalSorter, CycleError

deps = {"load": {"clean"}, "clean": {"extract"}, "extract": set()}
print(list(TopologicalSorter(deps).static_order()))
deps["extract"] = {"load"}
try:
    list(TopologicalSorter(deps).static_order())
except CycleError as exc:
    print("CycleError:", exc.args[0])
Output
['extract', 'clean', 'load']
CycleError: nodes are in a cycle

graphlib ships since Python 3.9. A legal order exists exactly when there is no cycle.

In production Counting repeated states before you commit to DP

This harness counts how often each state is reached and compares it to the number of distinct states. The domain is choosing, per pipeline stage, between a spot and an on-demand instance with a switch penalty. The model is invented to exercise the check.

PythonCalls versus distinct states, with and without a cacheruns
from collections import Counter
from functools import cache

COST = {"spot": [4, 9, 3, 8, 5, 7, 4, 6], "demand": [6, 5, 6, 5, 6, 5, 6, 5]}
SWITCH = 2


def _best(i, mode):
    """Cheapest cost to run stages i.. when stage i runs on `mode`."""
    if i == len(COST[mode]):
        return 0
    other = "demand" if mode == "spot" else "spot"
    stay = COST[mode][i] + best(i + 1, mode)
    move = SWITCH + COST[other][i] + best(i + 1, other)
    return min(stay, move)


def build(memo):
    global best
    seen = Counter()

    def counted(*args):
        seen[args] += 1
        return _best(*args)

    best = cache(counted) if memo else counted
    return seen


for memo in (False, True):
    seen = build(memo)
    answer = best(0, "spot")
    calls, states = sum(seen.values()), len(seen)
    print(f"memo={memo} answer={answer} calls={calls} distinct_states={states}")
    print("  repeated work:", calls > 2 * states)
Output
memo=False answer=44 calls=511 distinct_states=17
  repeated work: True
memo=True answer=44 calls=17 distinct_states=17
  repeated work: False

511 calls reach only 17 distinct states, so overlap survives. With the cache the answer is unchanged, which doubles as a regression test.

See it happen Calls fan out, states stay few

stayswitchstayswitchstayswitch(0, spot)(1, spot)(1, demand)reached 2xreached 2x
  1. The root state (0, spot) branches into stay and switch.
  2. Stage 1 has two states, each reached once so far.
  3. From (1, spot) we reach (2, spot) and (2, demand).
  4. From (1, demand) we reach the same two stage-2 states by different paths.
  5. Each stage-2 state is now reached twice: that duplication is the overlap, and it doubles at every stage in a plain recursion.
Notice: every stage has only two states however many paths lead there, so calls grow with paths while the work you need grows with states.
Scenario A

In your world

The situation

Your Jenkins deploy runs 14 SQL scripts in an order someone typed by hand. Each script has a comment -- requires: X, Y. The order broke twice last quarter.

What actually breaks

A new script requires report_views, which already requires the new script. Jenkins runs them in typed order, the first fails with "relation does not exist", the retry fails the other way round, and the release is blocked for two hours.

What you'd do on Monday

Parse the comments into a dict, use graphlib.TopologicalSorter, and fail the build before touching the database on a cycle:

PythonFail the build on a cycle (needs your script dir)
try:
    order = list(TopologicalSorter(deps).static_order())
except CycleError as exc:
    raise SystemExit(f"dependency cycle: {exc.args[1]}")
Scenario B

Imagine you work at Atlassian

300,000 linked work items

The numbers

V = 300,000 issues, E = 1,200,000 "blocks" links. A topological pass costs V + E = 1.5M steps. A naive "walk all upstream blockers of every issue" approaches V × E ≈ 3.6 × 10^11 on a deep chain.

What the Scenario-A answer does here

A topological sort still catches the bad link. What breaks is rerunning it on every edit: 5,000 edits/hour × 1.5M steps = 7.5 billion steps/hour, mostly redone work.

What flips at this scale

Cycle checks move to write time and become incremental: for "A blocks B", ask only whether B can already reach A, searching the affected subgraph. A full sort runs offline for reports.

The trade-off you'd defend

I would defend rejecting a cycle-forming link at write time over a periodic audit, trading a small search per edit for never storing an impossible plan.

Illustrative counts; not Atlassian-published figures.

Gotchas

Naming DP without repeated states

Symptom

The memoised version is no faster; the cache holds about as many entries as there were calls.

Cause

The recursion never reaches the same state twice.

Fix

Run the calls-versus-states check first; near 1, look for greedy or divide-and-conquer.

Union-find with deletions

Symptom

After removing a link, find still says two nodes are connected.

Cause

Union-find only merges; it cannot split a component.

Fix

Rebuild from the remaining edges, process offline in reverse, or choose another structure.

Tricky questions

Every shortest-looking question is BFS?
Most people say

A grid of cells with moves is just BFS.

Actually

BFS gives fewest hops only when every move costs the same. Different nonnegative costs point to Dijkstra; negative costs rule it out.

Scenario question

You're handed a build tool where tasks declare depends_on, and it sometimes hangs. It resolves each task by recursing into its dependencies. What do you check?

Model answer

I would suspect a cycle, because recursion without a visited set loops forever on one. I would reproduce with a two-task cycle, then switch to a topological sort that names the participating nodes. The trade-off is an O(V + E) pre-pass before any task runs, which turns a hang into a clear error.

Interview corner

CommonHow do you recognise a topological sort problem?
“I look for 'A before B' constraints, model them as a directed graph and check for cycles. A cycle means no valid order. The cost is O(V + E).”
TrickYou think a problem is DP. How do you check?
“I write the plain recursion, name the state, and count calls against distinct states. If every call is new, DP won't help.”
Experience checkDescribe a time ordering mattered in a pipeline you ran.
“Our SQL deploy scripts needed dependency order and a hand-typed list broke twice. I'd now sort the declared dependencies topologically and fail the build on a cycle.”

Memory hook

Dependencies are a building site: order the tasks, and shout if the plan loops back on itself.

If you remember only one thing:

A cue gives a hypothesis; test the one fact that would kill it.

Self-check

  1. What does graphlib raise on a cycle?

    graphlib.CycleError, with the participating nodes in its second argument.

  2. How do you test whether DP can help?

    Count recursive calls against distinct states; if close, nothing overlaps.

  3. Which operation breaks union-find?

    Deletion: it only merges.

Prove it

Write a dict of 8 or more tasks from your own project and print static_order(). Add one cycle-forming edge and print the CycleError argument. Then run the call-counting harness on a two-parameter recursion of your own and paste calls versus states. About 30 minutes.

dsa-01-05Card 5 of 6

Translate constraints into feasible complexity

MediumP1 · Must knowKnow cold8 min
constraintscomplexitybudgets

Why you care

In a coding round the stated limits decide most of the answer. At n = 100 anything works; at ten million only near-linear survives, and the interviewer expects you to read that off the numbers before writing code. On the job the same decision happens quietly: a quadratic dedupe passes on test data and dies in production. Cost models are owned by Complexity and amortization; this card uses them as a front end, without folklore like "a computer does a billion operations a second".

Explain like I'm 5

Before booking a taxi you ask how far the trip is and how much money you have. Ten streets: walk. Ten kilometres: cab. Ten thousand kilometres on a small wallet: not a taxi problem. Input size is the distance, limits are the wallet, algorithm families are the vehicles.

Core concept

The rule: turn the stated limits into a work budget, then keep only the families whose cost fits.

  1. Collect the limits: n, value range, time, memory (Clarify the input and output contract).
  2. Pick a budget in steps, not seconds. What is safe depends on language, machine and judge, so state it as an assumption. No universal operations-per-second figure exists.
  3. Cost each family at your n: pairs about n²/2; sort then scan about n log₂ n; single pass with a hash map about n, plus O(n) memory.
  4. Check memory. A CPython hash index costs many times n × 8 bytes; a value-indexed array costs by the value range.
  5. Keep the simplest family that fits.

Define work budget and family (brute force, sort-based, single pass). Never hard-code "n up to 1000 means quadratic".

Decision rule: if brute force fits and risk is low, start there and say what you would change if n grew (Know when quadratic work is acceptable). Otherwise move to sort-based, then single pass, rejecting any family whose memory exceeds the limit.

Minimal example Largest n each family allows

PythonBudget in, maximum n outruns
import math
BUDGET = 5 * 10**7  # assumed work units; you set this, it is not a law
def max_n(cost):
    lo, hi = 1, 10**9
    while lo < hi:
        mid = (lo + hi + 1) // 2
        lo, hi = (mid, hi) if cost(mid) <= BUDGET else (lo, mid - 1)
    return lo
for name, cost in [("n^2", lambda n: n * n), ("n log2 n", lambda n: n * math.log2(n)), ("n", lambda n: n)]:
    print(f"{name:9} -> n up to {max_n(cost):,}")
Output
n^2       -> n up to 7,071
n log2 n  -> n up to 2,361,678
n         -> n up to 50,000,000

The budget is an assumption. The lesson is the ratio: quadratic tops out near seven thousand, sort-based near two million.

In production A feasibility planner for time, memory and value range

Each family carries a time estimate, a memory estimate and a precondition, and the planner rejects with a reason. The domain is reconciling two ledgers of n integer transaction ids.

PythonReject families by time, memory or preconditionruns
import math

CANDIDATES = [
    # name, time(n, r), bytes(n, r), precondition(r, n)
    ("nested loop", lambda n, r: n * n / 2, lambda n, r: 0, lambda n, r: True),
    ("sort + scan", lambda n, r: n * math.log2(max(n, 2)), lambda n, r: 8 * n,
     lambda n, r: True),
    ("hash index", lambda n, r: n, lambda n, r: 100 * n, lambda n, r: True),
    ("count array", lambda n, r: n + r, lambda n, r: 8 * r, lambda n, r: r <= 10 * n),
]


def plan(n, value_range, time_budget, mem_budget):
    rows = []
    for name, t, m, pre in CANDIDATES:
        if not pre(n, value_range):
            rows.append((name, "REJECT precondition: value range too sparse"))
        elif t(n, value_range) > time_budget:
            rows.append((name, f"REJECT time {t(n, value_range):.1e} > {time_budget:.0e}"))
        elif m(n, value_range) > mem_budget:
            rows.append((name, f"REJECT memory {m(n, value_range):.1e} > {mem_budget:.0e}"))
        else:
            rows.append((name, "fits"))
    return rows


scenarios = [
    ("ledger 20k rows", 20_000, 50_000, 10**8, 10**9),
    ("ledger 2M rows", 2_000_000, 10**9, 10**8, 10**9),
    ("ledger 50M rows", 50_000_000, 10**12, 10**9, 4 * 10**9),
]
for label, n, r, tb, mb in scenarios:
    print(label)
    for name, verdict in plan(n, r, tb, mb):
        print(f"  {name:12} {verdict}")
Output
ledger 20k rows
  nested loop  REJECT time 2.0e+08 > 1e+08
  sort + scan  fits
  hash index   fits
  count array  fits
ledger 2M rows
  nested loop  REJECT time 2.0e+12 > 1e+08
  sort + scan  fits
  hash index   fits
  count array  REJECT precondition: value range too sparse
ledger 50M rows
  nested loop  REJECT time 1.2e+15 > 1e+09
  sort + scan  REJECT time 1.3e+09 > 1e+09
  hash index   REJECT memory 5.0e+09 > 4e+09
  count array  REJECT precondition: value range too sparse

The 100-byte constant and the budgets are assumptions; replace them with measurements (Locate hot paths with cProfile). At 50M rows nothing fits: change the design, not the algorithm.

Scenario A

In your world

The situation

Your reconciliation script compares yesterday's orders.csv to the Postgres orders table with a nested loop. It has run in four seconds for a year.

What actually breaks

Over a festive season the file grew from 20,000 to 2 million rows: 2,000,000² / 2 = 2 × 10^12 comparisons. The job ran 11 hours, missed the 6 am finance cut-off, and Jenkins killed it with no partial output.

What you'd do on Monday

Compute the cost at today's n before deploying, use a set, and fail loudly beyond the size you tested:

PythonSize guard on a reconciliation (needs your two id lists)
MAX_TESTED = 5_000_000
if len(file_ids) > MAX_TESTED:
    raise RuntimeError(f"{len(file_ids)} rows exceeds tested limit {MAX_TESTED}")
missing = set(file_ids) - set(db_ids)
Scenario B

Imagine you work at Google

1.5B log lines/day

The numbers

1.5 × 10^9 lines/day keyed by request id. A hash index at ~100 bytes per entry is 1.5 × 10^9 × 100 B = 150 GB. A worker has 16 GB and you keep half for the runtime, so 8 GB usable. Shards: 150 ÷ 8 = 18.75, so 19 is the floor; use 32 for headroom.

What the Scenario-A answer does here

Costing first still applies. What breaks is the family: the single-pass hash index is cheapest in time (1.5 × 10^9 steps) but needs about 19 times the usable 8 GB (9 times the 16 GB worker). Time was never the constraint.

What flips at this scale

Partition by key hash into 32 shards; each worker holds ≈47M × 100 B ≈ 4.7 GB, about 60% of the 8 GB, leaving room for the transient resize peak. The answer is the union of shard answers.

The trade-off you'd defend

I would defend sharding by key hash over an external sort, trading a shuffle step for one in-memory pass per shard.

Illustrative volumes and per-entry memory; not Google-published figures.

Gotchas

Quoting an operations-per-second constant

Symptom

You declare "a billion operations a second, so n² is fine to 30,000", and the job times out.

Cause

Python executes far fewer simple steps per second than compiled code, varying by machine.

Fix

State the budget as an assumption and size it from a measurement (Locate hot paths with cProfile).

Checking time but not memory

Symptom

Fast on test data, then MemoryError or an OOM kill on real input.

Cause

A dict or set of n entries uses many times n × 8 bytes.

Fix

Multiply bytes per entry by n before choosing a hash-based family; shard if it does not fit.

Tricky questions

n is 10^5. Is O(n²) really out?
Most people say

Yes, anything quadratic is dead at 10^5.

Actually

10^5 squared is 10^10 steps, too many for most Python limits, but the answer is "compute it against the stated budget", not a memorised cut-off.

Scenario question

You're handed a nightly job that joins two id lists with nested loops and "works fine". The lists will grow tenfold next quarter. What do you do before it breaks?

Model answer

I would compute the cost at ten times today's n: a hundredfold more work. I'd write the set-based version, assert both outputs match on last month's data, and keep the old one as a test reference. The trade-off is memory for the set, which I'd estimate against the container, plus a size guard so growth fails loudly.

Interview corner

CommonThe constraints say n up to 10^5. What does that tell you?
“I'd cost each candidate against that n. Quadratic is about 10^10 steps, too many for a typical limit, so I'd aim for n log n or linear, and I'd call the budget an assumption.”
TrickIs the fastest algorithm always the right choice?
“No, I'd check memory and preconditions too. A hash pass may need more memory than I have. I'd pick the cheapest family that satisfies every limit.”
DesignThe data is 150 GB and a worker has 16 GB. What changes?
“Memory is the constraint, not time. I'd partition by key hash so each shard fits and accept a shuffle step as the trade-off.”

Memory hook

Ask the distance and check the wallet before you choose the vehicle.

If you remember only one thing:

Let the limits choose the family, and show the arithmetic.

Self-check

  1. Why not quote a universal operations-per-second number?

    It varies by language, machine and operation, so it is an assumption to state.

  2. Name a precondition for a value-indexed counting array.

    The value range must be comparable to n.

  3. When is a quadratic baseline legitimate?

    When n fits the stated budget, or the output itself is quadratic.

Prove it

Run the planner on three scenarios from jobs you have run, replacing the 100-byte constant with a measured value (a 1M-element set under tracemalloc, divided). Paste bytes per entry and the planner output. About 40 minutes.

dsa-01-06Card 6 of 6

State and challenge the invariant

MediumP2 · Very likelyKnow cold8 min
invariantscorrectnesspseudocode

Why you care

Recognising a pattern is a guess; the invariant is the proof. An invariant is a sentence about your state that is true before every iteration, and it explains why discarding is safe, why you progress and why the loop ends. Interviewers ask "how do you know this works?" because candidates who cannot answer ship off-by-one errors and infinite loops. On the job a loop that "usually" terminates is a production incident.

Explain like I'm 5

A security guard keeps one rule: everyone left of the line has been checked, everyone right of it has not. Each step moves one person across and the rule still holds. When nobody remains on the right, everyone is cleared. The rule is the invariant, a crossing is progress, the empty right side is termination. If a step moves nobody, the guard stands there forever.

Core concept

The rule: before coding, say four things.

  1. State meaning. What each variable represents ("lo is the first index that might hold the answer").
  2. Safe discard. Why dropping those items is correct ("everything left of lo is smaller than the target").
  3. Progress. What strictly shrinks or advances ("hi - lo decreases").
  4. Termination. What invariant plus exit condition imply ("lo == hi, so the boundary is lo").

Define invariant (true before and after every iteration) and progress measure (a quantity that strictly moves toward a bound). Sketch generic pseudocode first:

Text
state := values that make the invariant true
while not done:
    examine one candidate
    discard candidates (justified by the invariant)
    advance state so the progress measure changes
return the answer implied by invariant + exit condition

Challenge it with one counter-condition (unsorted data, negatives, duplicates) and one alternative, such as a hash map.

Decision rule: if you cannot state the safe-discard sentence you have a template, not a pattern (Sequence signals and competing patterns). Otherwise code it and test empty, one element, all equal.

Minimal example Check the invariant on every iteration

PythonBoundary search with an asserted invariantruns
a = [1, 4, 6, 9, 12]
t = 9
lo, hi = 0, len(a)            # invariant: a[:lo] < t <= a[hi:]
while lo < hi:
    mid = (lo + hi) // 2
    if a[mid] < t:
        lo = mid + 1
    else:
        hi = mid
    assert all(x < t for x in a[:lo]) and all(x >= t for x in a[hi:])
    print(lo, hi, "width", hi - lo)
print("first index >= t:", lo)
Output
3 5 width 2
3 4 width 1
3 3 width 0
first index >= t: 3

The shrinking width is the progress measure; the assertion is the invariant. At exit lo == hi, so everything before is smaller and everything from there is at least t.

In production A harness that checks invariant and progress

The update step is a parameter so you can substitute a broken one. In debug mode the harness asserts the invariant and that the width shrank. The domain is a boundary search over sorted settlement timestamps.

PythonCatching a stuck loop and an unsorted preconditionruns
def lower_bound(a, t, step_lo, check=True):
    lo, hi = 0, len(a)            # claim: a[:lo] < t <= a[hi:]
    while lo < hi:
        width = hi - lo
        mid = (lo + hi) // 2
        if a[mid] < t:
            lo = step_lo(mid)
        else:
            hi = mid
        if check:
            if not (all(x < t for x in a[:lo]) and all(x >= t for x in a[hi:])):
                raise AssertionError(f"invariant broken: lo={lo} hi={hi}")
            if hi - lo >= width:
                raise RuntimeError(f"no progress: width stuck at {width}")
    return lo


good = lambda mid: mid + 1
stuck = lambda mid: mid          # keeps mid as candidate: looks safe, never shrinks
cases = [
    ("sorted, mid+1", [1, 4, 6, 9, 12], good),
    ("sorted, lo=mid", [1, 4, 6, 9, 12], stuck),
    ("unsorted, mid+1", [9, 1, 12, 4, 6], good),
]
for label, data, step in cases:
    try:
        print(label, "->", lower_bound(data, 9, step))
    except (AssertionError, RuntimeError) as exc:
        print(label, "->", f"{type(exc).__name__}: {exc}")
Output
sorted, mid+1 -> 3
sorted, lo=mid -> RuntimeError: no progress: width stuck at 1
unsorted, mid+1 -> AssertionError: invariant broken: lo=0 hi=2

lo = mid keeps the invariant true but never terminates; the progress check catches it. Unsorted input violates the invariant itself. The all(...) checks cost O(n) per step, so this is a test-time harness.

See it happen The invariant region shrinks every step

sorted values, t = 9146912state<<<>=>=
  1. Start: lo = 0 and hi = 5, so nothing is cleared yet.
  2. 6 < 9, so lo = 3 and indices 0 to 2 are cleared as smaller.
  3. 12 >= 9, so hi = 4 and index 4 is cleared as large enough.
  4. 9 >= 9, so hi = 3 and the unknown region is empty: the answer is index 3.
Notice: the unknown region shrinks on every step, and that is the progress measure.
Scenario A

In your world

The situation

Your Jenkins job compacts a sorted events.csv with two indexes, one reading and one writing. A teammate "simplified" the loop last sprint.

What actually breaks

The new loop advances the read index only on a match. On a file ending in equal timestamps it spins at 100 percent CPU. The step has no timeout, so it ran six hours until someone killed the agent, with nothing logged.

What you'd do on Monday

Write the four sentences as a comment above the loop and add a cheap progress guard inside it:

PythonCheap progress guard in a real loop (illustrative fragment)
prev = (read, write)
...
assert (read, write) != prev, f"no progress at read={read}, write={write}"
Scenario B

Imagine you work at Spotify

960M play events merged nightly

The numbers

24 hourly files × 40M events = 960M events. A full all(...) invariant check costs O(n) per step: about (960M)² / 2 ≈ 4.6 × 10^17 comparisons, impossible. An adjacent check ("each key ≥ the previous") costs 960M in total.

What the Scenario-A answer does here

A progress guard still works at any scale. What breaks is the full invariant assertion, which is a debugging tool.

What flips at this scale

Checking splits into two tiers. Full assertions run on thousands of small random inputs in CI. Production keeps O(1) sentinels: monotone output keys, a progress counter, rows in equal rows out.

The trade-off you'd defend

I would defend small-input exhaustive checks plus O(1) production sentinels, trading the chance of catching a large-input-only bug for runs that finish.

Illustrative event counts; not Spotify-published figures.

Gotchas

A loop that keeps a candidate but never shrinks

Symptom

CPU stays at 100 percent and the job never finishes (lo = mid, width stuck at 1).

Cause

The update keeps mid after rejecting it.

Fix

Exclude it (mid + 1) and assert in debug builds that the measure decreased.

Invariant true on tests, false on the contract

Symptom

Tests pass on sorted data; production returns a wrong index intermittently.

Cause

The discard rule needs sortedness, but the feed is sorted only per partition.

Fix

Put it in the contract (Clarify the input and output contract) and assert adjacent-key order at the boundary.

Tricky questions

The code passed the example, so the invariant holds?
Most people say

A passing example is evidence the loop is correct.

Actually

An example samples one path. The invariant covers all paths: true at the start, preserved by every step, implying the answer at exit. Say those three things, then test the edges.

Scenario question

You're handed a loop two engineers disagree about. One says it passes all tests; the other says it sometimes never terminates. How do you settle it?

Model answer

I would ask each to state the invariant and the progress measure, and write them from the code if neither can. Then I hunt for an input where the measure does not change, usually a duplicate or all-equal case. The trade-off is that debug assertions cost time per step, so I keep them in tests and leave O(1) sentinels in production.

Interview corner

CommonHow do you convince me your algorithm is correct?
“I state the invariant: what holds before every iteration, why the discard is safe, and what makes the loop progress. Then I show the exit condition plus the invariant gives the answer.”
TrickYour binary search loops forever on some input. Where do you look?
“I look for an update that keeps a rejected candidate, like lo = mid instead of mid + 1. The width never shrinks, and I'd confirm with an assertion on it.”
Experience checkWhen did a loop of yours misbehave in production?
“A compaction loop I maintained spun forever on equal timestamps. I now write the progress measure in a comment and assert it changed.”

Memory hook

The guard's rule: everyone left of the line is cleared, and every step moves someone across.

If you remember only one thing:

If you cannot say what shrinks and why discarding is safe, you do not have the pattern yet.

Self-check

  1. What four things do you state about a loop before coding?

    State meaning, safe discard, progress, and termination.

  2. Why does lo = mid loop forever in the example?

    It never excludes the rejected mid, so a width of 1 stays 1.

  3. Why keep full invariant assertions out of production?

    They cost O(n) per step; keep O(1) sentinels there.

Prove it

Take a loop from your ETL code. Write its four sentences as a comment, add a progress assertion in a debug copy, and run it on empty, one-element and all-equal inputs. Paste the comment and outputs. About 30 minutes.