top problems based on graphs for FAANG

Problem Type Algorithm / Notes Difficulty

1 Clone Graph Traversal BFS/DFS Easy 2 Number of Islands Connected Components DFS/BFS Easy 3 Max Area of Island Connected Components DFS/BFS Medium 4 Flood Fill Coloring / Traversal DFS/BFS Easy 5 Course Schedule I Topological Sort / Cycle Detection DFS / Kahn’s Medium 6 Minimum Depth of Binary Tree BFS Level-order BFS Easy 7 Course Schedule II Topological Sort DFS / Kahn’s Medium 8 Word Ladder Shortest Path BFS Medium 9 Network Delay Time Shortest Path Dijkstra Medium 10 Minimum Height Trees Tree / BFS Multi-source BFS Medium 11 Redundant Connection Cycle Detection Union-Find Medium 12 Critical Connections in Network Bridges Tarjan’s Algorithm Hard 13 Alien Dictionary Topological Sort Graph + DFS Hard 14 Cheapest Flights Within K Stops Shortest Path with Constraints BFS / DP / Dijkstra Hard 15 Number of Distinct Islands Connected Components + Hashing DFS + HashSet Medium 16 Graph Valid Tree Cycle Detection + Connected Components Union-Find Medium 17 Surrounded Regions BFS/DFS Flood fill variant Medium 18 Course Scheduling III (Weighted/Time) Topological Sort + DP DAG + DP Hard 19 Clone Binary Tree with Random Pointer DFS/BFS HashMap + DFS Hard 20 Traveling Salesman (Graph DP) Graph DP Bitmask DP Hard 21 Pacific Atlantic Water Flow BFS/DFS Multi-source BFS Medium 22 Bipartite Graph Check Coloring / Traversal BFS/DFS Medium 23 Cheapest Path in Weighted Graph Shortest Path Dijkstra / Bellman-Ford Medium 24 Course Schedule with Prerequisites Topological Sort DFS / Kahn’s Medium 25 Network Connectivity Queries Union-Find Disjoint Set Medium

Tips for Using This Checklist

1. Pattern First: Before coding, identify if it’s traversal, shortest path, topo sort, or connected components.
2. Algorithm Hint: Use the suggested algorithm as a starting point; optimize later.
3. Difficulty Ladder: Start from Easy → Medium → Hard; FAANG usually asks Medium/Hard.
4. Implementation Practice: Implement each in 2 languages you’re comfortable with (Java, Python, JS).
5. Edge Cases: Always test disconnected graphs, cycles, single-node graphs, and empty graphs.