Mock 4 — Graphs (60 min)

# Mock 4 — Graphs ## The brief Four graph problems, 60 minutes. Tests pattern recognition: when to BFS, when to DFS, when to topo sort, when to Dijkstra. ## Problem 1 — Number of Islands (Medium, ~12 min) Given a 2D grid of '1's (land) and '0's (water), count the number of islands. Islands are connected by 4-directional adjacency. ### Solution ```python def num_islands(grid): if not grid: return 0 rows, cols = len(grid), len(grid[0]) count = 0 def dfs(r, c): if r = rows or c = cols or grid[r][c] != '1': return grid[r][c] = '0' # mark visited for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: dfs(r + dr, c + dc) for r in range(rows): for c in range(cols): if grid[r][c] == '1': dfs(r, c) count += 1 return count ``` Grid as graph; DFS from each unvisited cell counts a component. ## Problem 2 — Course Schedule (Medium, ~15 min) `numCourses` courses (0 to numCourses-1). Prerequisites are pairs `[a, b]` meaning to take a, you must first take b. Return True if you can finish all courses. This is cycle detection in a directed graph. ### Solution (Kahn's algorithm) ```python from collections import defaultdict, deque def can_finish(num_courses, prerequisites): graph = defaultdict(list) in_degree = [0] * num_courses for a, b in prerequisites: graph[b].append(a) in_degree[a] += 1 q = deque(i for i in range(num_courses) if in_degree[i] == 0) completed = 0 while q: u = q.popleft() completed += 1 for v in graph[u]: in_degree[v] -= 1 if in_degree[v] == 0: q.append(v) return completed == num_courses ``` Kahn's algorithm: if you can topo-sort, no cycle. Otherwise, cycle exists. ## Problem 3 — Shortest Path in Binary Matrix (Medium, ~15 min) Given an N×N binary matrix, find the shortest path from top-left to bottom-right through 0-valued cells, 8-directional movement. Return -1 if impossible. This is BFS for shortest path on unweighted graph. ### Solution ```python from collections import deque def shortest_path(grid): n = len(grid) if grid[0][0] != 0 or grid[n-1][n-1] != 0: return -1 DIRS = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)] q = deque([(0, 0, 1)]) # (row, col, path_length) visited = {(0, 0)} while q: r, c, d = q.popleft() if r == n-1 and c == n-1: return d for dr, dc in DIRS: nr, nc = r + dr, c + dc if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0 and (nr, nc) not in visited: visited.add((nr, nc)) q.append((nr, nc, d + 1)) return -1 ``` BFS guarantees shortest path in unweighted graphs. ## Problem 4 — Network Delay Time (Medium, ~18 min) `n` network nodes, signals from node `k`. `times[i] = (u, v, w)`: edge from u to v with delay w. Return min time for signal to reach all nodes, -1 if impossible. This is single-source shortest path on a weighted graph: Dijkstra. ### Solution ```python import heapq from collections import defaultdict def network_delay_time(times, n, k): graph = defaultdict(list) for u, v, w in times: graph[u].append((v, w)) dist = {k: 0} pq = [(0, k)] while pq: d, u = heapq.heappop(pq) if d > dist.get(u, float('inf')): continue for v, w in graph[u]: new_d = d + w if new_d < dist.get(v, float('inf')): dist[v] = new_d heapq.heappush(pq, (new_d, v)) if len(dist) < n: return -1 return max(dist.values()) ``` Standard Dijkstra. Return max because we need time for ALL nodes to receive. ## Self-rubric - [ ] All 4 solved correctly - [ ] Identified correct algorithm BEFORE coding: BFS, DFS, topo, Dijkstra - [ ] Number of Islands: O(R·C) time and space - [ ] Course Schedule: explained cycle detection via Kahn's - [ ] Shortest path: BFS (not DFS!) - [ ] Network Delay: Dijkstra with proper PQ usage ## Deliverables - Solutions. - A short decision-tree note for yourself: "Given graph problem, ask: weighted? cyclic? shortest path? all reachable? — pick algorithm accordingly."