Design plant-infection algorithms
Company: OpenAI
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Consider an `m x n` grid where each cell contains one plant. Some plants are initially infected and all other plants are healthy. Time advances in whole days. On each day, every infected and still-alive plant infects its four orthogonally adjacent healthy plants. Newly infected plants become infectious on the next day.
Answer both algorithmic variants:
1. **Death-after-exposure rule**: After a plant becomes infected, if on any day it has at least `K` infected orthogonal neighbors, it is scheduled to die exactly `D` days later. Once dead, it is removed from the grid and stops infecting others. Compute how many plants eventually die.
2. **Firebreak optimization**: You may optionally, at the start of one chosen day, burn exactly one entire row or one entire column. Burned plants are removed immediately, count as dead, and cannot infect or be infected afterward. Design an algorithm to choose the day and the row or column so that the total number of dead plants is minimized.
Discuss the data structures, correctness, and time complexity of your approach.
Quick Answer: This question evaluates algorithm design and simulation skills for a data scientist role, focusing on modeling contagion spread on an m-by-n grid, event-driven scheduling of state changes, and constrained optimization of interventions.
Part 1: Count plants that eventually die
You are given a rectangular grid of 0s and 1s. A 1 means the plant is initially infected, and a 0 means it is healthy. Day 0 starts with all initially infected plants already infectious. Each day follows this exact order: (1) every alive infectious plant infects each orthogonally adjacent healthy plant; plants infected today become infectious on the next day, (2) after all infections of that day, every alive infected plant that has not already been scheduled checks how many orthogonally adjacent alive infected neighbors it has; if that count is at least K, it is scheduled to die at the end of day current_day + D, and (3) all plants scheduled for the current day die and are removed from the grid. Dead plants no longer infect others and no longer count as infected neighbors. Each plant can be scheduled at most once, on the first day the condition becomes true. Return the number of plants that eventually die. A strong solution should process infection and death as chronological events instead of rescanning the whole grid every day.
Constraints
- 0 <= m, n <= 200
- m * n <= 40000
- grid is rectangular
- 1 <= K <= 4
- 0 <= D <= 10^9
Examples
Input: ([], 2, 1)
Expected Output:
Explanation: Empty grid.
Input: ([[1]], 1, 2)
Expected Output:
Explanation: The single infected plant never has any infected neighbor, so it is never scheduled to die.
Input: ([[1, 1]], 1, 0)
Expected Output:
Explanation: Both plants already have 1 infected neighbor on day 0, so both are scheduled and die at the end of day 0.
Input: ([[1, 0], [0, 0]], 2, 1)
Expected Output:
Explanation: The infection reaches all four cells. Each cell reaches 2 infected neighbors on some day and is eventually scheduled to die.
Input: ([[1, 0, 0]], 1, 0)
Expected Output:
Explanation: On day 0 the middle plant is infected. Both infected plants then meet the threshold and die that same evening, so the last plant stays healthy forever.
Hints
- A plant's infected-neighbor count only increases when a new adjacent plant becomes infected. It never increases because of a death.
- You do not need to rescan all alive infected plants every day. Track only future infection events, future death events, and local neighbor-count updates.
Part 2: Minimize dead plants with one firebreak
In this variant, ignore the death-after-exposure rule from Part 1. The grid again contains 0s and 1s, where 1 means initially infected and 0 means healthy. Day 0 starts with all initially infected plants already infectious. Each day, every infected plant infects its four orthogonally adjacent healthy neighbors, and plants infected today become infectious on the next day. Any plant that is ever infected is counted as dead by the end. At the start of one chosen day, before that day's infections, you may optionally burn exactly one entire row or exactly one entire column. Burned plants die immediately, are removed permanently, and can neither infect nor be infected afterward. Return the minimum possible total number of dead plants. A strong solution should justify why the optimal burn, if any, can be assumed to happen on day 0 and then evaluate all rows and columns efficiently.
Constraints
- 0 <= m, n <= 2000
- m * n <= 200000
- grid is rectangular
- each grid value is either 0 or 1
Examples
Input: ([],)
Expected Output:
Explanation: Empty grid.
Input: ([[0, 0, 0], [0, 1, 0], [0, 0, 0]],)
Expected Output:
Explanation: Burn the middle row or the middle column on day 0. That removes the only infected plant and saves the other 6 plants.
Input: ([[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]],)
Expected Output:
Explanation: Burn column 0 on day 0. Only that column dies, including the infected corner plant.
Input: ([[0, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 1, 0]],)
Expected Output:
Explanation: Burn column 1 or column 2 on day 0. One side then has no initial infection and survives completely, so 4 plants are saved.
Input: ([[1, 0], [0, 1]],)
Expected Output:
Explanation: A burn cannot help here; doing nothing or burning any row or column still leads to 4 dead plants total.
Hints
- Does waiting ever help? Burning later never reduces the number of already infected plants, and the burned line always costs the same number of cells.
- After removing one full row, the remaining plants split into a top rectangle and a bottom rectangle. After removing one full column, they split into a left rectangle and a right rectangle.