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