Top 10 Graph Interview Problems: Patterns, Pitfalls & Solutions

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

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

Topological Sort: Handling Task Dependencies

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.

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

Frequently Asked Questions