Resolve Package Dependencies with Cycle Detection
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement `buildOrder(dependencies, target)`, which returns the packages needed to build and install `target` in a valid dependency-first order.
`dependencies` maps a package name to its direct dependencies. A package absent from the map has no dependencies. Only packages reachable from `target` belong in the result. Shared dependencies must appear exactly once.
Use depth-first search with two states that distinguish a package on the current recursion path from a package whose dependencies are complete. If any cycle is reachable from `target`, return an empty list and do not produce a partial order.
To make the result deterministic, every dependency list is supplied in strictly increasing lexicographic order. Visit dependencies in that order and append a package after all of its dependencies. A caller can implement `installWithDependencies(target)` by invoking each returned package object's `install()` method once, from left to right.
## Constraints
- Package names are nonempty ASCII strings and are compared byte-for-byte.
- Dependency lists contain no duplicates and are already sorted.
- The reachable graph contains at most `200,000` packages and `400,000` dependency edges.
- `target` may be absent from the map, in which case the result is `[target]`.
- Expected graph traversal time is `O(V + E)` over packages and edges reachable from `target`, with `O(V)` state and output space. An implementation may replace recursive calls with an explicit stack when recursion depth is unsafe.
## Example 1
```text
dependencies = {
"app": ["core", "ui"],
"core": ["util"],
"ui": ["util"],
"util": []
}
target = "app"
```
The result is:
```text
["util", "core", "ui", "app"]
```
`util` is emitted once even though two packages depend on it, and every dependency appears before the package that needs it.
## Example 2
```text
dependencies = {
"a": ["b"],
"b": ["c"],
"c": ["a"]
}
target = "a"
```
The reachable graph contains a cycle, so the result is `[]`.
Quick Answer: Produce a deterministic dependency-first build order for every package reachable from a target. Candidates must handle shared dependencies, references to undeclared packages, deep graphs, and reachable cycles without emitting a partial result.
Implement `buildOrder(dependencies, target)`, which returns every package that must be built and installed in order to build `target`, in a valid dependency-first order.
`dependencies` maps a package name to the list of packages it directly depends on. A package that is **absent** from the map has no dependencies. Only packages reachable from `target` (including `target` itself) belong in the result, and a shared dependency appears exactly **once** no matter how many packages need it. Packages present in `dependencies` but not reachable from `target` must not appear at all.
## Cycles
If any cycle is reachable from `target`, return an **empty list**. Never return a partial order: one reachable cycle collapses the whole answer to `[]`, even when some packages could have been ordered. A cycle that exists in `dependencies` but is **not** reachable from `target` is irrelevant and must not change the answer.
Distinguishing a cycle from a shared dependency needs two distinct "seen" states: a package still on the current search path versus a package whose dependencies are already complete. Re-reaching a completed package is normal; re-reaching a package on the current path is a cycle.
## Exact output order (this is graded)
The answer is pinned to one specific traversal, so exactly one output is correct:
1. Every dependency list is supplied in strictly increasing lexicographic order.
2. Run a depth-first search from `target`, visiting each package's dependencies left to right in that supplied order.
3. Append a package to the result immediately after all of its dependencies have been appended, and only the first time it completes.
In other words the result is the DFS post-order of the subgraph reachable from `target` with children visited in the given sorted order. Other valid topological orders (for example a Kahn / BFS ordering) are **not** accepted.
A caller can then implement `installWithDependencies(target)` by invoking each returned package object's `install()` method once, from left to right.
## Example 1
```text
dependencies = {
"app": ["core", "ui"],
"core": ["util"],
"ui": ["util"],
"util": []
}
target = "app"
```
Result: `["util", "core", "ui", "app"]`
`util` is emitted once even though two packages depend on it, and every dependency precedes the package that needs it. Note the order is *not* `["util", "ui", "core", "app"]`: `core` is visited before `ui` because the list `["core", "ui"]` is given in that order.
## Example 2
```text
dependencies = {
"a": ["b"],
"b": ["c"],
"c": ["a"]
}
target = "a"
```
The reachable graph contains a cycle, so the result is `[]`.
## Example 3
```text
dependencies = {
"app": ["safe"],
"safe": [],
"x": ["y"],
"y": ["x"]
}
target = "app"
```
Result: `["safe", "app"]`
The `x`/`y` cycle is never reached from `app`, so it does not affect the answer, and `x` and `y` are excluded from the result because they are unreachable.
Constraints
- Package names are nonempty ASCII strings and are compared byte-for-byte (comparison is case-sensitive, so "Zed" and "zed" are different packages).
- Every dependency list contains no duplicates and is already sorted in strictly increasing lexicographic order.
- The reachable graph contains at most 200,000 packages and at most 400,000 dependency edges.
- A package absent from `dependencies` has no dependencies; `target` may itself be absent, in which case the result is `[target]`.
- `dependencies` may contain packages that are not reachable from `target`; those never appear in the result.
- The problem carries no numeric inputs or outputs: every value is a package-name string.
- Expected graph traversal time is O(V + E) over the packages and edges reachable from `target`, with O(V) state and output space.
- A reachable dependency chain may be as long as the number of reachable packages, so recursion depth can be unsafe; an implementation may replace recursive calls with an explicit stack.
Examples
Input: ({'app': ['core', 'ui'], 'core': ['util'], 'ui': ['util'], 'util': []}, 'app')
Expected Output: ['util', 'core', 'ui', 'app']
Input: ({'a': ['b'], 'b': ['c'], 'c': ['a']}, 'a')
Expected Output: []
Hints
- One boolean "visited" flag cannot tell a cycle apart from a shared dependency. Give each package three states: never touched, currently on the search path, and fully finished.
- Reaching a fully finished package is normal and must not emit it a second time; reaching a package that is still on the current path is the cycle signal, and it should abandon the entire result rather than what has been collected so far.
- The stated bounds allow a chain far deeper than a default recursion limit. An explicit stack of (package, index-of-next-dependency-to-visit) frames performs the same post-order walk without recursing.