Openai·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026Remote

Summary

OpenAI coding round with a simulation problem that kept getting harder. The base infection spread question was manageable but then they added recovery and immunity mechanics and I had to rethink basically everything mid-interview.

Questions Asked (1)

Given a grid where infected cells spread to all 8 neighbors each day, and each infected cell recovers and becomes permanently immune after exactly D days, simulate the process and return how many days until the grid reaches equilibrium.

Algorithms & Data StructuresSystem Design

Author's notes

The first version of this problem felt fine, standard BFS-style spread.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the process as a multi-source BFS where each cell's infection time is the minimum Manhattan distance (Chebyshev distance for 8-neighbor) to an initial infected cell, and recovery occurs D days after infection. Simulate day by day using a queue, tracking each cell's state (infected with recovery day, immune, or susceptible), and stop when no new infections occur and all infected cells have recovered.

Pro tip: Clarify the timing semantics upfront: whether recovery happens at the end of the D-th day or the start of the next day, as this off-by-one can change the equilibrium day. Also, mention that equilibrium is reached when no new infections occur and all currently infected cells have recovered, which may be later than the last infection day.

1. Clarify problem semantics and edge cases

Ask about grid boundaries, initial infected cells, D value, and whether recovery is simultaneous with spread. Confirm if a cell can be reinfected after immunity and how days are counted.

2. Choose representation and algorithm

Use a 2D grid to store state (e.g., -1 susceptible, 0 immune, >0 days until recovery) and a queue for BFS. For 8-neighbor spread, use Chebyshev distance; simulate day-by-day or compute infection times directly.

3. Simulate the process

Initialize queue with infected cells and their recovery timers. Each day, process all currently infected cells: spread to susceptible neighbors (mark newly infected with timer D) and decrement timers; remove recovered cells. Track day count.

4. Determine equilibrium and return days

Equilibrium is when no new infections occur and no infected cells remain. Continue simulation until that condition, then return the total days elapsed.

5. Analyze complexity and optimize

Discuss time O(N*M) and space O(N*M) for grid and queue. Mention potential optimizations like early termination or using multi-source BFS to compute infection times in one pass.

Key Points to Mention

Multi-source BFS for simultaneous spread from all initially infected cells.
Chebyshev distance (L∞ norm) for 8-neighbor spread, contrasting with Manhattan distance for 4-neighbor.
State management: susceptible, infected (with recovery countdown), and immune.
Off-by-one pitfalls in day counting and recovery timing.
Equilibrium condition: no new infections and all infected cells recovered.
Complexity analysis: O(N*M) time and space, with possible optimizations.

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