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 Technical Screen rounds at OpenAI.

What role is this question designed for?

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

Compute Plant Infection Time | OpenAI Coding Question

Compute Plant Infection Time

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given an `m x n` grid representing a garden. Each cell is one of the following: - `0`: empty ground - `1`: a healthy plant - `2`: an infected plant - `-1`: a wall or blocked cell At the end of each minute, every infected plant spreads the infection to all orthogonally adjacent healthy plants: up, down, left, and right. Infection cannot pass through walls or empty cells. Implement a function that returns the minimum number of minutes required until no more plants can be infected. If every healthy plant can eventually be infected, return that number of minutes. If at least one healthy plant can never be reached by the infection, return `-1`. Clarify and handle edge cases such as: - No healthy plants initially - No infected plants initially - Multiple infected plants initially - Walls that isolate parts of the garden - Large grids where an efficient breadth-first search is expected

Quick Answer: This question evaluates a candidate's understanding of graph traversal and grid-based state propagation, including concepts like breadth-first search, reachability, obstacle handling, and edge-case reasoning.

You are given a garden as an m x n grid. Each cell contains one of four values: 0 for empty ground, 1 for a healthy plant, 2 for an infected plant, and -1 for a wall or blocked cell. At the end of each minute, every infected plant spreads the infection to all orthogonally adjacent healthy plants (up, down, left, right). Infection cannot move through walls or empty ground. Return the minimum number of minutes needed until no more plants can be infected if every healthy plant can eventually become infected. If at least one healthy plant can never be reached, return -1. If there are no healthy plants initially, return 0.

Constraints

0 <= m, n <= 200
Each grid cell is one of -1, 0, 1, or 2
The input is a rectangular grid
An O(m * n) breadth-first search solution is expected for large grids

Examples

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

Expected Output: 4

Explanation: The infection spreads layer by layer and reaches the last healthy plant after 4 minutes.

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

Expected Output: -1

Explanation: The healthy plant at the bottom-left is isolated by walls, so not every healthy plant can be infected.

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

Expected Output: 0

Explanation: There are no healthy plants initially, so no time is needed.

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

Expected Output: -1

Explanation: There are healthy plants but no infected plants to start the spread.

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

Expected Output: 2

Explanation: Two infection sources spread simultaneously, so all reachable healthy plants are infected in 2 minutes.

Input: ([],)

Expected Output: 0

Explanation: An empty grid contains no healthy plants, so the answer is 0.

Hints

Treat all initially infected plants as starting points in the same BFS queue.
Count how many healthy plants exist, and decrease that count as they become infected.

Quick Overview

This question evaluates a candidate's understanding of graph traversal and grid-based state propagation, including concepts like breadth-first search, reachability, obstacle handling, and edge-case reasoning.