Quick Overview

This question evaluates understanding of graph algorithms and dependency resolution, specifically topological ordering and cycle detection, within the Coding & Algorithms domain and tests both conceptual understanding and practical application of graph traversal and ordering techniques.

Compute build order from dependencies

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given a set of package build dependencies, output a valid build order so that each package is built only after all of its dependencies. The input is a list of (package, dependency) pairs or an adjacency list. Return one valid order, or report that no order exists if there is a cycle. Explain your algorithm, analyze time and space complexity, handle edge cases such as disconnected components and duplicate dependencies, and compare a BFS in-degree approach (Kahn's algorithm) with a DFS post-order approach, justifying your choice.

Quick Answer: This question evaluates understanding of graph algorithms and dependency resolution, specifically topological ordering and cycle detection, within the Coding & Algorithms domain and tests both conceptual understanding and practical application of graph traversal and ordering techniques.

You are given `n` packages labeled `0` to `n - 1` and a list of build `dependencies`. Each pair `[a, b]` means package `a` depends on package `b`, so `b` must be built **before** `a`. Return one valid build order such that every package appears only after all of its dependencies. If no valid order exists (the dependency graph contains a cycle), return an empty list. To make the answer unique and easy to grade, when several packages are simultaneously ready to be built, always pick the one with the **smallest label** first. Duplicate dependency pairs may appear and must be treated as a single edge. Packages with no dependencies (including fully disconnected ones) are still part of the output. **Example 1** ``` Input: n = 4, dependencies = [[1,0],[2,0],[3,1],[3,2]] Output: [0, 1, 2, 3] ``` Package 0 has no dependency, 1 and 2 depend on 0, and 3 depends on both 1 and 2. **Example 2** ``` Input: n = 2, dependencies = [[1,0],[0,1]] Output: [] ``` 0 and 1 depend on each other — a cycle, so no order exists. **Example 3** ``` Input: n = 3, dependencies = [] Output: [0, 1, 2] ``` No dependencies; all three are independent components, returned in label order.

Constraints

  • 0 <= n <= 10^4
  • 0 <= dependencies.length <= 10^5
  • Each dependency is a pair [a, b] with 0 <= a, b < n and a != b
  • Duplicate dependency pairs may appear and count as one edge
  • Among packages that are simultaneously ready, build the smallest-label one first
  • Return [] if and only if the dependency graph contains a cycle

Examples

Input: (4, [[1, 0], [2, 0], [3, 1], [3, 2]])

Expected Output: [0, 1, 2, 3]

Explanation: 0 builds first (no deps); then 1 and 2 (both depend only on 0, smaller label 1 first); finally 3 (depends on 1 and 2).

Input: (2, [[1, 0], [0, 1]])

Expected Output: []

Explanation: 0 depends on 1 and 1 depends on 0 — a 2-node cycle, so no valid build order exists.

Hints

  1. Model packages as nodes and each dependency [a, b] as a directed edge b -> a (b must come before a). The build order is a topological sort of this graph.
  2. Use Kahn's algorithm: repeatedly take a node with in-degree 0, append it to the order, and decrement the in-degree of its successors. Deduplicate edges first so duplicate pairs don't inflate in-degrees.
  3. For the deterministic 'smallest label first' rule, replace the plain queue with a min-heap of ready nodes. If at the end you have placed fewer than n nodes, some nodes were stuck in a cycle — return an empty list.
  4. The alternative DFS post-order approach pushes a node onto a stack after visiting all its dependencies, then reverses the stack; it detects cycles via a recursion/'in-progress' marker. Kahn's is often preferred here because in-degree tracking makes the smallest-label tie-break and cycle reporting straightforward without deep recursion.

Loading coding console...