Topological Sort Interview Questions: A Guide

Topological sort linearizes a directed acyclic graph (DAG) so that for every edge u → v, node u comes before node v in the ordering. It is the go-to pattern for dependency scheduling, course ordering, and task sequencing problems in FAANG interviews.

When to Use Topological Sort

Use topological sort when:

• The problem involves dependencies between tasks or courses
• You need to find a valid order to complete tasks with prerequisites
• The input is a directed graph and you need to determine if it is a DAG
• You need to detect cycles in a directed graph
• The problem asks if all tasks can be completed (cyclic dependency detection)

The Two Algorithms

The Trigger Pattern

The problem says "prerequisites," "dependencies," or "order" → topological sort. The problem says "is it possible to complete all tasks" → topological sort with cycle detection. Kahn's algorithm is simpler to implement and explain in interviews.

Kahn's Algorithm (BFS-Based)

Kahn's algorithm works by repeatedly removing nodes with no incoming edges. This is the cleaner variant for interviews because it naturally detects cycles.

from collections import deque, defaultdict

def topological_sort_kahn(num_courses, prerequisites):
    # Build adjacency list and in-degree array
    graph = defaultdict(list)
    in_degree = [0] * num_courses

    for dest, src in prerequisites:
        graph[src].append(dest)
        in_degree[dest] += 1

    # Start with all nodes that have no prerequisites
    queue = deque()
    for i in range(num_courses):
        if in_degree[i] == 0:
            queue.append(i)

    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # If order has all nodes, no cycle exists
    if len(order) == num_courses:
        return order
    else:
        return []  # Cycle detected

Why this works: Nodes with in-degree 0 have no dependencies and can be processed first. When you process a node, you remove its outgoing edges, potentially reducing other nodes' in-degree to 0. If the output contains fewer nodes than the input, a cycle exists because some nodes always have in-degree ≥ 1.

Time: O(V + E). Space: O(V).

DFS-Based Topological Sort

The DFS approach uses post-order traversal. You reverse the post-order to get the topological sort. This variant is useful when you need to detect cycles via back edges.

from collections import defaultdict

def topological_sort_dfs(num_courses, prerequisites):
    graph = defaultdict(list)
    for dest, src in prerequisites:
        graph[src].append(dest)

    # States: 0 = unvisited, 1 = visiting, 2 = visited
    state = [0] * num_courses
    order = []
    has_cycle = False

    def dfs(node):
        nonlocal has_cycle
        state[node] = 1  # Mark as visiting

        for neighbor in graph[node]:
            if state[neighbor] == 1:
                has_cycle = True  # Back edge = cycle
                return
            if state[neighbor] == 0:
                dfs(neighbor)
                if has_cycle:
                    return

        state[node] = 2  # Mark as visited
        order.append(node)  # Post-order: add after processing children

    for i in range(num_courses):
        if state[i] == 0:
            dfs(i)
            if has_cycle:
                return []

    order.reverse()  # Reverse post-order = topological order
    return order

Why this works: In DFS, a node is added to the result after all its descendants are processed (post-order). Reversing this gives topological order because the last node finished is the one with no dependencies. A back edge (visiting a node marked "visiting") indicates a cycle.

Time: O(V + E). Space: O(V).

Course Schedule (LeetCode 207)

The most common topological sort problem. Given numCourses and a list of prerequisites, determine if you can finish all courses.

from collections import deque, defaultdict

def can_finish(num_courses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * num_courses

    for dest, src in prerequisites:
        graph[src].append(dest)
        in_degree[dest] += 1

    queue = deque()
    for i in range(num_courses):
        if in_degree[i] == 0:
            queue.append(i)

    completed = 0

    while queue:
        node = queue.popleft()
        completed += 1

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return completed == num_courses

Why this works: This is Kahn's algorithm with an early termination check. If the count of completed courses equals the total number of courses, all dependencies are satisfiable. If not, a cycle exists.

Time: O(V + E). Space: O(V).

Course Schedule II (LeetCode 210)

Same as Course Schedule but return the actual order, not just a boolean. This is the full topological sort output.

from collections import deque, defaultdict

def find_order(num_courses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * num_courses

    for dest, src in prerequisites:
        graph[src].append(dest)
        in_degree[dest] += 1

    queue = deque()
    for i in range(num_courses):
        if in_degree[i] == 0:
            queue.append(i)

    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == num_courses else []

Why this works: This is the standard Kahn's algorithm. The output order is one valid topological ordering of the courses.

Time: O(V + E). Space: O(V).

Alien Dictionary (LeetCode 269)

This is the hardest topological sort problem commonly asked. Given a sorted list of words in an alien language, determine the character order.

from collections import deque, defaultdict

def alien_order(words):
    # Build graph: for each pair of adjacent words, find first differing char
    graph = defaultdict(set)
    in_degree = {c: 0 for word in words for c in word}

    for i in range(len(words) - 1):
        word1, word2 = words[i], words[i + 1]
        min_len = min(len(word1), len(word2))

        # Invalid case: longer word comes before shorter word
        if len(word1) > len(word2) and word1[:min_len] == word2[:min_len]:
            return ""

        for j in range(min_len):
            if word1[j] != word2[j]:
                if word2[j] not in graph[word1[j]]:
                    graph[word1[j]].add(word2[j])
                    in_degree[word2[j]] += 1
                break

    # Kahn's algorithm
    queue = deque()
    for c in in_degree:
        if in_degree[c] == 0:
            queue.append(c)

    order = []

    while queue:
        char = queue.popleft()
        order.append(char)

        for neighbor in graph[char]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(order) != len(in_degree):
        return ""  # Cycle in character dependencies

    return "".join(order)

Why this works: By comparing adjacent words, you extract character ordering constraints. Each difference creates a directed edge. Running topological sort on the character graph gives the alien alphabet order.

Time: O(C) where C is total characters across all words. Space: O(1) — at most 26 characters.

Common Mistakes

1. Forgetting cycle detection. The topological sort must handle cycles. In Kahn's, check if the output length equals the number of nodes. In DFS, check for back edges. Without cycle detection, you return an incorrect partial ordering.

2. Not handling disconnected components. A DAG can have multiple disconnected components. Initialize the BFS queue with ALL nodes that have in-degree 0, not just one. For DFS, iterate through all nodes and start DFS on unvisited ones.

3. Building the graph incorrectly. For prerequisites = [[1, 0]] meaning "to take 1, you need 0 first," the edge is 0 → 1. Getting the direction wrong reverses the entire topological order.

4. Modifying in-degree while iterating. In Kahn's algorithm, do not modify the in-degree array while iterating over it. Use a separate queue to track nodes ready for processing.

5. Using DFS when Kahn's is simpler. Kahn's is easier to implement and explain in interviews. It naturally produces the topological order without reversing. Use DFS only when you specifically need back edge detection or the problem requires it.

Practice Problems

Start with these problems to master topological sort:

1. Course Schedule — The entry-level topological sort problem. Tests cycle detection in a DAG.
2. Course Schedule II — Same as Course Schedule but return the actual order. Tests full topological sort output.
3. Alien Dictionary — The hardest common variant. Tests graph construction from implicit edges.
4. Parallel Courses — Topological sort with level tracking. Find the minimum number of semesters to finish all courses.
5. All Courses Could Be Finished? — Also known as "is it possible to finish all tasks." Tests whether the graph is a DAG.

Practice What You Learned

Ready to put this into practice? Try a mock coding interview with an AI interviewer who can ask you topological sort questions and evaluate your graph traversal approach.

Frequently Asked Questions