Skip to main content

Code Katas

Focused, repeatable coding exercises across every paradigm from this module. Complete each kata multiple times until it is automatic.

Format for every kata:

  • Time limit: as stated per kata
  • Polya comments: in your code, include four comments: # Understand, # Plan, # Invariant/Recurrence, # Reflect
  • Tests: write at least three test cases before coding, including one edge case and (where possible) one stress-test comparison with a brute-force oracle

Kata 1: Loop Invariants in Practice (insertion sort)​

Time limit: 20 minutes
Goal: Implement insertion sort from scratch with a written loop invariant and three tests.
Setup: Do not look at reference code.

Implementation plus at the top of the function a comment stating the outer-loop invariant. Tests: empty, single element, reverse-sorted, already-sorted.

Repeat until: you can write it and the invariant in under 10 minutes without reference.

Kata 2: Binary Search Variants​

Time limit: 25 minutes
Goal: Implement three binary-search variants in one session.
Setup: A sorted list of integers, possibly with duplicates.

Write:

  1. find(A, x): return any index i with A[i] == x, or -1.
  2. lower_bound(A, x): return the smallest i with A[i] >= x (len(A) if none).
  3. upper_bound(A, x): return the smallest i with A[i] > x.

Each must use explicit lo, hi with a single, stated invariant. Include at least two tests that stress boundary behavior (duplicates, target absent, target smaller/larger than every element).

Repeat until: no off-by-one bugs and all three variants correct on first run.

Kata 3: Divide-and-Conquer Mergesort and Inversion Count​

Time limit: 30 minutes
Goal: Implement mergesort, extend it to count inversions, and prove the recurrence.
Setup: A list of integers.

Implement merge_sort(A) returning a sorted copy, then modify to also return the number of inversions (pairs i < j with A[i] > A[j]). Include a comment stating the recurrence T(n) = 2 T(n/2) + n and its solution.

Tests: empty list, all-equal list, reverse-sorted (maximum inversions), random list compared to brute force O(n^2) counter.

Repeat until: you write mergesort from scratch in under 10 minutes and the inversion extension in under 10 more.

Kata 4: Greedy Activity Selection with Oracle​

Time limit: 20 minutes
Goal: Implement the earliest-finish-time greedy and validate against a brute-force oracle.
Setup: A list of (start, finish) activities.

Implement:

  1. greedy_select(activities): returns the maximum-size mutually compatible subset by earliest-finish-time.
  2. brute_select(activities): enumerates all 2^n subsets, returns the largest compatible one.
  3. Stress test both on 200 random inputs with n <= 12.

Repeat until: zero mismatches on 500 rounds and you can explain the exchange argument from memory.

Kata 5: Backtracking N-Queens​

Time limit: 25 minutes
Goal: Solve N-queens by backtracking with explicit extend / check / undo structure.
Setup: Integer n, return one valid placement (or all placements).

Use a cols array to track column choices per row. Attack test should consider column and both diagonals. Include # Invariant comment: "cols[0..r-1] is a valid partial placement".

Tests: n=1 (1 solution), n=2 and n=3 (0 solutions), n=4 (2 solutions), n=8 (92 solutions).

Repeat until: correct count for n=8 and clean recursion with no state leakage.

Kata 6: Dynamic Programming Minimum Coin Change​

Time limit: 25 minutes
Goal: Implement coin change both top-down (memoization) and bottom-up (tabulation).
Setup: A list of denominations C and target T.

Include both:

  • min_coins_topdown(C, T) using functools.lru_cache
  • min_coins_bottomup(C, T) using a dp array

State the recurrence dp[t] = 1 + min(dp[t - c] for c in C if c <= t) with base dp[0] = 0.

Tests: T = 0, unreachable target (should return -1 or inf), simple cases ([1,5,10,25], 30), adversarial case [1,3,4], 6 where greedy-by-largest fails.

Repeat until: both implementations agree on 300 random small inputs.

Kata 7: Amortized Dynamic Array​

Time limit: 20 minutes
Goal: Implement a dynamic array with doubling, and verify amortized O(1) cost empirically.
Setup: A custom DynArray class in Python.

Implement append, __getitem__, and internal _resize. Record the number of element writes (actual writes plus copies) for n = 1, 2, 4, ..., 2^20 appends. Plot or print total_writes / n; it should stay below a small constant.

Tests: verify len behaviour, element preservation across resizes, and that the write count matches the aggregate analysis bound.

Repeat until: you can explain the accounting-method credit assignment (bank 2 per append) from memory.

Kata 8: Paradigm Triage Timed Sprint​

Time limit: 30 minutes total
Goal: Pick a paradigm and sketch an approach for eight unfamiliar problems in under 4 minutes each.
Setup: Any set of eight problems you have not solved before (take them from exercises.md).

For each problem write:

  • task type (decision / optimization / counting / construction / enumeration)
  • paradigm choice
  • one-sentence justification
  • expected runtime

Do not implement anything. The goal is triage speed, not finishing.

Repeat until: you complete eight triages in under 30 minutes with reasonable paradigm choices.

Completion Standard​

  • All eight katas completed at least once
  • Katas 1, 2, 4, 5, 6 completed three or more times, within time limit, from scratch
  • Stress tests pass for all katas that include a brute-force oracle
  • Polya comments present in every final solution
  • You can recite the core pattern (invariant / recurrence / exchange / state) for every kata without reference

Additional Fluency Katas​

Kata 9: Big-O Repair Sheet​

Implement ten tiny functions that match the common loop shapes from the complexity workshop. Beside each function, write the exact count for a small input, the asymptotic bound, and one sentence saying whether the algorithm is practical for n = 10^6.

Kata 10: Paradigm Explainer​

For the same problem, write four approaches: brute force, greedy if plausible, divide-and-conquer if plausible, and dynamic programming if plausible. You may use a small scheduling, coin-change, or path problem. Mark invalid approaches explicitly and include a counterexample for each invalid greedy claim.