PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates graph traversal and grid-based simulation skills, including modeling a 2D grid as a graph, propagation dynamics with obstacles, multi-source propagation, and analysis of time and space complexity.

  • medium
  • OpenAI
  • Coding & Algorithms
  • Machine Learning Engineer

Simulate Plant Infection Spread

Company: OpenAI

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given an `m x n` grid representing farmland: - `0` = empty cell - `1` = healthy plant - `2` = infected plant - `3` = obstacle Every minute, each infected plant spreads infection to its 4-directional neighboring healthy plants. Infection cannot pass through obstacles. Implement a function that returns the minimum number of minutes required to infect all reachable healthy plants. Return `-1` if at least one healthy plant can never be infected. Possible follow-ups: 1. Return the infection time for every plant. 2. Support multiple initially infected cells. 3. Explain the time and space complexity. 4. Modify the simulation if diagonal spread is allowed. 5. Discuss how you would process very large grids efficiently.

Quick Answer: This question evaluates graph traversal and grid-based simulation skills, including modeling a 2D grid as a graph, propagation dynamics with obstacles, multi-source propagation, and analysis of time and space complexity.

Part 1: Minimum Minutes to Infect All Plants

You are given an `m x n` farmland grid where `0` means empty cell, `1` means healthy plant, `2` means infected plant, and `3` means obstacle. Every minute, each infected plant spreads infection to its 4-directional neighboring healthy plants. Infection cannot enter obstacles or pass through them. Return the minimum number of minutes required to infect all healthy plants. If at least one healthy plant can never be infected, return `-1`.

Constraints

  • 0 <= m, n <= 200
  • Each cell is one of: 0 (empty), 1 (healthy), 2 (infected), 3 (obstacle)
  • Infection spreads only up, down, left, and right

Examples

Input: ([[2, 1, 1], [1, 1, 0], [0, 1, 1]],)

Expected Output: 4

Explanation: The infection reaches all healthy plants in 4 minutes.

Input: ([[2, 1, 1], [1, 3, 1], [0, 1, 1]],)

Expected Output: 5

Explanation: The obstacle forces the infection to take a longer route, but every healthy plant is still reachable.

Input: ([[2, 1, 1], [0, 3, 0], [1, 1, 1]],)

Expected Output: -1

Explanation: The bottom row is disconnected by empty cells and an obstacle, so those healthy plants can never be infected.

Input: ([[1, 1], [1, 1]],)

Expected Output: -1

Explanation: There is no initially infected plant to start the spread.

Input: ([],)

Expected Output: 0

Explanation: An empty grid requires no time.

Hints

  1. Treat all initially infected plants as starting points in the same BFS queue.
  2. Keep a count of healthy plants remaining; when one gets infected, decrement it.

Part 2: Infection Time for Every Plant

You are given an `m x n` farmland grid where `0` means empty cell, `1` means healthy plant, `2` means infected plant, and `3` means obstacle. Every minute, each infected plant spreads infection to its 4-directional neighboring healthy plants. Return a matrix of the same size where each plant cell stores the minute it becomes infected. Use `0` for plants that are already infected at the start, a positive integer for healthy plants that later become infected, `-1` for healthy plants that are never infected, and `None` for cells that are not plants (`0` or `3`).

Constraints

  • 0 <= m, n <= 200
  • Each cell is one of: 0, 1, 2, 3
  • Infection spreads in 4 directions only

Examples

Input: ([[2, 1, 1], [1, 1, 0], [0, 1, 1]],)

Expected Output: [[0, 1, 2], [1, 2, None], [None, 3, 4]]

Explanation: Each healthy plant is labeled with the minute it first becomes infected.

Input: ([[2, 1, 1], [1, 3, 1], [0, 1, 1]],)

Expected Output: [[0, 1, 2], [1, None, 3], [None, 5, 4]]

Explanation: The obstacle changes the infection path and therefore the infection times.

Input: ([[2, 1, 1], [0, 3, 0], [1, 1, 1]],)

Expected Output: [[0, 1, 2], [None, None, None], [-1, -1, -1]]

Explanation: The bottom row plants are unreachable, so they stay `-1`.

Input: ([[2, 1, 2], [1, 3, 1]],)

Expected Output: [[0, 1, 0], [1, None, 1]]

Explanation: With multiple initial infected plants, BFS starts from all of them at minute 0.

Input: ([],)

Expected Output: []

Explanation: An empty grid returns an empty result.

Hints

  1. Run multi-source BFS starting from all initially infected cells.
  2. Initialize healthy plants with `-1` and overwrite that value when they are first reached.

Part 3: Measure BFS Work and Peak Frontier

You are given the same farmland grid. Simulate the standard 4-directional infection process using multi-source BFS, but instead of returning the finishing time, return three measurements that help explain the algorithm's time and space behavior. Return a tuple `(processed, inspected_neighbors, max_frontier)` where: - `processed` is the number of plant cells that are ever dequeued and processed by BFS. - `inspected_neighbors` is the number of in-bounds neighboring cells examined while processing those dequeued cells. - `max_frontier` is the largest number of infected cells waiting in the queue at the start of any minute. Count only in-bounds neighbors toward `inspected_neighbors`.

Constraints

  • 0 <= m, n <= 200
  • Each cell is one of: 0, 1, 2, 3
  • Use 4-directional spread

Examples

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

Expected Output: (4, 8, 2)

Explanation: All 4 plant cells are processed, each processed cell contributes its in-bounds neighbor count, and the largest minute frontier has size 2.

Input: ([[2, 1, 0], [3, 1, 1]],)

Expected Output: (4, 10, 1)

Explanation: The infection moves along a single path, so the peak frontier size is 1.

Input: ([[2, 1, 2], [1, 3, 1]],)

Expected Output: (5, 11, 3)

Explanation: Two starting sources create a larger frontier on the next minute.

Input: ([[1]],)

Expected Output: (0, 0, 0)

Explanation: No BFS starts because there is no initially infected plant.

Input: ([],)

Expected Output: (0, 0, 0)

Explanation: An empty grid has no work and no frontier.

Hints

  1. A level-order BFS naturally gives you the frontier size for each minute.
  2. When processing a cell, inspect each of the 4 directions and count only those that stay inside the grid.

Part 4: Minimum Minutes with Diagonal Infection

You are given an `m x n` farmland grid where `0` means empty cell, `1` means healthy plant, `2` means infected plant, and `3` means obstacle. Infection now spreads to all 8 neighboring cells each minute: up, down, left, right, and the 4 diagonals. Obstacles still cannot be infected. Return the minimum number of minutes required to infect all healthy plants, or `-1` if at least one healthy plant can never be infected. Diagonal spread does not require any special corner rule: if a diagonal neighbor is healthy, it can be infected directly.

Constraints

  • 0 <= m, n <= 200
  • Each cell is one of: 0, 1, 2, 3
  • Infection spreads to all 8 adjacent cells

Examples

Input: ([[2, 0, 1], [0, 1, 0], [1, 0, 1]],)

Expected Output: 2

Explanation: The center plant is infected diagonally first, then it infects the remaining corners.

Input: ([[2, 3, 1], [3, 1, 3], [1, 3, 1]],)

Expected Output: 2

Explanation: Diagonal spread allows the infection to move even though orthogonal neighbors are blocked.

Input: ([[2, 1, 1], [1, 1, 0], [0, 1, 1]],)

Expected Output: 2

Explanation: Allowing diagonals reduces the total infection time compared with the 4-directional version.

Input: ([[1, 1], [1, 1]],)

Expected Output: -1

Explanation: No infection can start because there are no initially infected plants.

Input: ([],)

Expected Output: 0

Explanation: An empty grid needs no work.

Hints

  1. This is still a multi-source BFS problem; only the direction list changes.
  2. Use 8 directions instead of 4, and keep the same unreachable check as before.

Part 5: Sparse Infection on a Massive Grid

A farmland grid is too large to store explicitly. You are given `rows` and `cols`, plus sparse coordinate lists for healthy plants, infected plants, and obstacles. All unspecified cells are empty. Each minute, infection spreads in 4 directions from every infected plant to adjacent healthy plants. Infection cannot enter obstacle cells. Because the grid may be enormous, your solution must avoid building a full `rows x cols` matrix. Return the minimum number of minutes needed to infect all listed healthy plants, or `-1` if some can never be infected.

Constraints

  • 1 <= rows, cols <= 10^9
  • 0 <= len(healthy) + len(infected) + len(obstacles) <= 2 * 10^5
  • All listed coordinates are unique, valid, and pairwise non-overlapping

Examples

Input: (1000000000, 1000000000, [(0, 1), (0, 2), (1, 2)], [(0, 0)], [(5, 5)])

Expected Output: 3

Explanation: The infection travels along the sparse chain of listed plants.

Input: (1000000, 1000000, [(1, 0), (1, 2), (2, 2)], [(0, 0), (0, 2)], [])

Expected Output: 2

Explanation: Two starting sources infect the nearby healthy plants first, then the final plant.

Input: (100, 100, [(0, 2)], [(0, 0)], [])

Expected Output: -1

Explanation: The empty cell at `(0, 1)` breaks the chain, so the healthy plant is unreachable.

Input: (50, 50, [], [(10, 10)], [(10, 11)])

Expected Output: 0

Explanation: There are no healthy plants to infect.

Input: (1, 1, [], [], [])

Expected Output: 0

Explanation: An empty sparse description requires no time.

Hints

  1. Do not allocate a `rows x cols` array; use sets or dictionaries keyed by coordinates.
  2. A healthy plant can only be infected if one of its 4 neighboring coordinates is already infected.
Last updated: Apr 19, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Infection Spread Simulation with Death Threshold - OpenAI (medium)
  • Spreading Contagion on a Grid - OpenAI (medium)
  • Streaming Entropy with Numerical Stability - OpenAI (hard)
  • Implement a Distributed Rate Limiter - OpenAI (medium)
  • Compute Plant Infection Time - OpenAI (medium)