Quick Overview

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 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.

Hints

  1. DFS postorder over the dependency subgraph.

Loading coding console...