Graph Representation Toolkit — Modeling Real Problems
Translate interviews into graph problems by choosing the right representation: adjacency lists, matrices, edge lists, and implicit neighbors.
Problem Statement
Before you can apply BFS, DFS, or Dijkstra, you have to model the input as a graph. Learn the trade-offs of common representations so you pick the right one quickly.
Why This Problem Matters
- Interviewers frequently hide graphs inside grids, word ladders, and scheduling problems.
- Choosing adjacency lists vs. matrices affects time and space complexity—showing that awareness is a differentiator.
- Good modeling prevents bugs: directed vs. undirected edges, weighted vs. unweighted, and implicit vs. explicit constructions.
Thought Process
Clarify direction and weights up front
Ask if edges are one-way or bidirectional, and whether costs exist. Your data structure must reflect those answers.
Pick adjacency list for sparse graphs
Most interview inputs are sparse; adjacency lists provide O(V + E) traversal and are memory efficient.
Use implicit neighbors when generation is cheaper than storage
Grids and word ladders let you compute neighbors on the fly, saving memory and setup time.
Step-by-Step Reasoning
- Identify the entities as vertices (cells, words, tasks).
- Define how vertices connect and whether the graph is directed or weighted.
- Choose a representation (adjacency list, matrix, implicit function).
- Implement helper functions to iterate neighbors cleanly.
Dry Run
Course schedule problem
Map each course to a vertex. For prerequisite pair (A, B) meaning A before B, add edge A → B in the adjacency list.
Word ladder
Rather than storing all edges, generate neighbors by swapping each character with letters a–z and checking dictionary membership.
Complexity Analysis
Time
O(V + E) to build adjacency lists
Space
O(V + E)
Why
Storing each edge twice when undirected doubles E, but remains linear. Implicit representations trade space for on-the-fly computation.
Annotated Solution
import java.util.*;
public class GraphBuilder {
public static Map<Integer, List<int[]>> buildAdjList(int n, int[][] edges, boolean directed) {
Map<Integer, List<int[]>> adj = new HashMap<>();
for (int i = 0; i < n; i += 1) {
adj.put(i, new ArrayList<>());
}
for (int[] edge : edges) {
int u = edge[0];
int v = edge[1];
int w = edge.length > 2 ? edge[2] : 1;
adj.get(u).add(new int[]{v, w});
if (!directed) {
adj.get(v).add(new int[]{u, w});
}
}
return adj;
}
}Adjacency lists store only existing edges. Including weights as part of each neighbor entry future-proofs the structure for algorithms like Dijkstra.
Common Pitfalls
- Forgetting to add the reverse edge in undirected problems results in missing connections.
- Using adjacency matrices unnecessarily for large sparse graphs wastes memory (O(V²)).
- Misreading weighted inputs and discarding costs limits you to BFS-only solutions.
Follow-Up Questions
- Show how to compress node ids when the input uses arbitrary strings.
- Discuss adjacency matrices for dense graphs where V is small but E is near V².
- Explain how to store graphs on disk or stream edges when memory is constrained.