Topological Sort Interview Questions

Optimal (Kahn's): Put indegree-zero nodes in a queue. Pop one, reduce neighbor indegrees, enqueue new zeros. If fewer than V nodes processed, a cycle exists.

Optimal (DFS): Finish a node, append to list, reverse at the end. Complexity: Time O(V + E) , Space O(V)

Kahn's algorithm: queue all nodes with indegree zero, peel them, reduce neighbor indegrees. If I processed fewer than n nodes, there is a cycle and no topological order. DFS with a stack also works: finish times reverse. I prefer Kahn in interviews because the cycle check is obvious. Course schedule is this problem. I would not sort by node id and hope. Order must respect edges.

Yes. Any time two nodes are incomparable — no path either way — I can emit them in either order. Kahn's algorithm's queue order decides which one I pick. If they want a unique order I check that the queue never holds more than one node, or I compare against a given sequence. Build order of courses often has many valid orders. I would ask if any valid order is enough.

Each package or task is a node. 'A depends on B' is an edge B to A if I must build B first. Topo order is a legal build order. A cycle is a circular dependency and the build should fail. I have explained this in interviews with npm or Maven in mind. The same graph is job scheduling with prerequisites. If tasks have durations I still topo, then I can add longest-path DP for the critical path.

I compare adjacent words, find the first differing characters, and add an edge earlier-letter to later-letter. Then topological sort. If a longer word is a prefix of a shorter one in the wrong way, the input is invalid. If the graph has a cycle, also invalid. This is topo plus careful prefix checks. I would not compare every pair of words if they already gave a sorted list — adjacent pairs are enough for the constraints.