Skip to content
RED SAGSkills
hard60 ptsgraphdevopstopological-sort

Parallel Install Waves for Packages

A build system installs packages in parallel waves. packages maps each package name to the list of packages it depends on.

First validate: every dependency must itself be a key of packages. If any is not, return { ok: false, reason: "missing", items } where items lists every offending "pkg->dep" pair once, sorted ascending.

Otherwise, wave 1 holds every package with no dependencies; each following wave holds every not-yet-installed package whose dependencies are all installed in earlier waves. Each wave is sorted ascending. If some packages can never be installed (they are on a dependency cycle or depend on one), return { ok: false, reason: "cycle", items } with those package names sorted ascending. Otherwise return { ok: true, waves }.

All sorting is plain string order.

Example 1

Input: packages = {"app":["web","db"],"web":["utils"],"db":["utils"],"utils":[]}
Output: {"ok":true,"waves":[["utils"],["db","web"],["app"]]}
Explanation: utils first, then db and web together, then app.

Example 2

Input: packages = {"a":["b","zz"],"b":[],"c":["yy","yy"]}
Output: {"ok":false,"reason":"missing","items":["a->zz","c->yy"]}
Explanation: zz and yy are not known packages.

Constraints

  • 0 <= number of packages <= 2000
  • Each package has at most 20 dependencies
  • A dependency list may repeat a name or name the package itself
Hint 1

Count unmet dependencies per package (Kahn's algorithm), but release a whole frontier at a time.

Hint 2

Packages left with unmet dependencies at the end are exactly the uninstallable ones.

Discussion 0

Join free to post in the discussion.

Good practice for: DevOps Engineer, Cloud Engineer, Site Reliability Engineer, Backend Developer, MLOps Engineer, Full Stack Developer

Run checks your code on 3 sample tests. Submit runs all 9 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.