← Openai Interview Insights

Openai·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say
Jun 2026Remote

Summary

OpenAI SWE coding round, one problem the whole session. Classic grid BFS spread question, felt straightforward but the edge cases around impossibility tripped me up a bit.

Questions Asked (1)

Q1

Given an m x n grid where cells are either empty, uninfected, or infected, find the minimum number of minutes for all uninfected cells to become infected (infected cells spread to 4-directional neighbors each minute). Return -1 if it's impossible.

Algorithms & Data Structures
Author's notes

Multi-source BFS, pretty standard once you recognize it.

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 time level by level, counting minutes until no more cells can be infected. If any uninfected cell remains, return -1.

Pro tip: Clarify edge cases upfront (e.g., no infected cells, all infected, unreachable regions) and mention that BFS is optimal because infection spreads uniformly in all directions at the same rate.

1. Understand the problem and edge cases

Restate the problem: each minute, infected cells spread to 4-directional neighbors. Identify edge cases: no infected cells, all cells infected, unreachable uninfected cells.

2. Choose the right algorithm

Recognize this as a multi-source BFS problem because infection spreads uniformly from multiple sources. BFS guarantees the minimum time.

3. Implement BFS with a queue

Initialize a queue with all infected cells and count total uninfected cells. Process level by level, infecting neighbors and decrementing the uninfected count.

4. Track time and check completion

Increment time after each BFS level. After BFS, if uninfected count is zero, return time; otherwise return -1.

5. Analyze complexity and test

State time and space complexity: O(m*n) time and O(m*n) space. Walk through a small example to verify correctness.

Key Points to Mention

  • Multi-source BFS is optimal for uniform spreading processes.
  • Use a queue to process cells level by level, representing minutes.
  • Count uninfected cells to detect impossibility early.
  • Handle edge cases: no infected cells, all infected, unreachable cells.
  • Time complexity O(m*n) and space complexity O(m*n) due to queue.
  • Avoid DFS because it doesn't guarantee minimum time.

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