Top 10 Graph problems for FAANG interview

Graph problems are very common in FAANG interviews, especially those involving BFS, DFS, shortest paths, cycles, and connected components. Here's a curated list of top 10 graph problems, with key techniques and interview tips.

Top 10 Graph Problems for FAANG

1. Number of Islands

• Problem: Given a 2D grid of '1's (land) and '0's (water), count the number of islands.
• Concept: Use DFS or BFS to explore connected components.
• Time: O(m * n), Space: O(m * n) (for visited)

2. Clone Graph

• Problem: Given a reference node, clone the entire graph (nodes + edges).
• Concept: Use DFS or BFS with a HashMap to track visited nodes.
• Common twist: Graph may have cycles.

3. Course Schedule (Topological Sort)

• Problem: Given prerequisites for courses, determine if you can finish all courses.
• Concept: Detect cycle in DAG using DFS or Kahn’s Algorithm (BFS topological sort).

4. Alien Dictionary

• Problem: Given a sorted dictionary of words, find the order of characters.
• Concept: Build a graph of character dependencies → Topological sort.

5. Minimum Spanning Tree (Kruskal / Prim)

• Problem: Connect all points/nodes with minimum cost (weighted undirected graph).
• Concept: Use Kruskal’s algorithm with Union-Find or Prim’s algorithm.
• Time: O(E log V)

6. Dijkstra’s Shortest Path

• Problem: Find shortest path from source to all nodes in weighted graph.
• Concept: Use min-heap (priority queue) + adjacency list.
• Variants: Can extend to A algorithm* for grids.

7. Word Ladder

• Problem: Transform a word to another using minimum steps, changing one letter at a time.
• Concept: Model as graph BFS, each word is a node, edges connect words with 1-letter difference.

8. Graph Cycle Detection

• Problem: Detect cycles in directed or undirected graphs.

• Concept:

  • Undirected: DFS with parent tracking
  • Directed: DFS with recursion stack or Kahn’s algorithm

9. Connected Components / Number of Connected Components

• Problem: Count number of connected components in a graph.
• Concept: DFS/BFS or Union-Find (Disjoint Set)

10. Network Delay Time / Shortest Path with Time

• Problem: Find minimum time for all nodes to receive a signal from a source.
• Concept: Dijkstra or Bellman-Ford algorithm.
• Variant: Weighted directed graphs, possibly negative edges (Bellman-Ford needed).

⚡ Graph Interview Tips

1. Know both adjacency list and adjacency matrix representations.
2. Always analyze directed vs undirected graphs.
3. BFS → good for shortest path in unweighted graphs DFS → good for connected components, cycle detection, topological sort
4. Union-Find is essential for MST and connected components problems.
5. Many problems have follow-ups: return path, detect multiple components, or weighted shortest paths.