Simulate Plant Infection With Controlled Burning
Company: OpenAI
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
You are given an R by C grid of plants. Each plant is initially healthy, infected, recovered, or dead. A plant has up to four orthogonal neighbors. Dead plants never change state and do not count as infected.
Parameters:
- T and K are infection thresholds, with T <= K.
- D is a positive integer delay in days.
- The simulation runs for N days.
For every non-dead plant that is not already in a countdown:
- If it has at least K infected neighbors, it enters a death countdown and becomes dead after D full days.
- Else, if it has at least T but fewer than K infected neighbors, it enters a recovery countdown and becomes recovered after D full days.
- Plants in a countdown still count as infected until the countdown finishes.
All decisions for a day are based on a snapshot of the grid at the beginning of that day, and all state updates for that day are applied simultaneously.
Implement the simulator and answer the following extension: before the simulation starts on day 1, you may choose exactly one entire row or exactly one entire column to burn. Burned plants immediately become dead. Find the row or column choice that minimizes the number of dead plants after N days. Return the minimum dead count and the chosen burn action. If multiple actions tie, return any one of them.
Overview: This question evaluates a candidate's ability to implement discrete-time grid simulations with delayed state transitions, reason about simultaneous updates and neighborhood effects, and perform a limited combinatorial optimization (choosing one row or column) to minimize a global outcome.
Read the full OpenAI Machine Learning Engineer interview experience this question came from
Part 1: Simulate Plant Infection With Countdown-Based Recovery and Death
You are given a grid of plants represented by equal-length strings using these characters: 'H' = healthy, 'I' = infected, 'R' = recovered, 'D' = dead. Initially, the grid contains only these four visible states.
The simulation runs for N days. Each day uses the grid snapshot from the beginning of that day.
For every plant that is not dead and is not already in a countdown:
- If it has at least K infected orthogonal neighbors, it starts a death countdown.
- Else, if it has at least T infected orthogonal neighbors, it starts a recovery countdown.
A countdown starts with D remaining days. Newly started countdowns do not lose a day immediately. At the end of each day, all countdowns that were already active before that day decrease their remaining time by 1. When a countdown reaches 0, the plant becomes dead or recovered, depending on the countdown type.
While a plant is in either countdown, it still counts as infected for neighbor counting.
All decisions for a day are based only on the start-of-day snapshot, and all updates are applied simultaneously.
Return the final visible grid after N days. If a plant is still in a countdown at the end, return it as 'I' because it still counts as infected and has not finished changing yet.
Constraints
- 0 <= R, C <= 100
- All rows in grid have the same length
- 0 <= N <= 1000
- 1 <= D <= 1000
- 0 <= T <= K <= 4
- Each plant has up to 4 orthogonal neighbors
Examples
Input: (["H"], 1, 1, 1, 3)
Expected Output: ["H"]
Explanation: Single-cell edge case. It has no infected neighbors, so nothing changes.
Input: (["II", "IH"], 1, 2, 1, 2)
Expected Output: ["DR", "RD"]
Explanation: On day 1, the top-left infected plant and the bottom-right healthy plant start death countdowns, while the other two start recovery countdowns. On day 2, those countdowns finish.
Hints
- Track the visible state and the countdown information separately. A plant in a countdown is not the same as a plain 'I' plant internally.
- Do not update cells in place while counting neighbors for the current day. First compute all new countdown starts from the morning snapshot, then apply all changes together.
Part 2: Burn One Row or Column to Minimize Final Deaths
You are given the same plant model as in Part 1. Before day 1 begins, you must burn exactly one entire row or exactly one entire column. Every burned plant immediately becomes dead.
After that single burn action, run the N-day simulation with these rules:
- A non-dead plant that is not already in a countdown starts a death countdown if it has at least K infected orthogonal neighbors.
- Otherwise, if it has at least T infected orthogonal neighbors, it starts a recovery countdown.
- A countdown starts with D remaining days and newly started countdowns do not lose a day immediately.
- At the end of each day, countdowns that were already active before that day decrease by 1. When a countdown reaches 0, the plant becomes dead or recovered.
- Plants in a countdown still count as infected.
- Each day uses the start-of-day snapshot, and updates are simultaneous.
Return the minimum possible number of dead plants after N days, along with the chosen burn action.
For deterministic output, if multiple actions give the same minimum dead count, choose the earliest action in this order:
1. ('row', 0), ('row', 1), ..., ('row', R-1)
2. ('col', 0), ('col', 1), ..., ('col', C-1)
Use 0-based indexing.
Constraints
- 1 <= R, C <= 30
- All rows in grid have the same length
- 0 <= N <= 30
- 1 <= D <= 30
- 0 <= T <= K <= 4
- A brute-force check over all rows and columns is acceptable under these limits
Examples
Input: (["HIHH", "HIHH", "HHHH"], 1, 2, 1, 3)
Expected Output: (3, ('col', 1))
Explanation: Burning column 1 removes both initial infected plants for a cost of 3, and no further spread occurs. Any other action leads to at least 4 dead plants.
Input: (["HH", "II", "HH", "HH"], 1, 1, 1, 2)
Expected Output: (2, ('row', 1))
Explanation: Burning row 1 immediately removes both infection sources with only 2 dead plants. Any other burn allows the infection to cause more deaths.
Approach
Approach. This is a brute force over every legal burn action wrapped around a faithful day-by-day simulation. Under the limits (R,C,N <= 30) trying all R + C burns is cheap, so we simulate each and keep the best.
Outer search. We try burning each row 0..R-1 first, then each column 0..C-1. For each, we deep-copy grid, set that whole row/column to 'D', call simulate_dead_count, and update best_dead/best_action only on a strict dead < best_dead. Because rows are scanned before columns and ties never overwrite, this yields exactly the required deterministic tie-break (earliest ('row', i) then ('col', j)).
Simulation (simulate_dead_count). For each of N days, using the start-of-day snapshot so updates are simultaneous:
- For every non-dead plant ('H', 'I', 'R'), count orthogonal neighbors that are infected — i.e. in ('I','CD','CR'), since plants mid-countdown still count as infected.
- If count >= K, queue a death countdown 'CD'; else if count >= T, queue a recovery countdown 'CR'. These are deferred in to_start, not applied yet.
- Then decrement timers of countdowns that were already active before this day (state[r][c] in ('CD','CR')); when a timer hits 0 the cell resolves to 'D' or 'R'.
- Finally apply the queued to_start cells with a fresh timer D. Applying them after the decrement is what makes a newly started countdown skip losing a day immediately.
A cell already in 'CD'/'CR' is skipped by the neighbor scan (it isn't 'H'/'I'/'R'), so active countdowns never restart. After N days we count 'D' cells. The minimum over all burns is returned with its action.
Time complexity: O((R + C) * N * R * C)
Space complexity: O(R * C)
Hints
- Write a helper that simulates the process for a fixed grid, then try each possible row burn and each possible column burn.
- To implement the required tie-breaker, iterate through rows first, then columns, and only replace the best answer when you find a strictly smaller dead count.