Python for Coding Interviews

Runtime boundaryPortable Python 3.11+ subset. Canonical examples execute in the focused fixture suite; the page itself never runs submitted code. Version-sensitive 3.14 conveniences are labeled and excluded from the compatibility floor.

ReviewedSeptember 5, 2026

Compatibility floorPython 3.11+

Fixture evidencePython 3.12.9 locally; hosted CI provisions and requires Python 3.11 for the compatibility floor.

Source notes

Python 3.11 data modelObjects, identity, and mutability.
Python copy semanticsAssignment and shallow/deep copy boundaries.
Python data structuresLists, tuples, sets, queues, and comprehensions.
Python built-in typesDictionary order and sequence/string semantics.
Python glossaryHashability, iterators, and annotations.
Python control flowFunctions, loops, and range conventions.
Python programming FAQShared defaults and language pitfalls.
Python collectionsCounter, defaultdict, and deque contracts.
Python 3.11 heapqPortable min-heap and tuple tie behavior.
Python 3.14 heapq differencesVersion boundary for public max-heap APIs.
Python bisectPartitions, key behavior, and insertion cost.
Python Sorting HOWTOStable keys and sort versus sorted.
Python functoolsCache hashability and lifetime policies.
Python sysRecursion limits and measurement caveats.
Python expressionsDivision, modulo, and expression semantics.
Python Unicode HOWTOCode points versus displayed characters.
Python built-in functionsIteration and conversion contracts.
Python itertoolspairwise, accumulate, and combinations.
Python mathgcd and isqrt domains.
CPython operation costsBuilt-in costs, amortization, and hash qualifications.
CPython listsort notesSorting auxiliary-workspace qualification.
CPython integer objectsMulti-digit integer representation.
PyPy string concatenation analysisGeneral copying model and CPython optimization caveat.
Princeton union-find referenceRank plus path-halving amortized bound.
Algorithm visualization meta-studyHistorical visualization research context; not an outcome claim for these players.
WCAG keyboard understandingKeyboard functionality.
WCAG reflow understanding320 CSS-pixel reflow boundary and exceptions.
WCAG target-size understanding24px minimum criterion; this product chooses 44px player controls.
WCAG interaction-animation understandingReduced spatial motion; no AA conformance claim is inferred.

Input and output conventions#

Function interview: Implement the requested function with typed parameters where useful. Return the requested value; do not parse stdin unless the prompt says to.
Online assessment: Follow the provider's exact stdin/stdout contract, avoid debug output, and confirm whether one or many cases are supplied.

Python interview sequence#

Read in order for a full review, or jump to the contract behind a syntax decision. This is one guide - not sixteen new routes.

Quick reference#

Compact recall cards point back to their full contract. They are not a separate source of truth.

Iteration and ordering

Use only when ordering and materialization costs match the contract.

for index, value in enumerate(values): ...
for left, right in zip(values, values[1:]): ...
ordered = sorted(values, key=lambda value: value)

Read the full lesson

Counting and adjacency

Keys must be hashable; choose dense lists or arbitrary-key dictionaries deliberately.

from collections import Counter, defaultdict
counts = Counter(values)
graph = defaultdict(list)

Read the full lesson

Queue and heap

Use deque for FIFO and a numeric tie-breaker before incomparable heap payloads.

queue = deque([start]); node = queue.popleft()
heappush(heap, (priority, sequence, payload))

Read the full lesson

Sorted boundaries

Input must be sorted; returned positions may equal len(values).

left = bisect_left(values, target)
right = bisect_right(values, target)  # duplicate run [left, right)

Read the full lesson

Contracts, functions, and input#

Module 1 of 16

Start with the caller's contract: accepted values, mutation permission, return shape, and whether the platform owns input and output.

Objectives

Type hints communicate intent but do not enforce inputs at runtime.
A function interview usually supplies values directly; an online assessment may own stdin and stdout.
Name empty, negative, duplicate, and mutation behavior before choosing a structure.

PrerequisitesVariables, conditions, loops, and functions in any language.

A bounded function contractpython

# example: P01-positive-total
def positive_total(values: list[int]) -> int:
    """Return the sum of positive values without mutating values."""
    total = 0
    for value in values:
        if value > 0:
            total += value
    return total

data = [4, -2, 0, 7]
assert positive_total(data) == 11
assert positive_total([]) == 0
assert data == [4, -2, 0, 7]

Expected: Returns 11, then 0; the input remains unchanged.

Assessment input contractpython

# example: P01-assessment-contract
def solve(text: str) -> str:
    tokens = text.split()
    if not tokens:
        raise ValueError("expected n and then n integers")
    n = int(tokens[0])
    if n < 0 or len(tokens) != n + 1:
        raise ValueError("wrong number of values")
    answer = sum(value for value in map(int, tokens[1:]) if value > 0)
    return str(answer) + "\n"

assert solve("4\n4 -2 0 7\n") == "11\n"
assert solve("0\n") == "0\n"

Expected: Returns one newline-terminated answer and rejects a mismatched token count.

Worked trace

The accumulator starts at zero. Each positive value extends the processed-prefix total; nonpositive values leave it unchanged. Returning after the loop also covers empty input.

PitfallDo not add stdin parsing to a function contract unless the prompt asks for it.

BoundariesSeparate function-style return contracts from assessment stdin/stdout contracts. State empty-input, negative-value, and mutation behavior before coding.

Cost modelO(n) time in the worst case and O(1) working memory.

TakeawayEstablish the caller's contract before selecting syntax or a container.

Deeper note and related practice

Defensive parsing for a reusable utility and assumed-valid input in an interview are different contracts; say which one you implement.

Names, objects, and mutation#

Module 2 of 16

Assignment binds a name to an object. It does not copy that object, so aliases observe mutation while rebinding changes only one name.

Objectives

Use == for value equality and is None for the absence sentinel.
Construct mutable defaults inside the function.
State whether a helper mutates, returns a copy, or transfers ownership.

PrerequisitesP01 · Contracts, functions, and input.

Mutation versus rebindingpython

# example: P02-bindings
a = [2, 4]
b = a
b.append(6)
assert a == [2, 4, 6] and a is b

b = [9]
c = [2, 4, 6]
assert a == c and a is not c
assert b == [9] and a == [2, 4, 6]

Expected: The append is visible through both aliases; rebinding b leaves a on the original list.

Fresh mutable state per callpython

# example: P02-fresh-default
def record(value: int, items: list[int] | None = None) -> list[int]:
    if items is None:
        items = []
    items.append(value)
    return items

assert record(2) == [2]
assert record(4) == [4]
owned = [1]
assert record(3, owned) is owned
assert owned == [1, 3]

Expected: Default calls own separate lists; an explicitly supplied list is mutated by contract.

Worked trace

a and b first refer to one list. Mutation changes that object for both names; rebinding b creates another list while a keeps its original reference.

PitfallA mutable default can retain state across calls. Use None, then allocate per call.

BoundariesUse value equality for values and identity only for sentinels or deliberate object-identity questions. Never infer behavior from integer or string interning.

Cost modelBinding and identity checks are O(1); equality may inspect the compared values.

TakeawayAsk which object is changing and which names currently reach it.

Names point to objects

Separate identity from equality while mutation and rebinding happen.

V01 · P02-references@2026-09-05

a = [2, 4]
b = a
b.append(6)
b = [9]
c = [2, 4, 6]
same_value = a == c
same_object = a is c

Step 1 of 8 · initialBefore binding

No names or list objects exist yet.

Names and values

No example names are bound.

Objects

No list objects exist in this teaching view.

Speed

Read all steps

Alias and rebind

Step 1: Before binding
No names or list objects exist yet.
names
Not available
objects
Not available
Step 2: Bind a
a points to list object L1.
a
→ L1
L1
[2, 4]
Step 3: Alias b
b points to the same L1 object; no copy occurs.
a
→ L1
b
→ L1
L1
[2, 4]
Step 4: Mutate through b
L1 changes, so both names observe the new value.
a
→ L1
b
→ L1
L1
[2, 4, 6]
Step 5: Rebind b
b now points to a new list L2; a still points to L1.
a
→ L1
b
→ L2
L1
[2, 4, 6]
L2
[9]
Step 6: Bind equal c
c points to distinct L3 with the same value as L1.
a
→ L1
b
→ L2
c
→ L3
L3
[2, 4, 6]
Step 7: Compare value
a and c contain equal values.
same_value
True
a
→ L1
c
→ L3
Step 8: Compare identity
Equal values do not make L1 and L3 the same object.
same_object
False
a
→ L1
b
→ L2
c
→ L3

Reverse a linked list

Follow each reference reassignment against the verified Python execution.

11 verified steps

The interactive code-and-state view loads only when requested or near the viewport.

Deeper note and related practice

Equality methods can be customized; the worked trace intentionally uses ordinary built-in lists.

Lists, tuples, and copies#

Module 3 of 16

Lists provide mutable indexed slots; tuples fix their slots but may still contain mutable objects. A shallow copy duplicates only the outer container.

Objectives

append and end-pop make a list a useful stack.
A slice of k elements allocates a new outer list containing k references.
Build nested rows independently when mutations must not leak.

PrerequisitesP02 · Names, objects, and mutation.

Independent matrix rowspython

# example: P03-nested-copy
from copy import deepcopy

rows = [[0, 0], [0, 0]]
shallow = rows.copy()
deep = deepcopy(rows)
rows[0][1] = 7
assert shallow == [[0, 7], [0, 0]]
assert deep == [[0, 0], [0, 0]]
assert shallow is not rows and shallow[0] is rows[0]
assert deep[0] is not rows[0]
safe = [[0] * 2 for _ in range(2)]
safe[0][1] = 7
assert safe == [[0, 7], [0, 0]]
container = ([1],)
container[0].append(2)
assert container == ([1, 2],)

Expected: The shallow copy shares rows, the deep copy does not, and independently constructed rows isolate mutation.

Worked trace

A shallow copy creates a new outer list but retains its child references. Independently constructed rows receive distinct identities, so one cell update stays local.

Pitfall[[0] * cols] * rows repeats one row reference; it does not create independent rows.

BoundariesIndexes can raise; slices clamp. Empty and singleton inputs are valid. Tuple slots are fixed, but a mutable object inside a tuple can still change.

Cost modelIndexing and end operations are O(1) amortized; membership and front removal are O(n); a k-item slice is O(k).

TakeawayCopy at the exact ownership level where independence is required.

Shallow versus independent rows

Track the outer list and inner-row identities, not just printed values.

V02 · P03-sequences@2026-09-05

bad = [[0, 0]] * 2
outer_copy = bad.copy()
bad[0][1] = 7
good = [[0, 0] for _ in range(2)]
good[0][1] = 7

Step 1 of 6 · initialInitial state

No example bindings or list objects exist yet.

Names and values

No example names are bound.

Objects

No list objects exist in this teaching view.

Speed

Read all steps

Nested copy

Step 1: Initial state
No example bindings or list objects exist yet.
names
Not available
objects
Not available
Step 2: Repeat one row reference
bad points to O1, whose two slots both refer to the single row R1.
bad
→ O1
O1
[→R1, →R1]
R1
[0, 0]
Step 3: Copy the outer list
outer_copy points to new O2, but O2 retains the same two references to R1.
bad
→ O1
outer_copy
→ O2
O1
[→R1, →R1]
O2
[→R1, →R1]
R1
[0, 0]
Step 4: Mutate shared R1
One object update is visible through four reference paths across O1 and O2.
bad
→ O1
outer_copy
→ O2
O1
[→R1, →R1]
O2
[→R1, →R1]
R1
[0, 7]
Step 5: Build independent rows
good points to O3, whose slots refer to distinct R2 and R3 objects.
good
→ O3
O3
[→R2, →R3]
R2
[0, 0]
R3
[0, 0]
Step 6: Mutate only R2
The selected row changes while R3 and the earlier shared grid retain their prior values.
bad
→ O1
outer_copy
→ O2
good
→ O3
O1
[→R1, →R1]
O2
[→R1, →R1]
O3
[→R2, →R3]
R1
[0, 7]
R2
[0, 7]
R3
[0, 0]

Deeper note and related practice

reverse mutates and returns None, slicing constructs a list, and reversed returns an iterator; those contracts are not interchangeable.

Strings and text construction#

Module 4 of 16

Strings are immutable sequences of Unicode code points. Build many fragments in a list and join once when repeated concatenation would recopy a growing prefix.

Objectives

ASCII-only contracts need explicit ASCII bounds.
Code points, encoded bytes, and user-perceived characters are different units.
Apply normalization or case folding only when the problem permits it.

PrerequisitesP03 · Lists, tuples, and copies.

Text construction and Unicode contractspython

# example: P04-string-building
def join_labels(labels: list[str]) -> str:
    return "|".join(labels)

assert join_labels(["map", "heap", "queue"]) == "map|heap|queue"
assert join_labels([]) == ""

text = "a\u0301"  # a followed by a combining acute accent
assert len(text) == 2  # two Unicode code points
assert [ord(character) for character in text] == [97, 769]
assert len(text.encode("utf-8")) == 3
assert "²".isdigit() and not ("0" <= "²" <= "9")
assert "Straße".casefold() == "strasse"

Expected: Joins labels once; the combining sequence has two code points and three UTF-8 bytes; isdigit and casefold demonstrate non-ASCII behavior.

Worked trace

The labels join to map|heap|queue in one result. The text a\u0301 contains code points U+0061 and U+0301 but encodes to three UTF-8 bytes; ² passes isdigit without being ASCII, and casefold expands Straße to strasse.

Pitfallisdigit() accepts more than ASCII 0–9; do not use it for an ASCII-only contract without checking bounds.

BoundariesDefine whether a character means an ASCII code point, a Unicode code point, encoded bytes, or a displayed grapheme. Empty text must remain valid.

Cost modelBuilding m output characters with a list plus join is O(m) time and O(m) returned output.

TakeawayState the text unit and count the output you actually construct.

Deeper note and related practice

Collecting every prefix can still require quadratic total output even when each final join is efficient.

Dictionaries, sets, and counting#

Module 5 of 16

Use dict when a key maps to information and set when membership is enough. Hashability requires a stable hash consistent with equality.

Objectives

Dictionary iteration preserves insertion order; set iteration has no insertion-order promise.
Counter reads a missing key as zero without inserting it.
With prefix counts, query earlier prefixes before recording the current prefix.

PrerequisitesP02–P04 · References, sequences, and strings.

Prefix-frequency orderpython

# example: P05-missing-keys
from collections import Counter, defaultdict

values = [4, 1, 4]
frequency = {}
for value in values:
    frequency[value] = frequency.get(value, 0) + 1
assert frequency == {4: 2, 1: 1}
assert list(frequency) == [4, 1]
counts = Counter(values)
assert counts[9] == 0 and 9 not in counts
counts[9] = 0
assert 9 in counts
groups = defaultdict(list)
assert groups.get("x") is None and "x" not in groups
groups["x"].append(3)
assert dict(groups) == {"x": [3]}
seen = {(0, 1), (1, 0)}
assert (0, 1) in seen

Expected: Missing-key reads and writes have distinct insertion behavior, and dictionary iteration preserves first insertion order.

Worked trace

For prefix counting, query the frequencies of earlier prefixes before recording the current prefix; the seeded zero prefix represents the empty prefix.

PitfallUpdating the frequency before querying lets the current prefix count itself.

BoundariesKeys must be hashable and equality-consistent. Expected constant-time lookup assumes ordinary hashing; collisions and expensive keys need separate qualification.

Cost modelExpected O(n) time and O(n) space under ordinary hash behavior; collision worst cases remain possible.

TakeawayChoose a set for membership and a dictionary when each key carries information.

Deeper note and related practice

Counter's missing-key read does not insert, while defaultdict access can; that difference matters while iterating or checking shape.

Iteration and materialization#

Module 6 of 16

Choose enumerate for index plus value, zip for aligned inputs, and explicit loops when several pieces of state must stay visible.

Objectives

Iterators are consumed; an exhausted generator does not restart.
zip stops at the shortest input unless strict=True is requested.
A lazy consumer does not undo allocations already made by a slice.

PrerequisitesP03 and P05 · Sequences and hashing.

Iteration without hidden slicespython

# example: P06-iteration
from itertools import pairwise

nums = [3, 5, 8]
assert list(enumerate(nums)) == [(0, 3), (1, 5), (2, 8)]
assert list(pairwise(nums)) == [(3, 5), (5, 8)]
assert list(range(4, -1, -2)) == [4, 2, 0]
squared_values = [value * value for value in nums]
assert squared_values == [9, 25, 64]

squares = (value * value for value in nums)
assert next(squares) == 9
assert list(squares) == [25, 64]
assert list(squares) == []

pairs = list(zip([1, 2], ["a"]))
assert pairs == [(1, "a")]

Expected: enumerate supplies indexes, pairwise avoids a sliced suffix, range descends by two, the comprehension materializes squares, and the generator exhausts after one pass.

Worked trace

enumerate pairs 3, 5, 8 with indexes; pairwise yields adjacent values without a suffix slice; range visits 4, 2, 0; the comprehension materializes three squares. The generator then yields 9, resumes for 25 and 64, and stays exhausted.

Pitfallzip(nums, nums[1:]) is lazy only after nums[1:] has already copied the suffix.

Boundarieszip stops at the shortest input unless strict mode is requested. pairwise over zero or one item is empty. A slice allocates before a lazy zip consumes it.

Cost modelIteration is O(n); materializing a result of k items adds O(k) output space.

TakeawayLazy evaluation avoids some materialization, but it is not free and it does not reverse work already performed.

Deeper note and related practice

Do not structurally mutate a collection while iterating unless the algorithm and iterator contract explicitly support it.

Stacks, queues, and deque#

Module 7 of 16

Use list append/end-pop for LIFO and collections.deque for FIFO or operations at both ends.

Objectives

Mark BFS nodes seen when enqueuing them.
A bounded deque drops an item when full; that is usually wrong for a frontier.
Middle indexing is not deque's strength.

PrerequisitesP03 and P06 · Sequences and iteration.

FIFO traversalpython

# example: P07-removal-order
from collections import deque

stack = [2, 4, 6]
assert [stack.pop(), stack.pop(), stack.pop()] == [6, 4, 2]
queue = deque([2, 4, 6])
assert [queue.popleft(), queue.popleft(), queue.popleft()] == [2, 4, 6]
bounded = deque([1, 2], maxlen=2)
bounded.append(3)
assert list(bounded) == [2, 3]

Expected: The stack returns LIFO, deque returns FIFO, and a bounded deque demonstrates its drop policy.

Worked trace

Both lanes remove the same FIFO values. The list model shifts the remaining references after each front removal; deque does not promise that internal work.

Pitfalllist.pop(0) shifts every remaining element and can turn a traversal quadratic.

BoundariesCheck emptiness before removal. A bounded deque silently discards an endpoint when full, so it is usually wrong for an unbounded search frontier.

Cost modeldeque append and popleft are O(1); n list front removals perform n(n−1)/2 element shifts in the simple model.

TakeawayChoose the container for the operations the algorithm performs, not merely for the final values it returns.

Queue work versus list shifts

Compare FIFO state and the element-shift model without making timing claims.

V03 · P07-queues@2026-09-05

Example

from collections import deque
items = [10, 20, 30, 40] # preset input
queue = deque(items)
shift_count = 0
removed = []
while items:
shift_count += len(items) - 1
left = items.pop(0)
right = queue.popleft()
assert left == right
removed.append(left)

Step 1 of 6 · initialInitialize both lanes

L1–L4 construct the list, deque, counter, and output before the first loop test.

list lane

010120230340

deque lane

010120230340

removed

[]

model shifts step / total

0 / 0

Speed

Read all steps

Four items

Step 1: Initialize both lanes
L1–L4 construct the list, deque, counter, and output before the first loop test.
list lane
[10, 20, 30, 40]
deque lane
[10, 20, 30, 40]
removed
[]
model shifts step / total
0 / 0
Step 2: Remove 10
L5–L10 run in source order: count prospective list shifts, remove both fronts, verify equality, then append output.
list lane
[20, 30, 40]
deque lane
[20, 30, 40]
removed
[10]
model shifts step / total
3 / 3
Step 3: Remove 20
L5–L10 run in source order: count prospective list shifts, remove both fronts, verify equality, then append output.
list lane
[30, 40]
deque lane
[30, 40]
removed
[10, 20]
model shifts step / total
2 / 5
Step 4: Remove 30
L5–L10 run in source order: count prospective list shifts, remove both fronts, verify equality, then append output.
list lane
[40]
deque lane
[40]
removed
[10, 20, 30]
model shifts step / total
1 / 6
Step 5: Remove 40
L5–L10 run in source order: count prospective list shifts, remove both fronts, verify equality, then append output.
list lane
[]
deque lane
[]
removed
[10, 20, 30, 40]
model shifts step / total
0 / 6
Step 6: Loop complete
Both lanes produced the same order. The list reference-shift model totals 6; this is not CPU instructions, elapsed time, or bytes.
list lane
[]
deque lane
[]
removed
[10, 20, 30, 40]
model shifts step / total
0 / 6

Empty

Step 1: Initialize empty lanes
The preset changes only the initial literal and expected result; removed starts empty and shifts start at zero.
list lane
[]
deque lane
[]
removed
[]
model shifts
0
Step 2: Loop complete
L5 is false, so the grouped body never runs.
removed
[]
model shifts
0

Wide BFS frontier

Step 1: Initialize star frontier
After a star's center is processed, [1,2,3,4] is the wide frontier. This is context, not another graph animation.
list lane
[1, 2, 3, 4]
deque lane
[1, 2, 3, 4]
removed
[]
model shifts step / total
0 / 0
Step 2: Remove vertex 1
The grouped L5–L10 actions preserve order while the list model shifts its remaining logical positions.
list lane
[2, 3, 4]
deque lane
[2, 3, 4]
removed
[1]
model shifts step / total
3 / 3
Step 3: Remove vertex 2
The grouped L5–L10 actions preserve order while the list model shifts its remaining logical positions.
list lane
[3, 4]
deque lane
[3, 4]
removed
[1, 2]
model shifts step / total
2 / 5
Step 4: Remove vertex 3
The grouped L5–L10 actions preserve order while the list model shifts its remaining logical positions.
list lane
[4]
deque lane
[4]
removed
[1, 2, 3]
model shifts step / total
1 / 6
Step 5: Remove vertex 4
The grouped L5–L10 actions preserve order while the list model shifts its remaining logical positions.
list lane
[]
deque lane
[]
removed
[1, 2, 3, 4]
model shifts step / total
0 / 6
Step 6: Loop complete
Both lanes preserve the same order; no wall-clock or deque-instruction count is claimed.
list lane
[]
deque lane
[]
removed
[1, 2, 3, 4]
model shifts step / total
0 / 6

Trace breadth-first search

Inspect the queue, visited set, and shortest-path distance one verified step at a time.

21 verified steps

The interactive code-and-state view loads only when requested or near the viewport.

Deeper note and related practice

Frontier width O(w), visited storage O(V), and returned traversal order are different quantities.

Stable sorting and mutation#

Module 8 of 16

sorted creates a new list; list.sort mutates and returns None. Python sorting is stable, and each key is evaluated once per item.

Objectives

Put ranking policy in a key function.
Stable ties retain their previous relative order.
In-place mutation does not imply O(1) auxiliary workspace.

PrerequisitesP03 and P06 · Sequences and iteration.

Stable ranked recordspython

# example: P08-stable-sort
records = [("A", 2), ("B", 1), ("C", 2)]
by_score = sorted(records, key=lambda item: item[1])
assert by_score == [("B", 1), ("A", 2), ("C", 2)]
assert records == [("A", 2), ("B", 1), ("C", 2)]
returned = records.sort(key=lambda item: item[1])
assert returned is None and records == by_score
descending = sorted(by_score, key=lambda item: -item[1])
assert descending == [("A", 2), ("C", 2), ("B", 1)]

Expected: Stable equal keys retain A before C; sorted returns a new list while list.sort mutates and returns None.

Worked trace

Keys map A→2, B→1, C→2. B moves first while A stays before C. sorted creates a new outer list; list.sort mutates and returns None.

PitfallDo not assign result = values.sort(); the method returns None.

BoundariesDefine tie order, empty/all-equal inputs, reverse order, and whether key results are mutually comparable.

Cost modelUsual worst-case O(n log n) comparisons plus n key evaluations; CPython may use O(n) auxiliary workspace.

TakeawayPut the ordering policy in the key and state what happens to ties.

Stable sort and mutation boundary

See conceptual key extraction, stable ties, and the difference between sorted and list.sort.

V04 · P08-sorting@2026-09-05

records = [("A", 2), ("B", 1), ("C", 2)]
ordered = sorted(records, key=lambda item: item[1])
returned = records.sort(key=lambda item: item[1])

Step 1 of 5 · afterOriginal order

A precedes C among rank-2 records; ordered is not bound yet.

records R

A:2 · B:1 · C:2

ordered

unbound

Speed

Read all steps

Stable ties

Step 1: Original order
A precedes C among rank-2 records; ordered is not bound yet.
records R
A:2 · B:1 · C:2
ordered
unbound
Step 2: Conceptual key mapping
State is unchanged while the key mapping is explained; this is not a simulated Timsort event.
records R
A:2 · B:1 · C:2
keys
A→2 · B→1 · C→2
key calls
3
Step 3: sorted returns O
B moves first; A stays before C because equal-key order is stable. O and R are distinct lists.
records R
A:2 · B:1 · C:2
ordered O
B:1 · A:2 · C:2
identity
O is not R
Step 4: Conceptual mutation boundary
State remains unchanged while the next call's target is explained: list.sort will rearrange R itself.
records R
A:2 · B:1 · C:2
ordered O
B:1 · A:2 · C:2
Step 5: list.sort completes
R now matches O by value, returned is None, and R and O remain distinct objects.
records R
B:1 · A:2 · C:2
ordered O
B:1 · A:2 · C:2
returned
None
identity
O is not R

Deeper note and related practice

Mutating in place does not imply constant auxiliary memory; implementation workspace and key storage still count.

Heaps, priorities, and ties#

Module 9 of 16

The portable 3.11 contract uses heapq as a min-heap. The root is minimal, but the backing list is not globally sorted.

Objectives

heapify builds a heap in O(n).
Use a numeric sequence tie-breaker before an incomparable payload.
Python 3.14 max-heap APIs are outside this guide's 3.11 compatibility floor.

PrerequisitesP03 and P08 · Sequences and sorting.

Safe priority tuplespython

# example: P09-ranked-events
import heapq

def select_events(events: list[tuple[int, str]], k: int) -> list[str]:
    if k < 0:
        raise ValueError("k must be nonnegative")
    if k == 0:
        return []
    heap = []
    for sequence, (priority, label) in enumerate(events):
        entry = (priority, -sequence, label)
        heapq.heappush(heap, entry)
        if len(heap) > k:
            heapq.heappop(heap)
    ranked = sorted(heap, key=lambda entry: (-entry[0], -entry[1]))
    return [entry[2] for entry in ranked]

events = [(5, "A"), (5, "B"), (4, "C"), (5, "D")]
assert select_events(events, 2) == ["A", "B"]
assert select_events(events, 0) == []
assert select_events(events, 8) == ["A", "B", "D", "C"]
assert select_events([], 2) == []

Expected: Retains the highest priorities, prefers earlier records on ties, and returns best-first labels.

Worked trace

The minimum tuple stays at the root. A numeric sequence field resolves equal priorities before Python ever needs to compare dictionary payloads.

PitfallTuples compare lexicographically. Equal priorities without a comparable tie-breaker can raise TypeError.

BoundariesEmpty root/pop access is invalid. Python 3.14 max-heap helpers are outside the portable 3.11 floor. Retention ties and output order must be explicit.

Cost modelheapify is O(n), root access O(1), and push/pop O(log n) comparison work.

TakeawayA priority tuple must encode the actual tie and retention policy.

Heap shape is not sorted order

Keep the heap array and conceptual tree synchronized while priorities and ties are processed.

V05 · P09-heaps@2026-09-05

import heapq
heap = []
heapq.heappush(heap, (2, 0, {"id": "A"}))
heapq.heappush(heap, (1, 1, {"id": "B"}))
heapq.heappush(heap, (2, 2, {"id": "C"}))
first = heapq.heappop(heap)
second = heapq.heappop(heap)
third = heapq.heappop(heap)

Step 1 of 7 · initialEmpty heap

No next item is available.

One heap, array view

empty

Same entries, parent/child view

empty

next: unavailable

Speed

Boundary check: Broken: (2, {"id": "A"}) and (2, {"id": "C"}) can raise TypeError because tied priorities compare dict payloads. Valid but globally unsorted heap: [(1,0,B), (3,1,A), (2,2,C)]. After the final removal, another heapq.heappop(heap) raises IndexError.

Read all steps

Priorities and ties

Step 1: Empty heap
No next item is available.
heap array
[]
next
unavailable
Step 2: Push A
The first entry becomes the root.
heap array
[(2,0,A)]
Step 3: Push B
Priority 1 moves to the root.
heap array
[(1,1,B), (2,0,A)]
Step 4: Push C
C ties A on priority but its sequence is later.
heap array
[(1,1,B), (2,0,A), (2,2,C)]
Step 5: Pop B
The minimum tuple leaves first.
heap array
[(2,0,A), (2,2,C)]
returned entries
first=B
Step 6: Pop A
The numeric sequence resolves the tied priority.
heap array
[(2,2,C)]
returned entries
first=B · second=A
Step 7: Pop C
The heap is empty again; another heapq.heappop(heap) would raise IndexError, so Next is unavailable.
heap array
[]
returned entries
first=B · second=A · third=C
next heappop
raises IndexError

Trace max-priority order

Watch negated priorities move through Python's min-heap implementation.

12 verified steps

The interactive code-and-state view loads only when requested or near the viewport.

Deeper note and related practice

heappushpop and heapreplace have different return/retention contracts; choose them only after establishing which item should survive.

Sorted boundaries with bisect#

Module 10 of 16

Lower bound is the first position at least the target; upper bound is the first position greater. Either may equal len(values).

Objectives

Use the half-open interval [left, right).
An insertion position is safe to return but not always safe to dereference.
Searching is logarithmic; inserting into a list can still shift O(n) items.

PrerequisitesP03 and P08 · Sequences and sorting.

Lower and upper boundariespython

# example: P10-boundaries
from bisect import bisect_left, bisect_right

def lower_bound(nums: list[int], target: int) -> int:
    left, right = 0, len(nums)
    while left < right:
        middle = (left + right) // 2
        if nums[middle] < target:
            left = middle + 1
        else:
            right = middle
    return left

nums = [1, 3, 3, 7]
assert lower_bound(nums, 3) == bisect_left(nums, 3) == 1
assert bisect_right(nums, 3) == 3
assert lower_bound([], 3) == 0
assert lower_bound(nums, 9) == 4
index = lower_bound(nums, 2)
assert index == 1 and not (index < len(nums) and nums[index] == 2)

Expected: The duplicate run occupies [1, 3); absent targets and empty input return safe insertion boundaries.

Worked trace

Each comparison shrinks a half-open undecided interval. Lower mode partitions values below the target from values at least the target; upper mode advances across equals.

PitfallDo not index values[position] until you have proved position < len(values).

BoundariesThe returned boundary may equal len(values) and need not point to an equal item. Never dereference it without a bounds and equality check.

Cost modelO(log n) comparisons for the search; O(n) movement if list insertion follows.

TakeawayBinary search finds a partition boundary, not necessarily a match.

Half-open binary-search boundaries

Follow [left, right) and reveal the insertion result only when the interval closes.

V06 · P10-bisect@2026-09-05

Example

def boundary(nums, target, upper=False):
left, right = 0, len(nums)
while left < right:
middle = (left + right) // 2
if nums[middle] < target or (upper and nums[middle] == target):
left = middle + 1
else: right = middle
return left

Step 1 of 5 · initialStart

Search [0, 4) with upper=False.

values

01132337

previous interval

Not available

new interval

[0,4)

result

hidden

Speed

Read all steps

lower 3

Step 1: Start
Search [0, 4) with upper=False.
values
[1,3,3,7]
previous interval
Not available
new interval
[0,4)
result
hidden
Step 2: Probe index 2
nums[2]=3; lower mode executes right=2.
previous interval
[0,4)
mid / value
2 / 3
new interval
[0,2)
result
hidden
Step 3: Probe index 1
nums[1]=3; lower mode executes right=1.
previous interval
[0,2)
mid / value
1 / 3
new interval
[0,1)
result
hidden
Step 4: Probe index 0
nums[0]=1; lower mode executes left=1.
previous interval
[0,1)
mid / value
0 / 1
new interval
[1,1)
result
hidden
Step 5: Return boundary
Only now is result 1 revealed.
interval
[1,1)
result
1

upper 3

Step 1: Start
Search [0, 4) with upper=True.
values
[1,3,3,7]
new interval
[0,4)
result
hidden
Step 2: Probe index 2
The upper-mode equality branch executes left=3.
previous interval
[0,4)
mid / value
2 / 3
new interval
[3,4)
result
hidden
Step 3: Probe index 3
nums[3]=7 is greater than 3, so right=3.
previous interval
[3,4)
mid / value
3 / 7
new interval
[3,3)
result
hidden
Step 4: Return boundary
Only now is the duplicate-run end 3 revealed.
interval
[3,3)
result
3

lower 9

Step 1: Start
Search [0, 4) with upper=False.
values
[1,3,3,7]
new interval
[0,4)
result
hidden
Step 2: Probe index 2
nums[2]=3 is below 9, so left=3.
previous interval
[0,4)
mid / value
2 / 3
new interval
[3,4)
result
hidden
Step 3: Probe index 3
nums[3]=7 is below 9, so left=4.
previous interval
[3,4)
mid / value
3 / 7
new interval
[4,4)
result
hidden
Step 4: Return len(nums)
Only now is the one-past-end result 4 revealed.
interval
[4,4)
result
4

empty

Step 1: Start empty
Both boundaries begin at zero; no midpoint exists.
values
[]
new interval
[0,0)
result
hidden
Step 2: Return zero
L2 is false, so no probe or dereference occurs.
interval
[0,0)
result
0

Trace binary search

See how the active interval narrows until the target index is found.

13 verified steps

The interactive code-and-state view loads only when requested or near the viewport.

Deeper note and related practice

A bisect key applies to stored elements, not the search target; record searches need a target expressed in key space.

Arithmetic, integers, and masks#

Module 11 of 16

Python // floors the mathematical quotient, while integer / produces a float. Arbitrary-size integers make bit length part of the cost model.

Objectives

Modulo follows the divisor's sign or is zero.
int(a / b) is not a reliable large-integer truncation technique.
State the bit-width and signedness assumptions of a mask.

PrerequisitesP01 · Contracts, functions, and input.

Floor division and maskspython

# example: P11-numbers
assert -7 // 3 == -3
assert -7 % 3 == 2
assert (-7 // 3) * 3 + (-7 % 3) == -7
large = 10**30 + 1
assert large // 3 == 333333333333333333333333333333
mask = (1 << 1) | (1 << 3)
assert mask == 10 and mask.bit_count() == 2
assert mask & (1 << 3)
assert (mask & ~(1 << 1)) == 8
assert ((~mask) & ((1 << 4) - 1)) == 5

Expected: Floor division reconstructs the dividend, large integers stay exact, and the four-bit mask has two set bits.

Worked trace

The mask changes 0→2→10 as bits 1 and 3 are set. Clearing bit 1 leaves 8; complement needs an explicit finite-width mask to produce 5.

PitfallDo not silently assume machine-word arithmetic when values may grow with the input.

BoundariesDivision by zero, negative operands, negative shifts, and finite versus unbounded bit masks need explicit contracts.

Cost modelBit operations on bounded machine-sized values are often modeled O(1); general integer work depends on operand bit length B.

TakeawayNo fixed-width overflow does not mean arbitrarily large integer work is constant time.

Deeper note and related practice

Integer arithmetic, hashing, and storage may depend on bit length B; use integer isqrt when float rounding would be unsafe.

Recursion frames and depth#

Module 12 of 16

Each recursive call owns local state. Its caller waits at the call site, receives a return value, and then resumes.

Objectives

Define a base case and measurable progress toward it.
The call stack counts as working memory.
Use an explicit stack when input depth is unbounded.

PrerequisitesP01 and P07 · Contracts and stack behavior.

Depth with explicit returnspython

# example: P12-call-stack
def triangular(n: int) -> int:
    if n == 0:
        return 0
    subtotal = triangular(n - 1)
    return n + subtotal

answer = triangular(3)
assert answer == 6
assert triangular(0) == 0

Expected: The deepest base case returns first; waiting callers resume with subtotals 0, 1, and 3 before returning 6.

Iterative accumulationpython

# example: P12-iterative-alternative
def triangular_iterative(n: int) -> int:
    total = 0
    for value in range(1, n + 1):
        total += value
    return total

assert triangular_iterative(3) == 6
assert triangular_iterative(0) == 0

Expected: Returns 6 and 0 with constant accumulator slots.

Worked trace

Calls for n=3,2,1 wait with separate local slots. The n=0 base returns 0; callers resume in reverse order and return 1,3,6.

PitfallRaising the recursion limit is not a general repair for unbounded input depth.

BoundariesThis function accepts small nonnegative n. Safe recursion depth depends on runtime and platform; raising the limit is not a general repair.

Cost modelO(n) calls and O(n) call-stack space for this linear recurrence.

TakeawayTrack one frame's responsibility and one returned value at a time.

Recursive callers wait

Distinguish a returned token from assignment into a waiting caller's local variable.

V07 · P12-recursion@2026-09-05

Example

def triangular(n):
if n == 0:
return 0
subtotal = triangular(n - 1)
return n + subtotal
answer = triangular(3)

Step 1 of 13 · initialInitial state

The module is ready to call triangular(3); answer is not bound yet.

Call stack · newest active frame first

call stackempty

Return token and shared state

answer: unbound

Speed

Read all steps

n = 3

Step 1: Initial state
The module is ready to call triangular(3); answer is not bound yet.
call stack
empty
answer
unbound
Step 2: Call F3
triangular(3) creates F3 with its own n and unbound subtotal.
F3
n=3 · subtotal=unbound
answer
unbound
Step 3: Call F2
F3 waits at its call site while triangular(2) creates F2.
F3
n=3 · waiting at L3
F2
n=2 · subtotal=unbound
Step 4: Call F1
F3 and F2 wait while triangular(1) creates F1.
F3
waiting at L3
F2
waiting at L3
F1
n=1 · subtotal=unbound
Step 5: Call F0
The final recursive call reaches n=0.
F3
waiting
F2
waiting
F1
waiting
F0
n=0
Step 6: Return 0 from F0
The base frame returns a distinct token; F1 is next to resume.
F1
waiting at L3
just returned
0
Step 7: Resume F1
F1 consumes the token into its own subtotal slot.
F1
n=1 · subtotal=0
older callers
F3, F2 waiting
Step 8: Return 1 from F1
F1 computes 1 + 0 and returns 1 to F2.
F2
waiting at L3
just returned
1
Step 9: Resume F2
F2 consumes the returned 1 into subtotal.
F2
n=2 · subtotal=1
older caller
F3 waiting
Step 10: Return 3 from F2
F2 computes 2 + 1 and returns 3 to F3.
F3
waiting at L3
just returned
3
Step 11: Resume F3
F3 consumes the returned 3 into subtotal.
F3
n=3 · subtotal=3
Step 12: Return 6 from F3
F3 computes 3 + 3; the call stack is now empty.
call stack
empty
just returned
6
Step 13: Bind answer
The module call consumes the token and binds answer to 6.
call stack
empty
answer
6

n = 0

Step 1: Initial state
The module is ready to call triangular(0); answer is unbound.
call stack
empty
answer
unbound
Step 2: Call F0
Create the boundary invocation with n=0.
F0
n=0
Step 3: Return 0
The base case produces a return token and the frame leaves.
call stack
empty
just returned
0
Step 4: Bind answer
The module consumes the token and binds answer to 0.
call stack
empty
answer
0

Trace recursive tree depth

Move through recursive calls and returns while the maximum depth is assembled.

16 verified steps

The interactive code-and-state view loads only when requested or near the viewport.

Deeper note and related practice

Sequential child calls do not add their maximum depths together, though each still contributes work.

Backtracking and memoized state#

Module 13 of 16

Backtracking chooses, explores, and restores shared path state. Memoization instead caches answers for state keys whose future behavior is identical.

Objectives

Copy the path when saving an answer.
Undo every mutation before returning to the caller.
A memo key must capture all state that affects future choices.

PrerequisitesP02, P05, and P12 · References, hashing, and recursion.

Subsets with restored statepython

# example: P13-subsets
def subsets(values: list[int]) -> list[list[int]]:
    answers, path = [], []
    def search(index: int) -> None:
        if index == len(values):
            answers.append(path.copy())
            return
        search(index + 1)
        path.append(values[index])
        search(index + 1)
        path.pop()
    search(0)
    return answers

assert subsets([1, 2]) == [[], [2], [1], [1, 2]]
assert subsets([]) == [[]]

Expected: Four independent saved lists are produced and empty input has one subset. Each invocation restores path to its own entry state before returning; that entry state may be nonempty.

A complete memoization keypython

# example: P13-memo-state
from functools import cache

def best_non_adjacent(values: list[int]) -> int:
    @cache
    def best(index: int) -> int:
        if index >= len(values):
            return 0
        return max(best(index + 1), values[index] + best(index + 2))
    return best(0)

assert best_non_adjacent([2, 7, 9, 3, 1]) == 12
assert best_non_adjacent([]) == 0
assert best_non_adjacent([-4, -1]) == 0

Expected: The fixed input makes index a complete key; choosing none preserves zero for negative-only input.

Worked trace

The working path follows one branch. Each invocation restores path to the state it had when that invocation began - not necessarily to empty - before returning to its caller. Each saved result is a copy, so later path mutations cannot rewrite earlier answers.

PitfallAppending path itself saves aliases to one mutable list; copy it at the answer boundary.

BoundariesSubsets enumerate input positions; repeated values may yield equal-looking outputs. Cache keys must contain every value that changes a subproblem's answer.

Cost modelO(n·2ⁿ) time and returned output for n-item subsets; O(n) active path/call-stack space excluding output.

TakeawaySnapshot completed outputs and cache complete immutable state.

Backtracking restores shared state

Watch one working path mutate while answer copies keep independent identities.

V08 · P13-subsets@2026-09-05

Example

def subsets(values):
answers = []
path = []
def search(index):
if index == len(values):
answers.append(path.copy())
return
search(index + 1) # exclude
path.append(values[index])
search(index + 1) # include
path.pop()
search(0)
return answers
result = subsets([1, 2])

Step 1 of 26 · afterInitialize outer frame

P is one shared working list. Every A-labelled saved value is a distinct copied list object.

Call stack · newest active frame first

search stack[]

Return token and shared state

phase: after
executed line: L2
outer frame: values=[1,2] · path=P · answers
path P: []
saved objects: []

Speed

Boundary check: Broken: answers.append(path) stores repeated references to the same working list. Executed regression: four saved answers must have four distinct identities and path must be empty after return.

Read all steps

values = [1, 2]

Step 1: Initialize outer frame
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[]
phase
after
executed line
L2
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[]
Step 2: Call search(0)
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0]
phase
call
executed line
L10
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[]
Step 3: Exclude 1
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
call
executed line
L6
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[]
Step 4: Exclude 2
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1,2]
phase
call
executed line
L6
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[]
Step 5: Save A0
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1,2]
phase
after
executed line
L4
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[A0=[]]
Step 6: Return leaf
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
return
executed line
L5
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[A0=[]]
Step 7: Choose 2
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
after
executed line
L7
outer frame
values=[1,2] · path=P · answers
path P
[2]
saved objects
[A0=[]]
Step 8: Include 2
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1,2]
phase
call
executed line
L8
outer frame
values=[1,2] · path=P · answers
path P
[2]
saved objects
[A0=[]]
Step 9: Save A1
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1,2]
phase
after
executed line
L4
outer frame
values=[1,2] · path=P · answers
path P
[2]
saved objects
[A0=[], A1=[2]]
Step 10: Return leaf
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
return
executed line
L5
outer frame
values=[1,2] · path=P · answers
path P
[2]
saved objects
[A0=[], A1=[2]]
Step 11: Undo 2
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
after
executed line
L9
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[A0=[], A1=[2]]
Step 12: Return search(1)
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0]
phase
return
executed line
L9
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[A0=[], A1=[2]]
Step 13: Choose 1
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0]
phase
after
executed line
L7
outer frame
values=[1,2] · path=P · answers
path P
[1]
saved objects
[A0=[], A1=[2]]
Step 14: Include 1
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
call
executed line
L8
outer frame
values=[1,2] · path=P · answers
path P
[1]
saved objects
[A0=[], A1=[2]]
Step 15: Exclude 2
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1,2]
phase
call
executed line
L6
outer frame
values=[1,2] · path=P · answers
path P
[1]
saved objects
[A0=[], A1=[2]]
Step 16: Save A2
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1,2]
phase
after
executed line
L4
outer frame
values=[1,2] · path=P · answers
path P
[1]
saved objects
[A0=[], A1=[2], A2=[1]]
Step 17: Return leaf
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
return
executed line
L5
outer frame
values=[1,2] · path=P · answers
path P
[1]
saved objects
[A0=[], A1=[2], A2=[1]]
Step 18: Choose 2
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
after
executed line
L7
outer frame
values=[1,2] · path=P · answers
path P
[1,2]
saved objects
[A0=[], A1=[2], A2=[1]]
Step 19: Include 2
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1,2]
phase
call
executed line
L8
outer frame
values=[1,2] · path=P · answers
path P
[1,2]
saved objects
[A0=[], A1=[2], A2=[1]]
Step 20: Save A3
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1,2]
phase
after
executed line
L4
outer frame
values=[1,2] · path=P · answers
path P
[1,2]
saved objects
[A0=[], A1=[2], A2=[1], A3=[1,2]]
Step 21: Return leaf
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
return
executed line
L5
outer frame
values=[1,2] · path=P · answers
path P
[1,2]
saved objects
[A0=[], A1=[2], A2=[1], A3=[1,2]]
Step 22: Undo 2
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
after
executed line
L9
outer frame
values=[1,2] · path=P · answers
path P
[1]
saved objects
[A0=[], A1=[2], A2=[1], A3=[1,2]]
Step 23: Return search(1)
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0]
phase
return
executed line
L9
outer frame
values=[1,2] · path=P · answers
path P
[1]
saved objects
[A0=[], A1=[2], A2=[1], A3=[1,2]]
Step 24: Undo 1
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0]
phase
after
executed line
L9
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[A0=[], A1=[2], A2=[1], A3=[1,2]]
Step 25: Return search(0)
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[]
phase
return
executed line
L9
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[A0=[], A1=[2], A2=[1], A3=[1,2]]
Step 26: Return result
The outer frame returns four independent snapshots; the working path was restored before return.
search stack
outer returns
phase
return
executed line
L12
outer frame
values=[1,2] · path=P · answers
path P
not live
saved objects
result=[[],[2],[1],[1,2]]

values = []

Step 1: Initialize outer frame
answers and path P are separate empty lists.
search stack
[]
phase
after
outer frame
values=[] · path=P · answers=[]
path P
[]
Step 2: Call search(0)
Index zero already equals input length.
search stack
[0]
phase
call
outer frame
values=[] · path=P · answers
path P
[]
Step 3: Save A0
path.copy() creates a saved object distinct from P.
search stack
[0]
phase
after
path P
[]
saved objects
[A0=[]]
Step 4: Return search(0)
No choice or restoration is needed.
search stack
[]
phase
return
path P
[]
saved objects
[A0=[]]
Step 5: Return result
The outer frame returns one independent empty subset.
phase
return
outer frame
returns
path P
not live
saved objects
result=[[]]

Trace subset backtracking

Follow the choice path, recursive frames, and restored state across the verified search.

38 verified steps

The interactive code-and-state view loads only when requested or near the viewport.

Deeper note and related practice

Memoization removes repeated subproblems, not recursion depth; a bottom-up formulation can preserve the recurrence without call-stack growth.

Linked lists and trees#

Module 14 of 16

Node problems are reference problems. Preserve the next edge before rewiring a list, and choose recursive or iterative tree traversal based on depth.

Objectives

Dummy nodes simplify head changes.
A traversal should define whether identity or value determines visited state.
Avoid recursive list concatenation that repeatedly copies growing results.

PrerequisitesP02, P07, and P12 · References, queues, and recursion.

Linear preorder accumulationpython

# example: P14-tree-preorder
class TreeNode:
    def __init__(self, value: int, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def preorder(root: TreeNode | None) -> list[int]:
    result: list[int] = []
    def visit(node: TreeNode | None) -> None:
        if node is None:
            return
        result.append(node.value)
        visit(node.left)
        visit(node.right)
    visit(root)
    return result

root = TreeNode(4, TreeNode(2), TreeNode(7))
assert preorder(root) == [4, 2, 7]
assert preorder(None) == []

Expected: The compatible TreeNode example constructs a binary tree; each node appends once and no recursive result lists are concatenated.

Reverse links without losing the suffixpython

# example: P14-list-reversal
class ListNode:
    def __init__(self, value: int, next: "ListNode | None" = None):
        self.value = value
        self.next = next

def reverse(head: ListNode | None) -> ListNode | None:
    previous = None
    current = head
    while current is not None:
        following = current.next
        current.next = previous
        previous, current = current, following
    return previous

head = reverse(ListNode(1, ListNode(2)))
assert head is not None and head.value == 2
assert head.next is not None and head.next.value == 1 and head.next.next is None

Expected: The same two nodes return in reverse order, with the old head terminating the list.

Worked trace

A linked-list update redirects references without copying node values. Tree traversal returns one result list rather than repeatedly concatenating subtree lists.

PitfallRepeated left + [value] + right can copy accumulated traversal results and become quadratic on skewed trees.

BoundariesDistinguish a missing node from a node whose value is falsy. Handle empty heads/roots and decide whether repeated or cyclic references are legal.

Cost modelO(n) time and O(h) active traversal stack, plus O(n) returned output.

TakeawayReason about node identity and pointer ownership separately from stored values.

Deeper note and related practice

Repeated list concatenation across recursive returns can copy growing partial outputs; append into one owned result when order permits.

Graphs and grids#

Module 15 of 16

Choose adjacency storage for dense indices or arbitrary keys, validate starts, and make the grid shape/passability contract explicit.

Objectives

Mark visited on enqueue for BFS.
A rectangular grid contract should define empty, ragged, blocked, and out-of-range inputs.
The frontier bound is O(V), not O(E), for a standard vertex-once traversal.

PrerequisitesP05, P07, and P12 · Hashing, queues, and recursion.

Validated BFS discovery orderpython

# example: P15-keyed-bfs
from collections import deque

def bfs_keys(graph: dict[str, list[str]], start: str) -> list[str]:
    queue = deque([start])
    seen = {start}
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in seen:
                seen.add(neighbor)
                queue.append(neighbor)
    return order

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"]}
assert bfs_keys(graph, "A") == ["A", "B", "C", "D"]
assert bfs_keys({}, "Z") == ["Z"]

Expected: Returns deterministic discovery order; a missing key represents a vertex with no outgoing edges.

Worked trace

BFS marks the start before enqueueing, records discovery order, and marks each neighbor when enqueued so a vertex enters the frontier once.

PitfallDo not describe discovery order as distance unless you actually record levels or parent distances.

BoundariesValidate the start index. For grids, define empty, ragged, blocked, and out-of-range behavior before traversing.

Cost modelO(V + E) time and O(V) visited/frontier space for adjacency lists.

TakeawayChoose adjacency storage for the identifier domain and mark visited at the moment that prevents duplicate work.

Deeper note and related practice

Discovery order is not automatically distance output or a unique topological order; record the additional state the prompt actually asks for.

Pattern toolbox and transfer#

Module 16 of 16

Use templates as recall scaffolds, then restate the invariant and adapt the boundaries to the actual prompt.

Objectives

Confirm allowed standard-library modules.
Test empty, singleton, duplicate, negative, tie, and boundary inputs relevant to the contract.
Return to the roadmap for recognition practice rather than memorizing syntax in isolation.

PrerequisitesP01–P15 as applicable to the selected pattern.

Dependable interview helperspython

# example: P16-toolbox
from itertools import accumulate, combinations
from math import gcd, isqrt

prefix = list(accumulate([3, -1, 4], initial=0))
assert prefix == [0, 3, 2, 6]
assert prefix[3] - prefix[1] == 3
assert list(combinations([1, 2, 3], 2)) == [(1, 2), (1, 3), (2, 3)]
assert gcd(18, 24) == 6
assert isqrt(26) == 5

Expected: accumulate includes the initial empty prefix, combinations yields three pairs, gcd returns 6, and isqrt floors √26 to 5.

Worked trace

accumulate starts with the explicit zero prefix, then produces 3, 2, and 6; subtracting boundaries gives the sum over a half-open range. combinations produces three distinct position pairs, while gcd and isqrt return exact integers.

PitfallA copied template is not an answer until its interval, mutation, and empty-input policies match the prompt.

BoundariesConfirm allowed libraries. An explicit initial zero makes prefix boundaries visible; combinations can produce large output, while gcd and isqrt require integer-domain reasoning.

Cost modelaccumulate is O(n) for n outputs; generating r combinations costs O(r) tuple outputs; integer gcd/isqrt costs depend on operand bit length.

TakeawayTemplates are recall scaffolds; the invariant and boundary contract make them an answer.

Deeper note and related practice

Iterator helpers defer production but do not erase output work. Prefer the simplest adequate helper or pattern and explain its domain and result contract.

Common interview templates#

These fifteen executable contracts are recall aids, not proprietary answers. Open the pattern you need, then adapt its invariant and boundaries.

Two PointersPrecondition: nums is sorted ascending. Use when a comparison can discard one boundary at a time.

Use when: Precondition: nums is sorted ascending. Use when a comparison can discard one boundary at a time.

Typical complexity: O(n) time and O(1) extra space.

Two Pointers templatepython

# example: T01-sorted-two-sum
def sorted_pair_sum(nums: list[int], target: int) -> tuple[int, int] | None:
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return left, right
        if total < target:
            left += 1
        else:
            right -= 1
    return None

assert sorted_pair_sum([1, 2, 4, 7], 6) == (1, 2)
assert sorted_pair_sum([1, 2, 4, 7], 3) == (0, 1)
assert sorted_pair_sum([], 3) is None

Sliding WindowPrecondition: every value is nonnegative. Use when an over-limit window can shrink monotonically.

Use when: Precondition: every value is nonnegative. Use when an over-limit window can shrink monotonically.

Typical complexity: O(n) time and O(1) extra space when every value is nonnegative.

Sliding Window templatepython

# example: T02-longest-bounded-window
def longest_sum_at_most(nums: list[int], limit: int) -> int:
    if any(value < 0 for value in nums):
        raise ValueError("nums must be nonnegative")
    left = 0
    answer = 0
    window_sum = 0
    for right, value in enumerate(nums):
        window_sum += value
        while left <= right and window_sum > limit:
            window_sum -= nums[left]
            left += 1
        answer = max(answer, right - left + 1)
    return answer

assert longest_sum_at_most([1, 2, 1, 0, 1], 3) == 3
assert longest_sum_at_most([], 3) == 0
try:
    longest_sum_at_most([1, -1], 3)
except ValueError:
    pass
else:
    raise AssertionError("negative input must be rejected")

Binary SearchPrecondition: nums is sorted ascending. Return the first insertion boundary, which may equal len(nums).

Use when: Precondition: nums is sorted ascending. Return the first insertion boundary, which may equal len(nums).

Typical complexity: O(log n) comparisons and O(1) space.

Binary Search templatepython

# example: T03-lower-bound
def lower_bound(nums: list[int], target: int) -> int:
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

assert lower_bound([1, 3, 3, 7], 3) == 1
assert lower_bound([1, 3, 3, 7], 9) == 4
assert lower_bound([], 3) == 0

BFSPrecondition: graph is a dense adjacency list with valid neighbor IDs. Return discovery order from a valid start; an empty graph returns [], while an invalid start in a nonempty graph raises ValueError.

Use when: Precondition: graph is a dense adjacency list with valid neighbor IDs. Return discovery order from a valid start; an empty graph returns [], while an invalid start in a nonempty graph raises ValueError.

Typical complexity: O(V + E) time and O(V) frontier/visited space.

BFS templatepython

# example: T04-bfs-order
from collections import deque

def bfs(graph: list[list[int]], start: int = 0) -> list[int]:
    if not graph:
        return []
    if not 0 <= start < len(graph):
        raise ValueError("invalid start")
    queue, seen, order = deque([start]), {start}, []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                queue.append(neighbor)
    return order

graph = [[1, 2], [3], [3], []]
assert bfs(graph, 0) == [0, 1, 2, 3]
assert bfs([]) == []
try:
    bfs(graph, -1)
except ValueError:
    pass
else:
    raise AssertionError("invalid nonempty start must be rejected")

DFSPrecondition: graph is a dense adjacency list with valid neighbor IDs. Use iterator frames for deterministic recursive-style order without recursive depth.

Use when: Precondition: graph is a dense adjacency list with valid neighbor IDs. Use iterator frames for deterministic recursive-style order without recursive depth.

Typical complexity: O(V + E) time and O(V) stack/visited space; each live iterator is part of the frontier.

DFS templatepython

# example: T05-iterator-dfs
def dfs(graph: list[list[int]], start: int = 0) -> list[int]:
    if not graph:
        return []
    if not 0 <= start < len(graph):
        raise ValueError("invalid start")
    stack = [(start, iter(graph[start]))]
    seen, order = {start}, [start]
    while stack:
        node, neighbors = stack[-1]
        try:
            neighbor = next(neighbors)
        except StopIteration:
            stack.pop()
            continue
        if neighbor not in seen:
            seen.add(neighbor)
            order.append(neighbor)
            stack.append((neighbor, iter(graph[neighbor])))
    return order

graph = [[1, 2], [3], [3], []]
assert dfs(graph, 0) == [0, 1, 3, 2]
assert dfs([]) == []
try:
    dfs(graph, 4)
except ValueError:
    pass
else:
    raise AssertionError("invalid nonempty start must be rejected")

Tree DFSPrecondition: a finite acyclic binary tree with no shared child nodes and recursion-safe height. Height counts nodes.

Use when: Precondition: a finite acyclic binary tree with no shared child nodes and recursion-safe height. Height counts nodes.

Typical complexity: O(n) time and O(h) call-stack space.

Tree DFS templatepython

# example: T06-tree-depth
class TreeNode:
    def __init__(self, value: int, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def tree_depth(node: TreeNode | None) -> int:
    if not node:
        return 0
    left_depth = tree_depth(node.left)
    right_depth = tree_depth(node.right)
    return 1 + max(left_depth, right_depth)

root = TreeNode(4, TreeNode(2), TreeNode(7))
assert tree_depth(root) == 2
assert tree_depth(TreeNode(4)) == 1
assert tree_depth(None) == 0

Tree BFSPrecondition: a finite acyclic binary tree with no shared child nodes. Return values grouped by distance from the root.

Use when: Precondition: a finite acyclic binary tree with no shared child nodes. Return values grouped by distance from the root.

Typical complexity: O(n) time, O(w) queue space, and O(n) returned output.

Tree BFS templatepython

# example: T07-tree-levels
from collections import deque

class TreeNode:
    def __init__(self, value: int, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def tree_levels(root: TreeNode | None) -> list[list[int]]:
    if not root:
        return []
    queue, result = deque([root]), []
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.value)
            for child in (node.left, node.right):
                if child:
                    queue.append(child)
        result.append(level)
    return result

root = TreeNode(4, TreeNode(2), TreeNode(7))
assert tree_levels(root) == [[4], [2, 7]]
assert tree_levels(None) == []

BacktrackingPrecondition: enumerate subsets of input positions in exclude-first order. Each call restores path to its own entry state, which may be nonempty.

Use when: Precondition: enumerate subsets of input positions in exclude-first order. Each call restores path to its own entry state, which may be nonempty.

Typical complexity: O(n·2ⁿ) time/output for this subsets contract and O(n) active path/stack space excluding output.

Backtracking templatepython

# example: P13-subsets
def subsets(values: list[int]) -> list[list[int]]:
    answers, path = [], []
    def search(index: int) -> None:
        if index == len(values):
            answers.append(path.copy())
            return
        search(index + 1)
        path.append(values[index])
        search(index + 1)
        path.pop()
    search(0)
    return answers

assert subsets([1, 2]) == [[], [2], [1], [1, 2]]
assert subsets([]) == [[]]

Heap / Top KPrecondition: numeric values; duplicates count separately. Return the largest k values ascending; oversized k returns all sorted.

Use when: Precondition: numeric values; duplicates count separately. Return the largest k values ascending; oversized k returns all sorted.

Typical complexity: O(n log(min(k,n)+1) + min(k,n) log(min(k,n)+1)) time and O(min(k,n)) heap/output space.

Heap / Top K templatepython

# example: T09-numeric-top-k
import heapq

def top_k(nums: list[int], k: int) -> list[int]:
    if k < 0:
        raise ValueError("k must be nonnegative")
    if k == 0:
        return []
    heap: list[int] = []
    for value in nums:
        heapq.heappush(heap, value)
        if len(heap) > k:
            heapq.heappop(heap)
    return sorted(heap)

assert top_k([5, 1, 8, 2, 7], 3) == [5, 7, 8]
assert top_k([4, 4, 1], 2) == [4, 4]
assert top_k([2, 1], 8) == [1, 2]
assert top_k([], 3) == [] and top_k([1], 0) == []
try:
    top_k([1], -1)
except ValueError:
    pass
else:
    raise AssertionError("negative k must be rejected")

Prefix SumPrecondition: 0 ≤ left ≤ right ≤ len(nums), and prefix came from nums. Query the half-open interval [left, right).

Use when: Precondition: 0 ≤ left ≤ right ≤ len(nums), and prefix came from nums. Query the half-open interval [left, right).

Typical complexity: O(n) preprocessing and O(1) per range query.

Prefix Sum templatepython

# example: T10-prefix-sum
def prefix_sums(nums: list[int]) -> list[int]:
    prefix = [0]
    for value in nums:
        prefix.append(prefix[-1] + value)
    return prefix

def range_sum(prefix: list[int], left: int, right: int) -> int:
    """Return the sum over the half-open interval [left, right)."""
    if not 0 <= left <= right < len(prefix):
        raise ValueError("invalid half-open range")
    return prefix[right] - prefix[left]

prefix = prefix_sums([2, -1, 4])
assert prefix == [0, 2, 1, 5]
assert range_sum(prefix, 0, 0) == 0
assert range_sum(prefix, 1, 3) == 3
try:
    range_sum(prefix, 3, 2)
except ValueError:
    pass
else:
    raise AssertionError("invalid half-open range must be rejected")

Monotonic StackPrecondition: return the next strictly greater index; equal values do not satisfy the boundary.

Use when: Precondition: return the next strictly greater index; equal values do not satisfy the boundary.

Typical complexity: O(n) time and O(n) space.

Monotonic Stack templatepython

# example: T11-next-greater
def next_greater(nums: list[int]) -> list[int]:
    answer = [-1] * len(nums)
    stack: list[int] = []
    for i, value in enumerate(nums):
        while stack and nums[stack[-1]] < value:
            answer[stack.pop()] = i
        stack.append(i)
    return answer

assert next_greater([2, 1, 2, 4, 3]) == [3, 2, 3, -1, -1]
assert next_greater([2, 2]) == [-1, -1]
assert next_greater([]) == []

Union FindPrecondition: nodes are dense integers in [0, n). Use when edges merge components and duplicate unions should return false.

Use when: Precondition: nodes are dense integers in [0, n). Use when edges merge components and duplicate unions should return false.

Typical complexity: Near-constant amortized operations with path compression and rank.

Union Find templatepython

# example: T12-union-find
class UnionFind:
    def __init__(self, n: int):
        if n < 0:
            raise ValueError("n must be nonnegative")
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n

    def find(self, node: int) -> int:
        while node != self.parent[node]:
            self.parent[node] = self.parent[self.parent[node]]
            node = self.parent[node]
        return node

    def union(self, first: int, second: int) -> bool:
        root_a, root_b = self.find(first), self.find(second)
        if root_a == root_b:
            return False
        if self.rank[root_a] < self.rank[root_b]:
            root_a, root_b = root_b, root_a
        self.parent[root_b] = root_a
        if self.rank[root_a] == self.rank[root_b]:
            self.rank[root_a] += 1
        self.components -= 1
        return True

groups = UnionFind(6)
for edge in ((0, 1), (1, 2), (3, 4), (2, 4)):
    assert groups.union(*edge) is True
assert groups.components == 2 and groups.find(0) == groups.find(4)
assert groups.union(0, 4) is False and groups.components == 2
assert UnionFind(0).components == 0
try:
    UnionFind(-1)
except ValueError:
    pass
else:
    raise AssertionError("negative n must be rejected")

Topological SortPrecondition: graph is a dense directed adjacency list with valid neighbor IDs. None reports a cycle; [] is the valid order for an empty graph.

Use when: Precondition: graph is a dense directed adjacency list with valid neighbor IDs. None reports a cycle; [] is the valid order for an empty graph.

Typical complexity: O(V + E) time and O(V) space.

Topological Sort templatepython

# example: T13-topological-order
from collections import deque

def topological_order(graph: list[list[int]]) -> list[int] | None:
    indegree = [0] * len(graph)
    for neighbors in graph:
        for neighbor in neighbors:
            indegree[neighbor] += 1
    queue = deque(i for i, degree in enumerate(indegree) if degree == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    return order if len(order) == len(graph) else None

assert topological_order([[1, 2], [3], [3], []]) == [0, 1, 2, 3]
assert topological_order([[1], [0]]) is None
assert topological_order([]) == []

1-D Dynamic ProgrammingContract: choose nonadjacent positions; choosing none is allowed, so negative-only input returns zero.

Use when: Contract: choose nonadjacent positions; choosing none is allowed, so negative-only input returns zero.

Typical complexity: O(n) time and O(1) accumulator space.

1-D Dynamic Programming templatepython

# example: T14-nonadjacent-total
def best_total(values: list[int]) -> int:
    previous_two = 0
    previous_one = 0
    for value in values:
        current = max(previous_one, previous_two + value)
        previous_two, previous_one = previous_one, current
    return previous_one

assert best_total([2, 7, 9, 3, 1]) == 12
assert best_total([-5, -2]) == 0
assert best_total([]) == 0

Grid TraversalContract: rectangular 0/1 grid, four-direction moves, and only value 1 is passable - including the start. Empty, blocked, or out-of-range starts return empty; ragged input raises.

Use when: Contract: rectangular 0/1 grid, four-direction moves, and only value 1 is passable - including the start. Empty, blocked, or out-of-range starts return empty; ragged input raises.

Typical complexity: O(rows + rows × cols) validation/traversal time and O(rows × cols) space in the worst case.

Grid Traversal templatepython

# example: T15-grid
from collections import deque

def visit_grid(grid: list[list[int]], start_row: int, start_col: int) -> set[tuple[int, int]]:
    rows = len(grid)
    if rows == 0:
        return set()
    cols = len(grid[0])
    if any(len(row) != cols for row in grid):
        raise ValueError("grid must be rectangular")
    if not (0 <= start_row < rows and 0 <= start_col < cols):
        return set()
    if grid[start_row][start_col] != 1:
        return set()
    queue = deque([(start_row, start_col)])
    seen = {(start_row, start_col)}
    while queue:
        row, col = queue.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = row + dr, col + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in seen:
                seen.add((nr, nc))
                queue.append((nr, nc))
    return seen

assert visit_grid([[1, 0], [1, 1]], 0, 0) == {(0, 0), (1, 0), (1, 1)}
assert visit_grid([], 0, 0) == set()
assert visit_grid([[]], 0, 0) == set()
assert visit_grid([[0]], 0, 0) == set()
assert visit_grid([[2]], 0, 0) == set()
assert visit_grid([[1]], -1, 0) == set()
try:
    visit_grid([[1], [1, 0]], 0, 0)
except ValueError:
    pass
else:
    raise AssertionError("ragged grid must be rejected")

Common interview mistakes#

Using pop(0) for a queue

It shifts the remaining list and costs O(n). Use deque.popleft().

Aliasing a 2-D list

[[0] * cols] * rows repeats references to one inner list. Build each row independently.

Forgetting string immutability

Accumulate many characters in a list and join once.

Confusing / and //

/ returns floating-point division; // performs floor division.

Treating heapq as a max heap

heapq is a min-heap. Use an intentional max-heap strategy for the supported runtime.

Ignoring recursion depth

A very deep DFS can exceed Python’s recursion limit; use an explicit stack when depth is unbounded.

Costly slicing inside loops

A slice copies its elements. Repeated large slices can turn an intended linear solution quadratic.

Unsafe heap tuple ties

When priorities tie, Python compares later tuple fields. Add a deterministic numeric tie-breaker when payloads are not comparable.

Mutating while iterating

Iterate over a copy or collect updates separately when structural mutation would change traversal behavior.

Broken and corrected examples#

Each repair keeps its failure visible beside the executable correction and its regression case.

FIFO without repeated shifts

Failure: Deleting index zero shifts every remaining list element and can make a BFS quadratic.

Regression case: Process a wide frontier and assert every node is visited once while the implementation uses deque.popleft.

Brokenpython

# Broken: index-zero removal shifts every remaining reference.
queue = [2, 4, 6]
order = []
while queue:
    order.append(queue.pop(0))

Correctedpython

# Corrected: deque removes from the left without list shifts.
from collections import deque

queue = deque([2, 4, 6])
order = []
while queue:
    order.append(queue.popleft())
assert order == [2, 4, 6]

Independent grid rows

Failure: Every outer entry references the same row, so one cell update leaks into other rows.

Regression case: Set grid[0][0] and assert grid[1][0] remains zero.

Brokenpython

# Broken: both outer entries refer to the same row.
grid = [[0] * 2] * 2
grid[0][0] = 7
assert grid == [[7, 0], [7, 0]]

Correctedpython

# Corrected: construct each row in a separate comprehension iteration.
grid = [[0] * 2 for _ in range(2)]
grid[0][0] = 7
assert grid == [[7, 0], [0, 0]]

Count earlier prefixes before updating

Failure: Updating first lets the current prefix count itself when target is zero.

Regression case: For nums=[0] and target=0, return one subarray, not two; signed inputs remain valid.

Brokenpython

# Broken loop body: recording first lets the current prefix count itself.
prefix += value
seen[prefix] = seen.get(prefix, 0) + 1
answer += seen.get(prefix - target, 0)

Correctedpython

# Complete executable correction: query earlier prefixes first.
def count_target_subarrays(nums: list[int], target: int) -> int:
    seen = {0: 1}
    prefix = 0
    answer = 0
    for value in nums:
        prefix += value
        answer += seen.get(prefix - target, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return answer

assert count_target_subarrays([0], 0) == 1
assert count_target_subarrays([0, 0], 0) == 3
assert count_target_subarrays([2, -2, 2], 2) == 3

Debugging checklist#

Restate the invariant and trace the smallest failing input before changing code.
Check aliasing, mutable defaults, slice copies, and whether a nested container shares references.
Verify every index boundary and whether binary-search intervals are closed or half-open.
Inspect queue and heap operations for an accidental O(n) front removal or reversed priority.
Test empty, singleton, duplicate, negative, and depth-heavy inputs; replace recursion when depth is not bounded.

Questions about the language#

These are reasonable discussion prompts, not claims about every interviewer or company.

Why dict and set keys must be hashable, and what mutation would invalidate a key model.
When deque is a better queue than list and when list remains better for indexed access.
What slicing and repeated string concatenation allocate.
How tuple ordering affects heap tie-breaking and what happens when payloads are incomparable.
When recursion depth makes an iterative traversal safer.

Language transfer exercises#

The five existing checks remain concealed until you choose to open them.

predict
Find the alias
Predict which cells change after grid = [[0] * 2] * 2; grid[0][1] = 7, and explain why.
Answer check
Both rows show 7 in column 1 because the outer list contains two references to the same inner list.
trace
Trace one BFS layer
Using deque, trace queue and visited state when A connects to B and C and both connect to D. Mark when visited changes.
Answer check
Mark on enqueue: start [A]/{A}; after A, [B,C]/{A,B,C}; after B, [C,D]/{A,B,C,D}; C must not enqueue D again.
repair
Repair the queue
A BFS repeatedly calls items.pop(0). Replace only the queue mechanics and state the complexity change.
Answer check
Use collections.deque with popleft; front removal changes from O(n) shifting to approximately O(1).
choose
Choose a container
Choose list, set, dict, deque, or heap for membership, stable append order, FIFO removal, and retaining the smallest k boundary.
Answer check
Set for membership, list for indexed append order, deque for FIFO, and a bounded max-heap strategy for retaining the smallest k.
transfer
Unlabeled transfer
Given a stream of events, keep the three highest priorities while preserving a deterministic order among ties. Name the stored tuple and test one tie.
Answer check
Use a size-three min-heap with a numeric tie-breaker such as (priority, sequence, event); never let Python compare non-orderable event payloads.

Reach this point to mark the lesson as read.

ReviewedSeptember 5, 2026

Compatibility floorPython 3.11+

Fixture evidencePython 3.12.9 locally; hosted CI provisions and requires Python 3.11 for the compatibility floor.

Source notes

Python 3.11 data modelObjects, identity, and mutability.
Python copy semanticsAssignment and shallow/deep copy boundaries.
Python data structuresLists, tuples, sets, queues, and comprehensions.
Python built-in typesDictionary order and sequence/string semantics.
Python glossaryHashability, iterators, and annotations.
Python control flowFunctions, loops, and range conventions.
Python programming FAQShared defaults and language pitfalls.
Python collectionsCounter, defaultdict, and deque contracts.
Python 3.11 heapqPortable min-heap and tuple tie behavior.
Python 3.14 heapq differencesVersion boundary for public max-heap APIs.
Python bisectPartitions, key behavior, and insertion cost.
Python Sorting HOWTOStable keys and sort versus sorted.
Python functoolsCache hashability and lifetime policies.
Python sysRecursion limits and measurement caveats.
Python expressionsDivision, modulo, and expression semantics.
Python Unicode HOWTOCode points versus displayed characters.
Python built-in functionsIteration and conversion contracts.
Python itertoolspairwise, accumulate, and combinations.
Python mathgcd and isqrt domains.
CPython operation costsBuilt-in costs, amortization, and hash qualifications.
CPython listsort notesSorting auxiliary-workspace qualification.
CPython integer objectsMulti-digit integer representation.
PyPy string concatenation analysisGeneral copying model and CPython optimization caveat.
Princeton union-find referenceRank plus path-halving amortized bound.
Algorithm visualization meta-studyHistorical visualization research context; not an outcome claim for these players.
WCAG keyboard understandingKeyboard functionality.
WCAG reflow understanding320 CSS-pixel reflow boundary and exceptions.
WCAG target-size understanding24px minimum criterion; this product chooses 44px player controls.
WCAG interaction-animation understandingReduced spatial motion; no AA conformance claim is inferred.

Input and output conventions#

Function interview: Implement the requested function with typed parameters where useful. Return the requested value; do not parse stdin unless the prompt says to.
Online assessment: Follow the provider's exact stdin/stdout contract, avoid debug output, and confirm whether one or many cases are supplied.

Python interview sequence#

Read in order for a full review, or jump to the contract behind a syntax decision. This is one guide - not sixteen new routes.

Quick reference#

Compact recall cards point back to their full contract. They are not a separate source of truth.

Iteration and ordering

Use only when ordering and materialization costs match the contract.

for index, value in enumerate(values): ...
for left, right in zip(values, values[1:]): ...
ordered = sorted(values, key=lambda value: value)

Read the full lesson

Counting and adjacency

Keys must be hashable; choose dense lists or arbitrary-key dictionaries deliberately.

from collections import Counter, defaultdict
counts = Counter(values)
graph = defaultdict(list)

Read the full lesson

Queue and heap

Use deque for FIFO and a numeric tie-breaker before incomparable heap payloads.

queue = deque([start]); node = queue.popleft()
heappush(heap, (priority, sequence, payload))

Read the full lesson

Sorted boundaries

Input must be sorted; returned positions may equal len(values).

left = bisect_left(values, target)
right = bisect_right(values, target)  # duplicate run [left, right)

Read the full lesson

Contracts, functions, and input#

Module 1 of 16

Start with the caller's contract: accepted values, mutation permission, return shape, and whether the platform owns input and output.

Objectives

Type hints communicate intent but do not enforce inputs at runtime.
A function interview usually supplies values directly; an online assessment may own stdin and stdout.
Name empty, negative, duplicate, and mutation behavior before choosing a structure.

PrerequisitesVariables, conditions, loops, and functions in any language.

A bounded function contractpython

# example: P01-positive-total
def positive_total(values: list[int]) -> int:
    """Return the sum of positive values without mutating values."""
    total = 0
    for value in values:
        if value > 0:
            total += value
    return total

data = [4, -2, 0, 7]
assert positive_total(data) == 11
assert positive_total([]) == 0
assert data == [4, -2, 0, 7]

Expected: Returns 11, then 0; the input remains unchanged.

Assessment input contractpython

# example: P01-assessment-contract
def solve(text: str) -> str:
    tokens = text.split()
    if not tokens:
        raise ValueError("expected n and then n integers")
    n = int(tokens[0])
    if n < 0 or len(tokens) != n + 1:
        raise ValueError("wrong number of values")
    answer = sum(value for value in map(int, tokens[1:]) if value > 0)
    return str(answer) + "\n"

assert solve("4\n4 -2 0 7\n") == "11\n"
assert solve("0\n") == "0\n"

Expected: Returns one newline-terminated answer and rejects a mismatched token count.

Worked trace

The accumulator starts at zero. Each positive value extends the processed-prefix total; nonpositive values leave it unchanged. Returning after the loop also covers empty input.

PitfallDo not add stdin parsing to a function contract unless the prompt asks for it.

BoundariesSeparate function-style return contracts from assessment stdin/stdout contracts. State empty-input, negative-value, and mutation behavior before coding.

Cost modelO(n) time in the worst case and O(1) working memory.

TakeawayEstablish the caller's contract before selecting syntax or a container.

Deeper note and related practice

Defensive parsing for a reusable utility and assumed-valid input in an interview are different contracts; say which one you implement.

Names, objects, and mutation#

Module 2 of 16

Assignment binds a name to an object. It does not copy that object, so aliases observe mutation while rebinding changes only one name.

Objectives

Use == for value equality and is None for the absence sentinel.
Construct mutable defaults inside the function.
State whether a helper mutates, returns a copy, or transfers ownership.

PrerequisitesP01 · Contracts, functions, and input.

Mutation versus rebindingpython

# example: P02-bindings
a = [2, 4]
b = a
b.append(6)
assert a == [2, 4, 6] and a is b

b = [9]
c = [2, 4, 6]
assert a == c and a is not c
assert b == [9] and a == [2, 4, 6]

Expected: The append is visible through both aliases; rebinding b leaves a on the original list.

Fresh mutable state per callpython

# example: P02-fresh-default
def record(value: int, items: list[int] | None = None) -> list[int]:
    if items is None:
        items = []
    items.append(value)
    return items

assert record(2) == [2]
assert record(4) == [4]
owned = [1]
assert record(3, owned) is owned
assert owned == [1, 3]

Expected: Default calls own separate lists; an explicitly supplied list is mutated by contract.

Worked trace

a and b first refer to one list. Mutation changes that object for both names; rebinding b creates another list while a keeps its original reference.

PitfallA mutable default can retain state across calls. Use None, then allocate per call.

BoundariesUse value equality for values and identity only for sentinels or deliberate object-identity questions. Never infer behavior from integer or string interning.

Cost modelBinding and identity checks are O(1); equality may inspect the compared values.

TakeawayAsk which object is changing and which names currently reach it.

Names point to objects

Separate identity from equality while mutation and rebinding happen.

V01 · P02-references@2026-09-05

a = [2, 4]
b = a
b.append(6)
b = [9]
c = [2, 4, 6]
same_value = a == c
same_object = a is c

Step 1 of 8 · initialBefore binding

No names or list objects exist yet.

Names and values

No example names are bound.

Objects

No list objects exist in this teaching view.

Speed

Read all steps

Alias and rebind

Step 1: Before binding
No names or list objects exist yet.
names
Not available
objects
Not available
Step 2: Bind a
a points to list object L1.
a
→ L1
L1
[2, 4]
Step 3: Alias b
b points to the same L1 object; no copy occurs.
a
→ L1
b
→ L1
L1
[2, 4]
Step 4: Mutate through b
L1 changes, so both names observe the new value.
a
→ L1
b
→ L1
L1
[2, 4, 6]
Step 5: Rebind b
b now points to a new list L2; a still points to L1.
a
→ L1
b
→ L2
L1
[2, 4, 6]
L2
[9]
Step 6: Bind equal c
c points to distinct L3 with the same value as L1.
a
→ L1
b
→ L2
c
→ L3
L3
[2, 4, 6]
Step 7: Compare value
a and c contain equal values.
same_value
True
a
→ L1
c
→ L3
Step 8: Compare identity
Equal values do not make L1 and L3 the same object.
same_object
False
a
→ L1
b
→ L2
c
→ L3

Reverse a linked list

Follow each reference reassignment against the verified Python execution.

11 verified steps

The interactive code-and-state view loads only when requested or near the viewport.

Deeper note and related practice

Equality methods can be customized; the worked trace intentionally uses ordinary built-in lists.

Lists, tuples, and copies#

Module 3 of 16

Lists provide mutable indexed slots; tuples fix their slots but may still contain mutable objects. A shallow copy duplicates only the outer container.

Objectives

append and end-pop make a list a useful stack.
A slice of k elements allocates a new outer list containing k references.
Build nested rows independently when mutations must not leak.

PrerequisitesP02 · Names, objects, and mutation.

Independent matrix rowspython

# example: P03-nested-copy
from copy import deepcopy

rows = [[0, 0], [0, 0]]
shallow = rows.copy()
deep = deepcopy(rows)
rows[0][1] = 7
assert shallow == [[0, 7], [0, 0]]
assert deep == [[0, 0], [0, 0]]
assert shallow is not rows and shallow[0] is rows[0]
assert deep[0] is not rows[0]
safe = [[0] * 2 for _ in range(2)]
safe[0][1] = 7
assert safe == [[0, 7], [0, 0]]
container = ([1],)
container[0].append(2)
assert container == ([1, 2],)

Expected: The shallow copy shares rows, the deep copy does not, and independently constructed rows isolate mutation.

Worked trace

A shallow copy creates a new outer list but retains its child references. Independently constructed rows receive distinct identities, so one cell update stays local.

Pitfall[[0] * cols] * rows repeats one row reference; it does not create independent rows.

BoundariesIndexes can raise; slices clamp. Empty and singleton inputs are valid. Tuple slots are fixed, but a mutable object inside a tuple can still change.

Cost modelIndexing and end operations are O(1) amortized; membership and front removal are O(n); a k-item slice is O(k).

TakeawayCopy at the exact ownership level where independence is required.

Shallow versus independent rows

Track the outer list and inner-row identities, not just printed values.

V02 · P03-sequences@2026-09-05

bad = [[0, 0]] * 2
outer_copy = bad.copy()
bad[0][1] = 7
good = [[0, 0] for _ in range(2)]
good[0][1] = 7

Step 1 of 6 · initialInitial state

No example bindings or list objects exist yet.

Names and values

No example names are bound.

Objects

No list objects exist in this teaching view.

Speed

Read all steps

Nested copy

Step 1: Initial state
No example bindings or list objects exist yet.
names
Not available
objects
Not available
Step 2: Repeat one row reference
bad points to O1, whose two slots both refer to the single row R1.
bad
→ O1
O1
[→R1, →R1]
R1
[0, 0]
Step 3: Copy the outer list
outer_copy points to new O2, but O2 retains the same two references to R1.
bad
→ O1
outer_copy
→ O2
O1
[→R1, →R1]
O2
[→R1, →R1]
R1
[0, 0]
Step 4: Mutate shared R1
One object update is visible through four reference paths across O1 and O2.
bad
→ O1
outer_copy
→ O2
O1
[→R1, →R1]
O2
[→R1, →R1]
R1
[0, 7]
Step 5: Build independent rows
good points to O3, whose slots refer to distinct R2 and R3 objects.
good
→ O3
O3
[→R2, →R3]
R2
[0, 0]
R3
[0, 0]
Step 6: Mutate only R2
The selected row changes while R3 and the earlier shared grid retain their prior values.
bad
→ O1
outer_copy
→ O2
good
→ O3
O1
[→R1, →R1]
O2
[→R1, →R1]
O3
[→R2, →R3]
R1
[0, 7]
R2
[0, 7]
R3
[0, 0]

Deeper note and related practice

reverse mutates and returns None, slicing constructs a list, and reversed returns an iterator; those contracts are not interchangeable.

Strings and text construction#

Module 4 of 16

Strings are immutable sequences of Unicode code points. Build many fragments in a list and join once when repeated concatenation would recopy a growing prefix.

Objectives

ASCII-only contracts need explicit ASCII bounds.
Code points, encoded bytes, and user-perceived characters are different units.
Apply normalization or case folding only when the problem permits it.

PrerequisitesP03 · Lists, tuples, and copies.

Text construction and Unicode contractspython

# example: P04-string-building
def join_labels(labels: list[str]) -> str:
    return "|".join(labels)

assert join_labels(["map", "heap", "queue"]) == "map|heap|queue"
assert join_labels([]) == ""

text = "a\u0301"  # a followed by a combining acute accent
assert len(text) == 2  # two Unicode code points
assert [ord(character) for character in text] == [97, 769]
assert len(text.encode("utf-8")) == 3
assert "²".isdigit() and not ("0" <= "²" <= "9")
assert "Straße".casefold() == "strasse"

Expected: Joins labels once; the combining sequence has two code points and three UTF-8 bytes; isdigit and casefold demonstrate non-ASCII behavior.

Worked trace

Pitfallisdigit() accepts more than ASCII 0–9; do not use it for an ASCII-only contract without checking bounds.

BoundariesDefine whether a character means an ASCII code point, a Unicode code point, encoded bytes, or a displayed grapheme. Empty text must remain valid.

Cost modelBuilding m output characters with a list plus join is O(m) time and O(m) returned output.

TakeawayState the text unit and count the output you actually construct.

Deeper note and related practice

Collecting every prefix can still require quadratic total output even when each final join is efficient.

Dictionaries, sets, and counting#

Module 5 of 16

Use dict when a key maps to information and set when membership is enough. Hashability requires a stable hash consistent with equality.

Objectives

Dictionary iteration preserves insertion order; set iteration has no insertion-order promise.
Counter reads a missing key as zero without inserting it.
With prefix counts, query earlier prefixes before recording the current prefix.

PrerequisitesP02–P04 · References, sequences, and strings.

Prefix-frequency orderpython

# example: P05-missing-keys
from collections import Counter, defaultdict

values = [4, 1, 4]
frequency = {}
for value in values:
    frequency[value] = frequency.get(value, 0) + 1
assert frequency == {4: 2, 1: 1}
assert list(frequency) == [4, 1]
counts = Counter(values)
assert counts[9] == 0 and 9 not in counts
counts[9] = 0
assert 9 in counts
groups = defaultdict(list)
assert groups.get("x") is None and "x" not in groups
groups["x"].append(3)
assert dict(groups) == {"x": [3]}
seen = {(0, 1), (1, 0)}
assert (0, 1) in seen

Expected: Missing-key reads and writes have distinct insertion behavior, and dictionary iteration preserves first insertion order.

Worked trace

For prefix counting, query the frequencies of earlier prefixes before recording the current prefix; the seeded zero prefix represents the empty prefix.

PitfallUpdating the frequency before querying lets the current prefix count itself.

BoundariesKeys must be hashable and equality-consistent. Expected constant-time lookup assumes ordinary hashing; collisions and expensive keys need separate qualification.

Cost modelExpected O(n) time and O(n) space under ordinary hash behavior; collision worst cases remain possible.

TakeawayChoose a set for membership and a dictionary when each key carries information.

Deeper note and related practice

Counter's missing-key read does not insert, while defaultdict access can; that difference matters while iterating or checking shape.

Iteration and materialization#

Module 6 of 16

Choose enumerate for index plus value, zip for aligned inputs, and explicit loops when several pieces of state must stay visible.

Objectives

Iterators are consumed; an exhausted generator does not restart.
zip stops at the shortest input unless strict=True is requested.
A lazy consumer does not undo allocations already made by a slice.

PrerequisitesP03 and P05 · Sequences and hashing.

Iteration without hidden slicespython

# example: P06-iteration
from itertools import pairwise

nums = [3, 5, 8]
assert list(enumerate(nums)) == [(0, 3), (1, 5), (2, 8)]
assert list(pairwise(nums)) == [(3, 5), (5, 8)]
assert list(range(4, -1, -2)) == [4, 2, 0]
squared_values = [value * value for value in nums]
assert squared_values == [9, 25, 64]

squares = (value * value for value in nums)
assert next(squares) == 9
assert list(squares) == [25, 64]
assert list(squares) == []

pairs = list(zip([1, 2], ["a"]))
assert pairs == [(1, "a")]

Expected: enumerate supplies indexes, pairwise avoids a sliced suffix, range descends by two, the comprehension materializes squares, and the generator exhausts after one pass.

Worked trace

Pitfallzip(nums, nums[1:]) is lazy only after nums[1:] has already copied the suffix.

Boundarieszip stops at the shortest input unless strict mode is requested. pairwise over zero or one item is empty. A slice allocates before a lazy zip consumes it.

Cost modelIteration is O(n); materializing a result of k items adds O(k) output space.

TakeawayLazy evaluation avoids some materialization, but it is not free and it does not reverse work already performed.

Deeper note and related practice

Do not structurally mutate a collection while iterating unless the algorithm and iterator contract explicitly support it.

Stacks, queues, and deque#

Module 7 of 16

Use list append/end-pop for LIFO and collections.deque for FIFO or operations at both ends.

Objectives

Mark BFS nodes seen when enqueuing them.
A bounded deque drops an item when full; that is usually wrong for a frontier.
Middle indexing is not deque's strength.

PrerequisitesP03 and P06 · Sequences and iteration.

FIFO traversalpython

# example: P07-removal-order
from collections import deque

stack = [2, 4, 6]
assert [stack.pop(), stack.pop(), stack.pop()] == [6, 4, 2]
queue = deque([2, 4, 6])
assert [queue.popleft(), queue.popleft(), queue.popleft()] == [2, 4, 6]
bounded = deque([1, 2], maxlen=2)
bounded.append(3)
assert list(bounded) == [2, 3]

Expected: The stack returns LIFO, deque returns FIFO, and a bounded deque demonstrates its drop policy.

Worked trace

Both lanes remove the same FIFO values. The list model shifts the remaining references after each front removal; deque does not promise that internal work.

Pitfalllist.pop(0) shifts every remaining element and can turn a traversal quadratic.

BoundariesCheck emptiness before removal. A bounded deque silently discards an endpoint when full, so it is usually wrong for an unbounded search frontier.

Cost modeldeque append and popleft are O(1); n list front removals perform n(n−1)/2 element shifts in the simple model.

TakeawayChoose the container for the operations the algorithm performs, not merely for the final values it returns.

Queue work versus list shifts

Compare FIFO state and the element-shift model without making timing claims.

V03 · P07-queues@2026-09-05

Example

from collections import deque
items = [10, 20, 30, 40] # preset input
queue = deque(items)
shift_count = 0
removed = []
while items:
shift_count += len(items) - 1
left = items.pop(0)
right = queue.popleft()
assert left == right
removed.append(left)

Step 1 of 6 · initialInitialize both lanes

L1–L4 construct the list, deque, counter, and output before the first loop test.

list lane

010120230340

deque lane

010120230340

removed

[]

model shifts step / total

0 / 0

Speed

Read all steps

Four items

Step 1: Initialize both lanes
L1–L4 construct the list, deque, counter, and output before the first loop test.
list lane
[10, 20, 30, 40]
deque lane
[10, 20, 30, 40]
removed
[]
model shifts step / total
0 / 0
Step 2: Remove 10
L5–L10 run in source order: count prospective list shifts, remove both fronts, verify equality, then append output.
list lane
[20, 30, 40]
deque lane
[20, 30, 40]
removed
[10]
model shifts step / total
3 / 3
Step 3: Remove 20
L5–L10 run in source order: count prospective list shifts, remove both fronts, verify equality, then append output.
list lane
[30, 40]
deque lane
[30, 40]
removed
[10, 20]
model shifts step / total
2 / 5
Step 4: Remove 30
L5–L10 run in source order: count prospective list shifts, remove both fronts, verify equality, then append output.
list lane
[40]
deque lane
[40]
removed
[10, 20, 30]
model shifts step / total
1 / 6
Step 5: Remove 40
L5–L10 run in source order: count prospective list shifts, remove both fronts, verify equality, then append output.
list lane
[]
deque lane
[]
removed
[10, 20, 30, 40]
model shifts step / total
0 / 6
Step 6: Loop complete
Both lanes produced the same order. The list reference-shift model totals 6; this is not CPU instructions, elapsed time, or bytes.
list lane
[]
deque lane
[]
removed
[10, 20, 30, 40]
model shifts step / total
0 / 6

Empty

Step 1: Initialize empty lanes
The preset changes only the initial literal and expected result; removed starts empty and shifts start at zero.
list lane
[]
deque lane
[]
removed
[]
model shifts
0
Step 2: Loop complete
L5 is false, so the grouped body never runs.
removed
[]
model shifts
0

Wide BFS frontier

Step 1: Initialize star frontier
After a star's center is processed, [1,2,3,4] is the wide frontier. This is context, not another graph animation.
list lane
[1, 2, 3, 4]
deque lane
[1, 2, 3, 4]
removed
[]
model shifts step / total
0 / 0
Step 2: Remove vertex 1
The grouped L5–L10 actions preserve order while the list model shifts its remaining logical positions.
list lane
[2, 3, 4]
deque lane
[2, 3, 4]
removed
[1]
model shifts step / total
3 / 3
Step 3: Remove vertex 2
The grouped L5–L10 actions preserve order while the list model shifts its remaining logical positions.
list lane
[3, 4]
deque lane
[3, 4]
removed
[1, 2]
model shifts step / total
2 / 5
Step 4: Remove vertex 3
The grouped L5–L10 actions preserve order while the list model shifts its remaining logical positions.
list lane
[4]
deque lane
[4]
removed
[1, 2, 3]
model shifts step / total
1 / 6
Step 5: Remove vertex 4
The grouped L5–L10 actions preserve order while the list model shifts its remaining logical positions.
list lane
[]
deque lane
[]
removed
[1, 2, 3, 4]
model shifts step / total
0 / 6
Step 6: Loop complete
Both lanes preserve the same order; no wall-clock or deque-instruction count is claimed.
list lane
[]
deque lane
[]
removed
[1, 2, 3, 4]
model shifts step / total
0 / 6

Trace breadth-first search

Inspect the queue, visited set, and shortest-path distance one verified step at a time.

21 verified steps

The interactive code-and-state view loads only when requested or near the viewport.

Deeper note and related practice

Frontier width O(w), visited storage O(V), and returned traversal order are different quantities.

Stable sorting and mutation#

Module 8 of 16

sorted creates a new list; list.sort mutates and returns None. Python sorting is stable, and each key is evaluated once per item.

Objectives

Put ranking policy in a key function.
Stable ties retain their previous relative order.
In-place mutation does not imply O(1) auxiliary workspace.

PrerequisitesP03 and P06 · Sequences and iteration.

Stable ranked recordspython

# example: P08-stable-sort
records = [("A", 2), ("B", 1), ("C", 2)]
by_score = sorted(records, key=lambda item: item[1])
assert by_score == [("B", 1), ("A", 2), ("C", 2)]
assert records == [("A", 2), ("B", 1), ("C", 2)]
returned = records.sort(key=lambda item: item[1])
assert returned is None and records == by_score
descending = sorted(by_score, key=lambda item: -item[1])
assert descending == [("A", 2), ("C", 2), ("B", 1)]

Expected: Stable equal keys retain A before C; sorted returns a new list while list.sort mutates and returns None.

Worked trace

Keys map A→2, B→1, C→2. B moves first while A stays before C. sorted creates a new outer list; list.sort mutates and returns None.

PitfallDo not assign result = values.sort(); the method returns None.

BoundariesDefine tie order, empty/all-equal inputs, reverse order, and whether key results are mutually comparable.

Cost modelUsual worst-case O(n log n) comparisons plus n key evaluations; CPython may use O(n) auxiliary workspace.

TakeawayPut the ordering policy in the key and state what happens to ties.

Stable sort and mutation boundary

See conceptual key extraction, stable ties, and the difference between sorted and list.sort.

V04 · P08-sorting@2026-09-05

records = [("A", 2), ("B", 1), ("C", 2)]
ordered = sorted(records, key=lambda item: item[1])
returned = records.sort(key=lambda item: item[1])

Step 1 of 5 · afterOriginal order

A precedes C among rank-2 records; ordered is not bound yet.

records R

A:2 · B:1 · C:2

ordered

unbound

Speed

Read all steps

Stable ties

Step 1: Original order
A precedes C among rank-2 records; ordered is not bound yet.
records R
A:2 · B:1 · C:2
ordered
unbound
Step 2: Conceptual key mapping
State is unchanged while the key mapping is explained; this is not a simulated Timsort event.
records R
A:2 · B:1 · C:2
keys
A→2 · B→1 · C→2
key calls
3
Step 3: sorted returns O
B moves first; A stays before C because equal-key order is stable. O and R are distinct lists.
records R
A:2 · B:1 · C:2
ordered O
B:1 · A:2 · C:2
identity
O is not R
Step 4: Conceptual mutation boundary
State remains unchanged while the next call's target is explained: list.sort will rearrange R itself.
records R
A:2 · B:1 · C:2
ordered O
B:1 · A:2 · C:2
Step 5: list.sort completes
R now matches O by value, returned is None, and R and O remain distinct objects.
records R
B:1 · A:2 · C:2
ordered O
B:1 · A:2 · C:2
returned
None
identity
O is not R

Deeper note and related practice

Mutating in place does not imply constant auxiliary memory; implementation workspace and key storage still count.

Heaps, priorities, and ties#

Module 9 of 16

The portable 3.11 contract uses heapq as a min-heap. The root is minimal, but the backing list is not globally sorted.

Objectives

heapify builds a heap in O(n).
Use a numeric sequence tie-breaker before an incomparable payload.
Python 3.14 max-heap APIs are outside this guide's 3.11 compatibility floor.

PrerequisitesP03 and P08 · Sequences and sorting.

Safe priority tuplespython

# example: P09-ranked-events
import heapq

def select_events(events: list[tuple[int, str]], k: int) -> list[str]:
    if k < 0:
        raise ValueError("k must be nonnegative")
    if k == 0:
        return []
    heap = []
    for sequence, (priority, label) in enumerate(events):
        entry = (priority, -sequence, label)
        heapq.heappush(heap, entry)
        if len(heap) > k:
            heapq.heappop(heap)
    ranked = sorted(heap, key=lambda entry: (-entry[0], -entry[1]))
    return [entry[2] for entry in ranked]

events = [(5, "A"), (5, "B"), (4, "C"), (5, "D")]
assert select_events(events, 2) == ["A", "B"]
assert select_events(events, 0) == []
assert select_events(events, 8) == ["A", "B", "D", "C"]
assert select_events([], 2) == []

Expected: Retains the highest priorities, prefers earlier records on ties, and returns best-first labels.

Worked trace

The minimum tuple stays at the root. A numeric sequence field resolves equal priorities before Python ever needs to compare dictionary payloads.

PitfallTuples compare lexicographically. Equal priorities without a comparable tie-breaker can raise TypeError.

BoundariesEmpty root/pop access is invalid. Python 3.14 max-heap helpers are outside the portable 3.11 floor. Retention ties and output order must be explicit.

Cost modelheapify is O(n), root access O(1), and push/pop O(log n) comparison work.

TakeawayA priority tuple must encode the actual tie and retention policy.

Heap shape is not sorted order

Keep the heap array and conceptual tree synchronized while priorities and ties are processed.

V05 · P09-heaps@2026-09-05

import heapq
heap = []
heapq.heappush(heap, (2, 0, {"id": "A"}))
heapq.heappush(heap, (1, 1, {"id": "B"}))
heapq.heappush(heap, (2, 2, {"id": "C"}))
first = heapq.heappop(heap)
second = heapq.heappop(heap)
third = heapq.heappop(heap)

Step 1 of 7 · initialEmpty heap

No next item is available.

One heap, array view

empty

Same entries, parent/child view

empty

next: unavailable

Speed

Read all steps

Priorities and ties

Step 1: Empty heap
No next item is available.
heap array
[]
next
unavailable
Step 2: Push A
The first entry becomes the root.
heap array
[(2,0,A)]
Step 3: Push B
Priority 1 moves to the root.
heap array
[(1,1,B), (2,0,A)]
Step 4: Push C
C ties A on priority but its sequence is later.
heap array
[(1,1,B), (2,0,A), (2,2,C)]
Step 5: Pop B
The minimum tuple leaves first.
heap array
[(2,0,A), (2,2,C)]
returned entries
first=B
Step 6: Pop A
The numeric sequence resolves the tied priority.
heap array
[(2,2,C)]
returned entries
first=B · second=A
Step 7: Pop C
The heap is empty again; another heapq.heappop(heap) would raise IndexError, so Next is unavailable.
heap array
[]
returned entries
first=B · second=A · third=C
next heappop
raises IndexError

Trace max-priority order

Watch negated priorities move through Python's min-heap implementation.

12 verified steps

The interactive code-and-state view loads only when requested or near the viewport.

Deeper note and related practice

heappushpop and heapreplace have different return/retention contracts; choose them only after establishing which item should survive.

Sorted boundaries with bisect#

Module 10 of 16

Lower bound is the first position at least the target; upper bound is the first position greater. Either may equal len(values).

Objectives

Use the half-open interval [left, right).
An insertion position is safe to return but not always safe to dereference.
Searching is logarithmic; inserting into a list can still shift O(n) items.

PrerequisitesP03 and P08 · Sequences and sorting.

Lower and upper boundariespython

# example: P10-boundaries
from bisect import bisect_left, bisect_right

def lower_bound(nums: list[int], target: int) -> int:
    left, right = 0, len(nums)
    while left < right:
        middle = (left + right) // 2
        if nums[middle] < target:
            left = middle + 1
        else:
            right = middle
    return left

nums = [1, 3, 3, 7]
assert lower_bound(nums, 3) == bisect_left(nums, 3) == 1
assert bisect_right(nums, 3) == 3
assert lower_bound([], 3) == 0
assert lower_bound(nums, 9) == 4
index = lower_bound(nums, 2)
assert index == 1 and not (index < len(nums) and nums[index] == 2)

Expected: The duplicate run occupies [1, 3); absent targets and empty input return safe insertion boundaries.

Worked trace

Each comparison shrinks a half-open undecided interval. Lower mode partitions values below the target from values at least the target; upper mode advances across equals.

PitfallDo not index values[position] until you have proved position < len(values).

BoundariesThe returned boundary may equal len(values) and need not point to an equal item. Never dereference it without a bounds and equality check.

Cost modelO(log n) comparisons for the search; O(n) movement if list insertion follows.

TakeawayBinary search finds a partition boundary, not necessarily a match.

Half-open binary-search boundaries

Follow [left, right) and reveal the insertion result only when the interval closes.

V06 · P10-bisect@2026-09-05

Example

def boundary(nums, target, upper=False):
left, right = 0, len(nums)
while left < right:
middle = (left + right) // 2
if nums[middle] < target or (upper and nums[middle] == target):
left = middle + 1
else: right = middle
return left

Step 1 of 5 · initialStart

Search [0, 4) with upper=False.

values

01132337

previous interval

Not available

new interval

[0,4)

result

hidden

Speed

Read all steps

lower 3

Step 1: Start
Search [0, 4) with upper=False.
values
[1,3,3,7]
previous interval
Not available
new interval
[0,4)
result
hidden
Step 2: Probe index 2
nums[2]=3; lower mode executes right=2.
previous interval
[0,4)
mid / value
2 / 3
new interval
[0,2)
result
hidden
Step 3: Probe index 1
nums[1]=3; lower mode executes right=1.
previous interval
[0,2)
mid / value
1 / 3
new interval
[0,1)
result
hidden
Step 4: Probe index 0
nums[0]=1; lower mode executes left=1.
previous interval
[0,1)
mid / value
0 / 1
new interval
[1,1)
result
hidden
Step 5: Return boundary
Only now is result 1 revealed.
interval
[1,1)
result
1

upper 3

Step 1: Start
Search [0, 4) with upper=True.
values
[1,3,3,7]
new interval
[0,4)
result
hidden
Step 2: Probe index 2
The upper-mode equality branch executes left=3.
previous interval
[0,4)
mid / value
2 / 3
new interval
[3,4)
result
hidden
Step 3: Probe index 3
nums[3]=7 is greater than 3, so right=3.
previous interval
[3,4)
mid / value
3 / 7
new interval
[3,3)
result
hidden
Step 4: Return boundary
Only now is the duplicate-run end 3 revealed.
interval
[3,3)
result
3

lower 9

Step 1: Start
Search [0, 4) with upper=False.
values
[1,3,3,7]
new interval
[0,4)
result
hidden
Step 2: Probe index 2
nums[2]=3 is below 9, so left=3.
previous interval
[0,4)
mid / value
2 / 3
new interval
[3,4)
result
hidden
Step 3: Probe index 3
nums[3]=7 is below 9, so left=4.
previous interval
[3,4)
mid / value
3 / 7
new interval
[4,4)
result
hidden
Step 4: Return len(nums)
Only now is the one-past-end result 4 revealed.
interval
[4,4)
result
4

empty

Step 1: Start empty
Both boundaries begin at zero; no midpoint exists.
values
[]
new interval
[0,0)
result
hidden
Step 2: Return zero
L2 is false, so no probe or dereference occurs.
interval
[0,0)
result
0

Trace binary search

See how the active interval narrows until the target index is found.

13 verified steps

The interactive code-and-state view loads only when requested or near the viewport.

Deeper note and related practice

A bisect key applies to stored elements, not the search target; record searches need a target expressed in key space.

Arithmetic, integers, and masks#

Module 11 of 16

Python // floors the mathematical quotient, while integer / produces a float. Arbitrary-size integers make bit length part of the cost model.

Objectives

Modulo follows the divisor's sign or is zero.
int(a / b) is not a reliable large-integer truncation technique.
State the bit-width and signedness assumptions of a mask.

PrerequisitesP01 · Contracts, functions, and input.

Floor division and maskspython

# example: P11-numbers
assert -7 // 3 == -3
assert -7 % 3 == 2
assert (-7 // 3) * 3 + (-7 % 3) == -7
large = 10**30 + 1
assert large // 3 == 333333333333333333333333333333
mask = (1 << 1) | (1 << 3)
assert mask == 10 and mask.bit_count() == 2
assert mask & (1 << 3)
assert (mask & ~(1 << 1)) == 8
assert ((~mask) & ((1 << 4) - 1)) == 5

Expected: Floor division reconstructs the dividend, large integers stay exact, and the four-bit mask has two set bits.

Worked trace

The mask changes 0→2→10 as bits 1 and 3 are set. Clearing bit 1 leaves 8; complement needs an explicit finite-width mask to produce 5.

PitfallDo not silently assume machine-word arithmetic when values may grow with the input.

BoundariesDivision by zero, negative operands, negative shifts, and finite versus unbounded bit masks need explicit contracts.

Cost modelBit operations on bounded machine-sized values are often modeled O(1); general integer work depends on operand bit length B.

TakeawayNo fixed-width overflow does not mean arbitrarily large integer work is constant time.

Deeper note and related practice

Integer arithmetic, hashing, and storage may depend on bit length B; use integer isqrt when float rounding would be unsafe.

Recursion frames and depth#

Module 12 of 16

Each recursive call owns local state. Its caller waits at the call site, receives a return value, and then resumes.

Objectives

Define a base case and measurable progress toward it.
The call stack counts as working memory.
Use an explicit stack when input depth is unbounded.

PrerequisitesP01 and P07 · Contracts and stack behavior.

Depth with explicit returnspython

# example: P12-call-stack
def triangular(n: int) -> int:
    if n == 0:
        return 0
    subtotal = triangular(n - 1)
    return n + subtotal

answer = triangular(3)
assert answer == 6
assert triangular(0) == 0

Expected: The deepest base case returns first; waiting callers resume with subtotals 0, 1, and 3 before returning 6.

Iterative accumulationpython

# example: P12-iterative-alternative
def triangular_iterative(n: int) -> int:
    total = 0
    for value in range(1, n + 1):
        total += value
    return total

assert triangular_iterative(3) == 6
assert triangular_iterative(0) == 0

Expected: Returns 6 and 0 with constant accumulator slots.

Worked trace

Calls for n=3,2,1 wait with separate local slots. The n=0 base returns 0; callers resume in reverse order and return 1,3,6.

PitfallRaising the recursion limit is not a general repair for unbounded input depth.

BoundariesThis function accepts small nonnegative n. Safe recursion depth depends on runtime and platform; raising the limit is not a general repair.

Cost modelO(n) calls and O(n) call-stack space for this linear recurrence.

TakeawayTrack one frame's responsibility and one returned value at a time.

Recursive callers wait

Distinguish a returned token from assignment into a waiting caller's local variable.

V07 · P12-recursion@2026-09-05

Example

def triangular(n):
if n == 0:
return 0
subtotal = triangular(n - 1)
return n + subtotal
answer = triangular(3)

Step 1 of 13 · initialInitial state

The module is ready to call triangular(3); answer is not bound yet.

Call stack · newest active frame first

call stackempty

Return token and shared state

answer: unbound

Speed

Read all steps

n = 3

Step 1: Initial state
The module is ready to call triangular(3); answer is not bound yet.
call stack
empty
answer
unbound
Step 2: Call F3
triangular(3) creates F3 with its own n and unbound subtotal.
F3
n=3 · subtotal=unbound
answer
unbound
Step 3: Call F2
F3 waits at its call site while triangular(2) creates F2.
F3
n=3 · waiting at L3
F2
n=2 · subtotal=unbound
Step 4: Call F1
F3 and F2 wait while triangular(1) creates F1.
F3
waiting at L3
F2
waiting at L3
F1
n=1 · subtotal=unbound
Step 5: Call F0
The final recursive call reaches n=0.
F3
waiting
F2
waiting
F1
waiting
F0
n=0
Step 6: Return 0 from F0
The base frame returns a distinct token; F1 is next to resume.
F1
waiting at L3
just returned
0
Step 7: Resume F1
F1 consumes the token into its own subtotal slot.
F1
n=1 · subtotal=0
older callers
F3, F2 waiting
Step 8: Return 1 from F1
F1 computes 1 + 0 and returns 1 to F2.
F2
waiting at L3
just returned
1
Step 9: Resume F2
F2 consumes the returned 1 into subtotal.
F2
n=2 · subtotal=1
older caller
F3 waiting
Step 10: Return 3 from F2
F2 computes 2 + 1 and returns 3 to F3.
F3
waiting at L3
just returned
3
Step 11: Resume F3
F3 consumes the returned 3 into subtotal.
F3
n=3 · subtotal=3
Step 12: Return 6 from F3
F3 computes 3 + 3; the call stack is now empty.
call stack
empty
just returned
6
Step 13: Bind answer
The module call consumes the token and binds answer to 6.
call stack
empty
answer
6

n = 0

Step 1: Initial state
The module is ready to call triangular(0); answer is unbound.
call stack
empty
answer
unbound
Step 2: Call F0
Create the boundary invocation with n=0.
F0
n=0
Step 3: Return 0
The base case produces a return token and the frame leaves.
call stack
empty
just returned
0
Step 4: Bind answer
The module consumes the token and binds answer to 0.
call stack
empty
answer
0

Trace recursive tree depth

Move through recursive calls and returns while the maximum depth is assembled.

16 verified steps

The interactive code-and-state view loads only when requested or near the viewport.

Deeper note and related practice

Sequential child calls do not add their maximum depths together, though each still contributes work.

Backtracking and memoized state#

Module 13 of 16

Backtracking chooses, explores, and restores shared path state. Memoization instead caches answers for state keys whose future behavior is identical.

Objectives

Copy the path when saving an answer.
Undo every mutation before returning to the caller.
A memo key must capture all state that affects future choices.

PrerequisitesP02, P05, and P12 · References, hashing, and recursion.

Subsets with restored statepython

# example: P13-subsets
def subsets(values: list[int]) -> list[list[int]]:
    answers, path = [], []
    def search(index: int) -> None:
        if index == len(values):
            answers.append(path.copy())
            return
        search(index + 1)
        path.append(values[index])
        search(index + 1)
        path.pop()
    search(0)
    return answers

assert subsets([1, 2]) == [[], [2], [1], [1, 2]]
assert subsets([]) == [[]]

Expected: Four independent saved lists are produced and empty input has one subset. Each invocation restores path to its own entry state before returning; that entry state may be nonempty.

A complete memoization keypython

# example: P13-memo-state
from functools import cache

def best_non_adjacent(values: list[int]) -> int:
    @cache
    def best(index: int) -> int:
        if index >= len(values):
            return 0
        return max(best(index + 1), values[index] + best(index + 2))
    return best(0)

assert best_non_adjacent([2, 7, 9, 3, 1]) == 12
assert best_non_adjacent([]) == 0
assert best_non_adjacent([-4, -1]) == 0

Expected: The fixed input makes index a complete key; choosing none preserves zero for negative-only input.

Worked trace

PitfallAppending path itself saves aliases to one mutable list; copy it at the answer boundary.

BoundariesSubsets enumerate input positions; repeated values may yield equal-looking outputs. Cache keys must contain every value that changes a subproblem's answer.

Cost modelO(n·2ⁿ) time and returned output for n-item subsets; O(n) active path/call-stack space excluding output.

TakeawaySnapshot completed outputs and cache complete immutable state.

Backtracking restores shared state

Watch one working path mutate while answer copies keep independent identities.

V08 · P13-subsets@2026-09-05

Example

def subsets(values):
answers = []
path = []
def search(index):
if index == len(values):
answers.append(path.copy())
return
search(index + 1) # exclude
path.append(values[index])
search(index + 1) # include
path.pop()
search(0)
return answers
result = subsets([1, 2])

Step 1 of 26 · afterInitialize outer frame

P is one shared working list. Every A-labelled saved value is a distinct copied list object.

Call stack · newest active frame first

search stack[]

Return token and shared state

phase: after
executed line: L2
outer frame: values=[1,2] · path=P · answers
path P: []
saved objects: []

Speed

Read all steps

values = [1, 2]

Step 1: Initialize outer frame
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[]
phase
after
executed line
L2
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[]
Step 2: Call search(0)
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0]
phase
call
executed line
L10
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[]
Step 3: Exclude 1
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
call
executed line
L6
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[]
Step 4: Exclude 2
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1,2]
phase
call
executed line
L6
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[]
Step 5: Save A0
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1,2]
phase
after
executed line
L4
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[A0=[]]
Step 6: Return leaf
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
return
executed line
L5
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[A0=[]]
Step 7: Choose 2
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
after
executed line
L7
outer frame
values=[1,2] · path=P · answers
path P
[2]
saved objects
[A0=[]]
Step 8: Include 2
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1,2]
phase
call
executed line
L8
outer frame
values=[1,2] · path=P · answers
path P
[2]
saved objects
[A0=[]]
Step 9: Save A1
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1,2]
phase
after
executed line
L4
outer frame
values=[1,2] · path=P · answers
path P
[2]
saved objects
[A0=[], A1=[2]]
Step 10: Return leaf
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
return
executed line
L5
outer frame
values=[1,2] · path=P · answers
path P
[2]
saved objects
[A0=[], A1=[2]]
Step 11: Undo 2
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
after
executed line
L9
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[A0=[], A1=[2]]
Step 12: Return search(1)
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0]
phase
return
executed line
L9
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[A0=[], A1=[2]]
Step 13: Choose 1
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0]
phase
after
executed line
L7
outer frame
values=[1,2] · path=P · answers
path P
[1]
saved objects
[A0=[], A1=[2]]
Step 14: Include 1
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
call
executed line
L8
outer frame
values=[1,2] · path=P · answers
path P
[1]
saved objects
[A0=[], A1=[2]]
Step 15: Exclude 2
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1,2]
phase
call
executed line
L6
outer frame
values=[1,2] · path=P · answers
path P
[1]
saved objects
[A0=[], A1=[2]]
Step 16: Save A2
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1,2]
phase
after
executed line
L4
outer frame
values=[1,2] · path=P · answers
path P
[1]
saved objects
[A0=[], A1=[2], A2=[1]]
Step 17: Return leaf
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
return
executed line
L5
outer frame
values=[1,2] · path=P · answers
path P
[1]
saved objects
[A0=[], A1=[2], A2=[1]]
Step 18: Choose 2
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
after
executed line
L7
outer frame
values=[1,2] · path=P · answers
path P
[1,2]
saved objects
[A0=[], A1=[2], A2=[1]]
Step 19: Include 2
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1,2]
phase
call
executed line
L8
outer frame
values=[1,2] · path=P · answers
path P
[1,2]
saved objects
[A0=[], A1=[2], A2=[1]]
Step 20: Save A3
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1,2]
phase
after
executed line
L4
outer frame
values=[1,2] · path=P · answers
path P
[1,2]
saved objects
[A0=[], A1=[2], A2=[1], A3=[1,2]]
Step 21: Return leaf
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
return
executed line
L5
outer frame
values=[1,2] · path=P · answers
path P
[1,2]
saved objects
[A0=[], A1=[2], A2=[1], A3=[1,2]]
Step 22: Undo 2
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0,1]
phase
after
executed line
L9
outer frame
values=[1,2] · path=P · answers
path P
[1]
saved objects
[A0=[], A1=[2], A2=[1], A3=[1,2]]
Step 23: Return search(1)
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0]
phase
return
executed line
L9
outer frame
values=[1,2] · path=P · answers
path P
[1]
saved objects
[A0=[], A1=[2], A2=[1], A3=[1,2]]
Step 24: Undo 1
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[0]
phase
after
executed line
L9
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[A0=[], A1=[2], A2=[1], A3=[1,2]]
Step 25: Return search(0)
P is one shared working list. Every A-labelled saved value is a distinct copied list object.
search stack
[]
phase
return
executed line
L9
outer frame
values=[1,2] · path=P · answers
path P
[]
saved objects
[A0=[], A1=[2], A2=[1], A3=[1,2]]
Step 26: Return result
The outer frame returns four independent snapshots; the working path was restored before return.
search stack
outer returns
phase
return
executed line
L12
outer frame
values=[1,2] · path=P · answers
path P
not live
saved objects
result=[[],[2],[1],[1,2]]

values = []

Step 1: Initialize outer frame
answers and path P are separate empty lists.
search stack
[]
phase
after
outer frame
values=[] · path=P · answers=[]
path P
[]
Step 2: Call search(0)
Index zero already equals input length.
search stack
[0]
phase
call
outer frame
values=[] · path=P · answers
path P
[]
Step 3: Save A0
path.copy() creates a saved object distinct from P.
search stack
[0]
phase
after
path P
[]
saved objects
[A0=[]]
Step 4: Return search(0)
No choice or restoration is needed.
search stack
[]
phase
return
path P
[]
saved objects
[A0=[]]
Step 5: Return result
The outer frame returns one independent empty subset.
phase
return
outer frame
returns
path P
not live
saved objects
result=[[]]

Trace subset backtracking

Follow the choice path, recursive frames, and restored state across the verified search.

38 verified steps

The interactive code-and-state view loads only when requested or near the viewport.

Deeper note and related practice

Memoization removes repeated subproblems, not recursion depth; a bottom-up formulation can preserve the recurrence without call-stack growth.

Linked lists and trees#

Module 14 of 16

Node problems are reference problems. Preserve the next edge before rewiring a list, and choose recursive or iterative tree traversal based on depth.

Objectives

Dummy nodes simplify head changes.
A traversal should define whether identity or value determines visited state.
Avoid recursive list concatenation that repeatedly copies growing results.

PrerequisitesP02, P07, and P12 · References, queues, and recursion.

Linear preorder accumulationpython

# example: P14-tree-preorder
class TreeNode:
    def __init__(self, value: int, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def preorder(root: TreeNode | None) -> list[int]:
    result: list[int] = []
    def visit(node: TreeNode | None) -> None:
        if node is None:
            return
        result.append(node.value)
        visit(node.left)
        visit(node.right)
    visit(root)
    return result

root = TreeNode(4, TreeNode(2), TreeNode(7))
assert preorder(root) == [4, 2, 7]
assert preorder(None) == []

Expected: The compatible TreeNode example constructs a binary tree; each node appends once and no recursive result lists are concatenated.

Reverse links without losing the suffixpython

# example: P14-list-reversal
class ListNode:
    def __init__(self, value: int, next: "ListNode | None" = None):
        self.value = value
        self.next = next

def reverse(head: ListNode | None) -> ListNode | None:
    previous = None
    current = head
    while current is not None:
        following = current.next
        current.next = previous
        previous, current = current, following
    return previous

head = reverse(ListNode(1, ListNode(2)))
assert head is not None and head.value == 2
assert head.next is not None and head.next.value == 1 and head.next.next is None

Expected: The same two nodes return in reverse order, with the old head terminating the list.

Worked trace

A linked-list update redirects references without copying node values. Tree traversal returns one result list rather than repeatedly concatenating subtree lists.

PitfallRepeated left + [value] + right can copy accumulated traversal results and become quadratic on skewed trees.

BoundariesDistinguish a missing node from a node whose value is falsy. Handle empty heads/roots and decide whether repeated or cyclic references are legal.

Cost modelO(n) time and O(h) active traversal stack, plus O(n) returned output.

TakeawayReason about node identity and pointer ownership separately from stored values.

Deeper note and related practice

Repeated list concatenation across recursive returns can copy growing partial outputs; append into one owned result when order permits.

Graphs and grids#

Module 15 of 16

Choose adjacency storage for dense indices or arbitrary keys, validate starts, and make the grid shape/passability contract explicit.

Objectives

Mark visited on enqueue for BFS.
A rectangular grid contract should define empty, ragged, blocked, and out-of-range inputs.
The frontier bound is O(V), not O(E), for a standard vertex-once traversal.

PrerequisitesP05, P07, and P12 · Hashing, queues, and recursion.

Validated BFS discovery orderpython

# example: P15-keyed-bfs
from collections import deque

def bfs_keys(graph: dict[str, list[str]], start: str) -> list[str]:
    queue = deque([start])
    seen = {start}
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph.get(node, []):
            if neighbor not in seen:
                seen.add(neighbor)
                queue.append(neighbor)
    return order

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"]}
assert bfs_keys(graph, "A") == ["A", "B", "C", "D"]
assert bfs_keys({}, "Z") == ["Z"]

Expected: Returns deterministic discovery order; a missing key represents a vertex with no outgoing edges.

Worked trace

BFS marks the start before enqueueing, records discovery order, and marks each neighbor when enqueued so a vertex enters the frontier once.

PitfallDo not describe discovery order as distance unless you actually record levels or parent distances.

BoundariesValidate the start index. For grids, define empty, ragged, blocked, and out-of-range behavior before traversing.

Cost modelO(V + E) time and O(V) visited/frontier space for adjacency lists.

TakeawayChoose adjacency storage for the identifier domain and mark visited at the moment that prevents duplicate work.

Deeper note and related practice

Discovery order is not automatically distance output or a unique topological order; record the additional state the prompt actually asks for.

Pattern toolbox and transfer#

Module 16 of 16

Use templates as recall scaffolds, then restate the invariant and adapt the boundaries to the actual prompt.

Objectives

Confirm allowed standard-library modules.
Test empty, singleton, duplicate, negative, tie, and boundary inputs relevant to the contract.
Return to the roadmap for recognition practice rather than memorizing syntax in isolation.

PrerequisitesP01–P15 as applicable to the selected pattern.

Dependable interview helperspython

# example: P16-toolbox
from itertools import accumulate, combinations
from math import gcd, isqrt

prefix = list(accumulate([3, -1, 4], initial=0))
assert prefix == [0, 3, 2, 6]
assert prefix[3] - prefix[1] == 3
assert list(combinations([1, 2, 3], 2)) == [(1, 2), (1, 3), (2, 3)]
assert gcd(18, 24) == 6
assert isqrt(26) == 5

Expected: accumulate includes the initial empty prefix, combinations yields three pairs, gcd returns 6, and isqrt floors √26 to 5.

Worked trace

PitfallA copied template is not an answer until its interval, mutation, and empty-input policies match the prompt.

BoundariesConfirm allowed libraries. An explicit initial zero makes prefix boundaries visible; combinations can produce large output, while gcd and isqrt require integer-domain reasoning.

Cost modelaccumulate is O(n) for n outputs; generating r combinations costs O(r) tuple outputs; integer gcd/isqrt costs depend on operand bit length.

TakeawayTemplates are recall scaffolds; the invariant and boundary contract make them an answer.

Deeper note and related practice

Iterator helpers defer production but do not erase output work. Prefer the simplest adequate helper or pattern and explain its domain and result contract.

Common interview templates#

These fifteen executable contracts are recall aids, not proprietary answers. Open the pattern you need, then adapt its invariant and boundaries.

Two PointersPrecondition: nums is sorted ascending. Use when a comparison can discard one boundary at a time.

Use when: Precondition: nums is sorted ascending. Use when a comparison can discard one boundary at a time.

Typical complexity: O(n) time and O(1) extra space.

Two Pointers templatepython

# example: T01-sorted-two-sum
def sorted_pair_sum(nums: list[int], target: int) -> tuple[int, int] | None:
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return left, right
        if total < target:
            left += 1
        else:
            right -= 1
    return None

assert sorted_pair_sum([1, 2, 4, 7], 6) == (1, 2)
assert sorted_pair_sum([1, 2, 4, 7], 3) == (0, 1)
assert sorted_pair_sum([], 3) is None

Sliding WindowPrecondition: every value is nonnegative. Use when an over-limit window can shrink monotonically.

Use when: Precondition: every value is nonnegative. Use when an over-limit window can shrink monotonically.

Typical complexity: O(n) time and O(1) extra space when every value is nonnegative.

Sliding Window templatepython

# example: T02-longest-bounded-window
def longest_sum_at_most(nums: list[int], limit: int) -> int:
    if any(value < 0 for value in nums):
        raise ValueError("nums must be nonnegative")
    left = 0
    answer = 0
    window_sum = 0
    for right, value in enumerate(nums):
        window_sum += value
        while left <= right and window_sum > limit:
            window_sum -= nums[left]
            left += 1
        answer = max(answer, right - left + 1)
    return answer

assert longest_sum_at_most([1, 2, 1, 0, 1], 3) == 3
assert longest_sum_at_most([], 3) == 0
try:
    longest_sum_at_most([1, -1], 3)
except ValueError:
    pass
else:
    raise AssertionError("negative input must be rejected")

Binary SearchPrecondition: nums is sorted ascending. Return the first insertion boundary, which may equal len(nums).

Use when: Precondition: nums is sorted ascending. Return the first insertion boundary, which may equal len(nums).

Typical complexity: O(log n) comparisons and O(1) space.

Binary Search templatepython

# example: T03-lower-bound
def lower_bound(nums: list[int], target: int) -> int:
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

assert lower_bound([1, 3, 3, 7], 3) == 1
assert lower_bound([1, 3, 3, 7], 9) == 4
assert lower_bound([], 3) == 0

Typical complexity: O(V + E) time and O(V) frontier/visited space.

BFS templatepython

# example: T04-bfs-order
from collections import deque

def bfs(graph: list[list[int]], start: int = 0) -> list[int]:
    if not graph:
        return []
    if not 0 <= start < len(graph):
        raise ValueError("invalid start")
    queue, seen, order = deque([start]), {start}, []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                queue.append(neighbor)
    return order

graph = [[1, 2], [3], [3], []]
assert bfs(graph, 0) == [0, 1, 2, 3]
assert bfs([]) == []
try:
    bfs(graph, -1)
except ValueError:
    pass
else:
    raise AssertionError("invalid nonempty start must be rejected")

DFSPrecondition: graph is a dense adjacency list with valid neighbor IDs. Use iterator frames for deterministic recursive-style order without recursive depth.

Use when: Precondition: graph is a dense adjacency list with valid neighbor IDs. Use iterator frames for deterministic recursive-style order without recursive depth.

Typical complexity: O(V + E) time and O(V) stack/visited space; each live iterator is part of the frontier.

DFS templatepython

# example: T05-iterator-dfs
def dfs(graph: list[list[int]], start: int = 0) -> list[int]:
    if not graph:
        return []
    if not 0 <= start < len(graph):
        raise ValueError("invalid start")
    stack = [(start, iter(graph[start]))]
    seen, order = {start}, [start]
    while stack:
        node, neighbors = stack[-1]
        try:
            neighbor = next(neighbors)
        except StopIteration:
            stack.pop()
            continue
        if neighbor not in seen:
            seen.add(neighbor)
            order.append(neighbor)
            stack.append((neighbor, iter(graph[neighbor])))
    return order

graph = [[1, 2], [3], [3], []]
assert dfs(graph, 0) == [0, 1, 3, 2]
assert dfs([]) == []
try:
    dfs(graph, 4)
except ValueError:
    pass
else:
    raise AssertionError("invalid nonempty start must be rejected")

Tree DFSPrecondition: a finite acyclic binary tree with no shared child nodes and recursion-safe height. Height counts nodes.

Use when: Precondition: a finite acyclic binary tree with no shared child nodes and recursion-safe height. Height counts nodes.

Typical complexity: O(n) time and O(h) call-stack space.

Tree DFS templatepython

# example: T06-tree-depth
class TreeNode:
    def __init__(self, value: int, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def tree_depth(node: TreeNode | None) -> int:
    if not node:
        return 0
    left_depth = tree_depth(node.left)
    right_depth = tree_depth(node.right)
    return 1 + max(left_depth, right_depth)

root = TreeNode(4, TreeNode(2), TreeNode(7))
assert tree_depth(root) == 2
assert tree_depth(TreeNode(4)) == 1
assert tree_depth(None) == 0

Tree BFSPrecondition: a finite acyclic binary tree with no shared child nodes. Return values grouped by distance from the root.

Use when: Precondition: a finite acyclic binary tree with no shared child nodes. Return values grouped by distance from the root.

Typical complexity: O(n) time, O(w) queue space, and O(n) returned output.

Tree BFS templatepython

# example: T07-tree-levels
from collections import deque

class TreeNode:
    def __init__(self, value: int, left=None, right=None):
        self.value, self.left, self.right = value, left, right

def tree_levels(root: TreeNode | None) -> list[list[int]]:
    if not root:
        return []
    queue, result = deque([root]), []
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.value)
            for child in (node.left, node.right):
                if child:
                    queue.append(child)
        result.append(level)
    return result

root = TreeNode(4, TreeNode(2), TreeNode(7))
assert tree_levels(root) == [[4], [2, 7]]
assert tree_levels(None) == []

BacktrackingPrecondition: enumerate subsets of input positions in exclude-first order. Each call restores path to its own entry state, which may be nonempty.

Use when: Precondition: enumerate subsets of input positions in exclude-first order. Each call restores path to its own entry state, which may be nonempty.

Typical complexity: O(n·2ⁿ) time/output for this subsets contract and O(n) active path/stack space excluding output.

Backtracking templatepython

# example: P13-subsets
def subsets(values: list[int]) -> list[list[int]]:
    answers, path = [], []
    def search(index: int) -> None:
        if index == len(values):
            answers.append(path.copy())
            return
        search(index + 1)
        path.append(values[index])
        search(index + 1)
        path.pop()
    search(0)
    return answers

assert subsets([1, 2]) == [[], [2], [1], [1, 2]]
assert subsets([]) == [[]]

Heap / Top KPrecondition: numeric values; duplicates count separately. Return the largest k values ascending; oversized k returns all sorted.

Use when: Precondition: numeric values; duplicates count separately. Return the largest k values ascending; oversized k returns all sorted.

Typical complexity: O(n log(min(k,n)+1) + min(k,n) log(min(k,n)+1)) time and O(min(k,n)) heap/output space.

Heap / Top K templatepython

# example: T09-numeric-top-k
import heapq

def top_k(nums: list[int], k: int) -> list[int]:
    if k < 0:
        raise ValueError("k must be nonnegative")
    if k == 0:
        return []
    heap: list[int] = []
    for value in nums:
        heapq.heappush(heap, value)
        if len(heap) > k:
            heapq.heappop(heap)
    return sorted(heap)

assert top_k([5, 1, 8, 2, 7], 3) == [5, 7, 8]
assert top_k([4, 4, 1], 2) == [4, 4]
assert top_k([2, 1], 8) == [1, 2]
assert top_k([], 3) == [] and top_k([1], 0) == []
try:
    top_k([1], -1)
except ValueError:
    pass
else:
    raise AssertionError("negative k must be rejected")

Prefix SumPrecondition: 0 ≤ left ≤ right ≤ len(nums), and prefix came from nums. Query the half-open interval [left, right).

Use when: Precondition: 0 ≤ left ≤ right ≤ len(nums), and prefix came from nums. Query the half-open interval [left, right).

Typical complexity: O(n) preprocessing and O(1) per range query.

Prefix Sum templatepython

# example: T10-prefix-sum
def prefix_sums(nums: list[int]) -> list[int]:
    prefix = [0]
    for value in nums:
        prefix.append(prefix[-1] + value)
    return prefix

def range_sum(prefix: list[int], left: int, right: int) -> int:
    """Return the sum over the half-open interval [left, right)."""
    if not 0 <= left <= right < len(prefix):
        raise ValueError("invalid half-open range")
    return prefix[right] - prefix[left]

prefix = prefix_sums([2, -1, 4])
assert prefix == [0, 2, 1, 5]
assert range_sum(prefix, 0, 0) == 0
assert range_sum(prefix, 1, 3) == 3
try:
    range_sum(prefix, 3, 2)
except ValueError:
    pass
else:
    raise AssertionError("invalid half-open range must be rejected")

Monotonic StackPrecondition: return the next strictly greater index; equal values do not satisfy the boundary.

Use when: Precondition: return the next strictly greater index; equal values do not satisfy the boundary.

Typical complexity: O(n) time and O(n) space.

Monotonic Stack templatepython

# example: T11-next-greater
def next_greater(nums: list[int]) -> list[int]:
    answer = [-1] * len(nums)
    stack: list[int] = []
    for i, value in enumerate(nums):
        while stack and nums[stack[-1]] < value:
            answer[stack.pop()] = i
        stack.append(i)
    return answer

assert next_greater([2, 1, 2, 4, 3]) == [3, 2, 3, -1, -1]
assert next_greater([2, 2]) == [-1, -1]
assert next_greater([]) == []

Union FindPrecondition: nodes are dense integers in [0, n). Use when edges merge components and duplicate unions should return false.

Use when: Precondition: nodes are dense integers in [0, n). Use when edges merge components and duplicate unions should return false.

Typical complexity: Near-constant amortized operations with path compression and rank.

Union Find templatepython

# example: T12-union-find
class UnionFind:
    def __init__(self, n: int):
        if n < 0:
            raise ValueError("n must be nonnegative")
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n

    def find(self, node: int) -> int:
        while node != self.parent[node]:
            self.parent[node] = self.parent[self.parent[node]]
            node = self.parent[node]
        return node

    def union(self, first: int, second: int) -> bool:
        root_a, root_b = self.find(first), self.find(second)
        if root_a == root_b:
            return False
        if self.rank[root_a] < self.rank[root_b]:
            root_a, root_b = root_b, root_a
        self.parent[root_b] = root_a
        if self.rank[root_a] == self.rank[root_b]:
            self.rank[root_a] += 1
        self.components -= 1
        return True

groups = UnionFind(6)
for edge in ((0, 1), (1, 2), (3, 4), (2, 4)):
    assert groups.union(*edge) is True
assert groups.components == 2 and groups.find(0) == groups.find(4)
assert groups.union(0, 4) is False and groups.components == 2
assert UnionFind(0).components == 0
try:
    UnionFind(-1)
except ValueError:
    pass
else:
    raise AssertionError("negative n must be rejected")

Topological SortPrecondition: graph is a dense directed adjacency list with valid neighbor IDs. None reports a cycle; [] is the valid order for an empty graph.

Use when: Precondition: graph is a dense directed adjacency list with valid neighbor IDs. None reports a cycle; [] is the valid order for an empty graph.

Typical complexity: O(V + E) time and O(V) space.

Topological Sort templatepython

# example: T13-topological-order
from collections import deque

def topological_order(graph: list[list[int]]) -> list[int] | None:
    indegree = [0] * len(graph)
    for neighbors in graph:
        for neighbor in neighbors:
            indegree[neighbor] += 1
    queue = deque(i for i, degree in enumerate(indegree) if degree == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    return order if len(order) == len(graph) else None

assert topological_order([[1, 2], [3], [3], []]) == [0, 1, 2, 3]
assert topological_order([[1], [0]]) is None
assert topological_order([]) == []

1-D Dynamic ProgrammingContract: choose nonadjacent positions; choosing none is allowed, so negative-only input returns zero.

Use when: Contract: choose nonadjacent positions; choosing none is allowed, so negative-only input returns zero.

Typical complexity: O(n) time and O(1) accumulator space.

1-D Dynamic Programming templatepython

# example: T14-nonadjacent-total
def best_total(values: list[int]) -> int:
    previous_two = 0
    previous_one = 0
    for value in values:
        current = max(previous_one, previous_two + value)
        previous_two, previous_one = previous_one, current
    return previous_one

assert best_total([2, 7, 9, 3, 1]) == 12
assert best_total([-5, -2]) == 0
assert best_total([]) == 0

Grid TraversalContract: rectangular 0/1 grid, four-direction moves, and only value 1 is passable - including the start. Empty, blocked, or out-of-range starts return empty; ragged input raises.

Use when: Contract: rectangular 0/1 grid, four-direction moves, and only value 1 is passable - including the start. Empty, blocked, or out-of-range starts return empty; ragged input raises.

Typical complexity: O(rows + rows × cols) validation/traversal time and O(rows × cols) space in the worst case.

Grid Traversal templatepython

# example: T15-grid
from collections import deque

def visit_grid(grid: list[list[int]], start_row: int, start_col: int) -> set[tuple[int, int]]:
    rows = len(grid)
    if rows == 0:
        return set()
    cols = len(grid[0])
    if any(len(row) != cols for row in grid):
        raise ValueError("grid must be rectangular")
    if not (0 <= start_row < rows and 0 <= start_col < cols):
        return set()
    if grid[start_row][start_col] != 1:
        return set()
    queue = deque([(start_row, start_col)])
    seen = {(start_row, start_col)}
    while queue:
        row, col = queue.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = row + dr, col + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in seen:
                seen.add((nr, nc))
                queue.append((nr, nc))
    return seen

assert visit_grid([[1, 0], [1, 1]], 0, 0) == {(0, 0), (1, 0), (1, 1)}
assert visit_grid([], 0, 0) == set()
assert visit_grid([[]], 0, 0) == set()
assert visit_grid([[0]], 0, 0) == set()
assert visit_grid([[2]], 0, 0) == set()
assert visit_grid([[1]], -1, 0) == set()
try:
    visit_grid([[1], [1, 0]], 0, 0)
except ValueError:
    pass
else:
    raise AssertionError("ragged grid must be rejected")

Common interview mistakes#

Using pop(0) for a queue

It shifts the remaining list and costs O(n). Use deque.popleft().

Aliasing a 2-D list

[[0] * cols] * rows repeats references to one inner list. Build each row independently.

Forgetting string immutability

Accumulate many characters in a list and join once.

Confusing / and //

/ returns floating-point division; // performs floor division.

Treating heapq as a max heap

heapq is a min-heap. Use an intentional max-heap strategy for the supported runtime.

Ignoring recursion depth

A very deep DFS can exceed Python’s recursion limit; use an explicit stack when depth is unbounded.

Costly slicing inside loops

A slice copies its elements. Repeated large slices can turn an intended linear solution quadratic.

Unsafe heap tuple ties

When priorities tie, Python compares later tuple fields. Add a deterministic numeric tie-breaker when payloads are not comparable.

Mutating while iterating

Iterate over a copy or collect updates separately when structural mutation would change traversal behavior.

Broken and corrected examples#

Each repair keeps its failure visible beside the executable correction and its regression case.

FIFO without repeated shifts

Failure: Deleting index zero shifts every remaining list element and can make a BFS quadratic.

Regression case: Process a wide frontier and assert every node is visited once while the implementation uses deque.popleft.

Brokenpython

# Broken: index-zero removal shifts every remaining reference.
queue = [2, 4, 6]
order = []
while queue:
    order.append(queue.pop(0))

Correctedpython

# Corrected: deque removes from the left without list shifts.
from collections import deque

queue = deque([2, 4, 6])
order = []
while queue:
    order.append(queue.popleft())
assert order == [2, 4, 6]

Independent grid rows

Failure: Every outer entry references the same row, so one cell update leaks into other rows.

Regression case: Set grid[0][0] and assert grid[1][0] remains zero.

Brokenpython

# Broken: both outer entries refer to the same row.
grid = [[0] * 2] * 2
grid[0][0] = 7
assert grid == [[7, 0], [7, 0]]

Correctedpython

# Corrected: construct each row in a separate comprehension iteration.
grid = [[0] * 2 for _ in range(2)]
grid[0][0] = 7
assert grid == [[7, 0], [0, 0]]

Count earlier prefixes before updating

Failure: Updating first lets the current prefix count itself when target is zero.

Regression case: For nums=[0] and target=0, return one subarray, not two; signed inputs remain valid.

Brokenpython

# Broken loop body: recording first lets the current prefix count itself.
prefix += value
seen[prefix] = seen.get(prefix, 0) + 1
answer += seen.get(prefix - target, 0)

Correctedpython

# Complete executable correction: query earlier prefixes first.
def count_target_subarrays(nums: list[int], target: int) -> int:
    seen = {0: 1}
    prefix = 0
    answer = 0
    for value in nums:
        prefix += value
        answer += seen.get(prefix - target, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return answer

assert count_target_subarrays([0], 0) == 1
assert count_target_subarrays([0, 0], 0) == 3
assert count_target_subarrays([2, -2, 2], 2) == 3

Debugging checklist#

Restate the invariant and trace the smallest failing input before changing code.
Check aliasing, mutable defaults, slice copies, and whether a nested container shares references.
Verify every index boundary and whether binary-search intervals are closed or half-open.
Inspect queue and heap operations for an accidental O(n) front removal or reversed priority.
Test empty, singleton, duplicate, negative, and depth-heavy inputs; replace recursion when depth is not bounded.

Questions about the language#

These are reasonable discussion prompts, not claims about every interviewer or company.

Why dict and set keys must be hashable, and what mutation would invalidate a key model.
When deque is a better queue than list and when list remains better for indexed access.
What slicing and repeated string concatenation allocate.
How tuple ordering affects heap tie-breaking and what happens when payloads are incomparable.
When recursion depth makes an iterative traversal safer.

Language transfer exercises#

The five existing checks remain concealed until you choose to open them.

predict
Find the alias
Predict which cells change after grid = [[0] * 2] * 2; grid[0][1] = 7, and explain why.
Answer check
Both rows show 7 in column 1 because the outer list contains two references to the same inner list.
trace
Trace one BFS layer
Using deque, trace queue and visited state when A connects to B and C and both connect to D. Mark when visited changes.
Answer check
Mark on enqueue: start [A]/{A}; after A, [B,C]/{A,B,C}; after B, [C,D]/{A,B,C,D}; C must not enqueue D again.
repair
Repair the queue
A BFS repeatedly calls items.pop(0). Replace only the queue mechanics and state the complexity change.
Answer check
Use collections.deque with popleft; front removal changes from O(n) shifting to approximately O(1).
choose
Choose a container
Choose list, set, dict, deque, or heap for membership, stable append order, FIFO removal, and retaining the smallest k boundary.
Answer check
Set for membership, list for indexed append order, deque for FIFO, and a bounded max-heap strategy for retaining the smallest k.
transfer
Unlabeled transfer
Given a stream of events, keep the three highest priorities while preserving a deterministic order among ties. Name the stored tuple and test one tie.
Answer check
Use a size-three min-heap with a numeric tie-breaker such as (priority, sequence, event); never let Python compare non-orderable event payloads.

Reach this point to mark the lesson as read.

Input and output conventions#

Python interview sequence#

Quick reference#

Iteration and ordering

Counting and adjacency

Queue and heap

Sorted boundaries

Contracts, functions, and input#

Names, objects, and mutation#

Names and values

Objects

Alias and rebind

Lists, tuples, and copies#

Names and values

Objects

Nested copy

Strings and text construction#

Dictionaries, sets, and counting#

Iteration and materialization#

Stacks, queues, and deque#

list lane

deque lane

removed

model shifts step / total

Four items

Empty

Wide BFS frontier

Stable sorting and mutation#

records R

ordered

Stable ties

Heaps, priorities, and ties#

One heap, array view

Same entries, parent/child view

Priorities and ties

Sorted boundaries with bisect#

values

previous interval

new interval

result

lower 3

upper 3

lower 9

empty

Arithmetic, integers, and masks#

Recursion frames and depth#

Call stack · newest active frame first

Return token and shared state

n = 3

n = 0

Backtracking and memoized state#

Call stack · newest active frame first

Return token and shared state

values = [1, 2]

values = []

Linked lists and trees#

Graphs and grids#

Pattern toolbox and transfer#

Common interview templates#

Common interview mistakes#

Using pop(0) for a queue

Aliasing a 2-D list

Forgetting string immutability

Confusing / and //

Treating heapq as a max heap

Ignoring recursion depth

Costly slicing inside loops

Unsafe heap tuple ties

Mutating while iterating

Broken and corrected examples#

FIFO without repeated shifts

Independent grid rows

Count earlier prefixes before updating

Debugging checklist#

Questions about the language#

Language transfer exercises#

Find the alias

Trace one BFS layer

Repair the queue

Choose a container