Lexicographically Smallest Topological Order
ByteDance● MediumFULLTIMEONSITE INTERVIEWProblem statement
Given a directed graph with vertices 0 through numNodes - 1, return a topological ordering of every vertex. Each row [u, v] in edges requires u to appear before v.
For this exercise, assume that when several valid orders exist, return the lexicographically smallest integer sequence. Compare two different orders at their first differing position; the order with the smaller integer there is smaller. Return the ordering itself, not a Boolean feasibility value.
If the graph contains a directed cycle, return an empty array; never return a partially processed prefix. An empty graph also returns an empty array. Self-loops are cycles. Duplicate edge rows impose the same precedence relationship and do not change the set of valid orders.
Function
topologicalOrder(numNodes: int, edges: int[][]) → int[]Examples
Example 1
numNodes = 4edges = [[2,0],[2,1]]return = [2,0,1,3]Initially vertices 2 and 3 are available, so choose 2. That releases 0 and 1. Choose 0, then 1, then 3, giving [2,0,1,3]. Keeping the initial available vertices in a FIFO queue would miss the smallest order.
Example 2
numNodes = 3edges = [[0,1],[1,2],[2,1]]return = []Vertices 1 and 2 form a directed cycle. Processing vertex 0 does not make a full ordering possible, so return an empty array rather than [0].
Example 3
numNodes = 0edges = []return = []There are no vertices and no edges, so the full ordering is empty.
Constraints
0 <= numNodes <= 2000.0 <= edges.length <= 10000.- Every edge row contains exactly
2integers. - Every edge endpoint is between
0and1999, inclusive, and is strictly smaller thannumNodes. - Self-loops and duplicate rows are allowed.