Top 5 Graphs Interview Questions
Browse 5 real-world technical and behavioral interview questions about Graphs. Review scenarios, edge cases, and architectural best practices.
Find the cheapest flight from one city to another using at most K stops. Why does plain Dijkstra give the wrong answer?
Plain Dijkstra minimises cost alone, so it can return a cheap route with too many stops, and settling each city once discards a dearer route that still has stops to spare. Make the state city plus edges used, or run Bellman-Ford for exactly K + 1 rounds, each reading only the previous round's distances.
Count the islands in a grid of land and water. Then land is added one cell at a time, and you report the island count after every addition.
For one grid, number of islands is a flood fill: each unvisited land cell starts a BFS or DFS, O(rows x cols). For land arriving cell by cell, rerunning that is too slow, so use union-find. Each new cell adds one island, and each union with a neighbour in a different set removes one, at near-constant amortised cost.
How do you decide between BFS and DFS - and how do you recognise a graph problem that nobody described as a graph?
Choose BFS when the question asks for the fewest steps in an unweighted graph or when you need results in distance order; choose DFS when you are asking a structural question such as connectivity, cycles or topological order, or when the graph is deep and narrow.
Find the cheapest route between two nodes in a weighted directed graph. Then tell me what breaks if one edge has a negative weight.
Dijkstra fails with negative edges because it finalises the current cheapest node under the assumption that no later edge can reduce it. Use Bellman-Ford when negative edges are possible, and reject graphs with negative cycles. It also connects shortest paths to the point an interviewer is testing.
You are given a set of tasks and their prerequisites. Produce a valid execution order, or report that none exists.
Topological sort produces an order only for a directed acyclic graph. Kahn's algorithm removes zero-in-degree nodes and detects a cycle when fewer than all nodes are emitted; DFS detects a cycle with a back edge into the active stack. Use this GRAPHS answer to show the decision, trade-off, and evidence rather than a memorised definition.