Deploy services in waves

MediumAbout 30 minProblem 2 of 2 in Graphs: breadth-first searchDraft

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

  1. deployWaves(["web", "api", "db", "cache"], [["web", "api"], ["api", "db"], ["api", "cache"]])returns [["db", "cache"], ["api"], ["web"]]
  2. deployWaves(["a", "b"], [["a", "b"], ["b", "a"]])returns nulla waits for b, and b waits for a.
  3. 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.

Your solution

Tab indents. Press Esc, then Tab, to leave the editor. Ctrl+Enter runs the examples.

Esc
↑ ↓ to move↵ to open