Game of Life

MediumMatrixin-place state encoding

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given an m x n grid board where each cell holds either 1 (a living cell) or 0 (a dead cell). The grid represents one snapshot of Conway's Game of Life. Every cell interacts with its eight neighbors (the cells touching it horizontally, vertically, or diagonally). The entire grid advances by exactly one step ("tick") according to four simultaneous rules: 1. A living cell with fewer than two living neighbors dies (as if from isolation). 2. A living cell with two or three living neighbors survives to the next step. 3. A living cell with more than three living neighbors dies (as if from overcrowding). 4. A dead cell with exactly three living neighbors becomes alive (as if by reproduction). Compute the next state and write it back into board. The key subtlety is that the transition happens **simultaneously** for all cells: every cell's fate is decided from the current snapshot, not from cells that have already been updated in this same tick. Return the updated board after applying one tick. **Follow-up:** Can you do this update in place using O(1) extra space, without allocating a second grid? This is what the "in-place state encoding" pattern targets — encode both the old and new value of a cell in a single integer so neighbors can still read the original state while you overwrite cells.

Examples

Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]
Each cell is recomputed from the original snapshot. For instance, the center cell at row 1, col 1 is dead but has exactly 3 living neighbors, so it becomes alive.
Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]
Each living cell has two or three living neighbors and survives, and the dead bottom-right cell has exactly 3 living neighbors so it comes alive.
Input: board = [[1,1,1],[1,1,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]
The four center-edge and middle cells have 5 or more living neighbors and die from overcrowding; the four corners each have 3 living neighbors and survive.

Constraints

  • `m == board.length`
  • `n == board[i].length`
  • `1 <= m, n <= 40`
  • `board[i][j]` is `0` or `1`

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.