Graph Interview Problems - Topological Sort Cycle Bug

Graph problems are the great filter of software engineering interviews. They appear in roughly 30% of FAANG-level coding rounds not because interviewers love theory, but because real systems — Google Maps, LinkedIn's friend-of-a-friend suggestions, Uber's dispatch engine, Kubernetes dependency resolution — are fundamentally graphs under the hood. If you can't navigate a graph, you can't reason about the systems that run the modern internet.

The challenge with graph interviews isn't memorizing algorithms. BFS and DFS are straightforward once you've seen them twice. The real difficulty is pattern recognition: knowing within 60 seconds whether a problem is a shortest-path problem, a cycle detection problem, a topological sort problem, or a connected-components problem — and then executing flawlessly under pressure without missing the edge cases that separate a 'hire' from a 'no hire'.

By the end of this article you'll have a mental framework for classifying any graph problem on sight, complete runnable solutions for the 10 most common interview problems, and the internal mechanics — why BFS gives shortest paths in unweighted graphs, why DFS finds cycles, why Union-Find beats DFS for dynamic connectivity — explained at the level an interviewer expects when they ask 'can you walk me through your reasoning?'

What Topological Sort Cycle Detection Actually Reveals

Topological sort is a linear ordering of vertices in a directed graph such that for every directed edge u→v, u appears before v. The core mechanic is simple: repeatedly pick nodes with zero in-degree (Kahn's algorithm) or perform DFS with a post-order stack. But the real interview challenge — and the production bug — is cycle detection. A cycle makes topological ordering impossible, and the bug surfaces when your algorithm silently returns a partial order or infinite loops.

Kahn's algorithm works by counting in-degrees, enqueuing zero-in-degree nodes, and decrementing neighbors. If the final sorted list length is less than the total node count, a cycle exists. DFS-based approaches track three states: unvisited, visiting (on current path), and visited. A cycle is detected when you encounter a node in the 'visiting' state. This is O(V+E) time and O(V) space — efficient enough for graphs with millions of nodes.

Use topological sort for dependency resolution (build systems, package managers), task scheduling, or course prerequisite ordering. In production, the cycle bug bites hardest in dependency graphs that evolve dynamically — like microservice startup order or data pipeline DAGs. A single cycle can cascade into deadlocked deployments or stuck batch jobs. Always validate acyclic property before trusting the order.

Breadth-First Search (BFS): The Shortest Path Pattern

Breadth-First Search is the definitive algorithm for finding the shortest path in an unweighted graph. It explores the graph in 'layers'—visiting all neighbors at distance 1, then distance 2, and so on. This guarantees that the first time you reach a target node, you've found the shortest route. In interviews, this pattern is frequently disguised as 'minimum number of moves to solve a puzzle' or 'nearest exit in a maze.'

Here's how the BFS pattern works in practice: you maintain a queue and a visited set. Each layer corresponds to one iteration over the current queue size. For each node popped, you examine its neighbors. If a neighbor hasn't been visited, mark it visited and enqueue it. The distance increments only after processing a full layer. This gives you the correct minimum distance by construction.

A common variant is the 'multi-source BFS' where you start from several nodes simultaneously — used in problems like 'walls and gates' or 'spreading fire.'

package io.thecodeforge.graphs;

import java.util.*;

public class BfsNavigator {
    /**
     * io.thecodeforge implementation of Shortest Path in an Adjacency List
     * Time Complexity: O(V + E), Space Complexity: O(V)
     */
    public int findShortestPath(int nodes, List<List<Integer>> adj, int start, int target) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[nodes];
        int distance = 0;

        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int current = queue.poll();
                if (current == target) return distance;

                for (int neighbor : adj.get(current)) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.add(neighbor);
                    }
                }
            }
            distance++;
        }
        return -1; // No path found
    }
}

Depth-First Search (DFS): Cycle Detection, Connectivity, and Exhaustive Paths

Depth-First Search explores as far as possible along each branch before backtracking. It's the algorithm of choice when you need to explore all possibilities — detecting cycles, finding connected components, or solving problems like 'clone a graph' or 'path exists between two nodes.' DFS can be implemented recursively (simpler) or iteratively with a stack (avoids stack overflow for deep graphs).

Cycle detection using DFS is a classic pattern. For undirected graphs, you need to check if you encounter a neighbor that is visited and is NOT the parent of the current node. For directed graphs, you also need a recursion stack (set) to detect a back edge — a node that is currently in the recursion stack means a cycle.

DFS also forms the backbone of backtracking problems on graphs, like finding all paths from source to target in a DAG. In those cases, you don't mark nodes as visited globally; instead, you mark them on the current path and unmark after recursion.

package io.thecodeforge.graphs;

import java.util.*;

public class DfsCycleDetector {
    /**
     * Detects cycle in a directed graph using DFS with recursion stack.
     * O(V+E) time, O(V) space.
     */
    public boolean hasCycle(int nodes, List<List<Integer>> adj) {
        int[] state = new int[nodes]; // 0=unvisited, 1=in current stack, 2=processed
        for (int i = 0; i < nodes; i++) {
            if (state[i] == 0) {
                if (dfs(i, adj, state)) return true;
            }
        }
        return false;
    }

    private boolean dfs(int u, List<List<Integer>> adj, int[] state) {
        state[u] = 1;
        for (int v : adj.get(u)) {
            if (state[v] == 1) return true; // back edge => cycle
            if (state[v] == 0 && dfs(v, adj, state)) return true;
        }
        state[u] = 2;
        return false;
    }
}

Topological Sort: Handling Task Dependencies (Kahn's Algorithm)

Topological sorting is only applicable to Directed Acyclic Graphs (DAGs). It provides a linear ordering of vertices such that for every directed edge $u \to v$, vertex $u$ comes before $v$. This is the foundation of build systems (like Gradle or Maven) and task scheduling. Kahn's Algorithm is the preferred iterative approach using in-degrees.

The algorithm works by maintaining an in-degree array for each node. Initialize a queue with all nodes that have in-degree 0. Then repeatedly pop a node, append it to result, and for each neighbor, decrement its in-degree. If a neighbor's in-degree becomes 0, push it into the queue. If at the end the result size doesn't equal the number of nodes, the graph has a cycle.

The alternative is recursive topological sort using DFS with a list of nodes in post-order — reverse of finishing times gives the topological order.

package io.thecodeforge.graphs;

import java.util.*;

public class DependencyResolver {
    /**
     * Resolves task order using Kahn's Algorithm (Topological Sort)
     */
    public int[] resolveOrder(int numTasks, int[][] dependencies) {
        int[] inDegree = new int[numTasks];
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numTasks; i++) adj.add(new ArrayList<>());

        for (int[] dep : dependencies) {
            adj.get(dep[1]).add(dep[0]);
            inDegree[dep[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numTasks; i++) {
            if (inDegree[i] == 0) queue.add(i);
        }

        int[] order = new int[numTasks];
        int index = 0;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            order[index++] = curr;

            for (int neighbor : adj.get(curr)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) queue.add(neighbor);
            }
        }

        return index == numTasks ? order : new int[0]; // Empty if cycle detected
    }
}

Union-Find (Disjoint Set Union): Dynamic Connectivity & Redundant Edges

Union-Find is designed for problems where you need to efficiently merge sets and answer connectivity queries under dynamic edge additions. It excels in scenarios like 'find redundant connection' (detect where an edge connects two already-connected nodes) or 'number of components after adding edges online.'

The core operations are find() — with path compression — and union() — using union by rank or size. Optimized versions run in almost O(1) amortized time (inverse Ackermann function). Union-Find does not handle graph traversal or shortest paths; it's strictly for connectivity.

A classic interview problem: given a list of edges in a graph, find which edge creates a cycle (redundant connection). Using Union-Find, you process edges one by one. For each edge (u, v), if find(u) == find(v), the edge is redundant. Otherwise, union(u, v).

package io.thecodeforge.graphs;

public class UnionFind {
    private int[] parent, rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }

    public int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]); // path compression
        return parent[x];
    }

    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return false; // already connected

        // union by rank
        if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
        else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
        else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }

    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
}

Graph Representation & Pattern Recognition: The First 60 Seconds

The most critical skill in graph interviews is recognising the pattern within the first minute. Here's a quick decision tree:

1. Need shortest path in unweighted graph? → BFS.
2. Need all paths or detect cycles? → DFS.
3. Need to process tasks in order? → topological sort (Kahn/DFS).
4. Need dynamic connectivity or detect redundant edges? → Union-Find.
5. Weighted graph, shortest path, no negative edges? → Dijkstra.
6. Weighted graph with negative edges? → Bellman-Ford.
7. Need all-pairs shortest paths? → Floyd-Warshall.

Graph representation also matters. Adjacency List (List<List<Integer>>) is the default for sparse graphs (V up to 10^5, E up to 10^5). Adjacency Matrix (int[][]) only if V is small (< 1000) or graph is dense (E ~ V²). Edge List (List<int[]>) is useful when you need to process edges without adjacency queries.

In interviews, you'll rarely need to implement Dijkstra from scratch — but you must be able to reason about its behavior and write BFS/DFS/Kahn without hesitation.

package io.thecodeforge.graphs;

import java.util.*;

public class GraphRepresentation {
    // Adjacency List (preferred)
    public List<List<Integer>> buildAdjList(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]); // for undirected
        }
        return adj;
    }

    // Adjacency Matrix (for dense/small)
    public int[][] buildAdjMatrix(int n, int[][] edges) {
        int[][] matrix = new int[n][n];
        for (int[] e : edges) {
            matrix[e[0]][e[1]] = 1;
            matrix[e[1]][e[0]] = 1;
        }
        return matrix;
    }

    // Edge List (for edge processing)
    public int[][] buildEdgeList(int[][] edges) {
        return edges; // already edge list
    }
}

Fundamentals Problems: The Non-Negotiable Baseline

Every interviewer starts here. Not because they're sadists, but because these problems strip away the syntax noise and reveal whether you actually understand graphs. If you can't implement BFS on an adjacency list in your sleep, you're not ready for anything harder.

The classics: Clone Graph, Course Schedule, Number of Islands. These aren't just practice — they're vocabulary. Clone Graph tests your grasp of graph traversal with a twist: you're building the graph as you walk it. Course Schedule is topological sort disguised as a college metaphor. Number of Islands is BFS/DFS with a grid wrapper.

Here's the real test: can you explain WHY the visited set must be checked before enqueuing, not after dequeuing? That single detail separates people who copy-paste from people who understand trade-offs. If you get this wrong in an interview, you've already lost.

Master these. Not by memorizing solutions, but by internalizing the traversal mechanics. Your interview won't ask you to solve Number of Islands — it'll ask you to solve something that reduces to Number of Islands. Recognize the pattern, not the problem statement.

// io.thecodeforge — interview tutorial

def count_islands(grid):
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    islands = 0
    
    def bfs(start_row, start_col):
        queue = [(start_row, start_col)]
        visited[start_row][start_col] = True
        while queue:
            r, c = queue.pop(0)
            for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    if grid[nr][nc] == '1' and not visited[nr][nc]:
                        visited[nr][nc] = True
                        queue.append((nr, nc))
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and not visited[r][c]:
                islands += 1
                bfs(r, c)
    return islands

Intermediate Problems: Where They Probe Your Edge Cases

Once you've proven you can walk a graph, interviewers start throwing wrenches. Directed vs undirected? Weighted vs unweighted? Dense vs sparse? These aren't academic distinctions — they determine whether your solution runs in milliseconds or crashes the production server.

Problems like Word Ladder and Network Delay Time hit this zone. Word Ladder isn't just BFS — it's BFS on an implicit graph where nodes are words and edges exist if words differ by one character. The naive approach builds the entire adjacency list upfront, O(N² K) where N is word count and K is word length. The production solution generates neighbors on the fly, O(N K²). That's the difference between passing and timing out.

Network Delay Time tests Dijkstra's algorithm, but more importantly, it tests whether you know why Dijkstra fails on negative weights. If you can't articulate that — and the fix (Bellman-Ford) — you're not ready for follow-ups.

These problems separate candidates who've seen graphs from those who've shipped graph code. The patterns here: build the graph efficiently, handle disconnected components, and know when shortest path means unweighted BFS vs weighted priority queue.

// io.thecodeforge — interview tutorial

from collections import deque

def word_ladder(start, end, word_list):
    word_set = set(word_list)
    if end not in word_set:
        return 0
    
    queue = deque([(start, 1)])
    while queue:
        current_word, steps = queue.popleft()
        if current_word == end:
            return steps
        
        # Generate neighbors on the fly — O(K²) per word
        for i in range(len(current_word)):
            for c in 'abcdefghijklmnopqrstuvwxyz':
                next_word = current_word[:i] + c + current_word[i+1:]
                if next_word in word_set:
                    word_set.remove(next_word)  # avoid cycles
                    queue.append((next_word, steps + 1))
    return 0

Advanced Problems: The Production Systems Interview

This is where FAANG+ pays its rent. These aren't toy problems — they're system design prototypes in disguise. Minimum Spanning Tree, strongly connected components, and maximum flow feel academic until your service needs to detect communities of fraudulent accounts or route traffic across regions.

Problems like Accounts Merge and Critical Connections in a Network test advanced Union-Find and Tarjan's algorithm. Accounts Merge looks like a connectivity problem, but the twist is you're merging sets based on shared emails. It's not enough to union — you must represent each person as a node, each email as an attribute, and then detect which persons actually form a group. The naive approach is O(N²) and gets slaughtered by test cases with 10,000 accounts.

Critical Connections tests Tarjan's algorithm for bridges in a graph. Most candidates freeze because they've never seen DFS with discovery times and low-link values outside of CLRS. But if you strip away the jargon: you're assigning each node a 'timestamp' on first visit, then tracking the smallest timestamp reachable via back edges. If a child can't reach an ancestor without passing through the parent, that edge is critical.

Master these and you've proven you can handle graphs at scale. Not because you'll implement Tarjan's in production, but because you understand the trade-offs between Union-Find, DFS, and BFS for real-world connectivity problems.

// io.thecodeforge — interview tutorial

def critical_connections(n, connections):
    graph = [[] for _ in range(n)]
    for u, v in connections:
        graph[u].append(v)
        graph[v].append(u)
    
    discovery = [-1] * n
    low = [0] * n
    visited = [False] * n
    result = []
    timer = [0]
    
    def dfs(node, parent):
        visited[node] = True
        timer[0] += 1
        discovery[node] = low[node] = timer[0]
        for neighbor in graph[node]:
            if neighbor == parent:
                continue
            if not visited[neighbor]:
                dfs(neighbor, node)
                low[node] = min(low[node], low[neighbor])
                if low[neighbor] > discovery[node]:
                    result.append([node, neighbor])
            else:
                low[node] = min(low[node], discovery[neighbor])
    
    for i in range(n):
        if not visited[i]:
            dfs(i, -1)
    return result