Minimize deaths in spreading plant infection
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an `m x n` grid representing a garden:
- `0`: empty cell
- `1`: healthy plant
- `2`: infected plant
The garden evolves day by day in the following order:
1. At the start of the day, you may optionally perform one intervention: burn exactly one entire row or one entire column. Every plant in that line is removed immediately. Burned cells become empty forever.
2. Each infected plant spreads the infection to its orthogonally adjacent healthy neighbors.
3. After the spread, check each infected plant. If an infected plant has ever had at least `K` orthogonally adjacent infected neighbors at the end of a day, it becomes marked for death.
4. A marked plant dies exactly `D` days after the first day it was marked, and the cell becomes empty.
Assume that once a plant is marked, its death timer does not reset. Dead or burned cells do not spread infection, cannot be infected again, and are not counted as infected neighbors.
Answer both parts:
1. Given the initial grid, `K`, and `D`, compute how many plants eventually die because of the overcrowding rule.
2. You may use the burn intervention at most once, on any chosen day. Burned plants are not counted as deaths. Design an algorithm to choose the best day and the best row or column to burn so that the number of eventual deaths is minimized.
Quick Answer: This question evaluates a candidate's ability to model and simulate dynamic grid processes, reason about infection propagation and delayed state changes, and incorporate constrained intervention decisions.
Part 1: Count overcrowding deaths in an infected garden
You are given an `m x n` grid representing a garden:
- `0` = empty cell
- `1` = healthy plant
- `2` = infected plant
The garden evolves day by day with no burning in this part:
1. Every infected plant spreads infection to its orthogonally adjacent healthy neighbors.
2. After the spread, each infected plant is checked. If it has at least `K` orthogonally adjacent infected neighbors at the end of that day, it becomes marked for death.
3. A marked plant dies exactly `D` days after the first day it was marked, and its cell becomes empty.
Important rules:
- Once a plant is marked, its death timer never resets.
- A marked plant is still infected and still spreads infection until the day it dies.
- Dead plants become empty forever and cannot spread or be infected again.
- Newly infected plants can also be marked on the same day they were infected.
Return the total number of plants that eventually die because of the overcrowding rule.
Constraints
- `grid[i][j]` is one of `0`, `1`, or `2`
- `1 <= m, n <= 50`
- `0 <= K <= 4`
- `0 <= D <= 50`
Examples
Input: ([[2]], 1, 0)
Expected Output:
Explanation: A single infected plant has no infected neighbors, so it is never marked.
Input: ([[0, 1], [1, 0]], 1, 2)
Expected Output:
Explanation: There is no infected plant initially, so nothing ever changes.
Input: ([[2, 2], [2, 2]], 2, 1)
Expected Output:
Explanation: All four plants are infected from the start and each has 2 infected neighbors, so all are marked on day 0 and die on day 1.
Input: ([[0, 2, 0], [2, 2, 2], [0, 2, 0]], 4, 0)
Expected Output:
Explanation: Only the center plant has 4 infected neighbors, so it is marked and dies immediately.
Input: ([[2, 1, 2]], 2, 0)
Expected Output:
Explanation: On day 0 the middle plant gets infected by both sides, immediately has 2 infected neighbors, and dies the same day.
Hints
- Store the first day each infected plant becomes marked. Its timer should never restart.
- Simulate the daily order exactly: spread first, then mark, then remove plants whose timers expire.
Part 2: Choose one row or column to burn to minimize deaths
You are given an `m x n` garden grid:
- `0` = empty cell
- `1` = healthy plant
- `2` = infected plant
Each day would normally evolve as follows:
1. At the start of the day, you may optionally burn exactly one entire row or one entire column. Every plant in that line is removed immediately, and those cells become empty forever.
2. Every infected plant spreads infection to its orthogonally adjacent healthy neighbors.
3. After the spread, each infected plant with at least `K` orthogonally adjacent infected neighbors becomes marked for death.
4. A marked plant dies exactly `D` days after the first day it was marked.
Burned plants are not counted as deaths.
Your task is to choose the best single burn intervention, or decide not to burn at all, so that the number of eventual overcrowding deaths is minimized.
Return one optimal plan as:
`[min_deaths, best_day, best_type, best_index]`
Where:
- `min_deaths` is the minimum possible number of overcrowding deaths
- `best_day` is the day to burn, using `0`-based days
- `best_type` is `'row'`, `'col'`, or `'none'`
- `best_index` is the row/column index, or `-1` if no burn is used
Tie-breaking:
1. If not burning already achieves the minimum, return no burn.
2. Otherwise choose the smallest day.
3. Then prefer a row over a column.
4. Then choose the smallest index.
Constraints
- `grid[i][j]` is one of `0`, `1`, or `2`
- `1 <= m, n <= 20`
- `0 <= K <= 4`
- `0 <= D <= 50`
Examples
Input: ([[0, 1], [1, 0]], 1, 2)
Expected Output:
Explanation: There are no infected plants, so the minimum death count is already 0 without burning.
Input: ([[2]], 1, 0)
Expected Output:
Explanation: The single infected plant never becomes overcrowded, so burning is unnecessary.
Input: ([[2, 2], [2, 2]], 2, 1)
Expected Output:
Explanation: Without burning, all 4 plants die. Burning row 0 on day 0 leaves only two adjacent infected plants, which are not overcrowded.
Input: ([[2, 2, 2], [2, 2, 2], [2, 2, 2]], 3, 0)
Expected Output:
Explanation: Burning the middle row on day 0 splits the garden into two separate rows of 3 infected plants, and none of them has 3 infected neighbors.
Hints
- Compare burning the same line on day 0 versus burning it later. Since burned plants are not counted as deaths, does waiting ever help?
- Once you know which days matter, you only need to simulate the garden a small number of times: no burn, each row burn, and each column burn.