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

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.

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

Expected Output: 0

Explanation: All cells are already infected at time 0.

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

Expected Output: 1

Explanation: When K = 0, every healthy cell becomes infected after one simultaneous update.

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

Expected Output: -1

Explanation: There are no initially infected cells, so infection can never start.

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

Expected Output: 3

Explanation: The initial cross infects the four diagonal-adjacent cells at t = 1, the remaining edge cells at t = 2, and the four corners at t = 3.

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

Expected Output: -1

Explanation: Only the center cell can ever reach 2 infected neighbors. After it becomes infected, every remaining healthy cell still has at most 1 infected neighbor, so the process stops early.

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

Hints

For each healthy cell, keep track of how many infected neighbors it has seen so far. The moment this count reaches K, that cell is scheduled to become infected one step later.
Instead of rescanning the whole grid after every time step, process newly infected cells with a queue starting from all initially infected cells.

Quick Overview

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