Graph Interview Problems

Problem-Solving Framework

Before diving into specific problems, remember this approach for any graph problem:

1. Model as graph: Identify vertices, edges, and whether directed/undirected/weighted
2. Choose traversal: BFS for shortest path/level-by-level, DFS for exhaustive search/components
3. Choose representation: Usually adjacency list, sometimes implicit (grid)

Problem 1: Number of Islands

Problem: Given a 2D grid of '1' (land) and '0' (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Approach: Each island is a connected component. Run DFS/BFS from each unvisited land cell, marking all connected land as visited. Count how many times you start a new traversal.

Time: O(M×N), Space: O(M×N) worst case for recursion stack.

Problem 2: Is Graph Bipartite?

Problem: Determine if a graph can be 2-colored (vertices divided into two sets with no edges within same set).

Approach: BFS/DFS coloring. Try to color the graph with 2 colors. If any adjacent vertices get the same color, it is not bipartite.

Problem 3: Clone Graph

Problem: Deep copy a connected undirected graph. Each node has a value and list of neighbors.

Approach: BFS/DFS with a hashmap mapping original nodes to their clones.

Problem 4: Course Schedule (Cycle Detection)

Problem: Given n courses and prerequisites, determine if you can finish all courses (no circular dependencies).

Approach: This is cycle detection in a directed graph. Use topological sort — if it processes all nodes, no cycle exists.

Problem 5: Word Ladder (Shortest Transformation)

Problem: Transform one word to another, changing one letter at a time, where each intermediate word must be in a dictionary. Find the shortest transformation sequence length.

Approach: BFS where each word is a vertex and edges connect words that differ by one letter.

Problem 6: Network Delay Time

Problem: Given a network of n nodes with weighted directed edges and a source, find time for signal to reach all nodes (longest shortest path from source).

Approach: Dijkstra from source, answer is max of all distances.

Problem 7: Surrounded Regions

Problem: Capture all 'O' regions that are completely surrounded by 'X'. Border-connected 'O' cells are NOT captured.

Approach: Reverse thinking — start DFS/BFS from all border 'O' cells (these survive). Everything else gets captured.

Problem 8: Cheapest Flights Within K Stops

Problem: Find cheapest flight from src to dst with at most K stops.

Approach: Modified BFS/Bellman-Ford limited to K+1 relaxation iterations, or Dijkstra with state (node, stops_remaining).

Problem 9: Detect Cycle in Directed Graph

Approach: DFS with three states: unvisited, in current recursion stack (GRAY), fully processed (BLACK). A back edge to a GRAY node indicates a cycle.

Problem 10: Shortest Path in Binary Matrix

Problem: Find shortest path from top-left to bottom-right in a 0/1 grid (can move in 8 directions, only through 0-cells).

Approach: Standard BFS on grid with 8-directional movement.

Problem 11: Alien Dictionary (Topological Sort)

Problem: Given a sorted list of words in an alien language, determine the order of characters.

Approach: Compare adjacent words to extract ordering constraints (directed edges). Then topological sort.

Problem 12: Minimum Height Trees

Problem: Find all roots of trees that give minimum height.

Approach: Topological peeling — repeatedly remove leaf nodes (degree 1). The last 1-2 remaining nodes are the answer (centroids of the tree).

Pattern Summary