Interviewers expect you to turn a problem into nodes and edges, choose an adjacency list unless the graph is dense, and say whether edges are directed or weighted. With V nodes and E edges, a list takes O(V + E) space and a matrix O(V²), and a full traversal costs O(V + E) or O(V²).
Representations and what they cost
A graph is not a built-in type in Python, JavaScript or Java, so you choose how to store it, and that choice sets every cost below.
| Representation | Space | Check one edge | List a node's neighbors | Full traversal | Best for |
|---|---|---|---|---|---|
| Adjacency list | O(V + E) | O(degree) | O(degree) | O(V + E) | The default: most interview graphs are sparse. |
| Adjacency set | O(V + E) | O(1) on average | O(degree) | O(V + E) | Many checks of a single edge. |
| Adjacency matrix | O(V²) | O(1) | O(V) | O(V²) | Dense graphs, or small fixed V. |
| Edge list | O(E) | O(E) | O(E) | n/a until built | Input format, and sorting edges by weight. |
| Implicit, such as a grid | O(1) beyond the grid | O(1) | O(1) for 4 neighbors | O(r · c) | Grids, or states you compute as you go. |
When to reach for it
Graph problems rarely use the word graph. Listen for things connected to other things, then ask what the nodes and edges are. The kind of graph tells you which algorithm fits.
| If the problem has | It is a | Reach for |
|---|---|---|
| Mutual links: friends, roads both ways | Undirected graph | BFS or DFS, or union-find for connectivity |
| One-way links: follows, dependencies | Directed graph | BFS or DFS, following edges one way |
| An order to respect, with no cycles | Directed acyclic graph | Topological sort |
| Costs on links, none negative | Weighted graph | Dijkstra with a heap |
| Equal cost per step | Unweighted graph | BFS for the fewest steps |
| Moves between cells | Implicit graph | BFS or DFS over the grid, with no list built |
Turning a problem into nodes and edges
This step is what the interviewer is really testing. Most of the difficulty is gone once you can say what a node is and what an edge means, and saying it out loud lets them correct you before you write any code. Here are five problems that never mention a graph:
| The problem | A node is | An edge means | So it is |
|---|---|---|---|
| The order to deploy services that depend on each other | A service | This one must go before that one | A directed acyclic graph: topological sort |
| The fewest one-letter changes from one dictionary word to another | A word | The two differ by one letter | Unweighted: BFS for the fewest steps |
| Counting islands on a map of land and water | A land cell | The two cells touch | Implicit: a search from each unvisited cell |
| The cheapest route between two airports | An airport | A flight, with its price as the weight | Weighted: Dijkstra |
| Merging user accounts that share an email | An account | The two share an email | Undirected: union-find or a search |
The word example shows why this matters. You are not given the edges, and comparing every pair of words is expensive, so how you generate neighbors becomes part of the answer. Often the graph is defined by a rule, and you compute edges as you go instead of storing them.
How it looks in Python, JavaScript and Java
Almost every graph answer starts with the same few lines: turn the input into an adjacency list. Say whether it is directed before you write them, because that changes one line.
from collections import defaultdict
def build_graph(edges, directed=False):
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
if not directed:
graph[b].append(a)
return graph
def grid_neighbors(grid, r, c):
"""An implicit graph: no list is built, neighbors are computed."""
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]):
yield nr, ncJavaScript
function buildGraph(edges, directed = false) {
const graph = new Map();
const add = (from, to) => {
if (!graph.has(from)) graph.set(from, []);
graph.get(from).push(to);
};
for (const [a, b] of edges) {
add(a, b);
if (!directed) add(b, a);
}
return graph;
}Java
import java.util.*;
class Graphs {
static Map<Integer, List<Integer>> build(int[][] edges, boolean directed) {
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] e : edges) {
graph.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
if (!directed) graph.computeIfAbsent(e[1], k -> new ArrayList<>()).add(e[0]);
}
return graph;
}
}One detail catches people: with these builders, a node with no edges never appears as a key. If the input lists nodes separately, add them all first, and do not assume every node shows up in the map.
How to explain the choice out loud
I'll model each user as a node and each follow as a directed edge, stored in an adjacency list, because the graph is sparse: a user follows far fewer people than exist. That's O(V + E) space, where a matrix would need O(V squared). A traversal then visits each node and edge once, so it's O(V + E) time. If the question turned into a lot of "does this one edge exist" checks, I'd switch the lists to sets for average constant-time lookups.
Common mistakes
- Starting to code before saying what the nodes and edges are.
- Adding an undirected edge in one direction only.
- Forgetting nodes that have no edges, so they never appear in the adjacency list.
- Building a matrix for a sparse graph, which can use far more memory than the input.
- Leaving out the seen set, which loops forever on a graph with a cycle.
Where to go next
- Patterns: graph patterns has the traversals, topological sort and a worked trace, and union-find handles connectivity.
- Worked problems: Recalculate a Spreadsheet After a Cell Changes and Degrees of Separation Between Members.
- All the figures in one place: the Big O cheat sheet.
- Practice saying it: a coding mock interview.