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.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Atlassian Interview Guide