Note: This is a five-stage progressive interview exercise. Each stage increases the complexity and extends the preceding rules. You have 60 minutes for all five stages.
You receive an grid describing a population. A cell contains 0 when its person is healthy and 1 when that person is infected.
The infection follows this rule:
N of its neighbors are infected.Only the four orthogonally adjacent cells—above, below, left, and right—are neighbors; diagonal cells are excluded.
Unless the interviewer specifies another range, assume 1 <= N <= 4. With four-directional adjacency, a value of N > 4 means that no healthy cell can become infected.
For the initial stage, determine the number of time steps required for every cell to become infected. Return -1 when complete infection cannot occur. The later stages retain the threshold rule while modifying the state transitions or the objective.
This is related in spirit to cellular grid simulations such as Game of Life, but the states here model infection dynamics rather than birth and death.
In this version, N is part of the problem from the beginning. A healthy cell is eligible to become infected only when the beginning-of-step snapshot contains at least N infected orthogonal neighbors.
Given an grid and a threshold N, simulate the spread and return the number of steps needed to infect the entire grid.
Every cell is evaluated against the state from the start of the step. Consequently, all changes for one step occur simultaneously.
def time_to_full_infection(grid: list[list[int]], N: int) -> int:
"""
Args:
grid: An n×m grid where 0 = healthy and 1 = infected
N: Minimum number of infected neighbors required for a healthy cell to become infected
Returns:
The number of time steps until all cells are infected,
or -1 if not all cells will be infected.
"""
pass
Example 1:
Input:
grid = [
[0, 0, 0],
[0, 1, 0],
[0, 0, 0]
]
N = 1
Output: 2
Explanation:
grid = [[0,0, 0], [0, 1, 0], [0, 0, 0]] N = 1
2
Start: a 3×3 grid with a single infected cell (1) at the center. All other cells are healthy (0).
The center first infects its orthogonal neighbors, and those newly infected cells reach the corners on the following step.
Example 2:
Input:
grid = [
[1, 1],
[1, 0]
]
N = 2
Output: 1
Explanation:
The only healthy cell has two infected orthogonal neighbors at the initial snapshot, so it changes on step one.
Example 3:
Input:
grid = [
[1, 0, 0],
[0, 0, 0],
[0, 0, 1]
]
N = 1
Output: 2
Explanation:
The two initial infection sources expand simultaneously, covering the grid after two waves.
Example 4:
Input:
grid = [
[0, 0, 0],
[0, 0, 0],
[0, 0, 0]
]
N = 1
Output: -1
Explanation:
Without an initial infected cell, no healthy cell can satisfy the threshold.
Example 5:
Input:
grid = [
[1, 1, 1],
[1, 1, 1],
[1, 1, 1]
]
N = 2
Output: 0
Explanation:
No simulation step is needed when the grid begins fully infected.
Extend Level 1 by allowing certain cells to be immune, represented by 2. Such cells are permanently resistant: they cannot become infected and they do not transmit infection.
How does this change your solution?
0.-1.def time_to_full_infection_with_immunity(grid: List[List[int]], N: int) -> int:
"""
Grid values:
- 0: Healthy
- 1: Infected
- 2: Immune (cannot be infected, does not spread)
"""
Example 1:
Input:
grid = [
[1, 0],
[0, 0]
]
N = 1
Output: 2
The infection reaches one adjacent healthy cell on step one and the final cell on step two.
Example 2:
Input:
grid = [
[2, 2, 2],
[2, 0, 2],
[2, 2, 1]
]
N = 1
Output: -1
The healthy center has no infected orthogonal neighbor because all of its adjacent cells are immune.
After remaining infected for D days, a cell becomes immune. An immune cell cannot transmit infection and cannot be infected again. Cells that were initially immune (2) remain permanently immune and continue to act as blockers.
Assume D >= 1.
The prior threshold rule remains in force: a healthy cell changes state only when the start-of-day snapshot contains at least N active infected neighbors.
Eventually, the grid reaches a stable condition in which every cell is either healthy or immune and no active infection remains.
Question: How many days pass before this stable condition is reached?
N neighbors are infected.D) → Immune.D still counts as infected during that day, and it becomes immune at the day's end.def time_to_stable_state(grid: List[List[int]], N: int, D: int) -> int:
"""
Grid values:
- 0: Healthy
- 1: Initially infected (day 0)
- 2: Initially immune (cannot be infected, does not spread)
N: Minimum number of infected neighbors required for a healthy cell to become infected
D: Days until infected becomes immune
Returns: Days until stable state (no active infections)
"""
Example 1:
Input:
grid = [
[1, 0]
]
N = 1
D = 1
Output: 2
The initial cell infects its neighbor on day one and becomes immune at that day's end; the newly infected neighbor becomes immune at the end of day two.
Example 2:
Input:
grid = [
[1, 0]
]
N = 2
D = 1
Output: 1
The healthy cell never reaches the threshold, while the initial infection recovers after one day.
Continue from Level 3 and add death. When an infected cell has been infected for D days, it dies instead of becoming immune if it has at least K infected neighbors at the moment of transition.
A dead cell is permanently removed: it cannot spread infection and cannot be infected again. Dead cells are different from immune cells.
Cells initially marked immune (2) remain immune forever and continue blocking transmission.
The threshold N still governs infection before the day's state changes are applied. Only active infected cells count when evaluating either the infection threshold N or the death threshold K.
You are given K as the death threshold. At the transition point:
The supplied statement ends while continuing the Level 4 daily-update specification.
grid = [[0,0, 0], [0, 1, 0], [0, 0, 0]] N = 1
2
Start: a 3×3 grid with a single infected cell (1) at the center. All other cells are healthy (0).