Katkat
Back

Simulate Plant Infection With Controlled Burning

OpenAIMachine Learning Engineer · Onsite
HardMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

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.

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.