How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Compute build order from dependencies

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.

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.

Input: (3, [])

Expected Output: [0, 1, 2]

Explanation: No dependencies; all three packages are independent disconnected components, emitted in ascending label order.

Input: (1, [])

Expected Output: [0]

Explanation: A single package with no dependencies builds immediately.

Input: (0, [])

Expected Output: []

Explanation: There are no packages, so the (trivially valid) build order is empty.

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

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

Explanation: The duplicate edge [1,0] is collapsed to one. Order: 0, then 1, then 2; package 3 has no dependencies and is appended (smallest ready label whenever it becomes available).

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

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

Explanation: A wider DAG; the smallest-label tie-break yields the canonical ascending order that still respects every dependency.

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

Expected Output: []

Explanation: 0 -> needs 1, 1 -> needs 2, 2 -> needs 0 forms a 3-node cycle, so the function returns an empty list.

Hints

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

Quick Overview