Topological Sort Problem | Dataford Interview Questions

Netflix's content processing pipeline contains stages that must run only after their prerequisite stages complete. Given n stages labeled 0 through n - 1 and a list of dependencies, return any valid execution order for all stages. If the dependencies contain a cycle, return an empty list.

Each dependency [stage, prerequisite] means prerequisite must appear earlier than stage in the result.

Formal Specification

Implement order_pipeline(n, dependencies), where n is an integer and dependencies is a list of integer pairs. Return a list containing every stage exactly once, or [] if no valid ordering exists.

Constraints

1 <= n <= 10^4
0 <= len(dependencies) <= 10^5
Each dependency contains two distinct stage IDs in [0, n - 1].
No dependency pair appears more than once.
A valid result may be any topological ordering.

Function Signature

def order_pipeline(n, dependencies):

Your question is Topological Sort Problem. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem