Conway’s Game of life Coding Question

This is a famous coding question frequently asked in many companies.

Problem Statement

Assume there is a grid of cells with each cell being categorized as living or dead. The goal is to generate the next board state based on certain rules (as from wikipedia article and leetcode):

1. Under population: Any living cell with fewer than two neighbors dies.
2. Next Generation: Any living cell with two or three neighbors continue to live on.
3. Over population: Any living cell with more than three living neighbors dies
4. Reproduction: Any dead cell with exactly three living neighbors becomes alive.

Example:

Input: [ [1, 1, 0], [0, 1, 1], [1, 0, 1], [0, 1, 0] ] Output: [ [1, 1, 1], [0, 0, 1], [1, 0, 1], [0, 1, 0] ]

If example is not given, always start with examples as it is crucial step to ensure that you share the same understanding as the interviewer.

Clarification Questions:

1. One can ask is it ok to assume if board if two dimensional?
   Interviewer might say that for the simplicity let’s assume it is a two dimensional board. If time permits you can address the issue.
2. Does 1 indicate alive and 0 dead?
3. Is it ok to change the board in memory? If this is ok, space can be optimized to O(1)? If not, a copy of the board needs to be kept to evaluate the state of the cells.

In-place memory solution:

class GameOfLife: def nextState(self, board: List[List[int]]) -> None: """ Modify board in-place. Return nothing. """ rows = len(board) cols = len(board[0]) # Directions to get the neighbors on the board for the given cell. directions = [(-1,0), (0, -1), (1, 0), (0, 1), (-1, 1), (1, -1), (-1, -1), (1, 1)] # Make a copy of original board oriCopyBoard = [[board[row][col] for col in range(cols)] for row in range(rows)] # Iterating over each cell on the board for row in range(rows): for col in range(cols): # Counting living neighbors for each cell aliveNeighbors = 0 for direction in directions: rd = row + direction[0] cd = col + direction[1] # Check for boundary conditions. And check if neighbor is living if (rd < rows and rd >= 0) and (cd < cols and cd >= 0) and oriCopyBoard[rd][cd] == 1: aliveNeighbors += 1 # Rule 1 OR Rule 3 if aliveNeighbors < 2 or aliveNeighbors > 3: board[row][col] = 0 # Rule 4 if board[row][col] == 0 and aliveNeighbors == 3: board[row][col] = 1

Python3 solution to Game of Life problem

Time Complexity: O(M * N). The time taken is mostly to iterate over the board cell by cell.

Space Complexity: O(M * N). The space is required to keep a copy of the board. The changing value on cell for in-memory requires us to keep a copy of the original state of board.

Follow Up:

What if board is not finite?

This follow up question is more about the scalability aspect of the problem. So far in our solution, the assumption was board is 2D. Now, what happens if the size of board is too large or maybe infinite? Is the above solution still holds valid or something has to change in order to support scalability?

Let’s understand the limitations of the current solution if board is infinitely large:

1. Storing a huge board in memory might not be feasible. Given that we are talking about GBs or TBs of data file.
2. What if only a few living cells are present on the board? This is a case of extremely sparse matrix and look like storing it will waste a lot of space.
3. Iterating through the entire matrix might be difficult.

The problem of sparse matrix with a very few living cells can resolved by finding out the living cells and applying the above rules only to those cells. This will save the computation resources too. Plus, once the next state is computed, the value can be updated in memory.

However, another issue here is what happens if the board size is too large and cannot be stored in memory. And even if we can storing such a big matrix in memory can be expensive. We definitely need some other solution in this case. Maybe storing the matrix content in a file could be a potential solution. We can plan to store one row at a time. Let’s think more. To evaluate the current state of any cell, only 8 of its neighbors state is required to be known.

So, if matrix is stored in a file row by row, and for updating a cell in a row, we only need one row above and one row below. Therefore, at any point of time max of three rows are in memory. Keep reading a row at a time and discarding the older rows could be good strategy.

One can argue what if file is too large, then we can divide the data among different files and can modify the algorithm based to process multiple files with the same logic as discussed above.

Originally published at https://raghavnyati.ghost.io on December 9, 2020.