Topological Sort Implementation | Dataford Interview Questions

Second question in interview was basic topological sort.

Implement topological_sort(num_nodes, prerequisites) for a directed graph. Each pair [a, b] means b must appear before a; return any valid ordering of nodes 0 through num_nodes - 1, or [] if the graph contains a cycle.

The function signature is topological_sort(num_nodes, prerequisites). Return a list of node IDs.

Constraints

1 <= num_nodes <= 10^4
0 <= len(prerequisites) <= 5 * 10^4
Each prerequisite pair has the form [course, prerequisite]
0 <= course, prerequisite < num_nodes
A pair may not contain duplicate node IDs

Function Signature

def topological_sort(num_nodes, prerequisites):

Whenever you're ready, walk me through your approach or go straight to the code. The requirements are in the Question tab.

Problem

Second question in interview was basic topological sort.

The function signature is topological_sort(num_nodes, prerequisites). Return a list of node IDs.

Constraints

1 <= num_nodes <= 10^4
0 <= len(prerequisites) <= 5 * 10^4
Each prerequisite pair has the form [course, prerequisite]
0 <= course, prerequisite < num_nodes
A pair may not contain duplicate node IDs

Function Signature

def topological_sort(num_nodes, prerequisites):

Whenever you're ready, walk me through your approach or go straight to the code. The requirements are in the Question tab.