Topological Sort Interview Questions
Last updated 2026-11-19
A topological sort orders the vertices of a directed acyclic graph so that every edge goes from an earlier vertex to a later one. It is the standard way to schedule tasks with dependencies, which is why course schedule and build order questions are so common in coding rounds.
This page works through a set of problems from the plain algorithm to alien dictionary and minimum height trees. Each shows Python and Java code with complexity and edge cases. For the underlying graph ideas see graph interview questions, and for cycle detection with DFS see DFS interview questions.
| Requirement | Directed acyclic graph |
|---|---|
| Algorithms | Kahn (BFS on in-degree) and DFS finish order |
| Cost | O(V + E) |
| Cycle signal | Fewer than V vertices processed |
The pattern and when to spot it
Whenever the problem states that something must happen before something else, think of dependencies as edges. Prerequisites, build orders, compile steps, task scheduling, and ordering letters from sorted words are all the same problem. If a valid order exists, the graph has no cycle, and Kahn algorithm doubles as the cycle test: if it cannot process all vertices, a cycle blocks the rest.
Processing in layers answers how many rounds are needed, as in parallel courses. Processing in order while propagating a value, such as the latest finish time or a path count, solves longest path and counting problems on a DAG in linear time. A peeling variant on an undirected tree, repeatedly removing leaves, finds its centre.
Details interviewers check
- The edge direction. Be explicit about whether [a, b] means a before b or b before a.
- Whether letters or courses that appear in no relation still belong in the output.
- Duplicate edges, which inflate in-degree if they are added twice but are balanced by decrementing twice.
- That a topological order is usually not unique, so tests may accept any valid order.
- Recursion depth for DFS on very long chains.
Topological Sort Interview Questions: questions with worked answers
1 Topological order with Kahn algorithm
easyCompute the in-degree of every vertex, queue the vertices with in-degree 0, and repeatedly pop one, append it to the order and decrement its neighbours in-degrees, queuing any that reach 0. If the order has fewer than n vertices the graph has a cycle. Time O(V + E), space O(V + E). Edge cases: a graph with a cycle returns fewer than n vertices, several valid orders exist (any is fine unless asked for the smallest), isolated vertices, n equal to 0.
pythonfrom collections import deque def topo_order(n, edges): g = [[] for _ in range(n)] indeg = [0] * n for a, b in edges: # a must come before b g[a].append(b) indeg[b] += 1 dq = deque(i for i in range(n) if indeg[i] == 0) order = [] while dq: u = dq.popleft() order.append(u) for v in g[u]: indeg[v] -= 1 if indeg[v] == 0: dq.append(v) return order if len(order) == n else []javaint[] topoOrder(int n, int[][] edges) { List<List<Integer>> g = new ArrayList<>(); for (int i = 0; i < n; i++) g.add(new ArrayList<>()); int[] indeg = new int[n]; for (int[] e : edges) { g.get(e[0]).add(e[1]); indeg[e[1]]++; } Queue<Integer> q = new ArrayDeque<>(); for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i); int[] order = new int[n]; int k = 0; while (!q.isEmpty()) { int u = q.poll(); order[k++] = u; for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v); } return k == n ? order : new int[0]; }2 Course schedule: can all courses be finished?
mediumEach prerequisite pair [course, pre] is an edge pre to course. All courses can be finished exactly when the dependency graph has no cycle, which is the same as Kahn algorithm processing all n vertices. Time O(V + E), space O(V + E). Edge cases: no prerequisites (true), a course that is its own prerequisite (false), duplicate pairs, which raise the in-degree twice but are also decremented twice.
pythonfrom collections import deque def can_finish(n, prereqs): g = [[] for _ in range(n)] indeg = [0] * n for c, p in prereqs: g[p].append(c) indeg[c] += 1 dq = deque(i for i in range(n) if indeg[i] == 0) done = 0 while dq: u = dq.popleft() done += 1 for v in g[u]: indeg[v] -= 1 if indeg[v] == 0: dq.append(v) return done == njavaboolean canFinish(int n, int[][] prereqs) { List<List<Integer>> g = new ArrayList<>(); for (int i = 0; i < n; i++) g.add(new ArrayList<>()); int[] indeg = new int[n]; for (int[] p : prereqs) { g.get(p[1]).add(p[0]); indeg[p[0]]++; } Queue<Integer> q = new ArrayDeque<>(); for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i); int done = 0; while (!q.isEmpty()) { int u = q.poll(); done++; for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v); } return done == n; }3 DFS-based topological sort
mediumRun DFS and append a vertex to a list after all its descendants finish; the reversed list is a topological order. Detect cycles with three states, since reaching a vertex that is still on the path means no ordering exists. Time O(V + E), space O(V + E). Edge cases: a cycle (return empty), reversing the finish order is required, deep graphs may overflow recursion.
pythondef topo_dfs(n, edges): g = [[] for _ in range(n)] for a, b in edges: g[a].append(b) state, out = [0] * n, [] def dfs(u): state[u] = 1 for v in g[u]: if state[v] == 1: return False if state[v] == 0 and not dfs(v): return False state[u] = 2 out.append(u) return True for s in range(n): if state[s] == 0 and not dfs(s): return [] return out[::-1]javaboolean ok; List<Integer> topoDfs(int n, int[][] edges) { List<List<Integer>> g = new ArrayList<>(); for (int i = 0; i < n; i++) g.add(new ArrayList<>()); for (int[] e : edges) g.get(e[0]).add(e[1]); int[] state = new int[n]; List<Integer> out = new ArrayList<>(); ok = true; for (int s = 0; s < n && ok; s++) if (state[s] == 0) dfs(g, s, state, out); if (!ok) return new ArrayList<>(); Collections.reverse(out); return out; } private void dfs(List<List<Integer>> g, int u, int[] state, List<Integer> out) { state[u] = 1; for (int v : g.get(u)) { if (state[v] == 1) { ok = false; return; } if (state[v] == 0) { dfs(g, v, state, out); if (!ok) return; } } state[u] = 2; out.add(u); }4 Parallel courses: minimum number of semesters
mediumTake every course with no remaining prerequisites in each semester. That is Kahn algorithm processed level by level, and the number of levels is the answer. If some courses are never processed, return -1. Time O(V + E), space O(V + E). Edge cases: a cycle (-1), no prerequisites (1 semester), a long chain (n semesters).
pythonfrom collections import deque def min_semesters(n, relations): # courses are 1..n g = [[] for _ in range(n + 1)] indeg = [0] * (n + 1) for a, b in relations: g[a].append(b); indeg[b] += 1 dq = deque(i for i in range(1, n + 1) if indeg[i] == 0) sem = done = 0 while dq: sem += 1 for _ in range(len(dq)): u = dq.popleft() done += 1 for v in g[u]: indeg[v] -= 1 if indeg[v] == 0: dq.append(v) return sem if done == n else -1javaint minSemesters(int n, int[][] relations) { List<List<Integer>> g = new ArrayList<>(); for (int i = 0; i <= n; i++) g.add(new ArrayList<>()); int[] indeg = new int[n + 1]; for (int[] r : relations) { g.get(r[0]).add(r[1]); indeg[r[1]]++; } Queue<Integer> q = new ArrayDeque<>(); for (int i = 1; i <= n; i++) if (indeg[i] == 0) q.add(i); int sem = 0, done = 0; while (!q.isEmpty()) { sem++; for (int k = q.size(); k > 0; k--) { int u = q.poll(); done++; for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v); } } return done == n ? sem : -1; }5 Project completion time with task durations (critical path)
mediumProcess tasks in topological order and keep finish[v] = max over predecessors u of finish[u], plus the duration of v. The answer is the maximum finish time. This is the longest path in a DAG, which is easy because there are no cycles, unlike on general graphs. Time O(V + E), space O(V + E). Edge cases: a cycle makes the project impossible, tasks with no prerequisites start at 0, independent tasks run in parallel.
pythonfrom collections import deque def project_time(durations, deps): # deps: (a, b) means a before b n = len(durations) g = [[] for _ in range(n)] indeg = [0] * n for a, b in deps: g[a].append(b); indeg[b] += 1 start = [0] * n dq = deque(i for i in range(n) if indeg[i] == 0) best = seen = 0 while dq: u = dq.popleft() seen += 1 end = start[u] + durations[u] best = max(best, end) for v in g[u]: start[v] = max(start[v], end) indeg[v] -= 1 if indeg[v] == 0: dq.append(v) return best if seen == n else -1javaint projectTime(int[] dur, int[][] deps) { int n = dur.length; List<List<Integer>> g = new ArrayList<>(); for (int i = 0; i < n; i++) g.add(new ArrayList<>()); int[] indeg = new int[n], start = new int[n]; for (int[] d : deps) { g.get(d[0]).add(d[1]); indeg[d[1]]++; } Queue<Integer> q = new ArrayDeque<>(); for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i); int best = 0, seen = 0; while (!q.isEmpty()) { int u = q.poll(); seen++; int end = start[u] + dur[u]; best = Math.max(best, end); for (int v : g.get(u)) { start[v] = Math.max(start[v], end); if (--indeg[v] == 0) q.add(v); } } return seen == n ? best : -1; }6 Count paths from 0 to n-1 in a DAG
mediumProcess vertices in topological order and propagate counts: ways[v] adds ways[u] for every edge u to v, starting with ways[0] = 1. This avoids exponential path enumeration. Vertices that cannot be reached keep a count of 0. Time O(V + E), space O(V + E). Edge cases: results growing large (take a modulus when asked), n equal to 1 (one empty path), unreachable target.
pythonfrom collections import deque def count_paths(n, edges): g = [[] for _ in range(n)] indeg = [0] * n for a, b in edges: g[a].append(b); indeg[b] += 1 ways = [0] * n ways[0] = 1 dq = deque(i for i in range(n) if indeg[i] == 0) while dq: u = dq.popleft() for v in g[u]: ways[v] += ways[u] indeg[v] -= 1 if indeg[v] == 0: dq.append(v) return ways[n - 1]javalong countPaths(int n, int[][] edges) { List<List<Integer>> g = new ArrayList<>(); for (int i = 0; i < n; i++) g.add(new ArrayList<>()); int[] indeg = new int[n]; for (int[] e : edges) { g.get(e[0]).add(e[1]); indeg[e[1]]++; } long[] ways = new long[n]; ways[0] = 1; Queue<Integer> q = new ArrayDeque<>(); for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i); while (!q.isEmpty()) { int u = q.poll(); for (int v : g.get(u)) { ways[v] += ways[u]; if (--indeg[v] == 0) q.add(v); } } return ways[n - 1]; }7 Find all recipes you can make from given supplies
mediumEach recipe depends on its ingredients, and an ingredient may itself be another recipe. Make an edge from ingredient to recipe, start the queue with the supplies and run Kahn algorithm. Every recipe that gets dequeued is makeable. Time O(V + E), space O(V + E). Edge cases: a recipe needing itself indirectly (never makeable), an ingredient that is neither supply nor recipe, duplicate ingredients.
pythonfrom collections import deque, defaultdict def find_recipes(recipes, ingredients, supplies): g, indeg = defaultdict(list), {} for r, ing in zip(recipes, ingredients): indeg[r] = len(ing) for i in ing: g[i].append(r) dq, out = deque(supplies), [] rs = set(recipes) while dq: x = dq.popleft() for r in g[x]: indeg[r] -= 1 if indeg[r] == 0: out.append(r) dq.append(r) return outjavaList<String> findRecipes(String[] recipes, List<List<String>> ing, String[] supplies) { Map<String, List<String>> g = new HashMap<>(); Map<String, Integer> indeg = new HashMap<>(); for (int i = 0; i < recipes.length; i++) { indeg.put(recipes[i], ing.get(i).size()); for (String x : ing.get(i)) g.computeIfAbsent(x, k -> new ArrayList<>()).add(recipes[i]); } Queue<String> q = new ArrayDeque<>(Arrays.asList(supplies)); List<String> out = new ArrayList<>(); while (!q.isEmpty()) { String x = q.poll(); for (String r : g.getOrDefault(x, List.of())) if (indeg.merge(r, -1, Integer::sum) == 0) { out.add(r); q.add(r); } } return out; }8 Alien dictionary: derive the alphabet order from sorted words
hardCompare each adjacent pair of words and find the first differing character; that gives an edge a to b meaning a comes before b. Then topologically sort the letters. Two traps: a longer word appearing before its own prefix is invalid input, and letters with no constraints must still appear in the output. Time O(total characters), space O(1) alphabet, plus edges. Edge cases: prefix violation such as abc before ab (return empty), cycle (return empty), a single word, duplicate edges counted twice in in-degree.
pythonfrom collections import deque def alien_order(words): g = {c: set() for w in words for c in w} indeg = {c: 0 for c in g} for a, b in zip(words, words[1:]): if len(a) > len(b) and a.startswith(b): return '' for x, y in zip(a, b): if x != y: if y not in g[x]: g[x].add(y) indeg[y] += 1 break dq = deque(c for c in g if indeg[c] == 0) out = [] while dq: c = dq.popleft() out.append(c) for nx in g[c]: indeg[nx] -= 1 if indeg[nx] == 0: dq.append(nx) return ''.join(out) if len(out) == len(g) else ''javaString alienOrder(String[] words) { Map<Character, Set<Character>> g = new LinkedHashMap<>(); Map<Character, Integer> indeg = new HashMap<>(); for (String w : words) for (char c : w.toCharArray()) { g.putIfAbsent(c, new HashSet<>()); indeg.putIfAbsent(c, 0); } for (int i = 0; i + 1 < words.length; i++) { String a = words[i], b = words[i + 1]; if (a.length() > b.length() && a.startsWith(b)) return ""; for (int j = 0; j < Math.min(a.length(), b.length()); j++) { char x = a.charAt(j), y = b.charAt(j); if (x != y) { if (g.get(x).add(y)) indeg.merge(y, 1, Integer::sum); break; } } } Queue<Character> q = new ArrayDeque<>(); for (char c : g.keySet()) if (indeg.get(c) == 0) q.add(c); StringBuilder sb = new StringBuilder(); while (!q.isEmpty()) { char c = q.poll(); sb.append(c); for (char nx : g.get(c)) if (indeg.merge(nx, -1, Integer::sum) == 0) q.add(nx); } return sb.length() == g.size() ? sb.toString() : ""; }9 Minimum height trees: choose roots that minimise tree height
hardThe best roots are the one or two centres of the tree. Repeatedly remove all current leaves, which are the vertices with degree 1, until at most two vertices remain. This is Kahn algorithm run on an undirected tree, peeling layers from the outside. Time O(V), space O(V). Edge cases: n equal to 1 (the only vertex), n equal to 2 (both vertices), a path graph (middle one or two), a star (the hub).
pythonfrom collections import deque def find_min_height_trees(n, edges): if n <= 2: return list(range(n)) g = [set() for _ in range(n)] for a, b in edges: g[a].add(b); g[b].add(a) leaves = deque(i for i in range(n) if len(g[i]) == 1) remaining = n while remaining > 2: for _ in range(len(leaves)): u = leaves.popleft() remaining -= 1 v = g[u].pop() g[v].discard(u) if len(g[v]) == 1: leaves.append(v) return list(leaves)javaList<Integer> findMinHeightTrees(int n, int[][] edges) { if (n <= 2) { List<Integer> r = new ArrayList<>(); for (int i = 0; i < n; i++) r.add(i); return r; } List<Set<Integer>> g = new ArrayList<>(); for (int i = 0; i < n; i++) g.add(new HashSet<>()); for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); } Queue<Integer> leaves = new ArrayDeque<>(); for (int i = 0; i < n; i++) if (g.get(i).size() == 1) leaves.add(i); int remaining = n; while (remaining > 2) { for (int k = leaves.size(); k > 0; k--) { int u = leaves.poll(); remaining--; int v = g.get(u).iterator().next(); g.get(v).remove(u); if (g.get(v).size() == 1) leaves.add(v); } } return new ArrayList<>(leaves); }10 Is the topological order unique (sequence reconstruction)?
hardThe order is unique exactly when, at every step of Kahn algorithm, the queue holds one vertex. If two vertices are ever available together, either could go first, so more than one order exists. Compare the unique order with the given sequence when asked to verify it. Time O(V + E), space O(V + E). Edge cases: a cycle (no order), several sources at the start, a queue holding two vertices even once means not unique.
pythonfrom collections import deque def unique_order(n, edges): g = [[] for _ in range(n)] indeg = [0] * n for a, b in edges: g[a].append(b); indeg[b] += 1 dq = deque(i for i in range(n) if indeg[i] == 0) count = 0 while dq: if len(dq) > 1: return False u = dq.popleft() count += 1 for v in g[u]: indeg[v] -= 1 if indeg[v] == 0: dq.append(v) return count == njavaboolean uniqueOrder(int n, int[][] edges) { List<List<Integer>> g = new ArrayList<>(); for (int i = 0; i < n; i++) g.add(new ArrayList<>()); int[] indeg = new int[n]; for (int[] e : edges) { g.get(e[0]).add(e[1]); indeg[e[1]]++; } Queue<Integer> q = new ArrayDeque<>(); for (int i = 0; i < n; i++) if (indeg[i] == 0) q.add(i); int count = 0; while (!q.isEmpty()) { if (q.size() > 1) return false; int u = q.poll(); count++; for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v); } return count == n; }
Frequently asked questions
What is the difference between Kahn algorithm and DFS topological sort?
Kahn uses in-degrees and a queue, emitting vertices when their prerequisites are done. DFS appends a vertex after exploring its descendants and reverses the list. Both run in O(V + E).
Can a graph with a cycle be topologically sorted?
No. A cycle means each vertex on it must come before another vertex on it, which is impossible. Algorithms detect this by processing fewer than V vertices or by finding a back edge.
Is the topological order unique?
Only when each step leaves exactly one vertex with no remaining prerequisites. In general many valid orders exist.
Where do topological sort questions appear?
Course schedule and dependency questions are frequent in product company rounds. See how to crack the DSA coding round for the wider topic list.
Related guides
More in DSA Interview Questions
- Tree DP Interview Questions
- Tree Traversal Interview Questions
- Trie (Prefix Tree) Interview Questions
- Two pointers interview questions with worked solutions
- Union-Find (Disjoint Set Union) Interview Questions
- Array interview questions with worked solutions
- Backtracking interview questions with worked solutions
- BFS (Breadth-First Search) Interview Questions
- Binary search interview questions with worked solutions
- Binary Search Tree Interview Questions and Answers
- Binary Tree Interview Questions and Answers
- Bit manipulation interview questions with worked solutions