# 10 Topological Sort Interview Questions and Answers

Prepare for technical interviews with our guide on topological sort, covering key concepts and practical applications in graph theory.

Prepare for technical interviews with our guide on topological sort, covering key concepts and practical applications in graph theory.

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 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]

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]

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]]

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']

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]

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

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]

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.

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']

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