Skip to main content

Code Katas

Focused, repeatable coding exercises. Complete each kata multiple times until implementation is automatic and you no longer need to look up the recurrence.

Kata 1: LIS in O(n log n)​

Time limit: 20 minutes
Goal: patience-sorting LIS with reconstruction.
Setup: input array a[1..n] with n ≤ 10^5.

Implement:

  1. lis_length(a) returning the LIS length in O(n log n) using the tails array and binary search.
  2. lis_sequence(a) returning one valid LIS of maximum length in O(n log n), by additionally recording (tails_index, prev_index) per position and walking back.

Verify on:

  • the strictly increasing array [1, 2, 3, 4, 5] -> length 5
  • the strictly decreasing array [5, 4, 3, 2, 1] -> length 1
  • the classic [2, 4, 3, 5, 1, 7, 6, 9, 8] -> length 5

Repeat until: you can reproduce both functions from scratch in under 15 minutes without references, and lis_sequence output is verified as increasing and of the correct length.

Kata 2: Edit Distance With Reconstruction​

Time limit: 20 minutes
Goal: full 2D edit-distance table and reconstruction of the edit script.
Setup: two strings s (length m) and t (length n).

Implement:

  1. edit_distance(s, t) returning the minimum number of insert/delete/substitute operations.
  2. edit_script(s, t) returning a list of operations, e.g., [("match", 'k'), ("sub", 'k', 's'), ("insert", 'g')], that transforms s into t.

Verify on:

  • ("kitten", "sitting") -> distance 3; script has three non-match operations.
  • ("", "abc") -> distance 3; three inserts.
  • ("abc", "") -> distance 3; three deletes.

Repeat until: you can produce both functions from memory in under 15 minutes, and the script correctly transforms s into t when applied left-to-right.

Kata 3: 0/1 Knapsack (Rolled + Full Table)​

Time limit: 20 minutes
Goal: both the rolled O(W) version and the full O(nW) table with reconstruction.
Setup: item list (w, v) for each of n items, capacity W.

Implement:

  1. knapsack_value(items, W) using a rolled O(W) array; iterate c in descending order.
  2. knapsack_items(items, W) using the full O(nW) table and walking back to recover chosen items.

Verify by checking that knapsack_value agrees with sum(v for item in knapsack_items) on 20 random instances.

Repeat until: both versions are second nature and you can articulate why c descends in 0/1 and ascends in unbounded.

Kata 4: Matrix Chain Multiplication​

Time limit: 20 minutes
Goal: interval DP with parenthesization reconstruction.
Setup: dimensions p[0..n] so that matrix A_i has shape p[i-1] x p[i].

Implement:

  1. matrix_chain_cost(p) returning the minimum scalar multiplications via O(n^3) interval DP.
  2. matrix_chain_parens(p) returning a string like ((A1 A2)((A3 A4) A5)) using the recorded split points.

Verify on p = [10, 30, 5, 60] (cost 4500, parens (A1 (A2 A3))).

Repeat until: filling the table in interval-length order (not row-major) is automatic, and parenthesization is reconstructed without hesitation.

Kata 5: Tree DP -- Maximum Independent Set​

Time limit: 20 minutes
Goal: tree DP with two states per node.
Setup: adjacency list of a tree with n vertices and weights w[1..n].

Implement:

  1. max_weight_independent_set(n, edges, w) returning the maximum total weight.
  2. Return the set of chosen vertices, not just the weight.

Verify on:

  • a path graph of 5 nodes with weights [1, 2, 3, 4, 5] -> pick alternating, total 9.
  • a star with center weight 10 and 4 leaves of weight 3 each -> max is 12 (leaves) or 10 (center); pick leaves.

Repeat until: you recurse with parent passed in, avoid revisiting the parent, and handle large n (10^5) with iterative DFS or increased stack.

Kata 6: TSP via Bitmask DP​

Time limit: 30 minutes
Goal: Held-Karp O(2^n n^2) DP with path reconstruction.
Setup: symmetric distance matrix d[n][n] with n ≤ 15.

Implement:

  1. tsp_cost(d) returning the minimum Hamiltonian cycle cost via dp[mask][j].
  2. tsp_path(d) returning the sequence of cities, starting and ending at city 0.

Verify on a small hand-computed example and against brute-force factorial enumeration for n ≤ 8.

Repeat until: you can iterate subsets (for mask in range(1, 1 << n)) and the inner j, k loops cleanly, and the path reconstruction walks the predecessor table without bugs.

Completion Standard​

  • Can complete each kata within the time limit on a fresh attempt.
  • Can explain the recurrence and fill order without looking at notes.
  • No need to look up off-by-one details for base cases or loop directions.
  • All katas include reconstruction of the optimal object, not only its value.