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

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