10 Topological Sort Interview Questions and Answers

Topological sort is a fundamental algorithm in computer science, particularly useful in scenarios involving dependency resolution, scheduling tasks, and organizing data structures. It is an essential concept in graph theory, where it provides a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u -> v, vertex u comes before vertex v in the ordering. Mastery of topological sort is crucial for solving complex problems efficiently and is a skill highly valued in technical roles.

This article offers a curated selection of topological sort interview questions designed to test and enhance your understanding of the algorithm. By working through these questions, you will gain deeper insights into its applications and be better prepared to tackle related challenges in technical interviews.

Topological Sort Interview Questions and Answers

1. Explain the concept of Topological Sort and its applications.

Topological Sort is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u -> v, vertex u appears before vertex v. This is useful in scenarios where tasks must be performed in a specific order, such as task scheduling, resolving symbol dependencies in linkers, and determining the order of compilation tasks.

The most common algorithms for Topological Sort are Kahn’s Algorithm and Depth-First Search (DFS). Both ensure that vertices are ordered to respect the dependencies represented by the graph’s edges.

Example using Depth-First Search (DFS):

from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)
    
    def add_edge(self, u, v):
        self.graph[u].append(v)
    
    def topological_sort_util(self, v, visited, stack):
        visited[v] = True
        for i in self.graph[v]:
            if not visited[i]:
                self.topological_sort_util(i, visited, stack)
        stack.insert(0, v)
    
    def topological_sort(self):
        visited = {i: False for i in self.graph}
        stack = []
        for i in self.graph:
            if not visited[i]:
                self.topological_sort_util(i, visited, stack)
        return stack

g = Graph()
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)

print(g.topological_sort())
# Output: [5, 4, 2, 3, 1, 0]

2. Implement a Topological Sort in Python using Kahn’s Algorithm.

Kahn’s Algorithm is an efficient way to perform topological sorting using an in-degree approach.

Here is a concise implementation of Topological Sort using Kahn’s Algorithm in Python:

from collections import deque, defaultdict

def kahn_topological_sort(vertices, edges):
    in_degree = {i: 0 for i in range(vertices)}
    graph = defaultdict(list)

    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1

    queue = deque([v for v in in_degree if in_degree[v] == 0])
    topological_order = []

    while queue:
        vertex = queue.popleft()
        topological_order.append(vertex)

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

    if len(topological_order) == vertices:
        return topological_order
    else:
        return "Graph has a cycle"

vertices = 6
edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]
print(kahn_topological_sort(vertices, edges))
# Output: [5, 4, 2, 3, 1, 0]

3. Write a function that returns all possible topological sorts of a given DAG.

To generate all possible topological sorts of a given DAG, we can use a backtracking approach. The idea is to repeatedly remove nodes with no incoming edges and recursively perform the same operation on the remaining graph.

from collections import defaultdict

def all_topological_sorts_util(graph, in_degree, visited, result, all_sorts):
    flag = False

    for i in range(len(in_degree)):
        if in_degree[i] == 0 and not visited[i]:
            for neighbor in graph[i]:
                in_degree[neighbor] -= 1

            result.append(i)
            visited[i] = True
            all_topological_sorts_util(graph, in_degree, visited, result, all_sorts)

            visited[i] = False
            result.pop()
            for neighbor in graph[i]:
                in_degree[neighbor] += 1

            flag = True

    if not flag:
        all_sorts.append(result.copy())

def all_topological_sorts(graph):
    in_degree = [0] * len(graph)
    for i in range(len(graph)):
        for neighbor in graph[i]:
            in_degree[neighbor] += 1

    visited = [False] * len(graph)
    result = []
    all_sorts = []
    all_topological_sorts_util(graph, in_degree, visited, result, all_sorts)
    return all_sorts

# Example usage:
graph = defaultdict(list)
graph[0].extend([1, 2])
graph[1].extend([3])
graph[2].extend([3])

print(all_topological_sorts(graph))
# Output: [[0, 2, 1, 3], [0, 1, 2, 3]]

4. Explain how Topological Sort can be used to solve the problem of task scheduling with dependencies.

Topological Sort can be used to solve task scheduling problems by representing tasks and their dependencies as a DAG. Each node represents a task, and each directed edge indicates that one task must be completed before another. Performing a topological sort on the DAG provides an ordering of tasks that respects these dependencies.

Here is an example of how to implement topological sort using Kahn’s algorithm:

from collections import deque, defaultdict

def topological_sort(tasks, dependencies):
    in_degree = {task: 0 for task in tasks}
    graph = defaultdict(list)

    for u, v in dependencies:
        graph[u].append(v)
        in_degree[v] += 1

    queue = deque([task for task in tasks if in_degree[task] == 0])
    sorted_order = []

    while queue:
        task = queue.popleft()
        sorted_order.append(task)

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

    if len(sorted_order) == len(tasks):
        return sorted_order
    else:
        return []  # Cycle detected, no valid ordering

tasks = ['A', 'B', 'C', 'D', 'E', 'F']
dependencies = [('A', 'D'), ('F', 'B'), ('B', 'D'), ('F', 'A'), ('D', 'C')]

print(topological_sort(tasks, dependencies))
# Output: ['F', 'E', 'A', 'B', 'D', 'C']

5. Given a list of courses and their prerequisites, write a program to determine the order in which the courses should be taken.

To determine the order in which courses should be taken based on prerequisites, represent the courses and their prerequisites as a directed graph. Perform a topological sort on this graph to find the order.

Here is an implementation using Kahn’s Algorithm:

from collections import deque, defaultdict

def find_course_order(num_courses, prerequisites):
    graph = defaultdict(list)
    in_degree = {i: 0 for i in range(num_courses)}

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

    queue = deque([k for k in in_degree if in_degree[k] == 0])
    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 len(order) == num_courses:
        return order
    else:
        return []

# Example usage:
num_courses = 4
prerequisites = [(1, 0), (2, 0), (3, 1), (3, 2)]
print(find_course_order(num_courses, prerequisites))
# Output: [0, 1, 2, 3] or [0, 2, 1, 3]

6. Write a function to check if a given sequence is a valid topological order of a DAG.

To check if a given sequence is a valid topological order of a DAG, ensure that for every directed edge u -> v, u appears before v in the sequence.

Here is an implementation:

def is_valid_topological_order(graph, sequence):
    position = {node: idx for idx, node in enumerate(sequence)}
    
    for u in graph:
        for v in graph[u]:
            if position[u] > position[v]:
                return False
    return True

# Example usage:
graph = {
    5: [2, 0],
    4: [0, 1],
    2: [3],
    3: [1],
    0: [],
    1: []
}

sequence = [5, 4, 2, 3, 1, 0]
print(is_valid_topological_order(graph, sequence))  # Output: True

7. Explain the difference between Topological Sort and other graph traversal algorithms like BFS and DFS.

Topological Sort provides a linear ordering of vertices in a DAG, ensuring that for every directed edge u -> v, vertex u appears before vertex v. This is useful in scenarios where tasks have dependencies, such as course scheduling or build systems.

Breadth-First Search (BFS) and Depth-First Search (DFS) are general-purpose graph traversal algorithms. BFS explores the graph level by level, suitable for finding the shortest path in unweighted graphs. DFS explores as far as possible along each branch before backtracking, useful for tasks like pathfinding and cycle detection.

Here is an example of Topological Sort using DFS:

from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)
    
    def add_edge(self, u, v):
        self.graph[u].append(v)
    
    def topological_sort_util(self, v, visited, stack):
        visited[v] = True
        for i in self.graph[v]:
            if not visited[i]:
                self.topological_sort_util(i, visited, stack)
        stack.insert(0, v)
    
    def topological_sort(self):
        visited = {i: False for i in self.graph}
        stack = []
        for i in self.graph:
            if not visited[i]:
                self.topological_sort_util(i, visited, stack)
        return stack

g = Graph()
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)

print(g.topological_sort())
# Output: [5, 4, 2, 3, 1, 0]

8. Describe a real-world scenario where Topological Sort is essential.

Topological Sort is essential in project scheduling, where tasks have dependencies that dictate the order in which they must be performed. For instance, in software development, certain modules may need to be completed before others can start. Similarly, in construction, the foundation must be laid before the walls can be built.

A real-world example is the build system for a large software project. In such a system, various components depend on each other. For instance, the user interface might depend on the backend services, which in turn depend on the database schema. Using Topological Sort, you can determine the order in which to build and deploy these components to ensure that all dependencies are satisfied.

9. How does Topological Sort handle graphs with multiple starting nodes?

Topological Sort handles graphs with multiple starting nodes by considering all nodes with no incoming edges as potential starting points. The algorithm uses a queue to manage these nodes. Initially, all nodes with no incoming edges are added to the queue. As nodes are processed, their outgoing edges are removed, and any new nodes with no incoming edges are added to the queue.

Here is an example:

from collections import deque, defaultdict

def topological_sort(graph):
    in_degree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1

    queue = deque([u for u in graph if in_degree[u] == 0])
    topo_order = []

    while queue:
        u = queue.popleft()
        topo_order.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    return topo_order

graph = {
    'A': ['C'],
    'B': ['C', 'D'],
    'C': ['E'],
    'D': ['F'],
    'E': ['F'],
    'F': []
}

print(topological_sort(graph))
# Output: ['A', 'B', 'C', 'D', 'E', 'F']

10. Write a function to verify if a given graph is a DAG.

A Directed Acyclic Graph (DAG) is a graph that is directed and contains no cycles. Verifying if a given graph is a DAG involves checking for the presence of cycles. If the graph contains any cycles, it is not a DAG.

Here is an example using Depth-First Search (DFS) to detect cycles:

def is_dag(graph):
    visited = set()
    rec_stack = set()

    def dfs(v):
        if v in rec_stack:
            return False
        if v in visited:
            return True

        visited.add(v)
        rec_stack.add(v)

        for neighbor in graph[v]:
            if not dfs(neighbor):
                return False

        rec_stack.remove(v)
        return True

    for node in graph:
        if not dfs(node):
            return False

    return True

# Example usage:
graph = {
    0: [1, 2],
    1: [2],
    2: [3],
    3: []
}

print(is_dag(graph))  # Output: True