What is Topological Sort?
A topological sort of a Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge (u → v), u appears before v. This represents a valid execution order for tasks with dependencies. Topological sort is only possible if the graph has no cycles (it is a DAG). If a cycle exists, no valid ordering exists. Two standard algorithms: Kahn’s (BFS-based, uses in-degree) and DFS post-order.
Kahn’s Algorithm (BFS-based)
Maintain the in-degree (number of incoming edges) for each node. Start with all nodes whose in-degree is 0 (no dependencies). Repeatedly: remove a zero-in-degree node from the queue, add to the result, decrement the in-degree of its neighbors, enqueue neighbors that now have in-degree 0. If the result contains all nodes: valid topological order. If fewer than all nodes: the graph has a cycle (the remaining nodes form a cycle with no zero-in-degree entry point).
from collections import deque
def topological_sort_kahn(graph, n):
in_degree = [0] * n
for u in range(n):
for v in graph[u]:
in_degree[v] += 1
queue = deque([i for i in range(n) if in_degree[i] == 0])
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
return order if len(order) == n else [] # empty = cycle detectedDFS Post-Order
DFS-based topological sort: run DFS on every unvisited node. When DFS finishes a node (all its descendants are processed), push it onto a stack. Reverse the stack to get the topological order. Cycle detection: track three states — UNVISITED, VISITING (currently in the DFS stack), VISITED (fully processed). If we encounter a VISITING node during DFS: a back edge exists — cycle detected.
def topological_sort_dfs(graph, n):
UNVISITED, VISITING, VISITED = 0, 1, 2
state = [UNVISITED] * n
result = []
has_cycle = [False]
def dfs(u):
if has_cycle[0]: return
state[u] = VISITING
for v in graph[u]:
if state[v] == VISITING:
has_cycle[0] = True; return
if state[v] == UNVISITED:
dfs(v)
state[u] = VISITED
result.append(u)
for i in range(n):
if state[i] == UNVISITED:
dfs(i)
return [] if has_cycle[0] else result[::-1]Course Schedule (LC 207, 210)
LC 207: can all courses be finished? = does the prerequisite graph have a cycle? Run Kahn’s: if the topological order contains all courses, no cycle. LC 210: return a valid course order. Return the topological order from Kahn’s. Both use the same algorithm — 207 just checks existence, 210 returns the actual order. Key: build the adjacency list from the prerequisites list: prerequisites[i] = [a, b] means b → a (b is a prerequisite of a — b must come before a). Edge direction: b → a means a depends on b.
Parallel Tasks with Dependencies (LC 1136, 1203)
LC 1136 (Parallel Courses): find the minimum number of semesters to complete all courses, where you can take multiple courses in parallel if their prerequisites are satisfied. Modified Kahn’s: process all zero-in-degree nodes in one semester (one BFS level). Count the number of BFS levels = minimum semesters. LC 1203 (Sort Items by Groups Respecting Dependencies): two-level topological sort. First sort items within each group; then sort groups. Build a group-level DAG and an item-level DAG. Run topological sort on both; combine results.
Alien Dictionary (LC 269)
Given a sorted list of words in an alien language, determine the character ordering. Build a DAG: for each adjacent pair of words, find the first differing character position — that pair gives an edge (earlier_char → later_char). Run topological sort on the character DAG. Edge case: if word A is a prefix of word B but appears after B in the list, the input is invalid (return “”.) O(C) time where C = total characters in all words.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the difference between Kahn’s algorithm and DFS-based topological sort?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Kahn’s algorithm is iterative (BFS-based) and uses in-degrees. It processes nodes with no incoming edges first, simulating the removal of satisfied prerequisites. It naturally detects cycles: if the output has fewer nodes than the graph, the remaining nodes form a cycle. DFS-based topological sort is recursive and uses post-order traversal: a node is added to the result only after all its descendants are fully processed (post-order). Cycle detection requires tracking the current DFS stack (VISITING state). Differences: Kahn’s is usually easier to implement iteratively and avoids recursion stack overflow for large graphs. DFS-based is more natural if you’re already writing a DFS traversal. Both are O(V+E). For interview purposes: Kahn’s is preferred because cycle detection is a simple size check, and BFS iteration is easier to reason about than DFS state tracking.”
}
},
{
“@type”: “Question”,
“name”: “How do you use topological sort to find the minimum number of steps to complete tasks with dependencies?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “This is the Parallel Courses problem (LC 1136). Modify Kahn’s algorithm to process all zero-in-degree nodes in one “round” (one BFS level) rather than one at a time. Each round represents one semester or parallel execution step. Count the number of rounds to process all nodes — this is the minimum number of steps (since all nodes in one round can execute simultaneously). Implementation: instead of processing one node per iteration, process the entire queue for the current level. After processing a level, all newly zero-in-degree nodes form the next level. If at the end, fewer than n nodes were processed: cycle detected (not all tasks completable). The answer is the number of levels (BFS depth). This is exactly BFS shortest-path level counting applied to task scheduling.”
}
},
{
“@type”: “Question”,
“name”: “How do you build the prerequisite graph for the Course Schedule problem?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “LC 207/210: prerequisites is a list of [a, b] pairs meaning “course b must be taken before course a.” Build an adjacency list: graph[b].append(a) (b must come before a, so edge goes from b to a). In-degree: in_degree[a] += 1 for each prerequisite [a, b]. This represents the dependency direction: b u2192 a means a depends on b. Common mistake: reversing the edge direction. To verify: if b u2192 a, then in Kahn’s, b will be processed before a (b appears earlier in the topological order). This matches the requirement that b is completed before a. After building the graph, run Kahn’s. If the result has all n courses: return it as a valid order (LC 210) or return True (LC 207). Empty result means a cycle exists.”
}
},
{
“@type”: “Question”,
“name”: “How does topological sort detect cycles in a directed graph?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Kahn’s algorithm cycle detection: after running until the queue is empty, count the nodes in the output. If output.length < n, the remaining nodes (those never added because their in-degree never reached 0) form a cycle. Each node in a cycle has at least one incoming edge from another cycle node, so their in-degree never drops to 0. DFS cycle detection: use three colors — WHITE (unvisited), GRAY (currently in the DFS stack — visiting), BLACK (fully processed). If DFS visits a GRAY node: a back edge is found, indicating a cycle. A back edge exists if and only if the graph has a cycle. GRAY nodes form the current recursion path; finding a GRAY neighbor means we've found a path from that node back to itself. Topological sort cannot be completed when a cycle exists, since no valid ordering satisfies all constraints simultaneously."
}
},
{
"@type": "Question",
"name": "What is the alien dictionary problem and how does topological sort solve it?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Given a list of words sorted in an alien language's alphabetical order, determine the character ordering. Extract ordering information: compare each adjacent pair of words. Find the first position where they differ: word1[i] != word2[i]. This means character word1[i] comes before word2[i] in the alien alphabet — add an edge word1[i] u2192 word2[i]. Edge case: if word1 is longer than word2 and word2 is a prefix of word1 (e.g., "abc" before "ab"), the input is invalid. Run topological sort on the character DAG. If a cycle exists: return "" (invalid input). Otherwise return the characters in topological order. Characters not appearing in any comparison can be placed anywhere. LC 269. Complexity: O(C) where C = total characters in all words (each character pair comparison is O(1) amortized)."
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Atlassian Interview Guide