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 medium 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 Spread | OpenAI Coding Question

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.

Loading coding console...

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

Run multi-source BFS starting from all initially infected cells.
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

A level-order BFS naturally gives you the frontier size for each minute.
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

This is still a multi-source BFS problem; only the direction list changes.
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

Do not allocate a `rows x cols` array; use sets or dictionaries keyed by coordinates.
A healthy plant can only be infected if one of its 4 neighboring coordinates is already infected.

Quick Overview