Topological Sort
A topological ordering of a directed acyclic graph (DAG) is a linear ordering of vertices such that for every edge u→v, u comes before v. Only possible in DAGs (no cycles). Use cases: task scheduling with dependencies, course prerequisite ordering (LC 207/210), build system dependency resolution, package installation order.
Kahn’s Algorithm (BFS-based): Compute in-degree of each vertex. Add all vertices with in-degree 0 to a queue. While queue is not empty: dequeue vertex u, add to result, decrement in-degree of all neighbors; if any neighbor’s in-degree becomes 0, enqueue it. If result size == number of vertices: valid topological order. Else: cycle exists (some vertices were never enqueued). O(V + E) time.
from collections import deque, defaultdict
def topo_sort(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
result = []
while queue:
u = queue.popleft()
result.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
return result if len(result) == n else [] # empty = cycleDFS-based topological sort: run DFS; on finish (all neighbors visited), push to a stack. Reverse the stack. Use visited[] and recursion_stack[] to detect cycles (if a neighbor is in the recursion stack, cycle found).
Course Schedule Problems
LC 207 (Can Finish): given N courses and prerequisites, can you finish all? = can you topological sort the prerequisite DAG? Detect cycle with Kahn’s: if result size < N, return False. LC 210 (Course Order): return the topological order. LC 269 (Alien Dictionary): given sorted alien words, deduce character order. Build a graph: for each adjacent pair of words, find the first differing character — that gives an edge. Topological sort the graph to get the character order. If a cycle: invalid. O(total characters in all words).
Strongly Connected Components (SCCs)
An SCC is a maximal set of vertices where every vertex is reachable from every other vertex. SCCs partition the vertices of any directed graph. Collapsing each SCC into a single node produces a DAG (the condensation graph). Use cases: find groups of mutually dependent packages, detect circular dependencies, 2-SAT problems.
Kosaraju’s Algorithm: (1) Run DFS on the original graph, push vertices to a stack in finish order. (2) Transpose the graph (reverse all edges). (3) Run DFS on the transposed graph in the order given by the stack (pop from stack). Each DFS in step 3 discovers one SCC. O(V + E).
Tarjan’s Algorithm: single DFS pass. Each vertex gets a discovery time disc[] and a low-link value low[] (lowest disc reachable via back/cross edges in the DFS subtree). A vertex u is the root of an SCC if low[u] == disc[u]. Uses an explicit stack to track vertices in the current SCC. Also O(V + E) but requires only one pass — preferred in practice.
2-SAT
2-SAT: given a boolean formula in conjunctive normal form (CNF) where each clause has exactly 2 literals, find a satisfying assignment. Encode as an implication graph: each clause (A OR B) becomes two implications: NOT A → B and NOT B → A. Condense the graph into SCCs. For each variable: if x and NOT x are in the same SCC, UNSAT. Otherwise, topological order of the condensation determines the assignment: x = True if x’s SCC comes after NOT x’s SCC in topological order. O(V + E) solution to an NP-complete problem class (general SAT) due to the 2-literal restriction.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “How does Kahn’s algorithm detect cycles in a directed graph?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Kahn’s algorithm detects a cycle by comparing the output size to the number of vertices. In a DAG, every vertex eventually has in-degree 0 and is added to the result. In a graph with a cycle, the vertices in the cycle never reach in-degree 0 (each vertex in the cycle depends on another in the cycle). After the algorithm completes, if result.length 0 is part of or downstream of a cycle. This is O(V + E) and is typically preferred over DFS-based detection because it naturally produces the topological order as a side effect.”
}
},
{
“@type”: “Question”,
“name”: “What is the difference between Kosaraju’s and Tarjan’s SCC algorithms?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Both find all SCCs in O(V + E), but differ in approach. Kosaraju’s uses two DFS passes: first on the original graph to get a finish-time ordering, then on the transposed graph in reverse finish-time order. Each DFS tree in the second pass is one SCC. Requires building the transpose graph (extra O(V + E) space). Conceptually simple. Tarjan’s uses a single DFS pass with a stack. It tracks discovery time disc[u] and low-link low[u] (smallest disc reachable from u’s subtree via back edges). When low[u] == disc[u], u is the root of an SCC — pop the stack until u to get the SCC. Single pass, no transpose. Slightly more complex to implement but preferred in practice (one less traversal, better cache behavior).”
}
},
{
“@type”: “Question”,
“name”: “How do you apply topological sort to detect a cycle in a course prerequisite graph?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Model courses as nodes, prerequisites as directed edges (Au2192B means A must be taken before B). A valid course ordering requires no cycles (you cannot take A before B and B before A simultaneously). Use Kahn’s algorithm: compute in-degrees, start BFS from courses with no prerequisites. Process courses in topological order. If all n courses appear in the result: no cycle, all can be completed. If result length < n: cycle exists, return false (impossible). The cycle-detection property comes from the fact that vertices in a cycle never have their in-degree reduced to 0 — they are always waiting for another course in the cycle. LC 207 uses this approach; LC 210 additionally returns the topological order."
}
},
{
"@type": "Question",
"name": "How are SCCs used to solve 2-SAT problems?",
"acceptedAnswer": {
"@type": "Answer",
"text": "2-SAT: satisfiability problem where each clause has exactly 2 literals. Encode as an implication graph. For clause (A OR B): if A is false then B must be true (NOT_A u2192 B), and vice versa (NOT_B u2192 A). Build this graph for all clauses. Run SCC to condense the graph. Key insight: if variable x and NOT_x are in the same SCC, they imply each other — if x is true, NOT_x must also be true (contradiction). So: UNSAT if any variable x has x and NOT_x in the same SCC. For satisfiable instances: assign truth values based on topological order of the condensation DAG. Variable x is True if the SCC containing x comes after the SCC containing NOT_x in topological order (later in reverse topological order of the condensed DAG)."
}
},
{
"@type": "Question",
"name": "What are practical interview problems that use topological sort beyond course scheduling?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Build system dependency resolution: given source files with includes, determine compilation order. Package installation: given packages with dependencies, find installation order. Task scheduling with deadlines: given tasks with prerequisite tasks, find if all tasks can be completed. Alien dictionary (LC 269): deduce character ordering from a sorted word list — build edges from first differing characters in adjacent words, topological sort. Longest path in a DAG: process vertices in topological order; dp[v] = max(dp[u] + weight(u,v)) over all predecessors u. This is O(V+E) vs O(2^n) for general graphs where longest path is NP-hard. Sequence reconstruction: check if a given sequence is the unique topological sort of a graph."
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Atlassian Interview Guide