Katkat
Back

Compute Plant Infection Stabilization

OpenAISoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to simulate state propagation across a grid over discrete time steps and determine the minimum number of interventions required to contain an infection.

Problem Statement

You are monitoring a grid of plants of size R x C. Each plant can be in one of three states: Healthy (0), Infected (1), or Dead (2).

  • An Infected plant remains infected for exactly K time steps, after which it dies.
  • Once a plant is Dead, it stays Dead forever.
  • At each time step, every Infected plant spreads the infection to all its immediate neighbors (up, down, left, right) that are Healthy. Newly infected plants begin their K time-step countdown at the next time step.

Your task is to write a function min_interventions(grid, K) that returns the minimum number of plants you must remove (change to state 2, 'Dead') at t=0 to ensure that no plants are Infected or Healthy after T time steps. If it is impossible to stabilize the entire grid, return -1.

Function Signature

def min_interventions(grid, K):
    # grid: List[List[int]]
    # K: int
    pass

Examples

Example 1: Input: grid = [[0, 1], [0, 0]], K = 1 Output: 1 Explanation: Removing the infected plant at (0, 1) prevents it from spreading to its neighbors.

Constraints

  • 1 <= R, C <= 20
  • 1 <= K <= 10
  • The grid contains only 0s and 1s initially.

Edge Cases

  • The grid is already empty or fully dead.
  • The infection is already at a stage where it cannot be contained.
  • K is larger than the dimensions of the grid.

Hints

Hint 1

Consider representing the state of the grid as a bitmask if the grid dimensions are small enough, or use a simulation approach to determine the reach of an infection.

Hint 2

Since you need to choose a set of plants to remove, consider a backtracking or BFS approach to explore the state space of possible 'removal' configurations.

Hint 3

Because the number of plants is small, you can iterate through all combinations of removals and verify the outcome via simulation.

Follow-up questions

  • How would your approach change if you could only remove one plant per time step rather than all at once at the start?
  • If the grid dimensions were significantly larger (e.g., 1000x1000), how would you optimize the search for the minimum number of interventions?
  • What if the infection probability was not 100% but followed a distribution based on distance?