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 hard 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 Infection Time in a Grid | OpenAI Coding Question

Quick Overview

This question evaluates competence in grid-based graph traversal and simulation of propagation dynamics, focusing on state management, time-step modeling, and handling unreachable cells.

hard
OpenAI
Coding & Algorithms
Software Engineer

Compute Infection Time in a Grid

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given an `m x n` grid where each cell is one of the following: - `0`: empty - `1`: healthy - `2`: infected Every minute, each infected cell spreads the infection to its adjacent healthy cells in the four cardinal directions. Return the minimum number of minutes needed until no healthy cells remain. If it is impossible to infect every healthy cell, return `-1`.

Quick Answer: This question evaluates competence in grid-based graph traversal and simulation of propagation dynamics, focusing on state management, time-step modeling, and handling unreachable cells.

You are given an m x n grid where each cell contains one of three values: 0 for an empty cell, 1 for a healthy cell, and 2 for an infected cell. Every minute, each infected cell spreads the infection to its adjacent healthy cells in the four cardinal directions (up, down, left, right). Return the minimum number of minutes needed until no healthy cells remain. If some healthy cells can never be infected, return -1.

Constraints

0 <= m, n <= 200
grid[i][j] is one of 0, 1, or 2
Infection spreads only in the four cardinal directions

Examples

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

Expected Output: 4

Explanation: The infection spreads outward each minute and reaches the last healthy cell after 4 minutes.

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

Expected Output: -1

Explanation: At least one healthy cell is isolated by empty cells and can never be infected.

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

Expected Output: 0

Explanation: There are no healthy cells at the start, so no time is needed.

Input: ([],)

Expected Output: 0

Explanation: An empty grid has no healthy cells to infect.

Input: ([[1]],)

Expected Output: -1

Explanation: There is one healthy cell and no infected cell to start the spread.

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

Expected Output: 2

Explanation: Infection starts from two cells and spreads from both sides, infecting the whole grid in 2 minutes.

Hints

Loading coding console...