Autocoder

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.

RequirementDirected acyclic graph
AlgorithmsKahn (BFS on in-degree) and DFS finish order
CostO(V + E)
Cycle signalFewer 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

Topological Sort Interview Questions: questions with worked answers

  1. 1

    Topological order with Kahn algorithm

    easy

    Compute 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.

    python
    from 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 []
    java
    int[] 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. 2

    Course schedule: can all courses be finished?

    medium

    Each 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.

    python
    from 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 == n
    java
    boolean 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. 3

    DFS-based topological sort

    medium

    Run 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.

    python
    def 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]
    java
    boolean 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. 4

    Parallel courses: minimum number of semesters

    medium

    Take 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).

    python
    from 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 -1
    java
    int 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. 5

    Project completion time with task durations (critical path)

    medium

    Process 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.

    python
    from 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 -1
    java
    int 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. 6

    Count paths from 0 to n-1 in a DAG

    medium

    Process 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.

    python
    from 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]
    java
    long 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. 7

    Find all recipes you can make from given supplies

    medium

    Each 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.

    python
    from 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 out
    java
    List<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. 8

    Alien dictionary: derive the alphabet order from sorted words

    hard

    Compare 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.

    python
    from 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 ''
    java
    String 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. 9

    Minimum height trees: choose roots that minimise tree height

    hard

    The 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).

    python
    from 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)
    java
    List<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. 10

    Is the topological order unique (sequence reconstruction)?

    hard

    The 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.

    python
    from 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 == n
    java
    boolean 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

See all in this section