~/problems

Problems

Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.

Weighted graphs

Union-Find

Path compression + union by rank; connectivity and grouping.

Visual guide Quiz (10) Spot the pattern
Notes

Recognise it when: grouping by connectivity, components, "are x and y connected", merging accounts, detecting a cycle in an undirected graph, Kruskal.

def find(x):
    root = x
    while parent[root] != root: root = parent[root]
    while parent[x] != root: parent[x], x = root, parent[x]   # compress
    return root

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb: return False
    if rank[ra] < rank[rb]: ra, rb = rb, ra
    parent[rb] = ra
    rank[ra] += rank[ra] == rank[rb]
    return True

Gotchas: recursive find blows the recursion limit on long chains, so write it iteratively. Keep a count of components.

9 problems

Interview roadmap

Weighted graphs Dijkstra, union-find, spanning trees.

Union-Find guide

esc