147Implement a dependency resolver using topological sorting
hardAbout 60 minutesCodinggraphstopological-sortdfskahn
Problem
Package managers, build tools and module bundlers all need to know what to install or build first. Implement:
findOrder(numCourses, prerequisites)(LeetCode 210):prerequisitesare pairs[a, b]meaning "takebbeforea". Return any order that takes every course, or[]if it is impossible (a cycle).resolveInstallOrder(packages):packagesmaps a name to its dependency names, for example{ app: ["react", "router"], router: ["react"], react: [] }. Return the install order (dependencies before dependents). Make it deterministic: when several packages are ready, take them in alphabetical order. Throw anError:Unknown dependency "x" required by "y"when a dependency is not inpackages;Circular dependency: a -> b -> a(the actual cycle path) when there is a cycle.
Try it yourself
Write your solution, run it, then submit to check it against the tests.
solution.jsJavaScript
Press Run or ⌘ Enter to execute your code.
Video walkthrough
Stuck? Watch someone solve it, then try again on your own.
Step-by-step
Draw an edge from each prerequisite to the course that needs it. A valid order is a topological order: every edge points forward. It exists exactly when the graph has no cycle.
Unlock the full solution
What's inside
- Step-by-step
- Approach
- Solution
- Complexity
- Edge cases
- Follow-up questions
- Tests
Includes 2 code listings, 5 edge cases, 4 follow-up questions.
One-time payment by UPI, card or net banking. Launch price.