Shelf · DSA Patterns · Chapter 8

Chapter 8: Interview execution protocol

Knowing a pattern is half of a coding round. This chapter covers the other half, which is how you spend the time, explain your choices, check your own work, recover from a blank, and avoid the Python traps that cost points.

Difficulty
Priority
dsa-08-01Card 1 of 6

A minute-by-minute coding-round protocol

EasyP5 · SkippableKnow it exists8 min
interviewtime-budgetprotocolclarify

Why you care

Most failed coding rounds fail on allocation, not knowledge: twenty-five minutes on an unchecked approach, no time to test, and a bug found at minute 44 by the interviewer instead of by you. On the job it is the transform written before anyone agreed what the output rows look like. Interviewers watch your order of work because it predicts how you behave on a ticket. This card gives a rehearsal schedule so the order becomes habit. It is a practice device, not a rule any company publishes.

Explain like I'm 5

A train has six stations and a fixed arrival time. A schedule does not make it faster. It tells you at each platform whether you are late, so you can drop something while there is still time.

Core concept

The protocol is six phases in a fixed order, sized for a 45-minute round:

  1. Clarify (0-5): inputs, outputs, sizes, duplicates, empty input, failure behaviour.
  2. Baseline and cost (5-10): a correct slow approach with its time and space.
  3. Approach (10-15): the invariant or structure that beats the baseline, with its cost.
  4. Implement (15-30): write it once, cleanly.
  5. Test (30-40): hand dry-run, then edge cases whose expected results you wrote first.
  6. Wrap-up (40-45): restate complexity and name one improvement.
  • Gates, not clocks. A phase ends when its output exists (a written contract, a stated cost, a chosen approach). Minutes only tell you when to cut.
  • Hard cut at minute 15. No approach yet means you code the baseline.
  • Scale it. Keep the ratio 5:5:5:15:10:5 in whole minutes; below 20 minutes the plan refuses to split. The hard cut stays at a third of the round (15 of 45, 21 of 60). Ask the recruiter for the duration, language and whether code runs.

Do not defend it against the interviewer: if they ask for a different test, they have overridden your plan.

Minimal example The 45 minutes on one screen

PythonPhase table and its totalruns
phases = [("clarify", 5), ("baseline", 5), ("approach", 5), ("implement", 15), ("test", 10), ("wrap-up", 5)]
t = 0
for name, mins in phases:
    print(f"{t:>2}-{t + mins:<2} {name}")
    t += mins
print("total", t)
Output
 0-5  clarify
 5-10 baseline
10-15 approach
15-30 implement
30-40 test
40-45 wrap-up
total 45

In production Rescale the plan to the real duration

Most rounds are not 45 minutes. This keeps the ratio with integer arithmetic, hands leftover minutes to the largest fractional parts, and refuses a round too short to give every phase a minute.

PythonLargest-remainder split of any round lengthruns
WEIGHTS = {"clarify": 5, "baseline": 5, "approach": 5, "implement": 15, "test": 10, "wrap-up": 5}
MIN_TOTAL = 20


def plan(total):
    """Split `total` whole minutes in the 5/5/5/15/10/5 ratio, largest remainder first."""
    if total < MIN_TOTAL:
        raise ValueError(f"{total} min is below the {MIN_TOTAL}-minute minimum")
    base = sum(WEIGHTS.values())
    quota = {k: total * w for k, w in WEIGHTS.items()}      # integer arithmetic only
    mins = {k: q // base for k, q in quota.items()}
    spare = total - sum(mins.values())
    by_rem = sorted(WEIGHTS, key=lambda k: (-(quota[k] % base), list(WEIGHTS).index(k)))
    for k in by_rem[:spare]:
        mins[k] += 1
    return mins


def clock(mins):
    t, rows = 0, []
    for name, m in mins.items():
        rows.append(f"{t}-{t + m} {name}")
        t += m
    return " | ".join(rows)


for total in (45, 60, 30, 35, 20, 12, 0):
    try:
        p = plan(total)
        assert sum(p.values()) == total
        print(total, "->", clock(p))
    except ValueError as e:
        print(f"ValueError: {e}")
Output
45 -> 0-5 clarify | 5-10 baseline | 10-15 approach | 15-30 implement | 30-40 test | 40-45 wrap-up
60 -> 0-7 clarify | 7-14 baseline | 14-21 approach | 21-41 implement | 41-54 test | 54-60 wrap-up
30 -> 0-4 clarify | 4-7 baseline | 7-10 approach | 10-20 implement | 20-27 test | 27-30 wrap-up
35 -> 0-4 clarify | 4-8 baseline | 8-12 approach | 12-23 implement | 23-31 test | 31-35 wrap-up
20 -> 0-2 clarify | 2-4 baseline | 4-6 approach | 6-13 implement | 13-18 test | 18-20 wrap-up
ValueError: 12 min is below the 20-minute minimum
ValueError: 0 min is below the 20-minute minimum

Every row sums to its total (the assert proves it). The 12-minute and 0-minute rounds fail loudly instead of printing a one-minute test.

See it happen Where the 45 minutes go

minutes0-55-1010-1515-2020-2525-3030-3535-4040-45phaseclarifycodecodecodecodecodecodecodetest
  1. The first five minutes produce no code, only a written contract: inputs, outputs, sizes and edge cases.
  2. Minutes 5-10 produce a correct slow approach and its cost, so a valid answer exists before any optimising.
  3. Minutes 10-15 pick the invariant or structure that beats the baseline, or fall back to the baseline if none appears.
  4. Fifteen minutes of implementation is a single clean pass; stopping to redesign here eats the test window.
  5. Ten minutes of testing is a hand dry-run plus edge cases you picked before running them.
  6. The last five minutes restate cost and name one improvement; the interviewer remembers the ending.
  7. The naive timeline: almost no clarifying, code until minute 40, and the first test in the last five minutes leaves no room to fix anything.
Notice: the test window sits before the wrap-up and is the first thing the naive timeline loses.
Scenario A

In your world

The situation

You practise in evening blocks with no clock, code the first idea that appears and run it on the sample input only.

What actually breaks

In a timed mock you read for one minute, code for 28 and run the sample at minute 31. It passes. The interviewer then feeds an empty list and a list of equal values, and both fail. Your log says "solved"; the mock says "no hire".

What you'd do on Monday

Set five alarms at 5, 10, 15, 30 and 40 minutes and at each write one line saying which gate output exists.

PythonGate log for one practice attempt (written by hand, not executed)
gates = {
    5:  "contract written: input, output, sizes, empty and duplicate behaviour",
    10: "baseline stated with time and space",
    15: "approach chosen, or baseline chosen as the plan",
    30: "code complete",
    40: "three edge cases run, expected values written before running",
}
Scenario B

Imagine you work at Zoho

600 candidates per hiring drive

The numbers

Illustrative: 600 candidates × 45 min = 27,000 min = 450 interviewer-hours. With 15 interviewers giving 6 interview-hours a day, capacity is 90 hours a day, so 450 ÷ 90 = 5 days. If rounds drift to 55 minutes: 600 × 55 = 33,000 min = 550 hours, 550 ÷ 90 ≈ 6.1, so 7 days.

What the Scenario-A answer does here

A timer on your screen works for one person. Ten extra minutes per candidate adds 100 interviewer-hours.

What flips at this scale

The schedule becomes a shared contract: the same six gates and a hard stop at minute 45, so transcripts are comparable.

The trade-off you'd defend

I would defend a fixed gated format over free-form conversation at this size, trading flexibility for comparable scores and a predictable five-day plan.

Illustrative capacity arithmetic; not Zoho-published numbers or its actual process.

Gotchas

Coding before the output contract is agreed

Symptom

The code prints a clean answer and the interviewer says it is not what they asked.

Cause

The prompt had two valid readings and you silently took one. The 2 largest of [5, 5, 3] differ depending on whether duplicates count.

Fix

Spend the first five minutes on the contract and say the choice aloud.

PythonSame prompt, two contractsruns
import heapq
xs = [5, 5, 3]
print(heapq.nlargest(2, xs), heapq.nlargest(2, set(xs)))
Output
[5, 5] [5, 3]

No fallback stated

Symptom

At minute 24 the clever approach has an open case and no code exists.

Cause

No baseline was named at minute 10.

Fix

At minute 15, without a clear approach, code the baseline.

Tricky questions

Everyone says optimise first, so is the baseline a waste?
Most people say

Skip the slow version and state only the optimal one.

Actually

The baseline takes two minutes and gives you a fallback, a number to beat and an oracle for testing the fast version.

Scenario question

You're handed a 60-minute round and a prompt you only half understand at minute 8.

Model answer

I would rescale first: about 7, 7, 7, 20, 13 and 6 minutes, cutting at minute 21, a third of 60. At minute 8 I ask the one question that unblocks me and state a baseline. The trade-off is less breadth of ideas, but 13 minutes stay reserved for tests.

Interview corner

CommonHow do you structure a coding interview?
“I clarify the contract first, state a brute-force answer with its cost, then pick the approach that beats it. I code once, test with cases chosen in advance, and close by restating complexity. I'd skip an optimisation before I'd skip testing.”
TrickYou are 15 minutes in with no approach. What now?
“I'd implement the baseline I already stated and say so. It gives me a correct answer to test with, and I can keep looking for the improvement meanwhile.”
Experience checkWhen did you last build before the requirements were clear?
“I wrote a transform before finance confirmed whether cancelled orders count, and we reloaded a month. Now the contract comes first, in a round too.”

Memory hook

A timetable does not make the train faster, it tells you at each station what to drop.

If you remember only one thing:

Protect the test window: cut the approach search at minute 15 and code the baseline.

Self-check

  1. How long is each phase in the 45-minute plan?

    Clarify 5, baseline 5, approach 5, implement 15, test 10, wrap-up 5.

  2. What do you do at minute 15 without an approach?

    Implement the baseline and say so.

  3. What does an interviewer redirect do to your plan?

    It overrides it; follow them, then return to the gate you skipped.

Prove it

Run one easy problem with alarms at 5, 10, 15, 30 and 40 minutes. Paste the filled gate log and the minute of your first edge case. Repeat three days later; the second minute should not be later.

dsa-08-02Card 2 of 6

Think aloud at decision points

EasyP2 · Very likelyTalk about it7 min
communicationinterviewassumptionstrade-offs

Why you care

An interviewer cannot grade thinking they cannot hear. A silent candidate with correct code scores below one who explains two options and picks one, because the explanation is the evidence of judgement. On the job a note saying "dict, because the key space is bounded; sorting rejected, we only need lookups" is reviewed in two minutes. A bare pull request takes a week of questions. Interviewers ask for thinking aloud and stop you when it turns into narration. This card is about where to speak, not how much.

Explain like I'm 5

Imagine a taxi driver on a new route. A good one says "I'll take the flyover because the main road has roadworks" at each fork. A bad one is either silent or reads out every turn of the steering wheel. You want the driver who speaks at the forks.

Core concept

A decision point is any moment with more than one reasonable path. Speak there; stay quiet while typing the path you already chose.

The five-part checkpoint, about 30-45 words:

  • Assumption: what you take as given.
  • Options: two candidates, named by structure.
  • Idea: what stays true that makes the choice work.
  • Cost: time and space in the stated sizes.
  • Rejection: one reason the other option loses here.

Speak after the contract, before choosing a structure, before changing plan mid-code, and when you find a bug (what, and how you will check). Do not narrate syntax or fill silence; "give me twenty seconds to compare two options" is fine. The rejection is the part most people drop and interviewers value most. If unsure of a cost, say "I believe this is O(n log n), I'll verify when I write the loop".

Design-style rounds have a different conversation shape: that is Design interview method: the eight-step flow. Here the scope is one function and its data structure.

Minimal example Words per round at two speaking styles

PythonNarrating everything versus checkpointsruns
speech_wpm = 130
round_minutes = 45
every_step = round_minutes * speech_wpm
checkpoints, words_each = 6, 40
print(every_step, checkpoints * words_each)
print(round(checkpoints * words_each / speech_wpm, 1), "minutes of talking")
Output
5850 240
1.8 minutes of talking

In production A checkpoint that refuses to be incomplete

A checkpoint must carry the idea, a cost and a rejection, and stay inside 50 words, one breath. Fields left at None fail loudly.

PythonCheckpoint renderer with completeness checkruns
from dataclasses import dataclass


@dataclass
class Checkpoint:
    assumption: str
    chosen: str
    idea: str | None = None
    rejected: str | None = None
    why_rejected: str | None = None
    cost: str | None = None

    def render(self, max_words=50):
        need = ("idea", "rejected", "why_rejected", "cost")
        missing = [f for f in need if not getattr(self, f)]
        if missing:
            raise ValueError("checkpoint incomplete: " + ", ".join(missing))
        text = (f"Assuming {self.assumption}, I'll use {self.chosen}: {self.idea}. "
                f"Cost {self.cost}. Not {self.rejected}, because {self.why_rejected}.")
        words = len(text.split())
        if words > max_words:
            raise ValueError(f"{words} words, over {max_words}")
        return text


good = Checkpoint("order ids repeat across files", "a set of seen ids",
                  "a repeat is an id already in the set", "sorting then scanning",
                  "it costs O(n log n) and I need no order", "O(n) time and space")
no_cost = Checkpoint("ids repeat", "a set", "seen-before test", "sorting", "no order needed")
empty = Checkpoint("input may be empty", "a set")
wordy = Checkpoint("the input has many properties " * 14, "a set", "seen-before test",
                   "sorting", "no order", "O(n)")
for cp in (good, no_cost, empty, wordy):
    try:
        print(cp.render())
    except ValueError as e:
        print(f"ValueError: {e}")
Output
Assuming order ids repeat across files, I'll use a set of seen ids: a repeat is an id already in the set. Cost O(n) time and space. Not sorting then scanning, because it costs O(n log n) and I need no order.
ValueError: checkpoint incomplete: cost
ValueError: checkpoint incomplete: idea, rejected, why_rejected, cost
ValueError: 85 words, over 50

The fourth case is a runaway checkpoint of 85 words against the 50-word limit; the good one is about 40.

Scenario A

In your world

The situation

At TCS you explain code in screen-shares where everyone knows the context, so "this part does the grouping" is enough.

What actually breaks

In a round you type for ten minutes in silence, then say "okay, done". The feedback reads "no visible reasoning": nobody heard why a dictionary, what else you considered, or what you assumed about duplicates. A correct solution reads as luck.

What you'd do on Monday

Rehearse checkpoints at the four decision points. Record one practice problem on your phone and count them: four to six in 45 minutes, each 20 seconds or less.

PythonSelf-review of a recording (counted by hand)
checkpoints_heard = 5          # target 4-6
longest_seconds = 25           # target <= 20
missing_rejection = 2          # target 0
Scenario B

Imagine you work at Salesforce

40 candidates per week through one panel

The numbers

Illustrative: an interviewer types notes at about 20 words per minute while reading code, so 45 minutes yields 45 × 20 = 900 words. Narrating every step at 130 words per minute is 5,850 words, 6.5 times what they can record. Six 40-word checkpoints are 240 words, which fits.

What the Scenario-A answer does here

Rehearsing checkpoints still works for you. At scale the problem is the debrief: 40 candidates × 3 interviewers = 120 notes a week, and "talked a lot" carries no reasoning to compare.

What flips at this scale

Panels score against a fixed shape: assumption, options, cost, rejection. A candidate whose checkpoints match it produces notes that map straight onto the form.

The trade-off you'd defend

I would defend short structured checkpoints over continuous commentary, trading some natural flow for notes a panel can score.

Illustrative; typing speed, volumes and form shape are assumptions, not Salesforce-published figures.

Gotchas

Narrating keystrokes

Symptom

The interviewer says "you can just write it" with 12 minutes gone and ten lines on screen.

Cause

Thinking aloud treated as a transcript of everything you type.

Fix

Speak at decision points only.

A choice announced with no rejection

Symptom

Feedback says "chose a hash map, did not discuss alternatives".

Cause

You gave the answer, not the comparison.

Fix

End every choice with "I'm not using X because Y".

Tricky questions

Should I explain every line so the interviewer follows?
Most people say

Yes, more explanation is always safer.

Actually

The interviewer reads code faster than you speak. Explain the decisions the code cannot show.

Scenario question

You're handed a task to de-duplicate a stream of events, and you can think of a set-based and a sort-based method.

Model answer

I would state the assumption first: ids are hashable and the stream fits in memory. Then both options: the set pass at O(n) time and space, the sort pass at O(n log n) with O(1) extra space if I may reorder. I pick the set because the contract keeps arrival order, which sorting would destroy. The trade-off is memory; if the stream outgrew RAM I would switch to partitioned hashing.

Interview corner

CommonHow much should I talk while coding?
“I speak at decision points: assumptions, a choice between structures, a change of plan. While I type a path I already chose, I stay quiet or give a one-line label.”
TrickThe interviewer says nothing for five minutes. What do you do?
“I treat it as neutral. I keep to my checkpoints and, if unsure about direction, ask one specific question such as whether duplicates should count.”
Experience checkDescribe a time you explained a technical trade-off.
“I told finance why I kept raw files in S3 and loaded a cleaned table: storage against being able to replay a month. Putting the rejected option in the sentence ended the debate.”

Memory hook

Speak at the forks in the road, not at every turn of the steering wheel.

If you remember only one thing:

Every choice you announce needs one reason the alternative lost.

Self-check

  1. What are the five parts of a checkpoint?

    Assumption, options, idea, cost, rejection.

  2. When do you not speak?

    While typing a path you already chose.

  3. What do you do with an uncertain cost?

    Say "I believe it is...", then verify against the final code aloud.

Prove it

Record yourself on one practice problem for 20 minutes. Transcribe only the checkpoints into a file and paste it with the count and a flag on each one missing a rejection. Target on a second recording three days later: at least four checkpoints, none missing a rejection.

dsa-08-03Card 3 of 6

Dry-run on paper with a state ledger

MediumP2 · Very likelyKnow cold7 min
dry-runinvarianttracingledger

Why you care

Reading your own code and saying "that looks right" finds almost nothing, because the eye completes what it expects. On the job it is the review that reads a diff and misses the batch that overshoots its size limit. Interviewers ask you to trace because it shows whether you can execute code precisely. This card is a tracing method that catches bugs instead of confirming hopes.

Explain like I'm 5

Counting cash at the end of a shift, you do not glance at the drawer and say it seems fine. You write the opening float, each note that went in, and the running total. When the total disagrees with the till slip, you know which line to look at.

Core concept

A state ledger is a small table written by hand: one row per transition, one column per piece of state that can change.

  • Columns: the input item, each variable, the structure contents, the output so far, pending work (what the loop has not reached), and an invariant column.
  • Write the invariant, one sentence true after every row, before the first row. If you cannot, you do not yet understand the algorithm.
  • Fill each row by executing the code literally. Evaluate each condition with the real numbers and write true or false.
  • Check the invariant after every row. The first row where it fails is the bug.

Choose the input on purpose: four or five items, with the awkward cases from the task (empty, single, repeated values). Write the expected boundary result before you trace, so you cannot adjust it to fit.

Skip it for one-liners; if a trace would take fifty rows, shrink the input but keep its shape. A ledger covers only the input you chose, so pair it with Test your own implementation.

Minimal example The first false row is the bug

PythonLedger of a buggy batch splitterruns
sizes, cap = [5, 4, 3, 2], 8
used, rows = 0, []
for s in sizes:
    if used > cap:            # bug: should test used + s > cap
        used = 0
    used += s
    rows.append((s, used, used <= cap))
for r in rows:
    print(r)
Output
(5, 5, True)
(4, 9, False)
(3, 3, True)
(2, 5, True)

The invariant is used <= cap. Row two breaks it: 5 + 4 = 9 against 8. The test looked at the old total, so reading the code never showed it.

In production Correct splitter with a ledger and invariant check

The corrected splitter records the same ledger as a trace. first_violation is the mechanical form of "check after every row".

PythonBatch splitter, traced, on awkward inputsruns
def split(sizes, cap, trace=None):
    """Group item sizes into batches whose total never exceeds cap."""
    out, cur, used = [], [], 0
    for i, s in enumerate(sizes):
        if s > cap:
            raise ValueError(f"item {i} has size {s}, above cap {cap}")
        if used + s > cap:
            out.append(cur)
            cur, used = [], 0
        cur.append(s)
        used += s
        if trace is not None:
            trace.append((i, s, used, len(out)))
    if cur:
        out.append(cur)
    return out


def first_violation(trace, cap):
    """Ledger check: the first row where the stated invariant used <= cap fails."""
    return next((row for row in trace if row[2] > cap), None)


cases = {"empty": ([], 8), "single": ([8], 8), "zeros": ([0, 0, 0], 8),
         "equal": ([4, 4, 4, 4], 8), "mixed": ([5, 4, 3, 2], 8), "oversize": ([3, 9], 8)}
for name, (sizes, cap) in cases.items():
    trace = []
    try:
        batches = split(sizes, cap, trace)
        ok = first_violation(trace, cap) is None and sum(map(sum, batches)) == sum(sizes)
        print(f"{name:<8} {batches} ledger_ok={ok}")
    except ValueError as e:
        print(f"{name:<8} ValueError: {e}")
Output
empty    [] ledger_ok=True
single   [[8]] ledger_ok=True
zeros    [[0, 0, 0]] ledger_ok=True
equal    [[4, 4], [4, 4]] ledger_ok=True
mixed    [[5], [4, 3], [2]] ledger_ok=True
oversize ValueError: item 1 has size 9, above cap 8

The oversize case is a contract decision: raise, or give the item its own batch. Ask.

See it happen The ledger grows one row per transition

item size (cap 8)5432used after the item5935batches closed so far0011
  1. Before any row, write the invariant: used never exceeds 8 after any transition.
  2. Item 5 fits an empty batch, so used becomes 5 and no batch is closed.
  3. Item 4 would make 9, over the cap, so the batch [5] closes and used restarts at 4.
  4. Item 3 fits beside the 4, so used becomes 7 and the closed count stays 1.
  5. Item 2 would make 9, so [4, 3] closes and used restarts at 2; the final batch [2] is flushed after the loop.
  6. The buggy version tested the old total, let used reach 9 on the second item, and the invariant column went false at once.
Notice: the failing row is visible the moment the invariant is checked, long before the end.
Scenario A

In your world

The situation

You review ETL changes by reading the diff and running the job once on yesterday's file, which has thousands of ordinary rows.

What actually breaks

A batching change passes review and the daily run. Three weeks later a single 9 MB row arrives against an 8 MB limit and the load fails at 02:10. A four-row ledger before merging would have raised the open question: what happens to one oversized item.

What you'd do on Monday

Before merging or answering, write the invariant in one sentence and trace a four-item input by hand, including the oversized item. Paste the rows into the pull request.

PythonLedger template to paste into a review (columns, not data)
# step | item | state vars after | structure contents | pending | invariant holds?
Scenario B

Imagine you work at Twilio

50M messages per day

The numbers

Illustrative: 50,000,000 messages ÷ 86,400 s ≈ 579 per second. Three transitions per message at ~120 bytes each is 50,000,000 × 3 × 120 B = 18 GB of trace per day. Sampling 1 in 1,000 leaves 18 GB ÷ 1,000 = 18 MB.

What the Scenario-A answer does here

Tracing by hand works on four items. You cannot hand-trace 50 million, and logging every transition costs 18 GB a day of storage and search.

What flips at this scale

Keep the ledger's shape but let the code fill it: one row per sampled message id with before-state, transition, after-state and an invariant check. Failures always emit a row; successes emit 1 in 1,000.

The trade-off you'd defend

I would defend sampled structured trace rows over full logging, trading replay of any single message for a thousandth of the storage.

Illustrative volumes and byte sizes; not Twilio-published figures.

Gotchas

Tracing the intention, not the code

Symptom

The ledger passes and the code fails on the same input.

Cause

You filled each row from what the line was meant to do, so the buggy used > cap read like used + s > cap.

Fix

Evaluate each condition with literal numbers and write true or false in a column.

Forgetting the pending item

Symptom

The last batch is missing and the output total is below the input total.

Cause

The loop ended with items still held.

Fix

Keep a pending-work column and compare sums.

Tricky questions

My dry-run matched my expected output, so the code is correct?
Most people say

Yes, the trace agrees with the expectation.

Actually

It is correct for that input only, and only if the expectation was written before the trace. Add an empty, a single and a repeated-value input.

Scenario question

You're handed your finished solution at minute 30 and told to show it works without running it.

Model answer

I would state the invariant, then trace a four-item input that hits each branch, with columns for the invariant and pending work, plus the empty and single cases. Expected results come first. The trade-off is about ten minutes by hand, but it finds the first failing row, not just a symptom.

Interview corner

CommonHow do you check your code before the interviewer does?
“I write the invariant, then trace a small input by hand, checking it after each step. I include an empty case and a repeated-value case and write expected results first.”
TrickYour trace matches, but the interviewer says it fails. Why?
“I probably traced what I meant, not what I wrote. I'd re-evaluate each condition with literal numbers and check the case I did not choose, likely a boundary or a repeat.”
Experience checkHow do you review a change to batching logic?
“I ask for the invariant and hand-trace four rows, including one oversized row. That has found size-limit bugs a green build missed.”

Memory hook

Count the till one note at a time, and stop at the first note that disagrees with the slip.

If you remember only one thing:

State the invariant first and check it after every row, not at the end.

Self-check

  1. What goes in a state ledger?

    One row per transition: input, variables, structure contents, output, pending work and an invariant check.

  2. When do you write the expected result?

    Before tracing, so it cannot be adjusted to fit.

  3. What does the first false row tell you?

    The transition that broke the invariant, so the line that produced it is the suspect.

Prove it

Write a function with a loop and two branches. State its invariant, hand-trace four items on paper and paste the ledger. Plant an off-by-one bug and mark the first false row.

dsa-08-04Card 4 of 6

Test your own implementation

MediumP1 · Must knowKnow cold7 min
testingedge-casesbaselinealiasing

Why you care

The most common reason for a "nearly there" rating is stopping after the sample input, which the interviewer picked to be friendly. Bugs sit at the edges: empty, one element, equal values, a mutated argument. In ETL work that is the file with no rows, or the code that sorts a list the caller still needs. A bug you find is a good signal; the same bug found by them is not. General strategy lives in Testing strategy: unit, integration, contract and e2e and pytest mechanics in Python test mechanics: pytest fixtures, assertions and lifecycle. This card covers what to test in a DSA function in ten minutes.

Explain like I'm 5

Before opening a bridge, engineers drive an empty truck, a full truck and two trucks at once. Nobody certifies a bridge because one car crossed it.

Core concept

Pick test inputs by category, then write the expected result before running anything:

  • Empty and singleton: loops that assume two elements fail here.
  • Extremes: smallest and largest allowed values, negatives, zero.
  • Duplicates: all equal, and one duplicate among distinct values.
  • Order: ascending, descending, reversed.
  • Shape: disconnected graphs, a cycle, a self-loop, a single node, a chain.
  • Mutation and aliasing: call twice with the same list; is the input unchanged?
  • Invalid preconditions: negative k, unsorted input to a function that needs sorted. Decide whether to raise or document, and say so.

Then add a baseline comparison: a slow, obviously correct version run against yours on every small input. Exhaustive small inputs, shortest first, find the smallest failing case, which is the easiest to debug. Seeded random inputs extend it to larger shapes.

Rules: expected value from the contract, never from the output; one change per run; keep the failing case as a permanent test. A correct quadratic function passes every small test; measure doubling sizes (Recover when stuck without bluffing).

Minimal example A helper that quietly mutates its input

PythonThe caller's list changedruns
def top2(xs):
    xs.sort(reverse=True)
    return xs[:2]

data = [3, 9, 4]
print(top2(data), data)
snapshot = [3, 9, 4]
top2(snapshot)
print("input unchanged:", snapshot == [3, 9, 4])
Output
[9, 4] [9, 4, 3]
input unchanged: False

The returned value is right, so a test on it alone passes. The bug shows only when you also check the argument.

In production Exhaustive small cases against a baseline

The function under test returns the k largest distinct values. The fast version has a planted bug: it keeps duplicates. The harness enumerates every list up to length 4 over three values, shortest first.

PythonSmall-scope check with mutation and precondition testsruns
import heapq
import itertools
import random

def baseline(xs, k):
    if k < 0:
        raise ValueError("k must be >= 0")
    return sorted(set(xs), reverse=True)[:k]

def fast_buggy(xs, k):
    if k < 0:
        raise ValueError("k must be >= 0")
    return heapq.nlargest(k, xs)                 # keeps duplicates

def fast_fixed(xs, k):
    if k < 0:
        raise ValueError("k must be >= 0")
    return heapq.nlargest(k, set(xs))

def small_cases(max_len, alphabet):
    for n in range(max_len + 1):                 # shortest inputs first
        for xs in itertools.product(range(alphabet), repeat=n):
            yield list(xs)

def check(fn, max_len=4, alphabet=3, ks=range(4)):
    count = 0
    for xs in small_cases(max_len, alphabet):
        for k in ks:
            before = list(xs)
            want, got = baseline(xs, k), fn(xs, k)
            count += 1
            if got != want or xs != before:
                return f"FAIL after {count} cases: xs={xs} k={k} want={want} got={got}"
    return f"ok, {count} cases"

print(check(fast_buggy))
print(check(fast_fixed))
rng = random.Random(7)
big = [[rng.randint(-5, 5) for _ in range(rng.randint(0, 12))] for _ in range(2000)]
print(all(fast_fixed(x, 3) == baseline(x, 3) for x in big), "random 2000")
for fn in (baseline, fast_fixed):
    try:
        fn([1], -1)
    except ValueError as e:
        print(f"{fn.__name__} ValueError: {e}")
Output
FAIL after 19 cases: xs=[0, 0] k=2 want=[0] got=[0, 0]
ok, 484 cases
True random 2000
baseline ValueError: k must be >= 0
fast_fixed ValueError: k must be >= 0

The count is 19: 4 cases for the empty list, 12 for the three one-element lists, then 3 on [0, 0]. The fixed version passes 121 inputs × 4 values of k = 484 cases.

Scenario A

In your world

The situation

Your Jenkins job has zero tests, and you check changes by running the pipeline on yesterday's file and comparing a row count.

What actually breaks

A dedupe change passes because yesterday's file had no repeated keys. On the first retry day the same order lands twice and the revenue report over-counts by 3.1%.

What you'd do on Monday

For any transform with a slow obvious form, write a ten-line script that runs old and new logic on every list up to length 5 and fails on any difference, then keep the failing case as a pytest test (Python test mechanics: pytest fixtures, assertions and lifecycle).

PythonMonday script shape (fill in your own transform)
for xs in small_cases(5, 3):
    assert new_transform(list(xs)) == old_transform(list(xs)), xs
Scenario B

Imagine you work at Canva

87,381 versus 22M exhaustive inputs

The numbers

Illustrative: lists of length 0 to 8 over 4 values give (4^9 − 1) ÷ 3 = 87,381 inputs. At ~20 µs a case that is 87,381 × 20 µs ≈ 1.7 s. Length 0 to 12 gives (4^13 − 1) ÷ 3 = 22,369,621 inputs, so 22,369,621 × 20 µs ≈ 447 s, about 7.5 minutes, past a 5-minute CI budget.

What the Scenario-A answer does here

Raising the bound by 4 multiplies cases by 4^4 = 256, turning 1.7 s into minutes.

What flips at this scale

Keep exhaustive checks at the small bound, where they find the smallest failing case, and add a seeded random run of 100,000 larger inputs: 100,000 × 20 µs = 2 s. Print the seed on failure so the case replays.

The trade-off you'd defend

I would defend small-scope exhaustive plus seeded random over exhaustive alone, trading certainty about large shapes for a 2 s check on every commit.

Illustrative case counts and per-case time; not Canva-published figures. The arithmetic is exact; the 20 µs is an assumption.

Gotchas

Passing only the happy path

Symptom

The sample passes, and the interviewer's first input (empty list, repeated value) raises IndexError or returns a wrong list.

Cause

Every test input was ordinary.

Fix

Run the category list before declaring done; the planted duplicate case above fails at the 19th input.

Expected value copied from the output

Symptom

A test passes but asserts a wrong number.

Cause

You wrote down what the code printed.

Fix

Write expected values from the contract first.

Tricky questions

The code handles the prompt's example, so are more cases overkill?
Most people say

One extra case is enough to be safe.

Actually

Each category finds a different bug: empty finds loop assumptions, duplicates find set versus list, a second call finds side effects.

Scenario question

You're handed a finished function and 8 minutes. The interviewer says "test it".

Model answer

I would run the categories cheapest first: empty, single, all equal, one duplicate, reversed, then a second call to check mutation, writing each expected result before running. If a slow version is quick to type, I compare against it on every list up to length 4. The trade-off is that 8 minutes will not cover performance, so I state the complexity separately.

Interview corner

CommonWhat test cases would you write for this function?
“I'd cover empty, one element, all equal, one duplicate, sorted both ways and an invalid parameter. I'd write the expected value first and call the function twice to check it does not mutate its input.”
TrickYour solution passes all your tests. Is it correct?
“It's correct for those inputs. My tests came from my own understanding, so I'd compare against a brute-force version on small inputs and check the categories I skipped.”
Experience checkHow do you test a transform in your pipeline today?
“By comparing row counts on yesterday's file, which missed a retry duplicate. I now compare against a small baseline on tiny inputs and keep failures as pytest cases.”

Memory hook

Drive an empty truck, a full truck and two trucks at once, not just the car that crossed on opening day.

If you remember only one thing:

Write the expected result from the contract before you run, then try empty, one, equal and called-twice.

Self-check

  1. Name five test categories.

    Empty or singleton, extremes, duplicates, order reversal, mutation or aliasing (also graph shapes and invalid preconditions).

  2. Why enumerate shortest inputs first?

    The first failure is then the smallest.

  3. What does a correct-looking quadratic function pass?

    Every small test; only measuring doubling sizes shows it.

Prove it

Write a slow baseline for a function of yours and run both on every list up to length 4 over three values. Paste the output line, then plant a bug and paste the smallest failing case.

dsa-08-05Card 5 of 6

Recover when stuck without bluffing

MediumP2 · Very likelyTalk about it8 min
stuckrecoverybaselinehonesty

Why you care

Everyone gets stuck in a round. What is graded is the next five minutes. The common failures are silence, a bluff that hides a gap ("O(n), I think" with no argument), and thrashing between half-ideas until the clock is gone. Interviewers offer hints on purpose and watch whether you use them. This card is a sequence of small moves that always produces something correct.

Explain like I'm 5

You are lost in a new city. You do not walk faster. You stop, check which street you are on, go back to the last place you were sure of, and ask one person one specific question: "Is the station left or right of this bridge?"

Core concept

The recovery ladder, in order. Stop at the first rung that gets you moving:

  1. Restate the constraints aloud: sizes, ranges, what to return. Half of all stuck moments are a missed constraint.
  2. Isolate the uncertain invariant. Say exactly what you do not know.
  3. Write the baseline. A correct slow version gives you a valid answer and an oracle.
  4. Simplify the representation. Trace three items by hand, try sorting first, change the structure.
  5. Ask one targeted question and name what you tried. "May I assume sorted input?" is a question; "I'm stuck" is not.
  6. Reassess complexity by counting operations against the stated sizes.

Honesty rules:

  • Never claim a cost you did not derive. "I believe" is fine if you then check.
  • Admit partial progress in one sentence: "I have a correct O(n squared) version and I'm looking for the step that avoids the inner loop."
  • If you recognise a memorised pattern, say so and derive why it applies.
  • At minute 25 with no working code, finish the baseline and test it.

Ask for a hint after a baseline and one concrete attempt, not before.

Minimal example Why the baseline's cost is worth stating

PythonComparisons for an all-pairs scanruns
def pair_checks(n):
    return n * (n - 1) // 2

for n in (0, 1, 10, 100, 1000):
    print(n, pair_checks(n))
print(pair_checks(2000) / pair_checks(1000))
Output
0 0
1 0
10 45
100 4950
1000 499500
4.002002002002002

Doubling the input multiplies the work by about 4: derived, not guessed.

In production Measure the baseline, then the candidate

When torn between two approaches, count operations at doubling sizes instead of arguing. The wrapper counts comparisons for two versions of a "does any value repeat" check. All values are distinct, the worst case for the brute-force scan.

PythonCounting comparisons on doubling sizesruns
import random

class Counted:
    calls = 0

    def __init__(self, v):
        self.v = v

    def __lt__(self, other):
        Counted.calls += 1
        return self.v < other.v

    def __eq__(self, other):
        Counted.calls += 1
        return self.v == other.v

def brute_has_dup(xs):
    for i in range(len(xs)):
        for j in range(i + 1, len(xs)):
            if xs[i] == xs[j]:
                return True
    return False

def sorted_has_dup(xs):
    s = sorted(xs)
    return any(a == b for a, b in zip(s, s[1:]))

def cost(fn, n, seed=1):
    rng = random.Random(seed)
    xs = [Counted(v) for v in rng.sample(range(10 * n + 1), n)]   # all distinct: worst case for brute
    Counted.calls = 0
    result = fn(xs)
    return Counted.calls, result

for fn in (brute_has_dup, sorted_has_dup):
    prev = None
    for n in (0, 1, 500, 1000, 2000):
        calls, res = cost(fn, n)
        ratio = "-" if not prev else f"x{calls / prev:.2f}"
        print(f"{fn.__name__:<15} n={n:<5} calls={calls:<8} dup={res} {ratio}")
        prev = calls
Output
brute_has_dup   n=0     calls=0        dup=False -
brute_has_dup   n=1     calls=0        dup=False -
brute_has_dup   n=500   calls=124750   dup=False -
brute_has_dup   n=1000  calls=499500   dup=False x4.00
brute_has_dup   n=2000  calls=1999000  dup=False x4.00
sorted_has_dup  n=0     calls=0        dup=False -
sorted_has_dup  n=1     calls=0        dup=False -
sorted_has_dup  n=500   calls=4325     dup=False -
sorted_has_dup  n=1000  calls=9643     dup=False x2.23
sorted_has_dup  n=2000  calls=21301    dup=False x2.21

About 4 per doubling means quadratic; a little over 2 means n log n.

Scenario A

In your world

The situation

At TCS you are rarely stuck in public. A slow transform gets a profiler alone, and a senior gets asked after an hour.

What actually breaks

In a timed round you freeze at minute 14, say "I think a hash map?" with no reason, rewrite twice, and reach minute 38 with 12 lines of half-working code and no tests. The interviewer's hint at minute 20 went unused because you never said what you had tried.

What you'd do on Monday

When progress stops for 90 seconds, say which rung you are on. At minute 15 with nothing, write the baseline; that leaves 30 minutes for implement, test and wrap-up.

PythonWhat to say at each rung (script, not code)
rungs = [
    "Constraints: n up to 10^5, values may repeat, return a list.",
    "Unknown: how to avoid rescanning earlier items.",
    "Baseline: all pairs, O(n^2), correct, here it is.",
    "Smaller case: three items sorted, what changes?",
    "One question: may I assume the input is sorted?",
]
Scenario B

Imagine you work at Blinkit

30,000 orders to assign per run

The numbers

Illustrative: all pairs at n = 300 is 300 × 299 ÷ 2 = 44,850 comparisons. At n = 30,000 it is 30,000 × 29,999 ÷ 2 = 449,985,000, about 10,033 times more: 100 times the rows costs about 10,000 times the work. At an assumed 5×10^6 comparisons per second, 4.5×10^8 ÷ 5×10^6 = 90 s. A sort-based check does about 30,000 × 14.9 ≈ 447,000 comparisons, roughly 0.09 s.

What the Scenario-A answer does here

The baseline still works as a correct oracle. As shipped code it is 90 s per run, and about 15 minutes at 100,000 rows.

What flips at this scale

Keep the baseline as the test oracle on 300 rows (9 ms) and ship the sort-based version on the 30,000. CI compares them on small data, so an optimisation never ships without its correct twin.

The trade-off you'd defend

I would defend a kept brute-force oracle plus the optimised version over only the optimised one, trading a second function in the repo for a way to find optimisation bugs on tiny inputs.

Illustrative sizes and per-second rate; not Blinkit-published figures. The comparison counts are exact arithmetic.

Gotchas

Bluffing a cost

Symptom

The interviewer asks "why O(n)?" and you cannot point to the loop.

Cause

The claim came from a half-remembered pattern, not from counting.

Fix

Count aloud: one pass, one dictionary lookup per item, so about n lookups.

Silent restarts

Symptom

Eleven minutes of new code and no explanation of what was ruled out.

Cause

Failed ideas were erased silently.

Fix

One sentence per abandoned idea.

Tricky questions

Asking for a hint means I fail?
Most people say

A hint is a mark against me, so I should struggle silently.

Actually

A hint request after a stated baseline and a specific question is normal. Silent struggle burns the minutes you need for tests.

Scenario question

You're handed a prompt, and at minute 14 you have no approach while the interviewer says nothing.

Model answer

I would restate the constraints and say what I do not know: how to avoid the repeated scan. Then I write the all-pairs baseline and state its cost, 4,950 comparisons for 100 items, and ask one question: can the input be sorted? The trade-off is giving up an elegant first answer, but I keep a correct one and the clock.

Interview corner

CommonWhat do you do when you do not know the answer?
“I restate the constraints, say what I'm unsure of, and implement a correct baseline. Then I ask one specific question or look for a simplification, and I keep time for tests.”
TrickWould you use a hint if the interviewer offered it?
“Yes, and I'd say how it changes my plan and what I had tried before it, so the hint reads as part of my reasoning.”
Experience checkTell me about a time you were stuck.
“A slow load: I measured row counts per stage, found the stage taking most of the time, and asked a senior one narrow question about it.”

Memory hook

When lost, stop, go back to the last place you were sure, and ask one specific question.

If you remember only one thing:

A correct baseline with a stated cost beats a silent search for the clever answer.

Self-check

  1. What is the first rung of the recovery ladder?

    Restate the constraints aloud.

  2. How should you ask for a hint?

    After a baseline and an attempt, with one targeted question naming what you tried.

  3. What does a ratio of about 4 per doubling indicate?

    Quadratic work.

Prove it

Run the counter from the production block for n = 250, 500, 1000, 2000 and paste the table with the ratio column. Add a one-line comment on which version you would ship at n = 30,000 and why.

dsa-08-06Card 6 of 6

Python-specific interview mechanics

MediumP2 · Very likelyKnow cold8 min
pythonheapqbisectrecursionaliasing

Why you care

Python lets you lose a round on a mechanic you never saw fail: a heap that raises TypeError on a tie, a grid whose rows are one list, xs = xs.sort() giving None, or recursion that dies at depth 1000. In ETL scripts this is a retry queue that crashes when two jobs share a priority. Interviewers watch for these because they separate daily Python users from people who learned the syntax. Iteration semantics are in Iterator protocol, exhaustion and pull model.

Explain like I'm 5

A shared kitchen has one salt jar. If you "copy" the jar by pointing at it, three cooks still empty the same jar. If you fill three jars, each cook has their own. Most of these traps are about whether you hold the thing or only a label pointing at it.

Core concept

Readable idioms to prefer:

  • enumerate(xs) and zip(a, b) instead of range(len(xs)).
  • Hashable tuple keys: (row, col) works in dicts and sets; lists raise TypeError: unhashable type.
  • Counter, defaultdict(list), and deque for O(1) pops from the left; sorting with key= is stable.
  • Heap tie-breakers: push (priority, seq, item) with a counter, so equal priorities never compare items.
  • bisect: key= exists from Python 3.10 and applies to list elements, not the probe value.

Audit before submitting:

  1. Slices copy. xs[1:] is O(n); in recursion it turns O(n) into O(n squared).
  2. Aliasing. [[0] * c] * r makes r references to one row. Use a comprehension.
  3. Missing keys. d[k] raises KeyError; reading a defaultdict creates the key; Counter returns 0 without storing.
  4. None-returning mutators. sort(), append(), reverse() return None; sorted() returns a new list.
  5. Max-heap. heapq is a min-heap. Python 3.14 added five *_max helpers (heapify_max, heappush_max, heappop_max, heappushpop_max, heapreplace_max). The interpreter may be older, so negate values and say what you assume.
  6. Recursion depth. CPython's default limit is 1000. Use an explicit stack for deep traversals; do not raise the limit as the fix.

Minimal example The heap tie that raises

PythonEqual priority compares the payloadruns
import heapq

h = []
heapq.heappush(h, (2, {"id": "a"}))
try:
    heapq.heappush(h, (2, {"id": "b"}))
except TypeError as e:
    print(f"TypeError: {e}")
h = []
for seq, (prio, item) in enumerate([(2, {"id": "a"}), (2, {"id": "b"})]):
    heapq.heappush(h, (prio, seq, item))
print(heapq.heappop(h)[2]["id"])
Output
TypeError: '<' not supported between instances of 'dict' and 'dict'
a

The second push ties on 2, so Python compares the dicts, which have no ordering. The sequence number settles the tie and gives first-in-first-out among equals.

In production The audit, one line per trap

Six traps in one block, each printing its symptom. Keep the output as the checklist.

PythonPython mechanics auditruns
import sys
from bisect import bisect_left
from collections import Counter, defaultdict, deque
import heapq
# 1. aliasing: one row object repeated vs three rows
grid_bad = [[0] * 2] * 3
grid_bad[0][0] = 1
grid_ok = [[0] * 2 for _ in range(3)]
grid_ok[0][0] = 1
print(grid_bad, grid_ok)
# 2. missing keys: defaultdict creates on read, Counter returns 0 without storing
d, c = defaultdict(list), Counter()
_ = d["x"], c["x"]
print(len(d), len(c))
# 3. max-heap by negation (works on every version; 3.14 adds native *_max helpers)
h = []
for v in (3, 9, 4):
    heapq.heappush(h, -v)
print(-heapq.heappop(h))
# 4. bisect with key= (3.10+): key applies to list items, not the probe
rows = [{"ts": 10}, {"ts": 20}, {"ts": 20}, {"ts": 30}]
print(bisect_left(rows, 20, key=lambda r: r["ts"]))
# 5. mutating methods return None
print(sorted([3, 1, 2]), [3, 1, 2].sort())
# 6. recursion depth vs explicit stack on a 5,000-long chain
nxt = {i: i + 1 for i in range(5000)}
def depth_rec(n):
    return 0 if n not in nxt else 1 + depth_rec(nxt[n])
def depth_iter(n):
    count, stack = 0, deque([n])
    while stack:
        cur = stack.pop()
        if cur in nxt:
            count += 1
            stack.append(nxt[cur])
    return count
print("limit:", sys.getrecursionlimit())
try:
    depth_rec(0)
except RecursionError as e:
    print(type(e).__name__)
print(depth_iter(0))
Output
[[1, 0], [1, 0], [1, 0]] [[1, 0], [0, 0], [0, 0]]
1 0
9
1
[1, 2, 3] None
limit: 1000
RecursionError
5000

The explicit stack handles 5,000 links where recursion fails at about 1,000 frames.

Scenario A

In your world

The situation

Your scripts are written for yourself and tested on real data, so a mutation or shared reference only matters when the data happens to expose it.

What actually breaks

A retry queue built with heapq.heappush(q, (priority, job_dict)) runs for months. On the first day two jobs share priority 2 the scheduler crashes with TypeError: '<' not supported between instances of 'dict' and 'dict', and 140 retries wait until morning.

What you'd do on Monday

Put a sequence number in the middle of the tuple, and run the audit above on any code that touches heaps, grids, slices or deep traversals.

PythonMonday change to a retry queue (needs your job objects)
import heapq, itertools
seq = itertools.count()
heapq.heappush(queue, (priority, next(seq), job))
Scenario B

Imagine you work at Urban Company

20,000 pending bookings

The numbers

Illustrative: 20,000 bookings across 5 priority levels means at least 20,000 ÷ 5 = 4,000 share a level (pigeonhole), so ties are certain. Heap work is about 20,000 × log2(20,000) ≈ 20,000 × 14.3 ≈ 286,000 comparisons, so some will be ties. A reassignment chain of 3,000 hops is three times the default recursion limit of 1000.

What the Scenario-A answer does here

The sequence number still fixes the tie. The second trap is a recursive chain-follower that passed with 40 hops and raises RecursionError at 3,000.

What flips at this scale

Push (priority, seq, booking_id) with ids, not dicts, and walk chains with an explicit stack. The tie-breaker also becomes a policy: first-come-first-served among equals.

The trade-off you'd defend

I would defend the sequence-numbered tuple and an iterative walk over the shortest recursive version, trading five lines of code for no crash on ties or deep chains.

Illustrative counts and priority levels; not Urban Company-published figures.

Gotchas

Heap crashes on equal priorities

Symptom

TypeError: '<' not supported between instances of 'dict' and 'dict', only on days with ties.

Cause

Tuples compare element by element, and the payload comes next.

Fix

(priority, seq, item) as in the minimal block.

Slices inside recursion

Symptom

A recursive helper copies 4,950 elements on 100 items but 124,750 on 500, 25 times more, and fails with RecursionError near 1,000.

Cause

Each xs[1:] copies the rest of the list.

Fix

Pass an index. The demo counts 124,750 copies for 500 items, which is 500 × 499 ÷ 2.

PythonSlice copies countedruns
copied = 0
def total(xs):
    global copied
    if not xs:
        return 0
    rest = xs[1:]
    copied += len(rest)
    return xs[0] + total(rest)
print(total(list(range(500))), copied, 500 * 499 // 2)
rows = [(2, "b"), (2, "a"), (1, "z")]
print(sorted(rows, key=lambda r: r[0]))
Output
124750 124750 124750
[(1, 'z'), (2, 'b'), (2, 'a')]

The second line shows stability: the two priority-2 rows keep input order.

Tricky questions

Is [[0] * c] * r just a shorter way to build a grid?
Most people say

Yes, it makes r separate rows.

Actually

It makes r references to one list, so grid[0][0] = 1 changes every row, as the audit shows. Use [[0] * c for _ in range(r)].

Scenario question

You're handed a priority scheduler to write in Python, the interpreter version is unknown, and tasks may share a priority.

Model answer

I would ask the version first, because native max-heap helpers exist only from 3.14. Without an answer I push negated priorities with a sequence number in the middle, so ties never compare payloads. I would avoid recursion for traversals. The trade-off is less readable negation, but it runs on every version.

Interview corner

CommonHow do you build a max-heap in Python?
“heapq is a min-heap, so I push negated values and negate on the way out. Python 3.14 added native max helpers, but I'd ask which version the environment runs before relying on them.”
TrickWhy does pushing tuples onto a heap sometimes raise TypeError?
“When the first elements tie, Python compares the next ones, and dicts or custom objects have no ordering. I put a counter in the middle so ties never reach the payload.”
Experience checkWhat do you do about the recursion limit?
“The CPython default is 1000, so I use an explicit stack for deep inputs. Raising the limit risks crashing the interpreter.”

Memory hook

A copy of the jar that points at the same jar is still one jar.

If you remember only one thing:

Before submitting, audit for slices, shared references, heap ties, None-returning mutators and recursion depth.

Self-check

  1. How do you stop a heap comparing payloads?

    Use (priority, seq, item) with a counter for seq.

  2. What does [[0] * 2] * 3 create?

    Three references to the same inner list.

  3. Which Python version added native heapq max helpers, and what is the default recursion limit?

    Python 3.14 added five (such as heappush_max); the CPython recursion limit defaults to 1000.

Prove it

Run the audit block and paste its output. Then reproduce a seventh trap from your own code in five lines and paste that output too.