20 graph problems for FAANG interviews

20 graph problems FAANG interviewers test, organized by 5 patterns. Key insight per problem, with the practice order that builds fluency fastest.

10 minutes
Intermediate
What you will learn

Why 5 graph patterns generate every FAANG interview question

Which 4 problems per pattern build full coverage

How to trace connected component problems using DFS flood fill

The practice order that builds graph fluency fastest

289 graph problems sit on LeetCode. Roughly 40 are tagged at FAANG companies. And yet the core variations that actually appear in graph problems FAANG interviews test cluster around just 5 patterns.

The pattern count is the number that matters, not the problem count.

⚡TL;DR
Graph interview problems fall into 5 patterns: DFS, BFS, connected components, topological sort, and Dijkstra. Four problems per pattern, practiced in the right order, covers every core variation FAANG companies test.

Why 5 patterns cover every graph problems

Graph problems cluster around 5 core patterns: DFS, BFS, connected components, topological sort, and shortest path. Mastering 4 problems per pattern covers the variations that appear in FAANG interviews.

That's not a simplification, it's how graph algorithms actually work.

Every graph problem you'll encounter in an interview is a composition of these building blocks. "Find all paths from source to target" is DFS. "Minimum steps to reach a cell" is BFS. "How many disconnected regions exist" is connected components. The wording changes, but the underlying pattern doesn't.

The 20 problems below aren't random picks from a difficulty filter. Each one isolates a specific variation within its pattern. After working through all four in a group, you've seen every way that pattern gets tested.

ℹ️ Info
This list uses problems from Codeintuition's Graph course, which teaches each pattern from first principles before any problems begin. The problems below map directly to those 5 pattern modules.

DFS: Paths, cycles, and enumeration

DFS problems are about exhaustive exploration. When a problem says "find all," "detect if a path exists," or "check for cycles," you're in DFS territory.

Each problem below isolates a different DFS variation.

  1. 1Source to target paths: Find all paths between two nodes. Pure DFS enumeration. You backtrack after exploring each branch to collect all paths, not just the first one you find.
  2. 2Detect cycle in a directed graph: Three-state coloring (white/grey/black) distinguishes unvisited, in-progress, and completed nodes. A grey-to-grey edge means a cycle. This is also the foundation for understanding why topological sort fails on cyclic graphs.
  3. 3Hamiltonian paths: Visit every node exactly once. The constraint "exactly once" forces you to track visited state globally and backtrack when a path dead-ends. This is where DFS and backtracking blur together, and honestly, the boundary between them is less clean than textbooks suggest. DFS explores a graph's topology. Backtracking explores a decision space. But the code often looks identical.
  4. 4Simple cycles: Enumerate all simple cycles, combining cycle detection with path enumeration. You need to track the recursion stack, not just the visited set.
“The wording changes across graph problems. The underlying DFS structure doesn't.”
Pattern recognition over problem memorization

BFS: Shortest unweighted paths

BFS is for minimum something in an unweighted graph. "Minimum steps," "shortest path," "nearest," "fewest moves." When weights are equal or absent, BFS guarantees the shortest path by exploring level by level.

  1. 1Minimum steps in a grid: Classic grid BFS. Start at top-left, reach bottom-right with fewest moves. Each cell is a graph node with 4 neighbours.
  2. 2Nearest Distance: Uses multi-source BFS. Instead of starting from one node, you start from all target nodes simultaneously. Enqueue every source at step 0 and let the BFS wavefront expand outward.
  3. 3Shortest word transformation: Transform one word to another, changing one letter at a time, using a dictionary. Each word is a node. Each single-letter change is an edge. The graph isn't given explicitly. You construct it from the dictionary.
  4. 4Minimum steps in a grid II: Traverse a grid with obstacles and the ability to remove a limited number of them. The state isn't just (row, col) but (row, col, removals_remaining). BFS on an expanded state space.

Once you've solved all four, BFS variants in a FAANG interview will feel like recombinations of these mechanics.

Connected components: Regions and islands

Connected component problems ask you to count, measure, or operate on disconnected regions. "How many islands," "size of the largest region," "are these nodes connected." You're not pathfinding here, you're partitioning.

  1. 1Island count: The canonical problem. Given a grid of 0s and 1s, count the number of islands. The DFS flood fill looks like this step by step:

  1. Python

The identification lesson for connected components teaches three recognition triggers: grid or adjacency list, no pathfinding requirement, and a question about groups or regions. When you spot those three together, you're looking at a connected component problem.

  1. 1Size of largest island: Same flood fill, but return the size of each component and track the maximum. The DFS return value carries the count upward.
  2. 2Sum of minimums: For each connected component, find the minimum value and sum them. Connected component problems aren't always about counting. Sometimes you compute a property per component.
  3. 3Find connected components: Build the component list explicitly using an adjacency list. This is the raw version of island counting without the grid abstraction.

Topological sort: Ordering with dependencies

Topological sort problems involve directed acyclic graphs where you need a valid ordering that respects dependencies. "Prerequisites," "build order," "course schedule," "task dependencies." If the problem mentions ordering with constraints, it's topological sort.

  1. 1Implement topological sort: The foundation. Build a valid ordering using DFS with a stack or BFS with in-degree tracking (Kahn's algorithm). A node gets added to the ordering only after all its dependencies are processed.
  2. 2Implement topological sort II: Return all valid topological orderings. There's usually more than one valid order. This forces you to understand what makes an ordering valid rather than just finding one.
  3. 3Detect cycle in a directed graph: This appears under DFS too, and that's intentional. Cycle detection is the prerequisite for topological sort. If the graph has a cycle, no valid topological ordering exists. The two are opposite sides of the same check.
  4. 4Course Schedule: (Classic FAANG problem). Given prerequisites, determine if you can finish all courses. This is topological sort applied to a real constraint. The answer reduces to "does the graph contain a cycle?"
💡 Tip
Topological sort shows up at Google and Amazon more frequently than most engineers expect. The pattern transfers directly to dependency resolution problems in system design rounds too.

Dijkstra: Weighted shortest paths

Dijkstra problems involve non-negative edge weights where you need the minimum-cost path. "Minimum cost," "cheapest route," "shortest time" combined with varying edge weights. When BFS won't work because edges have different costs, Dijkstra is the answer.

  1. 1Minimum cost path: Find the cheapest path through a weighted grid. Unlike BFS where you process nodes level by level, Dijkstra processes them by accumulated cost using a priority queue.
  2. 2Cheapest flights: Find the cheapest route between cities with at most K stops. The state is (city, stops_remaining), not just city. Dijkstra on an expanded state space, similar to how BFS expands state for the grid-with-removals problem.
  3. 3Minimum travel time: Shortest time between nodes with time-varying edges. Edge weights can encode different real-world quantities. The algorithm doesn't change. The modelling does.
  4. 4Teleporter Grid: Move through a grid with teleportation portals that have different costs. Portals create non-local edges in the graph. You model the grid as a weighted graph where adjacent cells have cost 1 and portals have their specified cost, then run Dijkstra.

How to work through these graph problems FAANG candidates miss

Don't solve them randomly. The order matters because each pattern reuses mechanics from the previous one.

Start with connected components. Island Count and its variations teach graph traversal mechanics (visited tracking, neighbour exploration, recursion on grids) without the complexity of pathfinding or ordering constraints. Move to DFS second, where you add path tracking and backtracking on top of the same traversal core. Source to Target Paths is the natural bridge.

BFS comes third because it shares the traversal mechanics but introduces the level-by-level guarantee. After DFS, the contrast clarifies when each traversal type applies. Then topological sort, which builds directly on DFS (the DFS-based topological sort is a modified DFS with a stack). You'll recognise the cycle detection code from the DFS section.

Dijkstra comes last. It builds on BFS (same frontier expansion idea) but replaces the FIFO queue with a priority queue. If you want the mathematical proof for why this greedy approach works, Dijkstra's original 1959 paper is surprisingly readable at three pages.

That's interleaving in practice. You're not studying five isolated topics. You're building one skill with five variations, and each variation reinforces the previous ones.

The engineers who struggle with graph problems aren't missing knowledge. They're missing scope. They don't know which problems matter, which patterns those problems belong to, or what order to tackle them in. Codeintuition's Graph course structures all 37 problems across these exact 5 patterns with the understanding and identification phase before any problem begins. You don't guess which pattern a problem belongs to. You learn to recognise it.

Codeintuition's Arrays and Singly Linked List courses (63 lessons, 85 problems, 15 patterns, all open access) cover the traversal foundations you'll need before the Graph course. If you haven't built that intuition through linked lists and trees yet, start there. The graph patterns won't stick without that foundation.

For the complete picture on graph algorithms, including shortest path proofs and advanced topics like max-flow and bipartite matching, see our full guide to graph algorithms. If you're also working through tree problems, the recursive traversal patterns in our BFS vs DFS comparison show how the same traversal mechanics transfer between trees and graphs.

Three months from now, you open a graph problem in your Amazon on-site. It describes a network of servers with varying latency. You don't panic because you see weighted edges, a source node, and a minimum-cost question. That's Dijkstra, and you've solved four problems with that exact shape. You start writing the solution.

Do you want to master data structures?

Try our data structures learning path made of highly visual and interactive courses. Get hands on experience by solving real problems in a structured manner. All resources you would ever need in one place for FREE

Start Learning
Twenty problems across 5 patterns gives you full coverage. The goal isn't volume. It's covering every variation within each pattern so that new problems feel like recombinations of what you've already seen.
Union-Find is useful for specific problems like detecting cycles in undirected graphs or dynamic connectivity queries. But it's not one of the 5 core patterns that generate most FAANG graph questions. Learn it after you've covered DFS, BFS, connected components, topological sort, and Dijkstra. Those five handle the majority of what you'll see.
Graph problems add two dimensions that tree problems don't have: cycles and multiple paths between nodes. Trees are a subset of graphs with no cycles and exactly one path between any two nodes. If you're comfortable with DFS and BFS on trees, the jump to graphs is smaller than it feels. The traversal mechanics are identical. The bookkeeping (visited sets, cycle detection) is what's new.
Start with connected components (simplest traversal), then DFS (adds path tracking), then BFS (adds shortest-path guarantee), then topological sort (builds on DFS), then Dijkstra (builds on BFS). Each pattern reuses mechanics from the previous one, so the learning compounds.
They appear rarely. Dijkstra handles the vast majority of weighted shortest-path questions in FAANG interviews because most problems use non-negative weights. Bellman-Ford shows up when negative weights are explicitly mentioned. Floyd-Warshall is typically a system design consideration, not a coding round problem. Focus on Dijkstra first.
Was this helpful?