Skip to main content

Code Katas

Focused implementation drills. Aim to complete each kata within the time limit from an empty file, with no copy-paste. Repeat each kata on different days until the muscle memory is stable.

Kata 1: BFS from Scratch​

Time limit: 15 minutes
Goal: Produce both the dist array and a parent pointer that lets you reconstruct any shortest path.
Setup: Start from an empty file. Graph given as an adjacency list of n vertices numbered 0..n-1.

Implement:

  • bfs(adj, s) returning (dist, parent)
  • shortest_path(parent, s, v) returning a list of vertices

Write a test that runs BFS on a 6-vertex graph you hand-draw and verifies the expected dist array.

Repeat until: you can produce correct BFS with path reconstruction in under 10 minutes without a reference.

Kata 2: DFS with Discovery and Finish Times​

Time limit: 15 minutes
Goal: Produce d[], f[], parent[], and an iterable of edge classifications {tree, back, forward, cross}.
Setup: Directed adjacency list.

Implement:

  • dfs(adj) returning the four arrays above
  • classify_edge(u, v, color, d) helper

Run on the directed graph from the DFS concept page and check that the cycle is detected via a back edge.

Repeat until: you no longer need to look up the WHITE/GRAY/BLACK color rules.

Kata 3: Dijkstra with Binary Heap (Lazy Deletion)​

Time limit: 20 minutes
Goal: Binary-heap Dijkstra that uses "push stale and skip" instead of decrease-key.
Setup: Weighted adjacency list with nonnegative weights.

Implement:

  • dijkstra(adj, s) returning (dist, parent)
  • skip stale pops by checking if the popped distance matches dist[u]

Benchmark on a 1000 x 1000 grid with random [1, 100] weights; expected runtime under a couple of seconds.

Repeat until: you can write the lazy-deletion loop from memory, including the stale-skip check.

Kata 4: Bellman-Ford with Negative-Cycle Detection​

Time limit: 15 minutes
Goal: SSSP on arbitrary-weight graphs plus cycle detection.
Setup: Edge list.

Implement:

  • bellman_ford(n, edges, s) returning (dist, parent, has_negative_cycle)
  • early exit if a pass produces no relaxations

Test on:

  • a small graph with negative edges but no negative cycle (expected: correct distances, False)
  • a graph with a negative cycle reachable from s (expected: True)

Repeat until: you write the |V| - 1 outer loop and the tripwire pass without prompts.

Kata 5: Kruskal with Union-Find​

Time limit: 20 minutes
Goal: MST by edge-sorted greedy plus union-find.
Setup: Edge list for an undirected weighted graph.

Implement:

  • UnionFind(n) with union by rank and path compression
  • kruskal(n, edges) returning the MST edge list

Test on a graph whose MST weight you know independently (use the graph from the MST concept). Also run on a disconnected graph and verify the algorithm returns a spanning forest of the correct weight.

Repeat until: your union-find is 10-15 lines with no branching for cases you have forgotten.

Kata 6: Prim with Binary Heap​

Time limit: 15 minutes
Goal: MST grown from a root using a binary heap.
Setup: Weighted adjacency list.

Implement:

  • prim(adj, r) returning the MST edge list

Verify: on the same graph, kruskal and prim return MSTs of the same total weight.

Repeat until: you reproduce the algorithm as "Dijkstra with key = min edge weight" and can explain the one-line change from Dijkstra.

Kata 7: Ford-Fulkerson / Edmonds-Karp​

Time limit: 30 minutes
Goal: Max flow with explicit residual edges and BFS for augmenting paths.
Setup: Flow network given as (source, sink, list of (u, v, capacity)).

Implement:

  • a residual-graph data structure where each forward edge and its reverse share a single mutable capacity object
  • max_flow(n, edges, s, t) returning (value, min_cut_side_of_s)

Test on the network from the Max Flow concept page; expected max-flow value 14.

Then wrap it for unweighted bipartite matching and verify on the example from the bipartite matching concept.

Repeat until: you can set up the residual-edge sharing and the BFS augmenting-path loop without looking anything up.

Completion Standard​

  • All seven katas completed at least twice, on separate days.
  • Each kata completed within its time limit from an empty file, without references.
  • Each kata explained out loud in one paragraph: invariant, running time, and one thing that could go wrong.
  • Combined test harness: a single script that runs all seven on a suite of small graphs and reports pass/fail.