Roblox·Machine Learning Engineer·Technical Phone Screen·Senior

Senior

Jul 2026

Summary

Got a coding question from Roblox for an ML Engineer role that was basically a topological sort with a specific deterministic leveling rule. The problem was well-defined but the edge cases around missing deps and cycles needed careful handling.

Questions Asked (1)

Given a list of component dependency declarations, return a valid build order where each component appears only after all its dependencies. The order must follow a deterministic wave-based leveling rule: at each step, all components whose dependencies are satisfied get emitted together, sorted by their original declaration index. Return an error if any dependency is undeclared or if there's a cycle.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The core of it is Kahn's algorithm but the twist is you can't just do a standard BFS and call it done.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the dependencies as a directed graph and perform a topological sort using Kahn's algorithm, but with a twist: at each iteration, collect all nodes with in-degree zero, sort them by their original declaration index, and emit them as a wave. Validate upfront that all dependencies are declared and detect cycles by checking if all nodes are emitted.

Pro tip: Clarify the deterministic wave-based rule upfront: it's not just any topological order, but a level-by-level emission where each wave is sorted by declaration index. This ensures reproducibility and matches the expected output.

1. Parse and Validate Input

Build a mapping from component names to their declaration indices and dependency lists. Check that every dependency is declared; if not, return an error immediately.

2. Build Graph and Compute In-Degrees

Construct an adjacency list for the dependency graph and compute the in-degree for each component (number of unmet dependencies).

3. Initialize Wave with Zero In-Degree Nodes

Collect all components with in-degree zero, sort them by declaration index, and add them to the current wave.

4. Process Waves Iteratively

For each wave, emit the sorted components, then for each component, decrement the in-degree of its dependents. Collect all dependents that reach zero in-degree, sort them by declaration index, and form the next wave. Repeat until no nodes remain.

5. Detect Cycles and Return Result

If the total number of emitted components is less than the total number of components, a cycle exists; return an error. Otherwise, return the concatenated waves as the build order.

Key Points to Mention

Topological sorting with Kahn's algorithm
Handling undeclared dependencies by validation
Cycle detection via incomplete emission
Deterministic ordering by sorting each wave by declaration index
Time and space complexity: O(V + E) with sorting overhead
Edge cases: empty input, single component, multiple independent components

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.