How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Simulate In-Place Cellular State Updates

Quick Overview

This question evaluates a candidate's ability to implement grid-based state transitions and manage in-place updates with strict space constraints, assessing skills in matrix manipulation, neighbor traversal, and correctness under simultaneous update rules.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given an `m x n` grid of cells, where each cell is either `0` for inactive or `1` for active. All cells update simultaneously according to these rules: - An active cell with fewer than two active neighbors becomes inactive. - An active cell with two or three active neighbors remains active. - An active cell with more than three active neighbors becomes inactive. - An inactive cell with exactly three active neighbors becomes active. Each cell has up to eight neighbors: horizontal, vertical, and diagonal adjacent cells. Implement a function that modifies the input grid in place to represent the next state of the grid. You may not allocate another `m x n` grid, but you may use constant extra space besides loop variables.

Quick Answer: This question evaluates a candidate's ability to implement grid-based state transitions and manage in-place updates with strict space constraints, assessing skills in matrix manipulation, neighbor traversal, and correctness under simultaneous update rules.

You are given an m x n grid of cells where each cell is either 0 (inactive) or 1 (active). Every cell updates simultaneously using these rules: - An active cell with fewer than two active neighbors becomes inactive. - An active cell with two or three active neighbors remains active. - An active cell with more than three active neighbors becomes inactive. - An inactive cell with exactly three active neighbors becomes active. Each cell has up to eight neighbors: horizontal, vertical, and diagonal adjacent cells. Modify the input grid in place so it represents the next state. You may not allocate another m x n grid, but you may use constant extra space. For testing, return the modified grid after updating it in place.

Constraints

0 <= m, n <= 200
grid[i][j] is either 0 or 1
All rows have the same length
Use O(1) extra space excluding the input grid itself

Examples

Input: ([[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]],)

Expected Output: [[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 1, 0]]

Explanation: This is the standard example. All cells update simultaneously based on the original grid, producing the shown next state.

Input: ([[1, 1], [1, 1]],)

Expected Output: [[1, 1], [1, 1]]

Explanation: Each active cell has exactly three active neighbors, so all four cells remain active.

Input: ([],)

Expected Output: []

Explanation: An empty grid has no cells to update, so it stays empty.

Input: ([[1]],)

Expected Output: [[0]]

Explanation: A single active cell has zero active neighbors, so it becomes inactive from underpopulation.

Hints

Try encoding state transitions directly inside the grid so you do not lose the original value of each cell during the first pass.
When counting neighbors, remember that a cell marked as 'alive -> dead' should still count as originally alive, while a cell marked as 'dead -> alive' should not.

Quick Overview