Mock 4 — Graphs (60 min)

Download and complete the starter notebook

Use the Download starter notebook button on this lesson. Open the .ipynb in JupyterLab, Jupyter Notebook, or another compatible Python 3 environment. Work in a saved copy, complete the TODOs and reflection cells, run the public checks, add the requested tests, then upload that completed .ipynb to this lesson. Do not submit a blank starter. The notebook intentionally contains no answer key or private reviewer rubric.

Instructions

You have 60 minutes. Complete the notebook implementations and explain why each problem uses its chosen traversal or algorithm. State time and space in terms of vertices/edges or grid cells. Iterative traversal is recommended for unbounded input depth; if using recursion, state an input limit or recursion-safety assumption.

Problem 1 — Number of Islands (Medium, about 12 minutes)

Implement num_islands(grid) for a rectangular grid of '1' land and '0' water. Islands use four-directional adjacency. An empty grid or zero-width grid returns 0. Ragged rows are invalid input. You may mutate the grid to mark visited cells; also-valid non-mutating solutions are accepted.

Problem 2 — Course Schedule (Medium, about 15 minutes)

Implement can_finish(num_courses, prerequisites). Course labels are 0..num_courses-1; [a, b] means b must precede a. Return whether all courses can be completed. Zero courses is finishable. Duplicate prerequisite pairs are allowed and must not create a false cycle; a self-loop makes completion impossible.

Problem 3 — Shortest Path in a Binary Matrix (Medium, about 15 minutes)

Implement shortest_path(grid) for a rectangular binary grid. Start at the top-left and end at the bottom-right; move in any of the eight neighboring directions through cells containing 0. Return the number of cells on the shortest path, including both endpoints, or -1 if no path exists. Empty/zero-width or ragged grids return -1. A one-cell open grid returns 1; a blocked endpoint returns -1.

Problem 4 — Network Delay Time (Medium, about 18 minutes)

Implement network_delay_time(times, n, k). Nodes are labeled 1..n, n >= 1, and k is a valid node. Each directed edge (u, v, w) has nonnegative integer weight w; duplicate edges and zero-weight edges are allowed. Return the greatest shortest-path distance from k if all nodes are reachable, otherwise -1. n=1 with no edges returns 0.

Submit the completed notebook

• Download this lesson's starter Jupyter notebook, complete the requested functions, and upload the saved .ipynb file here.
• Keep your implementation, added tests, complexity reasoning, and interview reflection in the notebook. No separate source file or NOTES.md is required.
• Do not upload the untouched starter. Public checks are examples, not a complete test suite; add the edge cases requested in the notebook.
• The downloadable notebook contains no reference solutions or reviewer rubric. Notebook outputs are not used as proof of correctness; the reviewer checks your submitted source and written reasoning.