Matching Tagged Problems to Skilled Programmers at Scale

0) Problem Restatement

Google asked: you have problems, each tagged with required skills (e.g., graphs, dp), and programmers, each with a skill set and a capacity (how many problems they can take). Assign problems to programmers who have the required skills, to maximize the number of problems assigned. Then extend it to very large inputs (distributed) and to a streaming setting where problems and programmers keep arriving.

1) Model: Bipartite Matching

• Left side: problems. Right side: programmers.
• An edge exists if the programmer has all of the problem's required skills (or enough of them, per the rules).
• Goal: choose edges so each problem gets at most one programmer and each programmer gets at most capacity problems, maximizing the matched problems.

This is maximum bipartite matching with capacities, which is solvable exactly as a max-flow problem:

source → each problem (capacity 1) → eligible programmers (capacity 1) → sink (capacity = programmer capacity)

The max flow = the max number of assigned problems.

flowchart LR
    S(("source")) --> P1["Problem: graphs"]
    S --> P2["Problem: dp"]
    S --> P3["Problem: graphs+dp"]
    P1 --> A["Alice - graphs, dp - cap 2"]
    P2 --> A
    P3 --> A
    P1 --> B["Bob - graphs - cap 1"]
    A --> T(("sink"))
    B --> T

2) Algorithms

• Greedy (simple): process problems in order of fewest eligible programmers first ("most constrained first"), and assign each to the eligible programmer with the most remaining capacity (or fewest other options). It's fast and often close to optimal, but not guaranteed.
• Exact: Hopcroft–Karp for unit capacities (O(E √V)), or Dinic's max-flow with capacities. For millions of edges, this is fine on one machine.
• Weighted version (prefer the best-fit programmer, e.g., skill level or cost): a min-cost max-flow or the Hungarian algorithm (for smaller sizes).

3) Building the Graph Efficiently

• Don't compare every problem with every programmer. Index programmers by skill: skill → set of programmers (bitsets). Eligible programmers for a problem = the intersection of the sets for its required skills. That's fast with bitset AND operations.
• Group identical skill profiles, since many programmers have the same set, to shrink the graph.

4) Scaling Up (distributed)

• Partition by skill domain: problems and programmers cluster naturally (frontend vs ML vs systems). Solve each partition independently in parallel, then run a small second pass to match leftovers across partitions.
• Distributed approximate matching: rounds of "propose and accept" (like the Gale–Shapley or auction algorithm), which parallelize well in a MapReduce or graph framework (Pregel/Spark GraphX). Each round, unmatched problems propose to eligible programmers with capacity, and programmers accept up to capacity.
• Exact global optimality at huge scale is expensive, so good approximations (within a few % of optimal) are usually acceptable. Say so.

5) Streaming Version

• Problems arrive continuously, so assign online: when a problem arrives, pick an eligible programmer with remaining capacity using a good rule (e.g., the one whose skills are least in demand, preserving flexible programmers for harder problems). Online greedy has known guarantees (it's at least 1/2 of optimal).
• Re-optimize periodically: every few minutes, run exact matching on the not-yet-started assignments and rebalance.
• Keep the skill index and remaining capacities in memory (or Redis), updated as programmers join or finish problems.

6) Wrap-Up

Model it as bipartite matching with capacities and solve it exactly as max-flow (Hopcroft–Karp/Dinic), building edges quickly with per-skill bitset indexes and grouped profiles. Use a most-constrained-first greedy when speed matters. At scale, partition by skill domain or run parallel propose/accept rounds for near-optimal results, and in streaming mode assign online with a smart greedy rule plus periodic re-optimization.