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 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.

Compute time to infect all cells | OpenAI Coding Question

Quick Overview

This question evaluates competency in modeling and analyzing discrete-time grid-based state propagation with threshold-based infection rules and boundary conditions.

Compute time to infect all cells

Company: OpenAI

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

You are given an `n × m` grid representing people in a city. - Each cell is either **infected** (`1`) or **healthy** (`0`). - Two cells are **neighbors** if they share an edge (4-directional: up/down/left/right). - Infection spreads in **discrete time steps** (t = 0, 1, 2, ...). - At each time step, **all updates happen simultaneously**: - Any healthy cell becomes infected at the next step if it currently has **at least `K` infected neighbors**. - Infected cells stay infected. ### Task Return the **minimum number of time steps** until **all** cells are infected. - If the grid is already fully infected, return `0`. - If it is **impossible** for all cells to become infected, return `-1`. ### Input - `grid`: an `n × m` matrix of `0/1` - `K`: an integer threshold (`0 ≤ K ≤ 4`) ### Output - An integer: minimum time steps to infect all cells, or `-1` if impossible. ### Notes / Edge cases - If `K = 0`, then all healthy cells become infected after `1` step (unless already all infected). - A cell on the border has fewer than 4 neighbors. (Assume `1 ≤ n, m ≤ 200` and aim for an efficient solution.)

Quick Answer: This question evaluates competency in modeling and analyzing discrete-time grid-based state propagation with threshold-based infection rules and boundary conditions.

You are given an n x m grid representing people in a city. Each cell is either infected (1) or healthy (0). Two cells are neighbors if they share an edge: up, down, left, or right. Infection spreads in discrete time steps t = 0, 1, 2, ... . At each step, all updates happen simultaneously: - Any healthy cell becomes infected at the next step if it currently has at least K infected neighbors. - Infected cells stay infected forever. Return the minimum number of time steps until all cells are infected. Special cases: - If the grid is already fully infected, return 0. - If it is impossible for all cells to become infected, return -1. - If K = 0, then every healthy cell becomes infected after 1 step unless the grid is already fully infected. Important: because updates are simultaneous, a cell that becomes infected at time t cannot help infect other cells until time t + 1.

Constraints

1 <= n, m <= 200
grid[i][j] is either 0 or 1
0 <= K <= 4

Examples

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

Expected Output: 3

Explanation: With K = 1, infection spreads outward one layer per step from the initial infected cell. The farthest cell is infected at time 3.

Loading coding console...

Solution

def solution(grid, K):
    from collections import deque

    if not grid or not grid[0]:
        return 0

    n, m = len(grid), len(grid[0])
    state = [row[:] for row in grid]
    healthy = 0
    q = deque()
    infected_neighbors = [[0] * m for _ in range(n)]

    for r in range(n):
        for c in range(m):
            if state[r][c] == 1:
                q.append((r, c, 0))
            else:
                healthy += 1

    if healthy == 0:
        return 0
    if K == 0:
        return 1
    if not q:
        return -1

    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    answer = 0

    while q:
        r, c, t = q.popleft()

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < m and state[nr][nc] == 0:
                infected_neighbors[nr][nc] += 1
                if infected_neighbors[nr][nc] == K:
                    state[nr][nc] = 1
                    healthy -= 1
                    nt = t + 1
                    answer = nt
                    q.append((nr, nc, nt))

    return answer if healthy == 0 else -1

Time complexity: O(n * m). Space complexity: O(n * m).

Quick Overview

Compute time to infect all cells

Constraints

Examples

Solution

Hints