Topological Sort Implementation | Dataford Interview Questions

Siemens NX workflows may contain modules that depend on other modules being initialized first. Given num_modules and directed dependency pairs, return a valid initialization order using topological sort. If multiple valid orders exist, return the lexicographically smallest one. If the dependencies contain a cycle, return an empty list.

Formal Specification

Implement topological_order(num_modules, prerequisites), where module IDs are integers from 0 through num_modules - 1. Each pair [module, prerequisite] means prerequisite must appear before module in the output.

Return a list containing every module exactly once, or [] when no valid ordering exists.

Constraints

1 <= num_modules <= 10^5
0 <= len(prerequisites) <= 2 * 10^5
Each prerequisite pair has the form [module, prerequisite].
Module IDs are in the range [0, num_modules - 1].
Dependency pairs are unique and contain distinct module IDs.

Function Signature

def topological_order(num_modules, prerequisites):

Your question is Topological Sort Implementation. 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