Skip to main content

Code Katas

Implementation drills. Pick any language. For each kata, write the data structure from scratch, add a minimal test harness, and record a two-to-three line note on what the bug-per-attempt pattern taught you.

Kata 1 - Red-Black Tree Insertion​

Implement:

  • insert(key) with fix-up loop that handles the three canonical uncle cases (red uncle, black uncle with left-right or right-left zig-zag, black uncle with straight line)
  • left and right rotation primitives
  • a post-insert validator that checks the five red-black invariants

Target: O(log n) insert, all five invariants hold after every call, passes a 10,000-insert randomized test with invariant check after each call.

Bonus: add delete(key) with the four deletion fix-up cases.

Kata 2 - Union-Find with Rank and Path Compression​

Implement:

  • make_set(x)
  • find(x) with path compression (either full compression or path halving)
  • union(x, y) with union by rank

Target: a sequence of n = 200,000 make_set calls followed by 200,000 random union/find operations should complete in under 100 ms on a modern laptop. Verify correctness by cross-checking against a brute-force equivalence-class implementation on small inputs.

Bonus: instrument and plot amortized cost per operation; confirm it stays roughly constant as n grows.

Kata 3 - Segment Tree with Lazy Propagation​

Implement:

  • build from an array of length n
  • point update update(i, v)
  • range query query(l, r) for sum (or min, or max - pick one)
  • range update update(l, r, delta) using a lazy[node] array

Target: correctness against a brute-force array on 1,000 randomized mixed operation sequences, each with n = 200. Then scale to n = 10^5 and run 10^5 mixed operations in under 500 ms.

Bonus: support a second combine operation (e.g., both range-sum and range-min in the same tree).

Kata 4 - Fenwick Tree (Binary Indexed Tree)​

Implement:

  • update(i, delta) for point update
  • query(i) for prefix sum arr[1..i]
  • query(l, r) = query(r) - query(l-1) for range sum

Target: both operations use only the low-bit trick i & (-i). Correctness checked against brute-force prefix sums on randomized inputs. Handle n = 10^6 with 10^6 mixed updates and queries in under 300 ms.

Bonus: extend to 2-D Fenwick tree for rectangular range sum on a grid.

Kata 5 - Skip List​

Implement:

  • randomized insert(key) that tosses coins to determine the node's level
  • search(key)
  • delete(key)
  • a configurable MAX_LEVEL and p (typically 0.5 or 0.25)

Target: correctness on 10,000 randomized operations compared against a sorted reference set. Measured expected per-operation time should stay O(log n) as n scales from 10^3 to 10^6.

Bonus: report the achieved level distribution and compare against the geometric expectation.

Kata 6 - Bloom Filter​

Implement:

  • init(m, k) with a bit array of length m and k hash functions (use double-hashing h_i(x) = h1(x) + i * h2(x))
  • insert(x)
  • contains(x) returning true if all k bits are set, false otherwise

Target: empirical false-positive rate should match the theoretical prediction (1 - e^(-kn/m))^k to within 10% on a test workload of n = 10,000 inserts, followed by 100,000 membership queries for values not in the set.

Bonus: compare measured memory against a Python set containing the same keys; report the compression factor.

Completion Checklist​

  • all six katas compile, pass randomized tests, and hit the stated time targets
  • each kata has a one-paragraph reflection on the main bug encountered during implementation
  • at least one instrumented run of kata 2 plotted to confirm near-constant amortized cost
  • at least one instrumented run of kata 6 compared to the theoretical false-positive formula

Core Structure Repair Katas​

Complete these if any advanced structure feels like magic.

  1. Implement a singly linked list with push_front, append, find, delete_first, and reverse.
  2. Implement a stack with array storage and use it to check balanced delimiters.
  3. Implement a queue with a circular buffer and prove each operation is O(1) amortized or worst-case.
  4. Implement binary-tree traversals: preorder, inorder, postorder, and level order.
  5. Implement a binary min-heap and use it for top-K selection.
  6. Implement a hash table with chaining and a resize threshold.

Evidence check: every kata must include unit tests, one edge-case test, and a complexity note for each public operation.