Level-Ordered Dependency Build Order
Company: Roblox
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Level-Ordered Dependency Build Order
You are given a list of **dependency declarations**. Each declaration is a non-empty list of strings:
- The **first element** is a component (a node).
- The **remaining elements** (if any) are the components it depends on — every dependency must be built **before** the component itself.
You must return a valid **build order**: a sequence in which every component appears only after all of its dependencies have already appeared.
## Build order rule (deterministic leveling)
The build proceeds in waves. At each step, **every** component whose dependencies have all already been built becomes buildable at the same time. These newly buildable components form one level. Within a single level, output the components in the **order their declarations appear in the input** (i.e., sorted by the index of the declaration in which the component is the first element). Then move to the next wave and repeat until all components are built.
## Error conditions
Return `["Error"]` (a single-element list containing the string `Error`) if either condition holds:
- **Missing dependency** — some component is listed as a dependency (a non-first element) but is never declared as a first element of any declaration.
- **Circular dependency** — the dependencies form a cycle, so no valid build order exists. A component that depends on itself counts as a cycle.
If both an error condition and a partial order exist, still return `["Error"]`.
## Input / output format
- **Input:** a list of declarations. Each declaration is a list of strings with length $\ge 1$. Element `0` is the component name; elements `1..` are its dependencies.
- **Output:** a list of strings giving the components in a valid build order, or exactly `["Error"]`.
## Constraints & assumptions
- Each distinct component is declared as the first element of **at most one** declaration. A single declaration may list multiple dependencies; that one declaration captures all of that component's dependencies.
- Component names are case-sensitive strings.
- A declaration may repeat a dependency name; duplicates have the same meaning as listing it once.
- There is at least one declaration. Total number of components and dependencies fits comfortably in memory.
## Examples
**Example 1**
```
Input: [["head"], ["torso"], ["leg"]]
Output: ["head", "torso", "leg"]
```
No component has dependencies, so all three are buildable in the first wave and are emitted in declaration order.
**Example 2**
```
Input: [["head", "leg"], ["leg", "head"]]
Output: ["Error"]
```
`head` depends on `leg` and `leg` depends on `head`: a cycle.
**Example 3**
```
Input: [["head"], ["leg", "torso"]]
Output: ["Error"]
```
`leg` depends on `torso`, but `torso` is never declared as a first element: a missing dependency.
**Example 4**
```
Input: [["hair", "head"], ["torso"], ["leg", "torso"], ["head"]]
Output: ["torso", "head", "hair", "leg"]
```
First wave: components with no unmet dependencies are `torso` (declaration index 1) and `head` (declaration index 3), emitted in declaration order as `torso`, `head`. Second wave: `hair` (needs `head`, now built, declaration index 0) and `leg` (needs `torso`, now built, declaration index 2), emitted as `hair`, `leg`.
Quick Answer: This question evaluates a candidate's ability to model dependency relationships as a graph and produce a valid topological build order. It tests knowledge of level-by-level (BFS-style) topological sorting, along with correct detection of cycles and missing references, a common way to assess graph traversal and edge-case reasoning in coding interviews.
You are given a list of dependency declarations. Each declaration is a non-empty list of strings: the first element is a component (a node), and the remaining elements (if any) are the components it depends on — every dependency must be built before the component itself.
Return a valid build order as follows. The build proceeds in waves. At each step, every component whose dependencies have all already been built becomes buildable at the same time; these form one level. Within a single level, output the components in the order their declarations appear in the input (sorted by the index of the declaration in which the component is the first element). Then move to the next wave and repeat until all components are built.
Return exactly ["Error"] if either condition holds:
- Missing dependency: some component is listed as a dependency (a non-first element) but is never declared as a first element of any declaration.
- Circular dependency: the dependencies form a cycle, so no valid build order exists. A component that depends on itself counts as a cycle.
Assumptions: each distinct component is declared as the first element of at most one declaration; component names are case-sensitive; duplicate dependency names within a declaration are treated as one; there is at least one declaration.
Example 1: Input [["head"], ["torso"], ["leg"]] -> Output ["head", "torso", "leg"].
Example 2: Input [["head", "leg"], ["leg", "head"]] -> Output ["Error"] (cycle).
Example 3: Input [["head"], ["leg", "torso"]] -> Output ["Error"] (torso never declared).
Example 4: Input [["hair", "head"], ["torso"], ["leg", "torso"], ["head"]] -> Output ["torso", "head", "hair", "leg"].
Constraints
- Each declaration is a list of strings of length >= 1; element 0 is the component name, elements 1.. are its dependencies.
- Each distinct component is declared as the first element of at most one declaration.
- Component names are case-sensitive strings.
- A declaration may repeat a dependency name; duplicates count once.
- There is at least one declaration.
- Return exactly ["Error"] on a missing dependency or any cycle (including a self-dependency).
Examples
Input: [["head"], ["torso"], ["leg"]]
Expected Output: ["head", "torso", "leg"]
Explanation: No component has dependencies, so all three are buildable in the first wave and are emitted in declaration order.
Input: [["head", "leg"], ["leg", "head"]]
Expected Output: ["Error"]
Explanation: head depends on leg and leg depends on head: a cycle, so no valid order exists.
Input: [["head"], ["leg", "torso"]]
Expected Output: ["Error"]
Explanation: leg depends on torso, but torso is never declared as a first element: a missing dependency.
Input: [["hair", "head"], ["torso"], ["leg", "torso"], ["head"]]
Expected Output: ["torso", "head", "hair", "leg"]
Explanation: Wave 1: torso (index 1) and head (index 3) have no unmet deps, emitted in declaration order. Wave 2: hair (needs head, index 0) and leg (needs torso, index 2), emitted as hair, leg.
Input: [["a", "a"]]
Expected Output: ["Error"]
Explanation: a depends on itself: a self-loop counts as a cycle.
Input: [["x"]]
Expected Output: ["x"]
Explanation: A single component with no dependencies builds immediately.
Input: [["c", "b"], ["b", "a"], ["a"]]
Expected Output: ["a", "b", "c"]
Explanation: A linear chain: a first (no deps), then b (needs a), then c (needs b) — one component per wave.
Input: [["a", "b", "c"], ["b"], ["c"]]
Expected Output: ["b", "c", "a"]
Explanation: Wave 1: b (index 1) and c (index 2) build; wave 2: a builds once both of its dependencies are ready.
Hints
- This is a topological sort. Model each declaration as a node whose in-edges are its dependencies, then peel off nodes with no remaining unmet dependencies.
- Process one whole 'wave' at a time so you can order the components within a level by their original declaration index — a plain queue-based Kahn's algorithm won't guarantee that tie-break.
- Before sorting, check that every dependency is actually declared somewhere; an undeclared dependency is the 'missing dependency' error.
- If at some wave no component is buildable yet components remain, a cycle exists — return ["Error"]. A component that lists itself as a dependency is a self-loop cycle.