Openai·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Interviewed for a software engineering role at OpenAI and got a grid-based BFS problem that was a twist on the classic infection spread question. The immune cell wrinkle was subtle but changed how you think about neighbor filtering.

Questions Asked (1)

You have a grid containing empty cells, infected cells, and immune cells. Each day, every infected cell spreads to its 8 neighboring empty cells, but immune cells can never be infected. How many days until the infection stops spreading? Walk through how you'd modify a BFS approach to handle this.

Algorithms & Data Structures

Author's notes

I'd done the basic version of this before so I jumped into BFS pretty fast, which was probably the wrong move because I initially forgot to filter out immune cells and just treated them like walls.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the grid as a graph and use multi-source BFS starting from all initially infected cells simultaneously. Track the day each cell becomes infected, and stop when no new cells can be infected; the answer is the maximum day reached.

Pro tip: Mention that immune cells act as obstacles and that the 8-directional spread requires checking all 8 neighbors, unlike standard 4-directional BFS. Also note that if the initial infected set is empty, the answer is 0 days.

1. Clarify the problem and edge cases

Confirm the grid dimensions, cell states (empty, infected, immune), and that infection spreads to all 8 neighbors each day. Discuss edge cases: no infected cells, all cells immune, or infection already contained.

2. Initialize BFS queue and day counter

Add all initially infected cells to a queue with day 0. Use a separate queue or level-order traversal to process cells day by day, incrementing the day after each level.

3. Process each day's infections

For each cell in the current day's queue, examine its 8 neighbors. If a neighbor is empty, mark it infected, add it to the next day's queue, and record its infection day.

4. Terminate and return result

Continue until the queue is empty (no new infections). The number of days is the maximum day recorded, or the number of levels processed minus one if starting from day 0.

5. Analyze complexity and optimizations

Time complexity is O(rows * cols) since each cell is processed once. Space complexity is O(rows * cols) for the queue and visited/infected tracking. Mention potential optimizations like using a 2D array for days or in-place modification.

Key Points to Mention

Multi-source BFS: all initially infected cells are sources, processed simultaneously.
8-directional neighbor checks (including diagonals) instead of standard 4-directional.
Immune cells are treated as blocked and never enqueued.
Day tracking: either store day per cell or process level by level.
Termination condition: when no new cells are infected in a day.
Edge cases: no initial infection (0 days), infection already contained (0 days), or all cells infected.

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