Graphs and Graph Algorithms Interview Questions for Data Structures and Algorithms
25 Graphs and Graph Algorithms questions with answers for data structures and algorithms roles — 7 easy, 13 medium, 5 hard.
About Graphs and Graph Algorithms
Represent graphs with adjacency lists and matrices, then master BFS, DFS, connected components, cycle detection, bipartite checks and topological sorting. Learn shortest path algorithms such as Dijkstra, Bellman-Ford and Floyd-Warshall, minimum spanning trees with Kruskal and Prim, and Union-Find for fast connectivity queries.
Sheet progressStart practicing
3 QUESTIONS FREESign up to unlock the full question bank and track your progress.Unlock every question and answer, then continue practising company-wise and package-wise.
✓ 3 questions free • Unlock the rest in seconds
01
What are the ways to represent a graph and when would you use each?
An adjacency list stores, for each vertex, a list of neighbours, using O(V plus E) memory; it is best for sparse graphs such as road or social networks and makes iterating neighbours fast. An adjacency matrix uses a V by V grid, O(V squared) memory, with O(1) edge checks; it suits dense or small graphs and Floyd-Warshall. An edge list is a simple list of pairs, convenient for Kruskal's algorithm.
02
What is the difference between BFS and DFS, and when do you use each?
BFS explores level by level with a queue and finds shortest paths in unweighted graphs, such as minimum moves on a board. DFS goes as deep as possible with recursion or a stack and suits cycle detection, topological sorting, connected components, path existence and backtracking. Both run in O(V plus E). BFS can use more memory on wide graphs, while DFS can hit recursion limits on deep ones.
03
Explain directed, undirected, weighted graphs and DAGs.
In an undirected graph edges work both ways, like friendships. In a directed graph edges have direction, like follows or web links. A weighted graph attaches a cost to each edge, like distance or price, which matters for shortest path algorithms. A DAG is a directed acyclic graph with no cycles; it models dependencies such as course prerequisites or build steps and allows topological ordering and linear-time shortest paths.
04
A metro app must find the route with the fewest stations between two stops. Which algorithm would you use?
If every hop counts equally, the network is an unweighted graph and BFS from the source gives the minimum number of stations in O(V plus E). I would store a parent for each visited station to reconstruct the path. If the goal changes to minimum travel time with different segment durations or interchange penalties, I would switch to Dijkstra with those weights, adding interchange cost as edges between line nodes.
05
A satellite image is a grid of land and water cells. How do you count the islands?
Treat each land cell as a vertex connected to its four neighbours that are also land. Scan the grid; when you find unvisited land, increase the island count and run DFS or BFS to mark the whole connected island as visited. Each cell is visited once, so the time is O(rows times columns). Use BFS or an explicit stack for very large grids to avoid recursion limits, or Union-Find if cells arrive over time.
06
Count the number of islands in a grid of 1s and 0s.
// Java
static int numIslands(char[][] g) {
int count = 0;
for (int r = 0; r < g.length; r++)
for (int c = 0; c < g[0].length; c++)
if (g[r][c] == '1') { count++; sink(g, r, c); }
return count;
}
static void sink(char[][] g, int r, int c) {
if (r < 0 || c < 0 || r >= g.length || c >= g[0].length || g[r][c] != '1') return;
g[r][c] = '0'; // mark visited
sink(g, r + 1, c); sink(g, r - 1, c);
sink(g, r, c + 1); sink(g, r, c - 1);
}
// O(rows * cols) time
Situation: I am starting my career with a strong interest in solving algorithmic and system problems. Task: grow into an engineer others rely on. Action: in the first years I want to master the codebase, deliver features reliably and deepen my skills in data structures, system design and the domain. Result: in five years I see myself as a senior engineer owning important components, mentoring juniors and contributing to design decisions in this team.
08
How does Dijkstra's algorithm work and why does it fail with negative edge weights?
Dijkstra keeps a min-heap of tentative distances. It repeatedly pops the closest unvisited vertex, marks its distance final and relaxes its outgoing edges, giving O((V plus E) log V). It relies on the fact that once a vertex is popped, no shorter path can appear later. A negative edge breaks that assumption because a longer path could later become cheaper. For negative weights use Bellman-Ford.
A topological order lists the vertices of a DAG so every edge goes from earlier to later, such as an order to take courses. Kahn's algorithm computes in-degrees, pushes zero in-degree vertices into a queue and repeatedly removes them while decreasing neighbours' in-degrees; if not all vertices are output, a cycle exists. The DFS method adds a vertex to a list after visiting its descendants and reverses the list. Both are O(V plus E).
10
What is the Union-Find data structure and what optimisations make it fast?
Union-Find, or disjoint set union, tracks which elements belong to the same group with find, returning a representative, and union, merging two groups. Path compression makes every node on a find path point directly to the root, and union by rank or size attaches the smaller tree under the larger. Together they give nearly constant amortised time, the inverse Ackermann function. It is used in Kruskal and dynamic connectivity.
11
Compare Kruskal's and Prim's algorithms for minimum spanning trees.
Both find a minimum spanning tree, the cheapest set of edges connecting all vertices. Kruskal sorts all edges by weight and adds each edge if it joins two different components, checked with Union-Find, O(E log E); it suits sparse graphs given as edge lists. Prim grows the tree from a start vertex, always adding the cheapest edge leaving the tree using a min-heap, O(E log V), which suits dense graphs with adjacency lists.
12
What is a bipartite graph and how do you check for one?
A graph is bipartite if its vertices can be split into two groups so every edge connects vertices from different groups, which is equivalent to having no odd-length cycle. To check, colour vertices with BFS or DFS: give the start vertex colour 0, its neighbours colour 1 and so on; if any edge connects two vertices of the same colour, it is not bipartite. Run it on each component, O(V plus E).
13
A learning platform has courses with prerequisites. How do you find a valid order, and what if none exists?
Model courses as vertices with an edge from each prerequisite to the course that needs it, then run topological sort with Kahn's algorithm. Courses with no pending prerequisites enter a queue first, and taking one reduces the in-degree of dependent courses. If the output has fewer courses than the total, there is a cycle, so no valid order exists, and I would report the courses involved so the content team can fix them.
14
How would you generate friend suggestions as friends of friends in a social network?
Run a BFS limited to depth 2 from the user. For every friend, look at their friends, skip the user and existing friends, and count how many mutual friends each candidate has using a hash map. Rank candidates by mutual friend count and other signals. For users with thousands of friends this gets expensive, so production systems precompute suggestions offline in batch jobs and cache them.
15
A build system hangs because some services depend on each other in a loop. How would you detect and report the cycle?
Model services as a directed graph and run DFS with three colours. When DFS reaches a node that is still on the current stack, it has found a back edge, and walking the parent pointers from the current node back to that node gives the exact cycle to report, such as A to B to C to A. Running this check in CI before every build prevents the problem, and Kahn's algorithm can list all nodes involved.
16
Find the shortest path length from the top-left to the bottom-right of a grid where 1 is a wall.
from collections import deque
def shortest_path(grid):
R, C = len(grid), len(grid[0])
if grid[0][0] or grid[R-1][C-1]:
return -1
q = deque([(0, 0, 1)])
seen = {(0, 0)}
while q:
r, c, d = q.popleft()
if (r, c) == (R - 1, C - 1):
return d
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and not grid[nr][nc] and (nr, nc) not in seen:
seen.add((nr, nc))
q.append((nr, nc, d + 1))
return -1
# BFS: O(R * C)
17
Implement Dijkstra's algorithm with a priority queue.
from collections import deque
def topo_sort(n, edges):
adj = [[] for _ in range(n)]
indeg = [0] * n
for u, v in edges: # u must come before v
adj[u].append(v)
indeg[v] += 1
q = deque(i for i in range(n) if indeg[i] == 0)
order = []
while q:
u = q.popleft()
order.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order if len(order) == n else [] # empty means a cycle exists
19
Tell me about a time you worked with people from other teams to solve a complex problem.
Situation: delivery route suggestions in our app were slow and the data team blamed the backend while we blamed the data. Task: find the real issue. Action: I set up a joint session, we traced one slow request end to end and found the graph was rebuilt from raw tables on every call. I proposed caching the adjacency lists, and the data team added change notifications. Result: response time dropped from 3 seconds to 200 milliseconds.
20
How do you handle disagreement with a reviewer about your solution in a code review?
Situation: a reviewer wanted me to replace my BFS solution with a more complex bidirectional search. Task: reach the best decision for the code, not win the argument. Action: I asked about their concern, which was latency on large graphs, then shared measurements showing our graphs were small and the simpler code was faster to maintain, and agreed to add a benchmark that would alert us if size grew. Result: the reviewer approved and we documented the trade-off.
Bellman-Ford finds single-source shortest paths with negative weights by relaxing all edges V minus 1 times, O(V times E), and one more pass detects negative cycles. Floyd-Warshall finds shortest paths between all pairs using dynamic programming over intermediate vertices, O(V cubed) time and O(V squared) space, suitable for small dense graphs of a few hundred nodes. For all pairs on large sparse graphs, running Dijkstra from each vertex is faster.
22
How does cycle detection differ in directed and undirected graphs?
In an undirected graph, DFS finds a cycle when it reaches an already visited vertex that is not the parent of the current vertex; Union-Find also works by checking whether an edge joins vertices already in the same set. In a directed graph you need three states, unvisited, in the current recursion stack and finished, and a cycle exists when DFS reaches a vertex still on the stack. Kahn's algorithm also detects directed cycles.
23
Find the cheapest flight from one city to another using at most K stops. Why does plain Dijkstra not work directly?
Plain Dijkstra finalises the cheapest path to a city, but that path may use too many stops, while a costlier path with fewer stops could still lead to a valid answer. One fix is Bellman-Ford limited to K plus 1 rounds, copying distances each round, O(K times E). Another is Dijkstra on states of city and stops used, or a BFS by levels that tracks cost, pruning states that are worse in both cost and stops.
24
A network has 10 million devices and connections are added continuously. You must answer whether two devices are connected in real time. How?
Running BFS for every query is too slow. Since connections are only added, Union-Find is ideal: each new link is a union, and each query compares find results, both nearly O(1) amortised with path compression and union by size. Memory is two integer arrays of 10 million entries, about 80 MB. If links can also be removed, the problem becomes much harder and needs offline processing or specialised dynamic connectivity structures.
25
Implement Union-Find with path compression and union by size.
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
# Nearly O(1) amortised per operation
Frequently asked questions
How important is Graphs and Graph Algorithms in Data Structures and Algorithms interviews?
Represent graphs with adjacency lists and matrices, then master BFS, DFS, connected components, cycle detection, bipartite checks and topological sorting. Learn shortest path algorithms such as Dijkstra, Bellman-Ford and Floyd-Warshall, minimum spanning trees with Kruskal and Prim, and Union-Find for fast connectivity queries.
How should I use the Graphs and Graph Algorithms sheet?
Go top to bottom — easy to hard. Answer before opening each answer, tick what you solved and save misses to Last-Minute Revision.