25 Graph Problems To Revise Before Interviews
sai ganesh reddy
2673
Graph TheoryGoogleMicrosoftAmazonLeetCodePlacementCareerDSAInterview

After posting 25 DP Problems To Revise Before Interviews, Today I've curated 25 carefully selected problems covering every major Graph pattern for interviews. If you're interviewing at Google or other DSA heavy companies, you might need extra practice, but for most tech interviews, this list is a solid foundation.

The 25 Essential Problems

1. Number of Islands - LeetCode 200

  • Pattern: Basic DFS/BFS on grid
  • Why: Foundation for all matrix-as-graph problems
  • Companies: Amazon, Microsoft, Meta, Bloomberg

2. Clone Graph - LeetCode 133

  • Pattern: Graph traversal with copying
  • Why: Tests understanding of graph representation
  • Companies: Meta, Amazon, Google

3. Pacific Atlantic Water Flow - LeetCode 417

  • Pattern: Multi-source BFS/DFS
  • Why: Shows reverse thinking and multiple traversals
  • Companies: Google, Amazon, Uber

4. Rotting Oranges - LeetCode 994

  • Pattern: Multi-source BFS with levels
  • Why: Classic BFS level-wise propagation
  • Companies: Amazon, Microsoft, Bloomberg

5. Word Ladder - LeetCode 127

  • Pattern: BFS for shortest path transformation
  • Why: Shows BFS on implicit graph
  • Companies: Amazon, Google, Meta

6. Number of Connected Components in Undirected Graph - LeetCode 323

  • Pattern: Basic DFS/Union-Find for components
  • Why: Foundation for connectivity problems
  • Companies: Google, Amazon, Meta

7. Graph Valid Tree - LeetCode 261

  • Pattern: Cycle detection + connectivity check
  • Why: Validates understanding of tree properties
  • Companies: Meta, Amazon, LinkedIn

8. Redundant Connection - LeetCode 684

  • Pattern: Cycle detection with Union-Find
  • Why: Classic Union-Find application
  • Companies: Amazon, Microsoft, Google

9. Accounts Merge - LeetCode 721

  • Pattern: Union-Find with grouping
  • Why: Real-world Union-Find application
  • Companies: Google, Meta, Amazon

10. Course Schedule - LeetCode 207

  • Pattern: Cycle detection in directed graph
  • Why: Foundation for dependency problems
  • Companies: Amazon, Meta, Microsoft

11. Course Schedule II - LeetCode 210

  • Pattern: Topological sort (Kahn's algorithm)
  • Why: Must know for ordering problems
  • Companies: Amazon, Google, Uber

12. Alien Dictionary - LeetCode 269

  • Pattern: Build graph + topological sort
  • Why: Tests graph construction from constraints
  • Companies: Google, Meta, Airbnb

13. Minimum Height Trees - LeetCode 310

  • Pattern: Topological sort from leaves
  • Why: Shows reverse topological thinking
  • Companies: Google, Amazon

14. Network Delay Time - LeetCode 743

  • Pattern: Dijkstra's algorithm
  • Why: Classic single-source shortest path
  • Companies: Amazon, Google, Microsoft

15. Cheapest Flights Within K Stops - LeetCode 787

  • Pattern: Modified Dijkstra/Bellman-Ford
  • Why: Shortest path with constraints
  • Companies: Google, Uber, Amazon

16. Path with Minimum Effort - LeetCode 1631

  • Pattern: Dijkstra on grid with custom cost
  • Why: Shows Dijkstra variation on matrix
  • Companies: Google, Amazon, Meta

17. Shortest Path in Binary Matrix - LeetCode 1091

  • Pattern: BFS for unweighted shortest path
  • Why: Grid shortest path, 8-directional movement
  • Companies: Amazon, Microsoft

18. Surrounded Regions - LeetCode 130

  • Pattern: Boundary DFS/BFS
  • Why: Teaches edge-based traversal
  • Companies: Amazon, Microsoft, Bloomberg

19. Is Graph Bipartite? - LeetCode 785

  • Pattern: Graph coloring, bipartite check
  • Why: Classic graph property verification
  • Companies: Amazon, Google

20. Critical Connections in a Network - LeetCode 1192

  • Pattern: Tarjan's algorithm for bridges
  • Why: Advanced DFS, shows articulation points concept
  • Companies: Amazon, Google, Meta

21. All Paths From Source to Target - LeetCode 797

  • Pattern: DFS with path tracking
  • Why: Backtracking on graphs
  • Companies: Amazon, Bloomberg

22. Bus Routes - LeetCode 815

  • Pattern: BFS on transformed graph
  • Why: Shows meta-node graph construction
  • Companies: Google, Amazon

23. Min Cost to Connect All Points - LeetCode 1584

  • Pattern: Minimum Spanning Tree (Kruskal's/Prim's)
  • Why: Classic MST problem
  • Companies: Amazon, Microsoft

24. Reconstruct Itinerary - LeetCode 332

  • Pattern: Eulerian path (Hierholzer's algorithm)
  • Why: Advanced DFS, lexicographic ordering
  • Companies: Google, Amazon

25. Shortest Path Visiting All Nodes - LeetCode 847

  • Pattern: BFS with bitmask state
  • Why: Combines BFS with dynamic programming
  • Companies: Google, Meta

Check out my posts which may help you in your preparation :

  1. Complete DP Problems & Resources Guide
  2. Complete Graph Problems & Resources Guide
  3. 13 DP Patterns for Interview Preparation
  4. 10 Dijkstra Variations for Interview Preparation
  5. Understanding Time Complexity: The 10^8 Operations Rule
  6. 10 Essential Design Problems for DSA Interviews
  7. Essential CS Fundamental Topics For Interviews
  8. Essential Graph Patterns for Coding Interviews
  9. Essential String Patterns for Coding Interviews
  10. 15 Essential DSA Patterns for Tech Interviews
  11. The 10 Variations of Two Pointers for Interview Preparation

These 25 problems are your foundation for Graphs. Master them, and Graphs becomes one of your strengths instead of a weakness.

Comment Additional questions which are worth solving!!!

Good luck! 🚀

Comments (4)