## Problem Given a bipartite graph where left nodes are workers and right nodes are tasks, and each edge means a worker can perform that task, find the maximum number of tasks that can be assigned (one task per worker, one worker per task). ```python def max_matching(n: int, m: int, edges: list[tuple[int,int]]) -> int: # n: number of workers (0..n-1) # m: number of tasks (0..m-1) # edges: list of (worker, task) indicating compatibility # returns: size of maximum matching pass def find_matching(n: int, m: int, edges: list[tuple[int,int]]) -> dict[int,int]: # returns: dict mapping worker -> assigned task (only matched workers) pass ``` **Example:** ``` edges = [(0,0),(0,1),(1,1),(2,2)] max_matching(3, 3, edges) -> 3 find_matching(3, 3, edges) -> {0: 0, 1: 1, 2: 2} ``` ## Follow-ups 1. Walk through the augmenting path algorithm. What is its time complexity? 2. How does Hopcroft-Karp improve on the naive augmenting path approach? 3. How would you model task scheduling with deadlines as a maximum matching problem? 4. When might a minimum vertex cover be more useful than maximum matching?

InterviewDB Question

Maximum Matching: Find Maximum Bipartite Matching Using Augmenting Paths

Onsite

Question Details

Problem Given a bipartite graph where left nodes are workers and right nodes are tasks, and each edge means a worker can perform that task, find the maximum number of tasks that can be assigned (one task per worker, one worker per task). Example: Follow-ups Walk through the augmenting path algorithm. What is its time complexity? How does Hopcroft-Karp improve on the naive augmenting path approach? How would you model task scheduling with deadlines as a maximum matching problem? When might a mini…

Full Details

🔒

Unlock all Waymo questions

Full insider details, leaked discussions, and candidate experiences.

or every company, $100/year →

About This Question

This is a reported interview question from a waymo interview during the onsite round.

It covers the following topics: Coding, Graph, Onsite .

Topics

Coding Graph Onsite

Maximum Matching: Find Maximum Bipartite Matching Using Augmenting Paths

Question Details

Full Details

About This Question

Topics

More Waymo Interview Questions