Problem RestatementProblem
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.
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
capacityproblems, 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.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
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 --> TDeep Dive — Choosing the assignment algorithmDeep dive
Problems need skills, programmers have skills and a capacity. The question is how many problems get assigned, and whether the answer is provably the best possible.
First eligible programmer wins
Walk the problems in order and give each one to the first programmer who is qualified and has capacity.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
P1["Problem A - needs graphs. Eligible: Sam, Rhea"] --> S["Assigned to Sam"]
P2["Problem B - needs graphs + dp. Eligible: Sam only"] --> NONE["Sam is full - B unassigned"]
NONE --> LOSS["A feasible complete assignment existed and was missed"]
ORDER["Change the input order"] --> DIFF["Completely different result"]The outcome depends on the order the problems happen to be listed in. Worse, it burns scarce programmers on problems that had alternatives, leaving constrained problems with nobody — the failure is systematic, not bad luck.
Greedy, most-constrained first
Process problems in order of fewest eligible programmers, and among eligible programmers prefer the one with the most remaining capacity.
A large improvement for two lines of change: the problems with the fewest options are served while options still exist. It is fast, order-independent, and usually close to optimal. It is still a heuristic — there are inputs where an earlier choice forecloses a better overall assignment, and nothing here can back that choice out.
Model it as a flow problem and solve it exactly
This is bipartite matching with capacities, which has exact polynomial algorithms:
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
SRC["Source"] -->|"capacity 1 each"| PR["Problem nodes"]
PR -->|"edge if the programmer has the required skills"| PG["Programmer nodes"]
PG -->|"capacity = how many they can take"| SNK["Sink"]
SNK --> MAX["Max flow = maximum number of problems assigned"]
W["Preferences - skill level, cost"] --> MCMF["Min-cost max-flow: the best assignment among the maximum ones"]- Unit capacities: Hopcroft–Karp, O(E√V). With capacities per programmer, Dinic's max-flow on the graph above.
- Augmenting paths are what greedy lacks. The algorithm can reassign an earlier match to free a programmer for a constrained problem — undoing a choice, which no greedy pass can do. That is precisely where the extra matches come from.
- Preferences become costs. When a best-fit matters — seniority, cost, past performance — min-cost max-flow finds the cheapest assignment among all maximum ones, so quality is optimised without sacrificing coverage.
Scale is rarely the reason to avoid this: millions of edges run comfortably on one machine. Build the graph efficiently by indexing programmers by skill so edges come from a lookup rather than a full cross product — that construction, not the solver, is usually the bottleneck.
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.
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.
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.
Wrap-UpWrap-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.