Katkat
Back

Scale Game of Life to huge matrices

Applied IntuitionSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to optimize grid-based simulations that exceed local memory capacity, focusing on sliding windows, buffer management, and efficient disk I/O.

Problem: External Memory Game of Life

Implement a function to compute the next state of Conway's Game of Life for a binary matrix of size N x N, where N is so large (e.g., 10^6) that the entire grid cannot fit into RAM.

The input grid is stored as a sequence of rows on disk. You must read the input from disk and write the output state for the next time step to a new file. Assume you have a limited buffer size M (where M < N).

Rules:

  1. Any live cell with fewer than two live neighbors dies (underpopulation).
  2. Any live cell with two or three live neighbors lives on.
  3. Any live cell with more than three live neighbors dies (overpopulation).
  4. Any dead cell with exactly three live neighbors becomes a live cell (reproduction).

Function Signature: def evolve_grid(input_path, output_path, N, buffer_size)

Constraints:

  • N: up to 1,000,000.
  • Disk access is expensive; minimize the number of passes over the file.
  • Cells outside the grid boundaries are assumed to be dead (0).

Example: If the grid is a 3x3 matrix: Input: [[0, 1, 0], [0, 1, 0], [0, 1, 0]] Output: [[0, 0, 0], [1, 1, 1], [0, 0, 0]]

Edge Cases:

  • Handling the first and last rows where neighbors only exist below/above.
  • Handling the first and last columns of each row.
  • Grid sizes where N is not a multiple of the buffer size.

Hints

Hint 1

To determine the state of a row `i`, you only need access to rows `i-1`, `i`, and `i+1` from the previous time step.

Hint 2

Maintain a rolling buffer of three rows in memory; as you process row `i`, discard row `i-2` and read row `i+1` from the file.

Hint 3

Represent the grid as a binary stream to minimize I/O overhead rather than storing integers.

Follow-up questions

  • How would your approach change if the grid were distributed across multiple machines in a cluster?
  • If the grid is extremely sparse (most cells are dead), how could you optimize the storage and simulation process?
  • How would you handle synchronization if multiple parallel processes are writing to different segments of the output file?