How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Onsite rounds at OpenAI.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at OpenAI during technical interviews.

Simulate Plant Infection With Controlled Burning

Quick 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.

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.

Quick Answer: 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.

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.

Input: (["IHH"], 1, 2, 2, 2)

Expected Output: ["III"]

Explanation: With D = 2, newly infected countdown plants remain active long enough to affect later days. After 2 days, all three cells are still visibly infected.

Input: (["HI", "RD"], 1, 2, 1, 0)

Expected Output: ["HI", "RD"]

Explanation: Boundary case N = 0. No simulation steps are performed.

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.

Input: (["HHH", "HHH"], 1, 1, 1, 0)

Expected Output: (2, ('col', 0))

Explanation: No days are simulated, so the answer is just the cheapest required burn. A column costs 2 plants, while a row costs 3.

Input: (["I"], 1, 1, 1, 5)

Expected Output: (1, ('row', 0))

Explanation: Row 0 and column 0 both lead to 1 dead plant, so the deterministic tie-breaker chooses ('row', 0).

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.

Quick Overview