Openai·Backend Engineer·Technical Phone Screen·Senior

Senior

May 2026

Summary

Went through a technical phone screen for a backend role at OpenAI and got hit with a grid BFS problem. Pretty standard if you've seen the rotting oranges problem before, but the edge cases can trip you up if you're not careful.

Questions Asked (1)

You're given an m x n grid where some cells start infected and the rest are healthy. Each minute, any healthy cell touching an infected one (up/down/left/right) also becomes infected. Return the minimum number of minutes until all cells are infected, or -1 if some healthy cell can never be reached.

Algorithms & Data Structures

Author's notes

Classic multi-source BFS setup.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the spread as a multi-source BFS where all initially infected cells are enqueued at time 0. Process the grid level by level, incrementing time after each level, and track the number of healthy cells infected. After BFS, if any healthy cell remains, return -1; otherwise return the total minutes elapsed.

Pro tip: Clarify that you're treating this as a shortest-path problem on an unweighted grid, and mention that you can optimize space by modifying the grid in place or using a visited set. Also, handle edge cases like no initial infected cells or an already fully infected grid.

1. Understand the problem and constraints

Restate the problem to confirm it's a multi-source BFS on a grid. Identify edge cases: empty grid, no infected cells, all infected, unreachable healthy cells.

2. Initialize BFS queue and counters

Scan the grid to enqueue all initially infected cells and count healthy cells. Use a queue for BFS and a variable to track remaining healthy cells.

3. Perform multi-source BFS level by level

While the queue is not empty, process all nodes at the current level, infecting adjacent healthy cells, marking them infected, decrementing the healthy count, and enqueueing them. Increment time after each level.

4. Check for unreachable cells and return result

After BFS, if the healthy count is zero, return the elapsed time; otherwise return -1. Discuss time and space complexity: O(m*n) time and O(m*n) space in worst case.

Key Points to Mention

Multi-source BFS is optimal for simultaneous spread from multiple sources.
Time complexity is O(m*n) since each cell is processed once.
Space complexity is O(m*n) for the queue in the worst case.
Edge cases: no initial infected cells (return -1 if any healthy), all infected (return 0), unreachable cells due to barriers.
In-place modification of the grid can save space but may not be allowed; discuss trade-offs.
Level-order traversal ensures correct minute count; increment time only after processing all nodes at current level.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.