top 5 graph problems for FAANG interview
1️⃣ Detect Cycle in Graph
Why FAANG loves it:
Cycle detection is critical in dependency graphs, deadlocks, and course scheduling.
Problem examples:
Detect cycle in a directed graph
Detect cycle in an undirected graph
Techniques:
DFS with visited & recursion stack → directed graphs
Union-Find / Disjoint Set → undirected graphs
Complexity: O(V + E)
2️⃣ Shortest Path Problems
Why FAANG loves it:
Shows knowledge of BFS/Dijkstra and ability to handle weighted/unweighted graphs.
Problem examples:
Shortest path in unweighted graph → BFS Shortest path in weighted graph with positive weights → Dijkstra Shortest path with negative edges → Bellman-Ford All-pairs shortest path → Floyd-Warshall
Pattern:
BFS → unweighted Min-heap Dijkstra → weighted
3️⃣ Connected Components / Number of Islands
Why FAANG loves it:
Common in grid problems and social network problems.
Problem examples:
Count connected components in a graph
Number of islands in a 2D grid
Techniques:
DFS / BFS traversal on unvisited nodes Union-Find / Disjoint Set for optimization
Pattern:
Iterate all nodes → run DFS/BFS if unvisited → count components
4️⃣ Topological Sort / Course Scheduling
Why FAANG loves it:
Tests understanding of dependencies and DAGs.
Problem examples:
Course Schedule I / II (LeetCode 207, 210)
Task scheduling problems
Techniques:
DFS-based topological sort Kahn’s algorithm (BFS with in-degree)
Complexity: O(V + E)
5️⃣ Graph Traversal / Flood Fill / Maze Problems
Why FAANG loves it:
Combines BFS/DFS logic with real-world scenarios like grids, mazes, or shortest paths in 2D/3D.
Problem examples:
Flood fill (LeetCode 733) Number of distinct islands Shortest path in a maze
Techniques:
BFS for shortest path DFS for area/fill counting
🔹 Extra High-Yield Patterns
Minimum Spanning Tree: Kruskal’s / Prim’s → used for network optimization
Graph coloring / bipartite check → used in scheduling problems
Word Ladder / BFS on implicit graphs → classic FAANG problem
Union-Find applications → friend circles, accounts merging
✅ Summary Table
Question Type Common Approach FAANG Example
- Cycle Detection DFS / Recursion Stack / Union-Find Detect cycle in directed/undirected graph
- Shortest Path BFS / Dijkstra / Bellman-Ford Shortest path in weighted/unweighted graph
- Connected Components DFS / BFS / Union-Find Number of islands / friend circles
- Topological Sort DFS / Kahn’s Algorithm Course Schedule / Task order
- Traversal / Flood Fill DFS / BFS Maze shortest path / flood fill