Scale Game of Life to huge matrices
Quick Overview
This question evaluates a candidate's ability to design space-efficient, I/O-aware algorithms and streaming or external-memory techniques for processing extremely large binary grids, with attention to neighbor counting and boundary handling in cellular automata.
You are given starter code for computing one step of a Game of Life–style cellular automaton on a binary grid, but the naive implementation loads the entire matrix into memory.
The input grid can be as large as 1,000,000 × 1,000,000, so it cannot fit in RAM.
Automaton rule
- Each cell is either 0 (dead) or 1 (alive).
- For each cell, count the 8 neighbors (up, down, left, right, diagonals).
-
Apply standard Game of Life rules:
- Alive cell survives if it has 2 or 3 alive neighbors; otherwise it dies.
- Dead cell becomes alive if it has exactly 3 alive neighbors.
I/O model
Assume the grid is stored on disk (e.g., one row at a time). You are provided helper functions similar to:
-
readRow(i) -> array<int>returns rowi(0/1 values) -
writeRow(i, row)writes the computed next-state rowi
Task
Modify/implement the update so that it can process the full grid without OOM, using limited memory (e.g., O(W) or O(3W) where W is the number of columns).
Be careful about:
- Boundary rows/columns (treat missing neighbors as 0)
- Ensuring correctness while streaming rows
Return/produce the next grid on disk.