~/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.

Graphs

Bipartite graphs / 2-colouring

BFS/DFS colouring; an odd cycle means not bipartite.

Visual guide Quiz (9) Spot the pattern
Notes

Recognise it when: you need to split into two groups with no conflicts inside a group, do a 2-colouring, or detect an odd cycle.

color = {}
for s in nodes:
    if s in color: continue
    color[s] = 0; q = deque([s])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in color:
                color[v] = 1 - color[u]; q.append(v)
            elif color[v] == color[u]:
                return None          # odd cycle
return color

Gotchas: the graph can be disconnected, so start from every uncoloured node. Union-Find with "enemy" sets is an alternative.

4 problems

Interview roadmap

Graphs Grids and networks: BFS, DFS, cycles, ordering.

Bipartite graphs / 2-colouring guide

esc