Prompt and when it applies
Assigning problems to programmers is a useful model: problems are on the left, programmers on the right, and an edge means they share a required tag. Each edge can be selected at most once, and the objective is to maximize assignments. A public PracHub interview prompt models this eligibility allocation as bipartite matching and extends it to edge generation, distributed coordination, and streaming changes; this article focuses on the single-machine coding core.
What the interviewer is testing
- Distinguishing any feasible, maximal, and maximum-cardinality matchings.
- Using augmenting paths to explain why a matching can grow while preserving invariants.
- Explaining BFS layering and DFS for a vertex-disjoint set of shortest augmenting paths.
- Stating worst-case O((V+E)√V) time, O(V+E) storage, and the algorithm's limits.
Clarifications to ask first
- Is the objective maximum cardinality, or are there weights, priorities, or fairness constraints?
- What are the bounds on n, m, and E, and is the input already bipartite and duplicate-free?
- Should the answer return only the size, or every pair and every unmatched vertex?
- Is the graph a static batch, or will edges be inserted and deleted under an online latency target?
A 30-second answer
“I model the two object classes as the two sides of a bipartite graph and eligibility as edges. I keep pair_left and pair_right. Each BFS starts from every unmatched left vertex and builds layers through alternating unmatched and matched edges. DFS then finds a vertex-disjoint set of shortest augmenting paths in that layered graph; flipping each path increases the matching. When no augmenting path remains, the augmenting-path theorem gives a maximum matching. The worst-case complexity is O((V+E)√V); for a small graph, a simpler DFS augmenting implementation may be enough.”
Step-by-step solution
Step 1: Build the graph and invariants
Store only real feasible edges in adjacency lists. pair_left[u] and pair_right[v] must point to each other, or both be -1. Flipping one augmenting path changes only its edges, so no vertex receives two matched edges.
Step 2: Build layers with BFS
Start simultaneously from every unmatched left vertex. Traverse an unmatched edge to the right side and then the matched edge back to a left vertex, recording the shortest layer. Keep the shortest layers that can reach an unmatched right vertex so DFS does not explore longer paths in the same phase.
Step 3: Augment in batches with DFS
Run DFS from each unmatched left vertex. Reaching an unmatched right vertex succeeds. Reaching a matched right vertex recurses through its matched left vertex only when the layer increases by one. A per-left adjacency cursor prevents rescanning failed edges in the same phase.
Step 4: Correctness and termination
An augmenting path has one more unmatched edge than matched edge, so symmetric difference along it increases cardinality by one. The augmenting-path theorem says a matching is maximum exactly when no augmenting path exists. Every phase increases the matching, so the loop terminates.
Step 5: Complexity and trade-offs
Hopcroft–Karp has worst-case O((V+E)√V) time, O(V) auxiliary space, and O(V+E) graph storage. Princeton's reference implementation also derives a minimum vertex cover; this prompt only needs a matching. For a small graph, per-left DFS is shorter but can take O(VE) in the worst case. Weighted objectives require Hungarian or min-cost flow instead.
Executable Python implementation
from collections import deque
def hopcroft_karp(left_size, right_size, edges):
adj = [[] for _ in range(left_size)]
for left, right in edges:
adj[left].append(right)
pair_left = [-1] * left_size
pair_right = [-1] * right_size
distance = [-1] * left_size
def bfs():
queue = deque()
for left in range(left_size):
if pair_left[left] == -1:
distance[left] = 0
queue.append(left)
else:
distance[left] = -1
found = False
while queue:
left = queue.popleft()
for right in adj[left]:
mate = pair_right[right]
if mate == -1:
found = True
elif distance[mate] == -1:
distance[mate] = distance[left] + 1
queue.append(mate)
return found
def dfs(left, next_edge):
while next_edge[left] < len(adj[left]):
right = adj[left][next_edge[left]]
next_edge[left] += 1
mate = pair_right[right]
if mate == -1 or (
distance[mate] == distance[left] + 1
and dfs(mate, next_edge)
):
pair_left[left] = right
pair_right[right] = left
return True
distance[left] = -1
return False
matching = 0
while bfs():
next_edge = [0] * left_size
for left in range(left_size):
if pair_left[left] == -1 and dfs(left, next_edge):
matching += 1
return matching, pair_leftA high-quality sample answer
“I first confirm that the objective is maximum cardinality, not weighted matching, and model eligibility as bipartite edges. Two pair arrays maintain a bidirectional invariant. BFS layers the shortest augmenting paths from all unmatched left vertices; DFS uses current-edge cursors to find as many vertex-disjoint paths in that layer graph as possible, then flips their edges. When no path remains, the augmenting-path theorem proves optimality. The implementation uses O((V+E)√V) time and O(V+E) storage; small graphs can use simple DFS, while weighted objectives need Hungarian or min-cost flow.”
Common mistakes
- Calling a greedy result maximum; a maximal matching can be much smaller than a maximum one.
- Storing only one side of each pair and creating duplicate occupancy after a flip.
- Stopping BFS at any reachable path, which breaks shortest-layer batching.
- Omitting current-edge cursors and rescanning failed edges in one phase.
- Claiming O((V+E)√V) for general, weighted, or dynamically updated matching.
Follow-ups and strong responses
How do you generate eligibility edges without comparing all n×m pairs?
Build an inverted index by tag. Bucket right-side objects, then union and deduplicate the buckets for each left object. E can still be large, so report E, hot-tag skew, and memory limits.
Why can the algorithm stop with no augmenting path?
Every augmenting path increases the matching size by one. The augmenting-path theorem states that a larger matching exists exactly when an augmenting path exists, so failure to find one proves maximum cardinality.
What changes for weighted preferences?
Hopcroft–Karp optimizes edge count only. Use Hungarian or min-cost max-flow, and restate complexity, integer-weight limits, and the fallback when no feasible assignment exists.
How would you handle continual edge churn?
The batch algorithm is suited to recomputation. An online service can search locally for augmenting paths around affected vertices, but must state latency, reassignment limits, and the temporary non-optimality contract.