# Match Tagged Problems to Skilled Programmers at Scale You have `N` problems and `M` programmers. Each problem has a set of required tags, and each programmer has a set of skills. A programmer is eligible for a problem when the two sets have at least one value in common. Each problem and programmer may appear in at most one assignment. ### Clarifying Questions to Ask - Is any eligible assignment acceptable, or must the number of assignments be maximum? - Are tags exact identifiers, and how large can each tag set be? - Does the full data set fit on one machine? - For streaming updates, may previous assignments be changed? ### Part 1: Produce and Maximize a Matching Describe how to produce a valid assignment, then how to maximize the number of assigned problems. State how you construct eligibility efficiently and give time and space complexity in terms of nodes and eligible edges. #### What This Part Should Cover - The bipartite-graph model and validity invariants - The distinction between greedy feasibility and maximum cardinality - An appropriate augmenting-path algorithm and its complexity - Avoiding an unnecessary all-pairs tag comparison ### Part 2: Distribute the Work Suppose the graph is too large for one machine. Design a distributed approach, including partitioning, coordination across partitions, convergence, and how you validate that the result is globally consistent. #### What This Part Should Cover - Candidate-edge generation through an inverted tag index - The correctness cost of cutting a graph across workers - A coordination or reconciliation strategy for contested vertices - Checkpointing, retries, and deterministic ownership ### Part 3: Handle Streaming Changes Problems and programmers now arrive and depart continuously. Explain how you would maintain useful assignments under latency constraints and what optimality guarantee you can realistically offer. #### What This Part Should Cover - Incremental matching and bounded reassignments - Event ordering, deletion handling, and idempotency - A stated trade-off between immediate decisions and global optimality - Metrics for match rate, churn, latency, and fairness ### What a Strong Answer Covers - A source-faithful bipartite model with explicit objectives - Correctness reasoning for both local and distributed state changes - Honest complexity and optimality trade-offs - Practical treatment of skew, hot tags, failures, and observability ### Follow-up Questions - How would weighted preferences change the algorithm? - Can a maximal matching be much smaller than a maximum matching? - How would you keep one common tag from overwhelming a partition? - What fairness policy would you add if some programmers are repeatedly displaced?