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 Software Engineer candidates at OpenAI during technical interviews.

Compute infection spread time | OpenAI Coding Question

Compute infection spread time

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given an `m x n` grid representing a population during an outbreak: - `0` = empty cell - `1` = healthy person - `2` = infected person Every minute, each infected person spreads the disease to any healthy person in the four adjacent cells: up, down, left, and right. Return the minimum number of minutes needed until no healthy person remains. If it is impossible to infect everyone, return `-1`. Example: - Input: `[[2,1,1],[1,1,0],[0,1,1]]` - Output: `4` Discuss the algorithm, its time complexity, and important edge cases.

Quick Answer: This question evaluates understanding of grid-based graph traversal and propagation dynamics, testing competencies in breadth-first search concepts, simulation of state changes, and analysis of time and space complexity.

You are given an m x n grid representing a population during an outbreak, where 0 means an empty cell, 1 means a healthy person, and 2 means an infected person. Every minute, each infected person spreads the disease to any healthy person in the four adjacent cells: up, down, left, and right. Return the minimum number of minutes needed until no healthy person remains. If it is impossible to infect every healthy person, return -1. If the grid is empty or there are no healthy people initially, return 0.

Constraints

0 <= number of rows, number of columns <= 200
grid[i][j] is one of {0, 1, 2}
At most 40,000 cells in the grid

Examples

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

Expected Output: 4

Explanation: The infection spreads outward from the initial infected cell, and the last healthy person becomes infected after 4 minutes.

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

Expected Output: -1

Explanation: The healthy person in the bottom-left area is isolated by empty cells, so not everyone can be infected.

Input: [[0,2]]

Expected Output: 0

Explanation: There are no healthy people at the start, so the answer is 0.

Input: []

Expected Output: 0

Explanation: An empty grid contains no healthy people, so no time is needed.

Input: [[1]]

Expected Output: -1

Explanation: There is one healthy person and no infected person to start the spread, so infection is impossible.

Hints

This is a shortest-spread problem on a grid, and all initially infected cells start spreading at the same time.
Use a multi-source BFS: put every infected cell into the queue first, then expand level by level where each level represents one minute.

Quick Overview

This question evaluates understanding of grid-based graph traversal and propagation dynamics, testing competencies in breadth-first search concepts, simulation of state changes, and analysis of time and space complexity.