Coding questions · Uber

Return a Package Build Order

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.

You are given an API:

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.

Package Build Order

Examples

Example 1

Input: ({'app': ['lib', 'ui'], 'lib': ['core'], 'ui': ['core'], 'core': []}, 'app')
Output: ['core', 'lib', 'ui', 'app']

Explanation: Shared dependency once.

Example 2

Input: ({'a': ['b'], 'b': ['a']}, 'a')
Output: []

Explanation: Cycle.

Hints

DFS postorder over the dependency subgraph.