Produce a valid dependency installation order with DFS state tracking, cycle detection, dependency-only packages, and exactly-once handling of shared prerequisites.
Given a map from each package to the list of packages it depends on, return an installation order in which every dependency is installed before its dependent. Install each package once, including packages that appear only in dependency lists. Report a cycle when no valid order exists.
### Constraints & Assumptions
Any valid topological order is acceptable. Treat missing map entries as packages with no listed dependencies. Duplicate dependency mentions must not duplicate installation.
### Clarifying Questions to Ask
- Can the graph contain cycles or disconnected components?
- Are packages appearing only as dependencies considered leaf packages?
```hint Distinguish unfinished from finished visits
Encountering a package on the current recursion path means something different from encountering one already installed.
```
### What a Strong Answer Covers
- Three-state traversal or an equivalent indegree method.
- Appending a package only after all dependencies finish.
- Cycle detection and exactly-once output across shared dependencies.
### Follow-up Questions
- How would you identify packages that can be installed in parallel?
- How would you avoid recursion-depth limits for a long dependency chain?
Overview: Produce a valid dependency installation order with DFS state tracking, cycle detection, dependency-only packages, and exactly-once handling of shared prerequisites.
Given a map from each package to the list of packages it depends on, return an installation order in which every dependency is installed before its dependent. Install each package once, including packages that appear only in dependency lists. Report a cycle when no valid order exists.
Constraints & Assumptions
Any valid topological order is acceptable. Treat missing map entries as packages with no listed dependencies. Duplicate dependency mentions must not duplicate installation.
Clarifying Questions to Ask Guidance
Can the graph contain cycles or disconnected components?
Are packages appearing only as dependencies considered leaf packages?
What a Strong Answer Covers Guidance
Three-state traversal or an equivalent indegree method.
Appending a package only after all dependencies finish.
Cycle detection and exactly-once output across shared dependencies.
Follow-up Questions Guidance
How would you identify packages that can be installed in parallel?
How would you avoid recursion-depth limits for a long dependency chain?