Why Graph Problems Dominate Technical Interviews
Graph algorithms are a staple of technical interviews at major tech companies. This is not arbitrary. Graphs model a wide range of real-world problems, and understanding graph algorithms demonstrates fundamental algorithmic thinking.
Key sources: "Introduction to Algorithms" (CLRS), "Cracking the Coding Interview" by Gayle Laakmann McDowell.
Why Graphs?
Graphs are a universal data structure. They model:
- Social networks: Users are nodes. Friendships are edges.
- Maps and navigation: Locations are nodes. Roads are edges.
- Web pages: Pages are nodes. Links are edges.
- Dependency management: Packages are nodes. Dependencies are edges.
- Network routing: Servers are nodes. Connections are edges.
- Recommendation systems: Users and items are nodes. Interactions are edges.
If you can solve graph problems, you can solve problems in any of these domains.
Graph Fundamentals
A graph is a collection of nodes (vertices) connected by edges.
- Directed graph: Edges have a direction (A → B is not the same as B → A)
- Undirected graph: Edges have no direction (A — B is the same as B — A)
- Weighted graph: Edges have weights (cost, distance, capacity)
- Cyclic vs acyclic: Whether the graph contains cycles
Representation:
```python graph = { 0: [1, 2], 1: [2], 2: [0, 3], 3: [3] }
graph = [ [0, 1, 1, 0], [0, 0, 1, 0], [1, 0, 0, 1], [0, 0, 0, 1] ] ```
The adjacency list is more space-efficient for sparse graphs. The adjacency matrix is simpler for dense graphs.
The Core Algorithms
Breadth-First Search (BFS)
Explores the graph level by level. Uses a queue. Finds the shortest path in unweighted graphs.
```python from collections import deque
def bfs(graph, start): visited = set() queue = deque([start]) visited.add(start)
while queue:
node = queue.popleft()
print(node) # Process node
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
```
Time complexity: O(V + E) where V is vertices and E is edges.
Use cases: Shortest path in unweighted graphs, web crawling, social network friend suggestions.
Depth-First Search (DFS)
Explores as far as possible along each branch before backtracking. Uses a stack (or recursion).
```python def dfs(graph, node, visited=None): if visited is None: visited = set()
visited.add(node)
print(node) # Process node
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
```
Time complexity: O(V + E).
Use cases: Topological sorting, detecting cycles, maze solving, finding connected components.
Dijkstra's Algorithm
Finds the shortest path in weighted graphs with non-negative weights.
```python import heapq
def dijkstra(graph, start): distances = {node: float('inf') for node in graph} distances[start] = 0 pq = [(0, start)]
while pq:
current_dist, current = heapq.heappop(pq)
if current_dist > distances[current]:
continue
for neighbor, weight in graph[current].items():
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
```
Time complexity: O((V + E) log V) with a binary heap.
Use cases: GPS navigation, network routing, any weighted shortest path problem.
Topological Sort
Orders nodes in a directed acyclic graph (DAG) such that for every edge (u → v), u comes before v.
```python def topological_sort(graph): visited = set() stack = []
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
stack.append(node) # Add to stack after processing all neighbors
for node in graph:
if node not in visited:
dfs(node)
return stack[::-1] # Reverse for topological order
```
Use cases: Build systems (Make, Bazel), course prerequisite ordering, dependency resolution.
Common Interview Patterns
1. Graph Traversal (BFS/DFS)
Problem: "Find if there is a path between two nodes."
BFS and DFS are the foundation. Choose BFS when you need the shortest path. Choose DFS when memory is limited and the graph is deep.
2. Cycle Detection
Problem: "Does this graph have a cycle?"
For undirected graphs: use DFS and check if a neighbor is visited and is not the parent. For directed graphs: use DFS with a recursion stack.
3. Connected Components
Problem: "How many islands are there in this grid?"
Treat the grid as a graph. Each cell is a node. Adjacent 1s are connected. Use BFS or DFS to find all connected components.
4. Shortest Path
Problem: "Find the minimum number of moves in a game."
Use BFS for unweighted graphs. Use Dijkstra for weighted graphs with non-negative weights. Use Bellman-Ford when negative weights exist.
5. Bipartite Graph Check
Problem: "Can this graph be colored with two colors such that adjacent nodes have different colors?"
Use BFS and assign alternating colors. If a conflict is found, the graph is not bipartite.
Why Interviewers Ask Graph Problems
Graph problems test several skills simultaneously:
- Problem modeling: Can you recognize that the problem is a graph?
- Algorithm selection: Which traversal or algorithm applies?
- Complexity analysis: Can you analyze time and space complexity?
- Edge cases: Do you handle empty graphs, disconnected graphs, cycles?
- Implementation: Can you write clean, correct code?
Key Takeaways
- Graphs are a universal data structure — social networks, maps, web pages, and dependencies are all graphs.
- BFS and DFS are the foundation. Master them before moving to Dijkstra or topological sort.
- The adjacency list is the most common representation for interview problems.
- Graph problems test modeling, algorithm selection, complexity analysis, and implementation.
- Practice by recognizing graph patterns: "connectivity" → BFS/DFS, "shortest path" → Dijkstra/BFS, "ordering" → topological sort.
Interview tip: When you see a problem about connections, relationships, networks, paths, or dependencies, think: "This is a graph problem."