Skip to main content

Essential Graph Problems for SDE Interviews

· 7 min read

If you're having your placement season in a few months or want to revise graph concepts, I've made a list of hand-picked problems to cover the depth and breadth of graphs.

This isn't a magic list that guarantees you'll crack every interview or assessment. But these are standard problems and patterns I've consistently seen across interview experiences, company blogs, and my own preparation journey.

I've organized these by pattern because that's how interviews work, they don't ask "solve graph problem #47." They ask problems that test whether you understand BFS, topological sort, or Union Find. Once you recognize the pattern, the solution follows.

Think of this as your focused revision toolkit. Not too overwhelming, not too sparse. just the right problems to build strong pattern recognition.

Let's gooo!

Connect with me on LinkedIn to stay updated with more coding resources, interview tips, and problem-solving strategies!

Problem List by Pattern​

1. Graph Traversal (DFS/BFS Fundamentals)​

  1. Number of Islands
  2. Clone Graph
  3. Max Area of Island
  4. Pacific Atlantic Water Flow
  5. Number of Connected Components in an Undirected Graph
  6. Surrounded Regions
  7. Keys and Rooms
  8. Count Sub Islands
  9. Flood Fill
  10. Island Perimeter

2. Shortest Path Problems​

  1. Shortest Path in Binary Matrix
  2. Rotting Oranges
  3. 01 Matrix
  4. Walls and Gates
  5. Shortest Bridge
  6. Network Delay Time
  7. Path with Maximum Probability
  8. Cheapest Flights Within K Stops
  9. Minimum Cost to Make at Least One Valid Path in a Grid
  10. Shortest Routes I

3. Topological Sort & Dependency Resolution​

  1. Course Schedule
  2. Course Schedule II
  3. Alien Dictionary
  4. Sequence Reconstruction
  5. Minimum Height Trees
  6. Parallel Courses
  7. Sort Items by Groups Respecting Dependencies
  8. Course Schedule IV
  9. Game Route

4. Union Find (Disjoint Set Union)​

  1. Number of Provinces
  2. Redundant Connection
  3. Graph Valid Tree
  4. Accounts Merge
  5. Most Stones Removed with Same Row or Column
  6. Smallest String With Swaps
  7. Satisfiability of Equality Equations
  8. Number of Operations to Make Network Connected
  9. Lexicographically Smallest Equivalent String
  10. Minimize Malware Spread

5. Cycle Detection​

  1. Find Eventual Safe States
  2. Detect Cycles in 2D Grid
  3. Redundant Connection II
  4. Find the Celebrity

6. Graph Coloring & Bipartite Graphs​

  1. Is Graph Bipartite?
  2. Possible Bipartition
  3. Divide Nodes Into the Maximum Number of Groups

7. Minimum Spanning Tree​

  1. Min Cost to Connect All Points
  2. Connecting Cities With Minimum Cost
  3. Optimize Water Distribution in a Village
  4. Find Critical and Pseudo-Critical Edges in MST
  5. Road Construction

8. Advanced DFS/BFS Applications​

  1. Word Ladder
  2. Word Ladder II
  3. Minimum Genetic Mutation
  4. Open the Lock
  5. Sliding Puzzle
  6. Snakes and Ladders
  7. Bus Routes
  8. Shortest Path to Get All Keys

9. Advanced Graph Algorithms​

  1. Critical Connections in a Network
  2. Reconstruct Itinerary
  3. Evaluate Division
  4. Longest Increasing Path in a Matrix
  5. Swim in Rising Water
  6. Shortest Path Visiting All Nodes
  7. Reachable Nodes In Subdivided Graph
  8. Minimum Number of Days to Disconnect Island
  9. Number of Ways to Arrive at Destination

10. Matrix & Grid Graph Problems​

  1. As Far from Land as Possible
  2. Shortest Path in a Grid with Obstacles Elimination
  3. Escape a Large Maze
  4. Shortest Path with Alternating Colors
  5. Time Needed to Inform All Employees

11. Graph Construction & Modeling​

  1. Reconstruct a 2-Row Binary Matrix
  2. Check if There is a Valid Path in a Grid
  3. Water and Jug Problem
  4. Pyramid Transition Matrix

12. Competitive Programming Classics​

  1. Labyrinth
  2. Building Roads
  3. Message Route
  4. Building Teams
  5. Round Trip
  6. Monsters
  7. Shortest Routes II
  8. High Score
  9. Flight Discount
  10. Cycle Finding
  11. Flight Routes
  12. Planet Queries I
  13. Road Reparation
  14. ABC 139 E - League
  15. ABC 168 D - .. (Double Dots)
  16. ABC 176 D - Wizard in Maze
  17. ABC 209 E - Shiritori
  18. ARC 090 D - People on a Line

Let's connect on LinkedIn - I regularly share interview tips, problem-solving strategies, and coding resources that can help accelerate your preparation!

Good luck!