Topological Sort Interview Questions

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. What a topological sort question is actually testing

The words "topological sort" almost never appear in the question. You get courses with prerequisites, build targets, task lists, a recipe, or a dictionary in an alien alphabet, and the interview is watching for three things.

Do you see the graph? Anything phrased as "X must come before Y" is a directed edge, and the answer is an ordering of the vertices. Do you get the arcs the right way round? This is the single most common failure, and it produces code that runs, returns an order, and is backwards. Do you know that the cycle check and the sort are the same computation? "Can this be scheduled" and "give me a schedule" are one algorithm with two different return statements.

After that, the variations are all the same sweep carrying something extra: a level number, a duration, a count, a second graph. Once the template is automatic, the interesting part of every one of these problems is the modelling, not the code. The mechanics themselves are covered in the guide to topological sorting; this page is about the eight questions that actually get asked.

Every worked example below was executed by script before it was written down.

2. The two templates, and when each one wins

There are exactly two implementations worth knowing, and an interviewer will accept either. Write whichever one you can produce without hesitating, and be able to say why you might want the other.

Kahn's algorithm, from his 1962 paper, is the iterative one. Count how many prerequisites each vertex still has, keep the ones at zero in a queue, and emit them.

from collections import deque

def kahn(n, edges):                  # edges hold (u, v) meaning u comes before v
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1                # count arcs INTO v
    q = deque(v for v in range(n) if indeg[v] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1            # u is done, so v needs one fewer
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []      # short output means a cycle

The last line carries the whole cycle test. If some vertices never reach in-degree zero, they are waiting on each other, and len(order) < n is the proof. Notice there is no visited set anywhere: the in-degree counter already guarantees each vertex is emitted exactly once.

On this graph the queue starts as [1, 2], and the emitted order is 1, 2, 4, 0, 5, 3, 6, 7. All eight vertices come out, so there is no cycle.

The DFS version is the other template. Run a depth first search and push each vertex onto a list when it finishes, then reverse. The subtlety that interviewers probe is the colouring.

WHITE, GREY, BLACK = 0, 1, 2      # unseen, on the stack, finished

def dfs_topo(n, adj):
    colour = [WHITE] * n
    out = []
    def visit(u):
        colour[u] = GREY
        for v in adj[u]:
            if colour[v] == GREY:          # back edge: we found a cycle
                return False
            if colour[v] == WHITE and not visit(v):
                return False
        colour[u] = BLACK
        out.append(u)                      # push on the way OUT, not the way in
        return True
    for v in range(n):
        if colour[v] == WHITE and not visit(v):
            return []
    return out[::-1]                       # reverse post-order

Three colours, not a visited set. A plain visited set cannot distinguish an arc back into the current recursion stack, which is a cycle, from an arc into a branch that was already finished, which is not. Say that sentence in the interview and the cycle-detection follow-up is already answered.

Which to use? Kahn if the problem wants levels, counts, lexicographic order, or anything that benefits from processing sources in waves. DFS if you are already writing a depth first search for another reason, or if you want the reverse post-order for a strongly connected components pass. Both are O(V + E). The one practical difference: the recursive DFS needs stack depth proportional to the longest chain, which on an adversarial input of a hundred thousand chained tasks will hit Python's default recursion limit, and Kahn will not.

3. Course Schedule: can every course be finished?

The question. There are n courses and a list of pairs [a, b] meaning "to take course a you must first take course b". Can you finish all of them?

The modelling step is the entire question, and it is where most candidates lose it. The pair [a, b] says b before a, so the arc runs b → a, and it is indeg[a] that goes up. Getting this backwards still produces a valid topological sort of a different graph, so nothing crashes and the answer is silently wrong on any asymmetric test case.

def can_finish(n, prerequisites):
    edges = [(b, a) for a, b in prerequisites]   # b before a
    return len(kahn(n, edges)) == n

That is it: run the sort, compare the count. Say out loud that a schedule exists exactly when the prerequisite graph is acyclic, because a cycle is a set of courses that each wait on another.

Add the arc 7 → 2 to the running graph and the queue starts with only vertex 1, emits 1 and 4, and then empties. Six vertices are left stuck, and they are precisely the cycle 2 → 0 → 3 → 6 → 7 → 2 together with vertex 5, which sits downstream of it.

The follow-up: which courses are the problem? The leftovers with non-zero in-degree are the vertices on or after a cycle, which is usually the answer they want. If they insist on the cycle itself rather than everything blocked by it, you need the DFS version: when you meet a grey vertex, the current recursion stack from that vertex onwards is the cycle.

The trap. Reversing the arcs. Read the pair aloud as "a depends on b, so b comes first" before you type, and confirm the direction with the interviewer on a two-element example.

4. Course Schedule II: return an order

The question. Same input, but return a valid order, or an empty list if none exists.

This is kahn unchanged, which is why the two questions are usually asked back to back. The only new idea is one you must volunteer: the order is not unique, and the grader accepts any valid one.

Kahn returns 1, 2, 4, 0, 5, 3, 6, 7 and the DFS returns 2, 5, 1, 4, 0, 3, 6, 7. Neither is more correct than the other, and an exhaustive count says this graph has 49 distinct valid orders. If your solution is being diffed against one expected answer, that is a broken test, not a broken solution.

The follow-up: return the lexicographically smallest order. Replace the queue with a min-heap. At each step you pop the smallest available vertex rather than the earliest queued one, which greedily fixes the smallest possible value at every position. The cost goes from O(V + E) to O(V + E log V), and being able to state that trade-off is the point of the follow-up. On the running graph the smallest order is 1, 2, 0, 3, 4, 5, 6, 7.

The trap. Returning order without the length check. On a cyclic input you hand back a partial schedule that looks entirely plausible, and every automated test with a cycle fails while your local run of the happy path passes.

5. Alien Dictionary: recovering an alphabet

The question. You are given words sorted according to an unknown alphabet. Recover an order of the letters consistent with that sorting, or report that none exists.

Nothing here looks like a graph until you notice what "sorted" tells you. Compare two adjacent words, find the first position where they differ, and you have learnt exactly one fact: that letter of the first word precedes that letter of the second. Everything after the first difference tells you nothing. Then topologically sort the letters.

def alien_order(words):
    adj = {c: set() for w in words for c in w}
    indeg = {c: 0 for c in adj}
    for w1, w2 in zip(words, words[1:]):
        if len(w1) > len(w2) and w1.startswith(w2):
            return ""                       # "abc" before "ab" is impossible
        for a, b in zip(w1, w2):
            if a != b:
                if b not in adj[a]:         # do not count a duplicate twice
                    adj[a].add(b)
                    indeg[b] += 1
                break                       # only the FIRST difference counts
    ...                                     # then Kahn over the letters

Three details in six lines, and interviewers check all three. Only adjacent pairs. Comparing every pair of words adds edges the input does not justify. Only the first differing position, then break. The prefix rule: if a word is a strict prefix of the one before it, the input contradicts itself and the answer is the empty string, with no graph built at all.

On the classic input ["wrt", "wrf", "er", "ett", "rftt"] the comparisons give t → f, w → e, r → t and e → r, and the sort returns "wertf". On ["abc", "ab"] the prefix rule fires and returns "". On ["z", "x", "z"] the edges z → x and x → z form a cycle, so the length check returns "" too.

The follow-up: is the alphabet you returned the only one? That is the uniqueness question of section 7: the order is forced exactly when the queue holds a single letter at every step. Any letter that never appears in a comparison floats free, and its position is arbitrary.

The trap. Seeding the graph from the letters that appear in comparisons rather than from every letter in every word. Letters that are never compared still have to appear in the output, and dropping them is the failure that gets caught by a hidden test rather than by your own.

6. Parallel courses: the minimum number of semesters

The question. You may take any number of courses at once, as long as every prerequisite is already done. What is the fewest semesters needed?

The answer is the number of levels in the DAG, and the level of a vertex is one more than the largest level among its predecessors. Carry that number through the same sweep.

def min_semesters(n, edges):
    order = kahn(n, edges)
    if len(order) != n:
        return -1                          # a cycle: never finishes
    level = [1] * n
    for u in order:                        # every predecessor of u is final
        for v in adj[u]:
            level[v] = max(level[v], level[u] + 1)
    return max(level)

Because the loop runs in topological order, every predecessor of u has already contributed before u is read, which is the property that makes one pass enough. On the running graph the levels are {1, 2}, then {0, 4, 5}, then {3}, then {6}, then {7}, so the answer is 5 semesters.

The follow-up: what if you can take at most k courses per semester? The easy answer collapses. Unlimited parallelism is linear because greedily taking everything available is optimal; capping the width turns it into precedence-constrained scheduling on k machines, which is NP-hard in general. Two identical machines with unit tasks is the classic tractable case, solved by Coffman and Graham in 1972. Recognising that the follow-up changes complexity class, rather than trying to patch the loop, is what the interviewer is listening for.

The trap. Assigning a level the first time a vertex is reached, as though this were an ordinary BFS from the sources. A vertex must wait for its slowest predecessor, so the level is a maximum, not a first arrival. The BFS-by-waves variant works only if you pop a whole layer at a time and never look at a vertex before its in-degree hits zero.

7. Is the order unique? Sequence reconstruction

The question. Given a DAG, decide whether it has exactly one valid topological order. The usual dressing is sequence reconstruction: you are handed a sequence and a set of subsequences, and asked whether the sequence is the only one consistent with them.

The test is one line inside Kahn's loop.

    while q:
        if len(q) > 1:
            return False              # a choice existed, so the order is not forced
        u = q.popleft()
        ...

If the queue ever holds two vertices, both are available and either may come next, so at least two valid orders exist. If it holds exactly one at every step, no choice was ever made and the order is forced.

There is a second, equivalent way to say it that impresses: the order is unique exactly when consecutive vertices in it are joined by an arc, that is, when the topological order is a Hamiltonian path in the DAG. Both formulations are checkable in O(V + E), and quoting the Hamiltonian path version shows you understand why uniqueness is a structural property rather than an accident of the queue.

On the running graph the queue sizes at the eight pops are 2, 2, 3, 2, 2, 1, 1, 1. The very first step already offers a choice between 1 and 2, so the order is not unique, which the 49 valid orders counted in section 4 confirm. On the chain 0 → 1 → 2 → 3 the sizes are 1, 1, 1, 1 and the order is forced.

The follow-up: sequence reconstruction itself. Build the graph from consecutive pairs in each subsequence, then run the check above and additionally verify that the emitted order equals the given sequence. Both conditions are needed: a unique order that differs from the sequence you were handed is still a "no".

The trap. Checking the queue size only once, at the start. A graph can begin with a single source and branch three steps later, so the comparison has to run on every iteration. Worth knowing: "every level holds exactly one vertex" is an equivalent test, because a forced order makes the levels a strict chain, so reasoning in levels is not wrong, it just costs you a second pass to compute them.

8. The longest path, and the critical path

The question. Each task takes a known number of days and cannot start until its prerequisites are done. When does the project finish, and which tasks are the ones that decide it?

This is the longest path problem, and on a general graph it is NP-hard. On a DAG it is linear, and the reason is the topological order: every predecessor of a vertex is final before that vertex is read, so a single forward pass settles it.

def critical_path(n, edges, dur):
    order = kahn(n, edges)
    finish = list(dur)                     # earliest finish if nothing blocks it
    prev = [-1] * n
    for u in order:
        for v in adj[u]:
            if finish[u] + dur[v] > finish[v]:
                finish[v] = finish[u] + dur[v]
                prev[v] = u                # remember who forced the delay
    end = max(range(n), key=lambda v: finish[v])
    path = []
    while end != -1:
        path.append(end); end = prev[end]
    return max(finish), path[::-1]

Give the running graph the durations 3, 2, 4, 5, 1, 2, 6, 3 for vertices 0 to 7 and the earliest finish times come out as 7, 2, 4, 12, 3, 6, 18, 21. The project takes 21 days and the critical path is 2 → 0 → 3 → 6 → 7, whose durations add to exactly 21. That chain is what a manager means by "the critical path": slip any task on it by a day and the whole project slips by a day, while task 5 has slack and can drift for days before anyone notices. This is the Kelley and Walker method from 1959, and saying its name out loud costs nothing.

The follow-up: shortest path instead. Change the comparison to < and you have single-source shortest paths on a DAG, in O(V + E), and it works with negative weights, which Dijkstra cannot. Any time an interviewer mentions negative edges on an acyclic graph, this is the answer, not Bellman-Ford. Compare with the general case in shortest path algorithms.

The trap. Relaxing in the wrong order. Iterating over vertices 0 to n-1 instead of over the topological order gives a value that depends on the labelling: on this graph it silently reports 17 instead of 21, because vertex 0 is read before vertex 2 has contributed to it. The whole point of the topological order is that it makes one pass sufficient.

9. Eventual safe states: sort the reverse graph

The question. A node is safe if every path leaving it reaches a terminal node, so you can never get stuck in a cycle. Return all safe nodes in ascending order.

Phrased forwards this is awkward. Reverse every arc and it becomes a topological sort: peel off the nodes with out-degree zero, which are the terminals, and every time a node's remaining out-degree hits zero, all of its successors were safe, so it is safe too.

def safe_nodes(graph):
    n = len(graph)
    rev = [[] for _ in range(n)]
    outdeg = [len(graph[u]) for u in range(n)]
    for u in range(n):
        for v in graph[u]:
            rev[v].append(u)
    q = deque(v for v in range(n) if outdeg[v] == 0)   # terminals
    safe = []
    while q:
        u = q.popleft()
        safe.append(u)
        for p in rev[u]:
            outdeg[p] -= 1
            if outdeg[p] == 0:
                q.append(p)
    return sorted(safe)

It is Kahn's algorithm with in-degree replaced by out-degree and the arcs reversed, which is worth saying explicitly because it demonstrates you recognise the template under a disguise. On the standard example [[1,2], [2,3], [5], [0,5], [5], [], []] the answer is [2, 4, 5, 6]: nodes 5 and 6 are terminal, 2 and 4 lead only into them, and 0, 1 and 3 sit on the cycle 0 → 1 → 3 → 0.

The follow-up: do it with DFS instead. Three colours again. A node is safe if no arc from it reaches a grey vertex, and you can memoise the result per node so the whole thing stays linear. Interviewers often want to hear both, because the reverse-graph version is the one candidates rarely find on their own.

The trap. Answering "the nodes not on a cycle". Node 3 lies on no cycle of its own by that reading, yet it has an arc into the cycle through 0, so it is unsafe. Safety is about every path from the node, not about the node itself.

10. Sort items by group: two levels at once

The question. Items belong to groups, some items must precede others, and items in the same group must end up contiguous in the output. Return a valid order or an empty list.

This is the hard variant, and the insight is small: run two topological sorts. One over the groups, using an arc between groups whenever an item in one must precede an item in another, and one over the items inside each group. Then concatenate the groups in group order, each filled with its own sorted items.

The only fiddly part is the ungrouped items. An item with group -1 is constrained by nobody's grouping, so give each one a fresh private group of its own. Merging them all into a single group instead is the classic wrong answer: it forces unrelated items to be contiguous and can turn a solvable instance into an unsolvable one.

Either sort failing means the whole instance fails, so the length check runs twice. The complexity stays O(V + E) across both passes, since every item and every dependency is touched a constant number of times.

The follow-up: is one course a prerequisite of another? That is Course Schedule IV, and it wants reachability rather than an order. Process vertices in topological order and union each vertex's reachable set into its successors, using bitsets: O(V × E / 64) in practice, and the topological order is what guarantees a set is complete before it is copied forward.

The trap. Sorting the groups but forgetting that a group can also be a cycle with itself through two items in different groups. Build the group graph from item dependencies only when the two groups differ, or you create self-loops that fail the sort for no reason.

11. The complexity answers

Have these ready, because they are asked verbatim and the answer is short.

Two things to add unprompted. First, the graph is usually not given to you as an adjacency list: it arrives as a list of pairs, and building the list costs O(V + E) too, so quoting a bound that ignores construction is wrong. Second, a topological sort is not a comparison sort and is not bound by O(n log n): it is linear precisely because the input already supplies the ordering constraints rather than making you discover them.

The recursive DFS version also uses O(V) stack depth in the worst case, which is a real limit rather than a theoretical one. A chain of 100,000 tasks exhausts Python's default recursion limit of 1,000 long before it exhausts memory.

12. Mistakes that fail the interview

Ordered by how often they appear; the first two account for most rejected solutions.

• Building the arcs backwards. The pair [a, b] in Course Schedule means b before a. Reversed, the code still returns an order, it is just an order for the mirrored problem. Read the pair aloud before typing.
• Dropping the len(order) == V check. Without it a cyclic input yields a partial schedule that looks fine. The count is the cycle test, and the order is the by-product.
• Using a visited set in the DFS version. Two states cannot distinguish a back edge from an arc into a finished branch, so you either miss cycles or invent them. Three colours, every time.
• Losing vertices with no edges. Building the graph from the pair list alone silently drops every course with no prerequisites and no dependents. Start from the vertex count you were given.
• Assigning levels on first arrival. A vertex waits for its slowest predecessor, so its level is a maximum over predecessors, not the first value that reaches it.
• Relaxing outside the topological order. The longest-path and shortest-path sweeps are correct only because every predecessor is final when a vertex is read. Iterating over vertex indices instead quietly returns a smaller number.
• Double counting duplicate dependencies. If the input can repeat a pair, either deduplicate before counting in-degrees or decrement once per stored arc. Counting a duplicate in one place and not the other leaves a vertex permanently stuck at in-degree one.
• Claiming the order is unique. It rarely is, and asserting it invites the follow-up you have not prepared. Say "a valid order" and offer the uniqueness test if they want it.
• Not asking about the input. Can dependencies repeat? Can a course depend on itself? Are vertex ids dense integers or arbitrary strings? Each answer changes the first ten lines you write.

The habit that prevents most of these: before writing anything, say which direction the arcs run and what the answer is when the sort comes up short. If you cannot state both in one sentence, you are not ready to type yet.

14. References

The papers that introduced these techniques and the texts that analyse them, in chronological order.

1. Kelley, J. E. and Walker, M. R. (1959). “Critical-path planning and scheduling.” Proceedings of the Eastern Joint Computer Conference, 160–173.
2. Kahn, A. B. (1962). “Topological sorting of large networks.” Communications of the ACM, 5(11), 558–562.
3. Knuth, D. E. (1968). The Art of Computer Programming, Volume 1: Fundamental Algorithms, Section 2.2.3. Addison-Wesley.
4. Coffman, E. G. and Graham, R. L. (1972). “Optimal scheduling for two-processor systems.” Acta Informatica, 1(3), 200–213.
5. Tarjan, R. E. (1972). “Depth-first search and linear graph algorithms.” SIAM Journal on Computing, 1(2), 146–160.
6. Tarjan, R. E. (1976). “Edge-disjoint spanning trees and depth-first search.” Acta Informatica, 6(2), 171–185.
7. Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009). Introduction to Algorithms, 3rd edition, Section 22.4. MIT Press.
8. Sedgewick, R. and Wayne, K. (2011). Algorithms, 4th edition, Section 4.2. Addison-Wesley.
9. McDowell, G. L. (2015). Cracking the Coding Interview, 6th edition. CareerCup.
10. Skiena, S. S. (2020). The Algorithm Design Manual, 3rd edition, Section 5.10. Springer.