OpenAI's 5-Part Coding Interview Question

Most people prep for OpenAI expecting LeetCode, then get handed one problem that keeps changing under them. This grid simulation is flagged high frequency in recent OpenAI onsites. It opens as a clean breadth-first search and ends as an open optimization problem. Here is the full question, all five parts, with a Java solution for each and the rubric the interviewer scores you against.

The question

Input: 3x4 grid
X.........X.
Output: 2 (days)

If you reach for a fresh search from every cell on every day, you have already lost the thread. The intended core is a multi-source breadth-first search seeded from all infected cells at once, where the answer is the depth of the last layer reached. Then the follow-ups begin.

Part 1 · Basic infection

Multi-source BFS from every initial X. Track how many healthy cells remain so you can stop as soon as the grid is saturated, and count one day per BFS layer.

import java.util.*;

class Solution {
    private static final int[][] DIRS = {
        {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}
    };

    // Days until no healthy plant ('.') can be infected.
    public int daysToStable(char[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        Deque<int[]> queue = new ArrayDeque<>();
        int healthy = 0;
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                if (grid[r][c] == 'X') queue.add(new int[]{r, c});
                else if (grid[r][c] == '.') healthy++;

        int days = 0;
        while (!queue.isEmpty() && healthy > 0) {
            for (int n = queue.size(); n > 0; n--) {
                int[] cur = queue.poll();
                for (int[] d : DIRS) {
                    int r = cur[0] + d[0], c = cur[1] + d[1];
                    if (r < 0 || r >= rows || c < 0 || c >= cols) continue;
                    if (grid[r][c] != '.') continue;
                    grid[r][c] = 'X';
                    healthy--;
                    queue.add(new int[]{r, c});
                }
            }
            days++;
        }
        return days;
    }
}

Part 2 · Immune plants

I cells are immune. They never get infected and they block spread, acting as walls. The signal is whether your Part 1 code already handled cell types cleanly. It does: the guard only infects . cells, so I is treated as a wall with no special case. The only change is the neighbor check.

for (int[] d : DIRS) {
    int r = cur[0] + d[0], c = cur[1] + d[1];
    if (r < 0 || r >= rows || c < 0 || c >= cols) continue;
    if (grid[r][c] != '.') continue;   // 'I' is not '.', so it blocks spread
    grid[r][c] = 'X';
    healthy--;
    queue.add(new int[]{r, c});
}

If adding immunity forced you to rewrite the loop, that is the tell the interviewer is waiting for. A clean Part 1 makes Part 2 a one-line comment.

Part 3 · Recovery after D days

Infected plants recover to . after exactly D days and can be reinfected. A plain BFS layer count no longer works, because cells now have different lifetimes. Move to an event-driven simulation: a priority queue of recovery events keyed by the day each cell flips back, and a frontier that spreads outward one day at a time. The answer is the last day anything changed.

import java.util.*;

class Solution {
    private static final int[][] DIRS = {
        {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}
    };

    // Cells recover to '.' D days after infection and can be reinfected.
    // Returns the last day on which any infection or recovery happened.
    public int daysToStable(char[][] grid, int D) {
        int rows = grid.length, cols = grid[0].length;
        int[][] infectedAt = new int[rows][cols];
        for (int[] row : infectedAt) Arrays.fill(row, -1);

        // Recovery events ordered by the day a cell flips back to '.'.
        PriorityQueue<int[]> recoveries = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        Deque<int[]> frontier = new ArrayDeque<>();   // cells infected the previous day

        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                if (grid[r][c] == 'X') {
                    infectedAt[r][c] = 0;
                    frontier.add(new int[]{r, c});
                    recoveries.add(new int[]{D, r, c});
                }

        int day = 0, lastChange = 0;
        int maxDays = rows * cols * (D + 1) + D;       // bounds pathological oscillation
        while ((!frontier.isEmpty() || !recoveries.isEmpty()) && day < maxDays) {
            day++;

            // 1) Recoveries scheduled for today.
            while (!recoveries.isEmpty() && recoveries.peek()[0] == day) {
                int[] ev = recoveries.poll();
                int r = ev[1], c = ev[2];
                if (grid[r][c] == 'X' && infectedAt[r][c] == day - D) {
                    grid[r][c] = '.';
                    infectedAt[r][c] = -1;
                    lastChange = day;
                }
            }

            // 2) Spread: only yesterday's frontier infects, each cell once.
            Deque<int[]> next = new ArrayDeque<>();
            for (int n = frontier.size(); n > 0; n--) {
                int[] cur = frontier.poll();
                if (grid[cur[0]][cur[1]] != 'X') continue;   // recovered before it could spread
                for (int[] d : DIRS) {
                    int r = cur[0] + d[0], c = cur[1] + d[1];
                    if (r < 0 || r >= rows || c < 0 || c >= cols) continue;
                    if (grid[r][c] != '.') continue;
                    grid[r][c] = 'X';
                    infectedAt[r][c] = day;
                    recoveries.add(new int[]{day + D, r, c});
                    next.add(new int[]{r, c});
                    lastChange = day;
                }
            }
            frontier = next;
        }
        return lastChange;
    }
}

The subtlety the interviewer probes here: for very small D, a recovered cell can be reinfected by the receding wave, which can oscillate. The maxDays cap and a repeated-state check are the honest answers. Say so out loud.

Part 4 · Death condition

If an infected plant has K or more infected neighbors when its D days are up, it dies instead of recovering. A dead cell D is permanent and blocks spread like a wall. This is a one-branch change to the recovery step from Part 3 plus a neighbor count, because the event model already generalizes.

// Replaces the recovery block inside the day loop in Part 3.
while (!recoveries.isEmpty() && recoveries.peek()[0] == day) {
    int[] ev = recoveries.poll();
    int r = ev[1], c = ev[2];
    if (grid[r][c] == 'X' && infectedAt[r][c] == day - D) {
        // A heavily surrounded plant dies rather than recovering.
        grid[r][c] = infectedNeighbors(grid, r, c) >= K ? 'D' : '.';
        infectedAt[r][c] = -1;
        lastChange = day;
    }
}

private int infectedNeighbors(char[][] g, int r, int c) {
    int count = 0;
    for (int[] d : DIRS) {
        int nr = r + d[0], nc = c + d[1];
        if (nr < 0 || nr >= g.length || nc < 0 || nc >= g[0].length) continue;
        if (g[nr][nc] == 'X') count++;
    }
    return count;
}

Because D is not ., the spread guard already treats dead cells as walls. Three interacting event types, one new branch.

Part 5 · Optimization

At the start of any day you may burn one entire row or column, turning those cells into firebreaks that block spread and never die. Minimize total deaths. This is deliberately open. There is no clean closed form, so the interviewer wants a defensible heuristic and your reasoning about its limits. A greedy that each day burns the line holding the most infected plants is a solid starting point.

import java.util.*;

class Solution {
    private static final int[][] DIRS = {
        {-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}
    };

    // Greedy heuristic: each day burn the row or column with the most infected
    // plants, then advance the simulation. Burned cells become firebreaks ('#').
    // NOTE: this is NOT provably optimal. The optimal burn schedule is an open
    // search problem (exponential state space); discuss greedy vs beam search.
    public int minDeathsGreedy(char[][] grid, int D, int K) {
        int rows = grid.length, cols = grid[0].length;
        int[][] infectedAt = new int[rows][cols];
        for (int[] row : infectedAt) Arrays.fill(row, -1);
        Deque<int[]> frontier = new ArrayDeque<>();
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                if (grid[r][c] == 'X') { infectedAt[r][c] = 0; frontier.add(new int[]{r, c}); }

        int deaths = 0, day = 0, maxDays = rows * cols * (D + 1) + D;
        while (hasInfected(grid) && day < maxDays) {
            burnBestLine(grid);                 // 1) sacrifice the worst line
            day++;
            for (int r = 0; r < rows; r++)      // 2) resolve D-day-old infections
                for (int c = 0; c < cols; c++)
                    if (grid[r][c] == 'X' && infectedAt[r][c] == day - D) {
                        if (infectedNeighbors(grid, r, c) >= K) { grid[r][c] = 'D'; deaths++; }
                        else grid[r][c] = '.';
                        infectedAt[r][c] = -1;
                    }
            Deque<int[]> next = new ArrayDeque<>();   // 3) spread survivors
            for (int n = frontier.size(); n > 0; n--) {
                int[] cur = frontier.poll();
                if (grid[cur[0]][cur[1]] != 'X') continue;
                for (int[] d : DIRS) {
                    int r = cur[0] + d[0], c = cur[1] + d[1];
                    if (r < 0 || r >= rows || c < 0 || c >= cols) continue;
                    if (grid[r][c] != '.') continue;
                    grid[r][c] = 'X'; infectedAt[r][c] = day; next.add(new int[]{r, c});
                }
            }
            frontier = next;
        }
        return deaths;
    }

    private void burnBestLine(char[][] g) {
        int rows = g.length, cols = g[0].length, best = 0, kind = -1, idx = -1;
        for (int r = 0; r < rows; r++) {
            int cnt = 0;
            for (int c = 0; c < cols; c++) if (g[r][c] == 'X') cnt++;
            if (cnt > best) { best = cnt; kind = 0; idx = r; }
        }
        for (int c = 0; c < cols; c++) {
            int cnt = 0;
            for (int r = 0; r < rows; r++) if (g[r][c] == 'X') cnt++;
            if (cnt > best) { best = cnt; kind = 1; idx = c; }
        }
        if (kind == 0) for (int c = 0; c < cols; c++) g[idx][c] = '#';
        else if (kind == 1) for (int r = 0; r < rows; r++) g[r][idx] = '#';
    }

    private boolean hasInfected(char[][] g) {
        for (char[] row : g) for (char ch : row) if (ch == 'X') return true;
        return false;
    }

    private int infectedNeighbors(char[][] g, int r, int c) {
        int count = 0;
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nr >= g.length || nc < 0 || nc >= g[0].length) continue;
            if (g[nr][nc] == 'X') count++;
        }
        return count;
    }
}

Naming this as a heuristic and sketching what optimal would cost is the win. Freezing because there is no clean answer is the trap.

How OpenAI scores it

You are not expected to finish Part 5. You are expected to be clearly strong on the first three rows.

The whole question is one test repeated five times: when the rules change, does your earlier design bend or shatter. Candidates who write Part 1 as if Part 4 is coming sail through. Those who hardcode the happy path rewrite from scratch four times and run out of clock.

OpenAI interview FAQ