Practice Problems

Most graph problems are half solved the moment you decide what the vertices and edges are. The four problems below were written for this guide and mirror patterns that come up often in coding interviews. Try each one before reading the solution.

Problem 1. Warehouse robot

A warehouse map is given as a list of strings. S is the robot's start, E the target, # a shelf (blocked) and . an empty cell. The robot moves one cell up, down, left or right per step. Return the minimum number of steps to reach the target, or -1 if it cannot.

Approach: cells are vertices and adjacent open cells share an edge. Every move costs 1, so the distance at which BFS first reaches E is the answer.

from collections import deque

def min_steps(grid):
    rows, cols = len(grid), len(grid[0])
    start = next((r, c) for r in range(rows) for c in range(cols) if grid[r][c] == "S")
    dist = {start: 0}
    queue = deque([start])
    while queue:
        r, c = queue.popleft()
        if grid[r][c] == "E":
            return dist[(r, c)]
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and (nr, nc) not in dist:
                dist[(nr, nc)] = dist[(r, c)] + 1
                queue.append((nr, nc))
    return -1

print(min_steps(["S.#.", "..#E", "...."]))  # 6

The shelves force a detour through the bottom row, so the answer is 6 rather than the Manhattan distance of 4.

Problem 2. Server clusters

You have n servers and a list of cables (a, b). Servers linked directly or indirectly form one cluster. Return the number of clusters and the size of the largest one.

Approach: this is connected components. Start a traversal from every unvisited server and count how many servers it reaches. An explicit stack avoids the recursion limit.

def server_groups(n, cables):
    adj = [[] for _ in range(n)]
    for a, b in cables:
        adj[a].append(b)
        adj[b].append(a)
    seen = [False] * n
    groups, largest = 0, 0
    for s in range(n):
        if seen[s]:
            continue
        groups += 1
        seen[s] = True
        stack, size = [s], 0
        while stack:
            u = stack.pop()
            size += 1
            for v in adj[u]:
                if not seen[v]:
                    seen[v] = True
                    stack.append(v)
        largest = max(largest, size)
    return groups, largest

print(server_groups(7, [(0, 1), (1, 2), (3, 4)]))  # (4, 3)

Problem 3. Module build order

A dictionary maps each module to the modules that must be built before it. Return an order that builds everything; when several modules are ready at once, pick the alphabetically smallest. Return if there is a circular dependency.