Topological Sorting

Topological sorting is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before v in the ordering.

---

Why This Matters in Interviews

Topological sorting is important because:

• Dependency resolution: Task scheduling, build systems, package managers
• Graph problems: Many graph problems require topological order
• Cycle detection: Can detect cycles in directed graphs
• Algorithm design: Foundation for many graph algorithms

Interviewers use topological sorting to assess your understanding of DAGs, your ability to handle dependencies, and your problem-solving approach.

---

Core Concepts

• DAG requirement: Graph must be acyclic (no cycles)
• Multiple solutions: DAG can have multiple valid topological orders
• Kahn's algorithm: Uses in-degree counting
• DFS approach: Uses depth-first search with finishing times
• In-degree: Number of incoming edges to a vertex
• Source nodes: Vertices with in-degree 0
• Cycle detection: If can't process all vertices, cycle exists

---

Detailed Explanation

Kahn's Algorithm (BFS-based)

function topologicalSortKahn(graph: Map<number, number[]>): number[] {
  const inDegree = new Map<number, number>();
  const result: number[] = [];
  const queue: number[] = [];
  
  // Calculate in-degrees
  for (const [node, neighbors] of graph.entries()) {
    if (!inDegree.has(node)) {
      inDegree.set(node, 0);
    }
    
    for (const neighbor of neighbors) {
      inDegree.set(neighbor, (inDegree.get(neighbor) || 0) + 1);
    }
  }
  
  // Find all nodes with in-degree 0
  for (const [node, degree] of inDegree.entries()) {
    if (degree === 0) {
      queue.push(node);
    }
  }
  
  // Process nodes
  while (queue.length > 0) {
    const node = queue.shift()!;
    result.push(node);
    
    // Reduce in-degree of neighbors
    for (const neighbor of graph.get(node) || []) {
      const newDegree = (inDegree.get(neighbor) || 0) - 1;
      inDegree.set(neighbor, newDegree);
      
      if (newDegree === 0) {
        queue.push(neighbor);
      }
    }
  }
  
  // Check for cycle
  if (result.length !== graph.size) {
    throw new Error('Cycle detected - not a DAG');
  }
  
  return result;
}

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

DFS-based Approach

function topologicalSortDFS(graph: Map<number, number[]>): number[] {
  const result: number[] = [];
  const visited = new Set<number>();
  const recStack = new Set<number>();
  
  function dfs(node: number): void {
    if (recStack.has(node)) {
      throw new Error('Cycle detected');
    }
    
    if (visited.has(node)) {
      return;
    }
    
    visited.add(node);
    recStack.add(node);
    
    // Visit all neighbors first
    for (const neighbor of graph.get(node) || []) {
      dfs(neighbor);
    }
    
    recStack.delete(node);
    // Add to front (post-order)
    result.unshift(node);
  }
  
  // Process all nodes
  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      dfs(node);
    }
  }
  
  return result;
}

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

All Topological Sorts

function allTopologicalSorts(graph: Map<number, number[]>): number[][] {
  const inDegree = new Map<number, number>();
  const result: number[][] = [];
  
  // Calculate in-degrees
  for (const [node, neighbors] of graph.entries()) {
    if (!inDegree.has(node)) {
      inDegree.set(node, 0);
    }
    for (const neighbor of neighbors) {
      inDegree.set(neighbor, (inDegree.get(neighbor) || 0) + 1);
    }
  }
  
  function backtrack(current: number[], available: Set<number>): void {
    // Base case: all nodes processed
    if (current.length === graph.size) {
      result.push([...current]);
      return;
    }
    
    // Try each available node (in-degree 0)
    for (const node of available) {
      current.push(node);
      const newAvailable = new Set(available);
      newAvailable.delete(node);
      
      // Update in-degrees
      for (const neighbor of graph.get(node) || []) {
        const newDegree = (inDegree.get(neighbor) || 0) - 1;
        inDegree.set(neighbor, newDegree);
        if (newDegree === 0) {
          newAvailable.add(neighbor);
        }
      }
      
      backtrack(current, newAvailable);
      
      // Restore in-degrees (backtrack)
      for (const neighbor of graph.get(node) || []) {
        inDegree.set(neighbor, (inDegree.get(neighbor) || 0) + 1);
      }
      
      current.pop();
    }
  }
  
  const available = new Set<number>();
  for (const [node, degree] of inDegree.entries()) {
    if (degree === 0) {
      available.add(node);
    }
  }
  
  backtrack([], available);
  return result;
}

---

Examples

Course Schedule

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const graph = new Map<number, number[]>();
  const inDegree = new Array(numCourses).fill(0);
  
  // Build graph
  for (const [course, prereq] of prerequisites) {
    if (!graph.has(prereq)) {
      graph.set(prereq, []);
    }
    graph.get(prereq)!.push(course);
    inDegree[course]++;
  }
  
  // Kahn's algorithm
  const queue: number[] = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) {
      queue.push(i);
    }
  }
  
  let count = 0;
  while (queue.length > 0) {
    const course = queue.shift()!;
    count++;
    
    for (const next of graph.get(course) || []) {
      inDegree[next]--;
      if (inDegree[next] === 0) {
        queue.push(next);
      }
    }
  }
  
  return count === numCourses; // All courses can be taken
}

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const graph = new Map<number, number[]>();
  const inDegree = new Array(numCourses).fill(0);
  
  for (const [course, prereq] of prerequisites) {
    if (!graph.has(prereq)) {
      graph.set(prereq, []);
    }
    graph.get(prereq)!.push(course);
    inDegree[course]++;
  }
  
  const queue: number[] = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) {
      queue.push(i);
    }
  }
  
  const result: number[] = [];
  while (queue.length > 0) {
    const course = queue.shift()!;
    result.push(course);
    
    for (const next of graph.get(course) || []) {
      inDegree[next]--;
      if (inDegree[next] === 0) {
        queue.push(next);
      }
    }
  }
  
  return result.length === numCourses ? result : [];
}

Build Order

function buildOrder(projects: string[], dependencies: [string, string][]): string[] {
  const graph = new Map<string, string[]>();
  const inDegree = new Map<string, number>();
  
  // Initialize
  for (const project of projects) {
    graph.set(project, []);
    inDegree.set(project, 0);
  }
  
  // Build graph
  for (const [dependent, dependency] of dependencies) {
    if (!graph.has(dependency)) {
      graph.set(dependency, []);
    }
    graph.get(dependency)!.push(dependent);
    inDegree.set(dependent, (inDegree.get(dependent) || 0) + 1);
  }
  
  // Topological sort
  const queue: string[] = [];
  for (const [project, degree] of inDegree.entries()) {
    if (degree === 0) {
      queue.push(project);
    }
  }
  
  const result: string[] = [];
  while (queue.length > 0) {
    const project = queue.shift()!;
    result.push(project);
    
    for (const dependent of graph.get(project) || []) {
      const newDegree = (inDegree.get(dependent) || 0) - 1;
      inDegree.set(dependent, newDegree);
      if (newDegree === 0) {
        queue.push(dependent);
      }
    }
  }
  
  if (result.length !== projects.length) {
    throw new Error('Circular dependency detected');
  }
  
  return result;
}

---

Common Pitfalls

• Not checking for cycles: Algorithm may give incomplete result. Fix: Check if all vertices processed
• Wrong in-degree calculation: Missing some edges. Fix: Calculate in-degrees correctly
• Not handling disconnected graph: Missing some components. Fix: Process all unvisited nodes
• Multiple solutions: Assuming unique order. Fix: Understand that multiple valid orders exist
• Edge direction confusion: Reversing dependencies. Fix: Be clear about edge direction

---

Interview Questions

Beginner

Q: What is topological sorting and what are its requirements?

A:

Topological Sorting is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every edge (u, v), u comes before v.

Requirements:

• Directed graph: Edges have direction
• Acyclic: No cycles (if cycle exists, no valid topological order)
• DAG: Directed Acyclic Graph

Key properties:

• Multiple solutions: A DAG can have multiple valid topological orders
• Source nodes first: Nodes with no incoming edges (in-degree 0) come first
• Sink nodes last: Nodes with no outgoing edges come last

Example:

Graph: A → B → D
        ↓   ↓
        C → E

Valid orders:
- A, B, C, D, E
- A, C, B, D, E
- A, B, D, C, E

Applications:

• Task scheduling
• Build systems (make, gradle)
• Course prerequisites
• Package dependencies

---

Intermediate

Q: Compare Kahn's algorithm and DFS-based topological sort. When would you use each?

A:

Kahn's Algorithm (BFS-based):

// Uses in-degree counting
// Processes nodes with in-degree 0
// More intuitive, easier to understand

Advantages:

• Intuitive: Easy to understand and implement
• Early cycle detection: Can detect cycle during processing
• Level-by-level: Processes in levels (useful for some problems)

DFS-based:

// Uses depth-first search
// Processes in post-order
// More efficient for some cases

Advantages:

• Natural recursion: Fits recursive thinking
• Post-order processing: Natural for dependency resolution
• Can find all solutions: Easier to generate all topological orders

Comparison:

Feature	Kahn's	DFS
Approach	BFS (queue)	DFS (stack)
In-degree	Required	Not needed
Cycle detection	During processing	During DFS
Implementation	Iterative	Recursive/iterative
Use when	Need levels, intuitive	Recursive thinking, all solutions

When to use:

• Kahn's: When you need level information, prefer iterative
• DFS: When thinking recursively, need all solutions

---

Senior

Q: Design a build system that uses topological sorting to determine build order. Handle parallel builds, incremental builds, and detect circular dependencies.

A:

class BuildSystem {
  private dependencyGraph: Map<string, string[]>;
  private buildCache: BuildCache;
  private executor: BuildExecutor;
  
  constructor() {
    this.dependencyGraph = new Map();
    this.buildCache = new BuildCache();
    this.executor = new BuildExecutor();
  }
  
  async build(targets: string[]): Promise<BuildResult> {
    // Build dependency graph
    const allTargets = this.getAllDependencies(targets);
    const graph = this.buildGraph(allTargets);
    
    // Topological sort
    const buildOrder = this.topologicalSort(graph);
    
    if (!buildOrder) {
      return { success: false, error: 'Circular dependency detected' };
    }
    
    // Execute builds in parallel where possible
    return await this.executeBuilds(buildOrder);
  }
  
  private topologicalSort(graph: Map<string, string[]>): string[] | null {
    const inDegree = new Map<string, number>();
    const queue: string[] = [];
    const result: string[] = [];
    
    // Calculate in-degrees
    for (const [target, deps] of graph.entries()) {
      if (!inDegree.has(target)) {
        inDegree.set(target, 0);
      }
      for (const dep of deps) {
        inDegree.set(dep, (inDegree.get(dep) || 0) + 1);
      }
    }
    
    // Find targets with no dependencies
    for (const [target, degree] of inDegree.entries()) {
      if (degree === 0) {
        queue.push(target);
      }
    }
    
    // Process
    while (queue.length > 0) {
      const target = queue.shift()!;
      result.push(target);
      
      for (const dependent of graph.get(target) || []) {
        const newDegree = (inDegree.get(dependent) || 0) - 1;
        inDegree.set(dependent, newDegree);
        if (newDegree === 0) {
          queue.push(dependent);
        }
      }
    }
    
    // Check for cycle
    if (result.length !== graph.size) {
      return null;
    }
    
    return result;
  }
  
  private async executeBuilds(buildOrder: string[]): Promise<BuildResult> {
    const results = new Map<string, boolean>();
    const executing = new Set<string>();
    
    // Execute in parallel where possible
    const executeLevel = async (level: string[]): Promise<void> => {
      // Check cache first
      const toBuild = level.filter(target => !this.buildCache.isValid(target));
      
      if (toBuild.length === 0) {
        return; // All cached
      }
      
      // Execute in parallel
      await Promise.all(
        toBuild.map(async (target) => {
          executing.add(target);
          try {
            const success = await this.executor.build(target);
            results.set(target, success);
            if (success) {
              this.buildCache.markBuilt(target);
            }
          } catch (error) {
            results.set(target, false);
          } finally {
            executing.delete(target);
          }
        })
      );
    };
    
    // Group by level (can build in parallel)
    const levels = this.groupByLevel(buildOrder);
    
    for (const level of levels) {
      await executeLevel(level);
      
      // Check if any failed
      const failed = Array.from(results.entries())
        .filter(([_, success]) => !success)
        .map(([target]) => target);
      
      if (failed.length > 0) {
        return {
          success: false,
          error: `Build failed for: ${failed.join(', ')}`
        };
      }
    }
    
    return { success: true };
  }
  
  private groupByLevel(buildOrder: string[]): string[][] {
    // Group targets that can be built in parallel
    // (have same number of dependencies processed)
    const levels: string[][] = [];
    const processed = new Set<string>();
    
    for (const target of buildOrder) {
      const deps = this.dependencyGraph.get(target) || [];
      const depsProcessed = deps.filter(d => processed.has(d)).length;
      
      if (levels.length === 0 || levels[levels.length - 1].length === 0) {
        levels.push([target]);
      } else {
        // Check if can be added to current level
        const currentLevel = levels[levels.length - 1];
        const firstTargetDeps = this.dependencyGraph.get(currentLevel[0]) || [];
        const firstDepsProcessed = firstTargetDeps.filter(d => processed.has(d)).length;
        
        if (depsProcessed === firstDepsProcessed) {
          currentLevel.push(target);
        } else {
          levels.push([target]);
        }
      }
      
      processed.add(target);
    }
    
    return levels;
  }
  
  private getAllDependencies(targets: string[]): Set<string> {
    const all = new Set<string>();
    const queue = [...targets];
    
    while (queue.length > 0) {
      const target = queue.shift()!;
      if (all.has(target)) continue;
      
      all.add(target);
      const deps = this.dependencyGraph.get(target) || [];
      queue.push(...deps);
    }
    
    return all;
  }
  
  private buildGraph(targets: Set<string>): Map<string, string[]> {
    const graph = new Map<string, string[]>();
    
    for (const target of targets) {
      graph.set(target, this.dependencyGraph.get(target) || []);
    }
    
    return graph;
  }
}

interface BuildResult {
  success: boolean;
  error?: string;
}

Features:

1. Topological sort: Determines correct build order
2. Parallel execution: Build independent targets simultaneously
3. Incremental builds: Cache to skip unchanged targets
4. Cycle detection: Detect and report circular dependencies
5. Level grouping: Group targets by dependency level

---

Key Takeaways

• Topological sort: Linear ordering of DAG vertices
• Requirements: Directed acyclic graph (no cycles)
• Kahn's algorithm: Uses in-degree counting, BFS-based
• DFS approach: Uses depth-first search, post-order
• Multiple solutions: DAG can have multiple valid orders
• Cycle detection: If can't process all vertices, cycle exists
• Applications: Task scheduling, build systems, dependency resolution