Compute Plant Infection Stabilization
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an `m x n` grid of plants.
Cell types:
- `X`: infected plant
- `.`: healthy plant
- `I`: immune plant (used only in some variants)
Two cells are neighbors if they share an edge or a corner, so each cell has up to 8 neighbors. Time advances in discrete days, and updates are synchronous.
Base infection rule:
- On each day, every plant that is infected at the **start** of the day attempts to infect all infectable neighbors.
- Newly infected plants become active on the **next** day.
- A process is considered stable when no future state changes can occur.
- If the grid is already stable, return `0`.
Implement or design algorithms for the following related variants:
1. **Base spread**
The grid contains only `X` and `.`. Return the number of days required until no more plants can be infected.
2. **Immune plants**
Now the grid may also contain `I`, and immune plants can never be infected. Return the number of days required until the system becomes stable.
3. **Recovery after a fixed delay**
You are also given an integer `R`. Each infected plant remains infected for exactly `R` full days after it becomes infected, then recovers. In this variant, a recovered plant becomes inactive: it no longer infects other plants and cannot be infected again. Return the number of days until no further infection or recovery events can occur.
4. **Death triggered by local crowding**
This variant extends the previous one. In addition to recovery, you are given integers `K` and `D`. If an infected plant has at least `K` infected neighbors at the start of any day, and it has not already been scheduled to die, it is scheduled to die exactly `D` days later. A dead plant is removed permanently and can neither infect nor be infected. If a plant would both recover and die on the same day, death takes precedence. Return the number of days until no further infection, recovery, or death events can occur.
5. **Row or column burning intervention**
At the start of each day, before infection spreads, you may choose at most one entire row or one entire column and burn it. All plants in that row or column die immediately and are removed from the process. Design an algorithm that minimizes the total number of dead plants by the time the system becomes stable.
Your task is to handle these five subproblems under the rules above.
Quick Answer: This question evaluates a candidate's ability to model and simulate discrete-time state transitions on grids, reason about propagation dynamics and event scheduling (infection, recovery, death), and formulate constrained optimization for interventions.