Simulate Grid Infection
Company: OpenAI
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Implement a grid infection simulator.
Base problem:
- You are given a 2D grid.
- `X` means infected.
- `.` means healthy.
- Each day, every currently infected cell simultaneously infects all 8 neighbors that are still healthy.
- A cell infected on the current day cannot spread until the next day.
- Return the number of days until the system becomes stable, meaning no new cells are infected.
Required edge cases:
- Empty grid
- No initial infected cells
- Already fully infected grid
- Single row or single column
- Multiple infection sources
- `1 x 1` grid
Common follow-ups:
1. Add immune cells `I` that can never be infected and block spread.
2. Add recovery: an infected cell becomes immune after `D` days, and you must return the day when no active infected cells remain.
3. Add threshold infection: a healthy cell becomes infected only if at least `T` of its 8 neighbors were infected at the start of the day.
4. Add a countdown or death state, which requires careful synchronous state transitions.
The main skills tested are multi-source BFS, simulation with synchronous updates, boundary handling, and off-by-one correctness.
Quick Answer: This question evaluates skills in multi-source breadth-first search, synchronous simulation updates, boundary handling, and off-by-one correctness within coding and algorithms contexts focused on grid-based simulations.
You are given a rectangular grid representing plants in a garden. Each cell is one of:
- 'X': already infected plant
- '.': healthy plant
- 'I': immune cell
Every day, all currently infected cells spread infection to their 8 neighboring cells (up, down, left, right, and the 4 diagonals). A healthy cell becomes infected only if it is adjacent to an infected cell at the start of that day. Cells that become infected today do not spread until the next day. Immune cells never change and can never be infected.
Return [days, dead_plants], where:
- days is the number of days until the grid stops changing
- dead_plants is the number of originally healthy cells ('.') that eventually become infected
Important:
- If the grid is already stable at the beginning, return [0, 0]
- This is about stabilization, not about infecting every healthy cell
- Some healthy cells may remain forever healthy if immune cells cut them off from all infection sources
Constraints
- 0 <= number of rows, number of columns <= 200
- If the grid is non-empty, all rows have the same length
- Infection spreads in 8 directions
- Count only cells that start as '.' and later become infected as dead_plants
Examples
Input: ([],)
Expected Output: [0, 0]
Explanation: An empty grid has no cells and no changes.
Input: (['...', '.I.', '...'],)
Expected Output: [0, 0]
Explanation: There is no initial infection source, so the grid is stable from day 0.
Input: (['XX', 'XX'],)
Expected Output: [0, 0]
Explanation: All plants are already infected, so no new infection happens.
Input: (['...', '.X.', '...'],)
Expected Output: [1, 8]
Explanation: The center infected cell reaches all 8 surrounding healthy cells in one day.
Input: (['X..I.'],)
Expected Output: [2, 2]
Explanation: In a single row, infection moves right one step per day until the immune cell blocks further spread.
Input: (['X..', 'III', '...'],)
Expected Output: [2, 2]
Explanation: The middle immune row blocks the bottom row completely. Only the two healthy cells on the top row get infected.
Input: (['X.I', '...', 'I.X'],)
Expected Output: [1, 5]
Explanation: Two infection sources simultaneously infect all reachable healthy neighbors in one day.
Input: (['.'],)
Expected Output: [0, 0]
Explanation: A 1x1 healthy grid with no infection source never changes.
Hints
- Treat every initial 'X' cell as a starting point in a multi-source BFS.
- Store the day each cell gets infected so that newly infected cells only start spreading on the following day.