Return a Package Build Order
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an API:
```python
get_dependencies(package) -> list[str]
```
It returns the direct dependencies of a given package. If package `A` depends on package `B`, then `B` must be built before `A`.
Given a target package name, return any valid build order for the target package and all packages it transitively depends on. Every dependency must appear before the package that depends on it.
The dependency graph is not provided upfront; you must discover only the dependency subgraph reachable from the target package by calling `get_dependencies` as needed.
Requirements:
- Return any valid build order; the order does not need to be unique.
- Only include packages that are required to build the target package.
- If a circular dependency exists in the reachable dependency graph, return an empty list or raise an error.
- Consider edge cases and failure cases, such as missing packages, duplicate dependencies, repeated API calls, and dependency cycles.
Quick Answer: This question evaluates a candidate's skills in dependency resolution, graph traversal and cycle detection while reasoning about an externally discovered dependency subgraph and ordering constraints.
Return a dependency-before-dependent build order for the target package and reachable dependencies, or [] on cycle.
Examples
Input: ({'app': ['lib', 'ui'], 'lib': ['core'], 'ui': ['core'], 'core': []}, 'app')
Expected Output: ['core', 'lib', 'ui', 'app']
Explanation: Shared dependency once.
Input: ({'a': ['b'], 'b': ['a']}, 'a')
Expected Output: []
Explanation: Cycle.
Input: ({}, 'solo')
Expected Output: ['solo']
Explanation: Missing package treated as no dependencies.
Hints
- DFS postorder over the dependency subgraph.