Practice tools, glossary and shared structures

A. Diagnose the implementation gap

When an attempt fails, record the smallest failing input and the first state that no longer matches its meaning. Avoid writing only "off-by-one" or "need more practice." Those labels do not identify the decision to rehearse.

Model: you solved a different problem, such as a substring instead of a subsequence, a walk instead of a simple path, or ordered sequences instead of unordered combinations. Rewrite the output contract and one distinguishing example.

State: a variable mixed two meanings, such as height and diameter, current-window validity and historical maximum, or a previous DP layer and a current one. Rename the quantities and write their meanings at one specific point in the loop.

Timing: you stored the current element before a lookup that required earlier elements, committed before repairing a window, or marked a graph vertex too late. Write the exact ingest, update, repair and commit order, then trace two adjacent iterations.

Boundary: an inclusive endpoint was treated as exclusive, a binary-search update did not shrink the interval, or a leaf was confused with one missing child. Draw the smallest empty, singleton and two-candidate states.

Ownership: a recursive branch did not undo its mutation, a result retained a mutable path reference, or a linked-list rewrite lost the next node. Name the owner of every changed object and the point at which it is restored or transferred.

Schedule: a DP state read an unfinished predecessor, an in-place relaxation reused one item, or a graph algorithm used the wrong frontier. Draw the dependency arrows and choose a processing order that respects them.

Cost: the algorithm was correct but hidden slicing, list insertion, hashing or repeated subtree work made the claimed complexity wrong. Count the actual operations in this language, including output materialization.

B. A repeatable interview rehearsal

Use a blank editor and a problem statement with its topic hidden. First restate the contract aloud. Ask only questions that change the model: duplicates, order, mutation, endpoint semantics, missing answers or constraints. Work one example manually before choosing the mechanism.

State a simple baseline, then identify its repeated work. Derive the improved state from that waste. Write a protocol and one invariant sentence before implementation. Translate the protocol in order rather than typing a remembered code shape and hoping its variables acquire meaning.

During implementation, keep the state sentence visible. When adding a branch, say what it proves and why the discarded alternatives are safe. For recursion, say what the child returns and which mutations belong to the current frame.

Validate with a normal example, the smallest legal input, an equality/tie case and an adversarial case tied to the proof. Explain time, auxiliary space, output size and recursion depth. If time remains, discuss one changed constraint that would invalidate the mechanism.

After the rehearsal, score five abilities from zero to two: contract clarity, derivation, executable translation, verification and explanation. Zero means missing, one means achieved with a hint, and two means independent. Use the pattern of scores to choose the next practice action. The score is a personal learning instrument, not a hiring prediction.

C. Retrieval map

Prefix evidence: scans and maps, 001-020. Ask what the processed prefix can summarize and whether the current item belongs in that summary before a query.

Ordered frontiers: sorting, two pointers and windows, 021-050. Ask what ordering or contiguity permits you to discard, compact or repair.

Boundary algebra: prefixes, differences and sweeps, 051-060 and 091-100. Ask whether an interval can be represented by two boundary events or two prefix states.

Unfinished candidates: stacks, monotonic structures, queues and heaps, 061-090. Ask why a candidate is removed: resolved, dominated, expired or selected.

References and search intervals: linked lists and binary search, 101-120. Ask which objects or candidate positions remain reachable after the next update.

Coordinates and traversal: matrices and grid search, 121-140. Ask which neighbors exist, when discovery is marked and whether updates need original cell state.

Calls and choices: recursion, backtracking and trees, 141-180. Ask what one call promises, what it owns and whether its state must be restored.

Connectivity and dependency order: graphs, DAGs, DSU and weighted frontiers, 181-210. Ask whether the task is reachability, enumeration, ordering, connection cost or route cost.

Optimal substructure: greedy arguments and DP, 211-240. Ask whether one choice dominates alternatives, or whether several complete predecessor answers must be compared.

Persistent invariants: bits, mathematics and designed structures, 241-250. Ask which algebraic identity or cross-structure relationship survives every operation.

D. Glossary of working terms

Invariant: a statement true at a named point before and after every iteration or operation. It must connect maintained state to the problem, not merely describe the code.

Candidate interval: the positions in which a sought result or boundary can still lie. A half-open interval [left,right) includes left and excludes right; its width is right-left.

Monotone predicate: a boolean condition whose value changes at most once over an ordered search domain. It justifies searching for a first true or first false boundary.

Commit point: the moment maintained state is valid and complete enough to update or emit an answer. A repaired window and a completed recursive path have different commit conditions.

Frontier: discovered work waiting to be processed. FIFO, LIFO, minimum-priority and monotonic frontiers imply different ordering guarantees.

Dominance: one candidate is at least as useful as another for every possible future continuation, allowing the weaker candidate to be discarded safely.

Amortized cost: the total cost of a sequence divided across its operations. A particular operation may be expensive even when the average per operation is constant.

State axis: one dimension needed to identify a subproblem, such as prefix length, remaining budget, vertex or capacity. Omitting a necessary axis merges situations with different futures.

Pseudopolynomial: polynomial in a numeric value such as capacity, but potentially exponential in the number of bits used to encode that value.

Output-sensitive work: runtime or memory that necessarily depends on how many answers or output characters are produced. Enumerating exponentially many subsets cannot take linear total time.

Aliasing: two references designate the same mutable object. Saving a path without copying it and allocating matrix rows by repeated references are common accidental forms.

Stable ordering: equal-key records retain their earlier relative order. It is a property of how ties are handled, not simply of whether the final keys are sorted.

E. Running the examples and keeping editions aligned

Use Python 3.10 or newer. The solution files themselves use only the standard library. Download the complete solution bundle and keep its files together: some later lessons deliberately import an earlier kata or the shared structures module.

From the solutions directory, start Python and import the named function or class, then paste an example call. List and tree examples use the constructors and serializers printed in the next appendix. Stateful examples use run_operations: the first argument is a class, the second is a sequence of method-name/argument tuples, and any remaining arguments initialize the class. The returned list includes None for mutation methods.

The package README gives exact rebuild commands. tools/check.py regenerates all Python files and executes every published example. tests/independent_checks.py exercises bounded independent oracles and stateful invariants. tools/build_book.py generates the chapter Markdown, website and PDF from the verified lesson records.

For a correction, edit the relevant authoring/module_NN.py record, not just a generated Python or HTML file. Re-run verification and rebuild every edition. Preserve kata IDs so links, review notes and progress records remain meaningful.

Printed code may wrap long lines for page layout; the downloadable Python preserves original line breaks. Trace line numbers refer to those downloadable files. Original text diagrams are schematic rather than to scale. Local browser progress stays on that browser and is not a cross-device learning record.

F. Shared Python structures

"""Shared interview data types and small example adapters used by the book."""
from collections import deque

class ListNode:
    def __init__(self, val=0, next=None, random=None):
        self.val, self.next, self.random = val, next, random

def build_list(values):
    dummy = ListNode()
    tail = dummy
    for value in values:
        tail.next = ListNode(value)
        tail = tail.next
    return dummy.next

def list_values(head):
    output, seen = [], set()
    while head is not None:
        if head in seen:
            raise ValueError('Cannot serialize a cyclic chain as a finite list')
        seen.add(head)
        output.append(head.val)
        head = head.next
    return output

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def build_tree(values):
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue = deque([root])
    i = 1
    while queue and i < len(values):
        node = queue.popleft()
        for side in ('left', 'right'):
            if i < len(values) and values[i] is not None:
                child = TreeNode(values[i])
                setattr(node, side, child)
                queue.append(child)
            i += 1
    return root

def tree_values(root):
    if root is None:
        return []
    output, queue = [], deque([root])
    while queue:
        node = queue.popleft()
        if node is None:
            output.append(None)
        else:
            output.append(node.val)
            queue.extend((node.left, node.right))
    while output and output[-1] is None:
        output.pop()
    return output

class GraphNode:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = [] if neighbors is None else neighbors

def run_operations(factory, operations, *constructor_args):
    """Return the result of every named operation, including None for mutations."""
    instance = factory(*constructor_args)
    output = []
    for operation in operations:
        method, *args = operation
        output.append(getattr(instance, method)(*args))
    return output