Roblox·Software Engineer·Technical Phone Screen·Senior

Senior

Apr 2026

Summary

Roblox technical phone screen that was basically one meaty graph problem the whole time. The question sounds straightforward until you get into the tie-breaking rule and realize you need more than just a standard BFS approach.

Questions Asked (1)

Given a list of dependencies as a 2D array of directed edges (e.g. [[a, b], [c, d], ...] meaning a must come before b), return a valid topological ordering. When multiple nodes are available at the same step, break ties by the order each node first appears as a source in the edge list.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I started with Kahn's algorithm and felt pretty good about it, but the tie-breaking requirement tripped me up for a few minutes.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use Kahn's algorithm (BFS-based topological sort) with a min-heap or sorted list to break ties by the order nodes first appear as sources. First, build the graph and compute in-degrees while recording the first-seen order of source nodes. Then repeatedly extract the available node with the smallest first-seen index, append it to the result, and decrement in-degrees of its neighbors.

Pro tip: Clarify edge cases upfront—such as cycles, duplicate edges, or nodes that appear only as destinations—and mention that the tie-breaking rule is a stable ordering constraint that can be implemented with a priority queue keyed by first-seen index. This shows you think about robustness and real-world data quality.

1. Parse and Build Graph

Iterate through the edge list to build an adjacency list and compute in-degrees for each node. Also record the first-seen order of each node when it appears as a source (the first element of an edge).

2. Initialize Available Nodes

Collect all nodes with in-degree zero into a priority queue (or sorted list) ordered by their first-seen index. If a node never appears as a source, assign it a default order (e.g., infinity) or handle it as needed.

3. Process Nodes with Tie-Breaking

While the priority queue is not empty, extract the node with the smallest first-seen index, add it to the topological order, and for each neighbor, decrement its in-degree. If a neighbor's in-degree becomes zero, insert it into the priority queue.

4. Detect Cycles and Validate

After processing, if the topological order does not contain all nodes, a cycle exists. Return an error or empty list as appropriate. Otherwise, return the valid ordering.

Key Points to Mention

Kahn's algorithm (BFS-based topological sort) is ideal because it naturally supports tie-breaking via a priority queue.
Tie-breaking rule: nodes are ordered by the index of their first appearance as a source in the edge list; this requires a stable ordering key.
Handling nodes that never appear as sources: assign them a default order (e.g., after all source nodes) or treat them as having infinite first-seen index.
Cycle detection: if the result size is less than the number of unique nodes, a cycle exists, and no valid topological ordering is possible.
Time complexity: O(V + E + V log V) with a heap, or O(V^2) with a simple list; space complexity O(V + E).
Edge cases: empty input, duplicate edges, self-loops, and disconnected components.

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