Deploy services in waves
A re-solve is due. Start from a blank template and solve it without the editorial. That is what makes the pattern stick.
The problem
A release deploys services in waves. Each entry of deps is [service, needs]: service may only deploy after needs has deployed in an earlier wave.
Each wave contains every service whose needs are all in earlier waves, in the order they appear in services. Return the waves, or null if some services can never deploy because their needs form a cycle.
- 1 ≤ services.length ≤ 100,000, names distinct
- 0 ≤ deps.length ≤ 200,000, every name is in services
- deps may repeat
Examples
deployWaves(["web", "api", "db", "cache"], [["web", "api"], ["api", "db"], ["api", "cache"]])returns[["db", "cache"], ["api"], ["web"]]deployWaves(["a", "b"], [["a", "b"], ["b", "a"]])returnsnulla waits for b, and b waits for a.deployWaves(["x", "y"], [])returns[["x", "y"]]
Hints
Hint 1 of 2
For each service, count how many of its needs have not deployed yet, counting a repeated pair once. The first wave is every service at zero.
Hint 2 of 2
Keep, for each service, the list of services that need it. When a wave deploys, lower the counts of everything that needs its services; those that reach zero form the next wave. Sort each wave by position in services.
Editorial
Opens once you solve the problem, or after three checked attempts.
Read the editorial and a reference solution
This is a topological order built in waves. Count, for every service, how many distinct needs it is still waiting on, and keep the reverse lists: for each service, who needs it. The services waiting on nothing form the first wave.
Deploying a wave lowers the counts of everything that needs one of its services; the ones that reach zero form the next wave. Sort each wave by position in services to keep the required order. Each dependency is looked at once, so the work is linear apart from the sorting.
Repeated pairs must count once, or a service waits for a need that will only ever be done once. And if the waves run out before every service has deployed, the rest wait on each other in a cycle: return null instead of a partial plan.
function deployWaves(services, deps) {
const pos = new Map(services.map((s, i) => [s, i]));
const waiting = new Array(services.length).fill(0);
const neededBy = services.map(() => []);
const seen = new Set();
for (const [s, need] of deps) {
const key = s + '\u0000' + need;
if (seen.has(key)) continue;
seen.add(key);
waiting[pos.get(s)]++;
neededBy[pos.get(need)].push(pos.get(s));
}
let wave = services.map((_, i) => i).filter((i) => waiting[i] === 0);
const waves = [];
let done = 0;
while (wave.length) {
waves.push(wave.map((i) => services[i]));
done += wave.length;
const next = [];
for (const i of wave) for (const j of neededBy[i]) if (--waiting[j] === 0) next.push(j);
wave = next.sort((a, b) => a - b);
}
return done === services.length ? waves : null;
}Complexity. O(V + E) for V services and E dependencies, plus sorting each wave: O(V log V) in all.
Your solution
TypeScript types are removed before the tests run, not checked: the tests judge what the code does.
Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.