Graphs interview questions

Graph problems are often hidden: a grid of islands, a list of course prerequisites, words that differ by one letter. The first skill is noticing that the question is about nodes and connections.

How do I solve graphs interview questions?

Graph problems model items as nodes and relationships as edges. Build an adjacency list, then use depth-first search to explore or detect cycles, breadth-first search for the shortest path in an unweighted graph, and topological sort for dependency order. Track visited nodes so each is processed once.

Practise graphs

How to recognise a graphs problem

The input is a grid, a list of pairs, prerequisites, friendships or transformations, and the question asks about connectivity, the number of groups, a path or an ordering.

You need the fewest steps to get from one state to another when every step costs the same, which is breadth-first search.

Tasks depend on other tasks and you need a valid order or to detect that none exists, which is topological sort.

How to build the solution

Build an adjacency list from the input, or treat the grid cells and their four neighbours as the graph. Decide if the graph is directed.

Keep a visited set. Mark a node when you add it to the queue (breadth-first search) or when you enter it (depth-first search) so it is never processed twice.

For the shortest path in an unweighted graph, run breadth-first search from the start and record the distance as you go; the first time you reach the target is the shortest.

For ordering, count incoming edges, start from nodes with none, and repeatedly remove them; if you cannot remove every node there is a cycle.

Classic problems to practise

Number of Islands, Clone Graph, Course Schedule, Rotting Oranges, Word Ladder, Pacific Atlantic Water Flow, Number of Connected Components, Network Delay Time (weighted).

Mistakes interviewers see

Marking visited too late in breadth-first search, so the same node enters the queue many times.

Forgetting disconnected graphs: loop over every node as a possible start.

Using breadth-first search on weighted edges. Shortest paths with weights need Dijkstra's algorithm, which uses a priority queue.

Going out of bounds on grids, and confusing rows and columns when moving.

Practise it as an interview

Take a topic-based interview on graphs to practise the pattern the way it is asked: say the pattern before you code, write and run the solution in a live editor, and answer the cross-questions about edge cases and complexity. The scored report shows whether you lost points explaining, coding or defending. Your first 3 single-question interviews are free for life, every interview report is free, and a new account also gets 6 welcome credits.

Frequently asked questions

What is the time complexity of BFS and DFS?

Linear in the number of nodes plus edges when the graph is an adjacency list. On a grid with n cells, it is linear in n.

When do I use Union-Find instead of DFS?

When the question is about connectivity as edges arrive, or about counting groups after merges. It handles a stream of merges efficiently.