How should I practice Topological Sort with Secondary Ordering?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Roblox phone screen problems in FastPrep.

Is Topological Sort with Secondary Ordering associated with Roblox?

FastPrep tags this as a Roblox phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Topological Sort with Secondary Ordering

Learn this problem

● Medium

RobloxFULLTIMEPHONE SCREEN

See Roblox hiring insights

Problem statement

You are given dependency rules as a 2D array of strings. In each row, the first string depends on the remaining strings in that row. Return an ordering in which every dependency appears before the item that depends on it.

This is a Course Schedule II / install-dependencies variant with two twists reported from Roblox interviews:

The input uses strings instead of integer course IDs.
The input is a 2D array, not a flat list of prerequisite pairs. rules[i][0] depends on each of rules[i][1..]. A row may contain only a single item with no prerequisites.

When more than one item is eligible to be output at the same time (all of its dependencies already placed), break the tie by the order in which the items first appear in the input. Scan the rows left to right, and within each row scan the strings left to right; the first time a string is seen fixes its appearance index. Among all currently-eligible items, always emit the one with the smallest appearance index next.

The graph edge direction is the common mistake: for a row ["Hair", "Head"], Hair depends on Head, so the edge must point Head -> Hair (and Hair gains indegree 1). Building the reverse edge produces a wrong order.

Approach: build the dependency graph and indegree counts, seed a min-heap (keyed by appearance index) with every indegree-0 item, and run Kahn's algorithm, pushing each neighbor into the heap as its indegree drops to 0. The heap is responsible only for the tie-breaker; the indegree bookkeeping enforces the dependency constraint.

Follow-up: a numeric variant gives integer course IDs and prerequisite pairs and asks you to always pick the smallest available course ID. It is the same structure with the heap keyed by the integer ID instead of appearance index.

Function

dependencyOrder(rules: String[][]) → String[]

Examples

Example 1

rules = [["Hair", "Head"], ["Hat", "Hair"], ["Head"]]return = ["Head", "Hair", "Hat"]

Hair depends on Head, so Head must come before Hair. Hat depends on Hair, so Hair must come before Hat. Head has no prerequisites. The only valid dependency order is Head -> Hair -> Hat.

Example 2

rules = [["app", "libA", "libB"], ["libA"], ["libB"]]return = ["libA", "libB", "app"]

app depends on both libA and libB. libA and libB are both eligible first; libA appears before libB in the input, so it is emitted first, then libB, then app once both prerequisites are placed.

Example 3

rules = [["C"], ["A"], ["B"]]return = ["C", "A", "B"]

There are no dependencies, so every item is eligible immediately. The tie-breaker emits them in order of first appearance in the input: C, then A, then B.

Constraints

1 <= rules.length
Each row has at least one string; rules[i][0] is the dependent item and rules[i][1..] are its prerequisites.
Strings consist of letters, digits, and underscores.
The dependency graph is acyclic (a valid ordering exists).
Ties among currently-eligible items are broken by first appearance order in the input.