PracHub
QuestionsPremiumLearningGuidesCheatsheetNEWCareers

Quick Overview

This question evaluates the ability to implement and reason about discrete-time, grid-based simulations with multi-state cells and neighbor-dependent transitions, including state aging, immunity, and death tracking.

  • hard
  • OpenAI
  • Coding & Algorithms
  • Machine Learning Engineer

Simulate Infection Spread on a Grid

Company: OpenAI

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given an `m x n` grid representing cells in a population. Each day, all state changes happen simultaneously. Infection neighbors are the 8 surrounding cells, including diagonals. Implement functions for the following progressively extended simulations. ### Part 1: Basic infection spread Each cell is one of: - `'X'`: infected - `'.'`: healthy On each day, a healthy cell becomes infected if it has at least `T` infected neighbors. Return the number of days until the grid becomes stable, meaning no new cell becomes infected on the next day. ### Part 2: Immune cells Add a third cell type: - `'I'`: immune Immune cells never become infected and do not spread infection. Return the number of days until the grid becomes stable, meaning no new cell becomes infected on the next day. ### Part 3: Recovery after infection In addition to Part 2, every infected cell recovers after `D` days and becomes immune, represented by `'I'`. Assume initially infected cells have infection age `0` at day `0`, and newly infected cells also start with infection age `0` on the day they become infected. Return the number of days until the grid becomes stable, meaning there are no infected cells left. ### Part 4: Death after high exposure Extend Part 3 with a death rule. If any non-immune, non-dead cell has at least `K` infected neighbors on a day, it is scheduled to die after `D` days. Dead cells should be treated as inactive: they do not become infected, do not recover, and do not spread infection. Return a tuple: ```text (days_until_stable, total_deaths) ``` where `days_until_stable` is the number of days until there are no infected cells left, and `total_deaths` is the total number of cells that died during the simulation. Focus on writing a correct direct simulation rather than optimizing complexity.

Quick Answer: This question evaluates the ability to implement and reason about discrete-time, grid-based simulations with multi-state cells and neighbor-dependent transitions, including state aging, immunity, and death tracking.

Part 1: Basic Infection Spread

You are given a grid of '.' and 'X'. '.' means healthy and 'X' means infected. Each day, all changes happen simultaneously. A healthy cell becomes infected if at least T of its 8 neighbors (horizontal, vertical, and diagonal) are infected. Infected cells never recover. Return the number of days until the grid becomes stable, meaning the next simulated day would produce no new infections.

Constraints

  • 0 <= len(grid) <= 30
  • 0 <= len(grid[0]) <= 30 if grid is non-empty
  • Each row has the same length
  • Grid characters are only '.' or 'X'
  • 1 <= T <= 8

Examples

Input: (["X..", "...", "..."], 1)

Expected Output: 2

Explanation: The infection spreads from the top-left corner outward. Three cells infect on day 1, and the remaining cells infect on day 2.

Input: (["...", "..."], 1)

Expected Output: 0

Explanation: There are no infected cells initially, so the grid is already stable.

Input: (["...", ".X.", "..."], 8)

Expected Output: 0

Explanation: Each healthy cell has at most 1 infected neighbor, so none meet the threshold of 8.

Input: (["X." , ".X"], 2)

Expected Output: 1

Explanation: Each healthy cell has exactly 2 infected neighbors, so both become infected after one day.

Input: (["X"], 1)

Expected Output: 0

Explanation: A single infected cell has no healthy neighbors to infect.

Hints

  1. Simulate the process day by day, but collect all cells that should change before modifying the grid.
  2. There are only 8 possible neighbor directions, so a direct neighbor count is enough.

Part 2: Infection Spread with Immune Cells

You are given a grid containing '.', 'X', and 'I'. '.' means healthy, 'X' means infected, and 'I' means immune. Each day, all changes happen simultaneously. A healthy cell becomes infected if at least T of its 8 neighbors are infected. Immune cells never become infected and do not spread infection. Infected cells remain infected forever. Return the number of days until the grid becomes stable, meaning the next day would produce no new infections.

Constraints

  • 0 <= len(grid) <= 30
  • 0 <= len(grid[0]) <= 30 if grid is non-empty
  • Each row has the same length
  • Grid characters are only '.', 'X', or 'I'
  • 1 <= T <= 8

Examples

Input: (["X.I", "...", "I.."], 1)

Expected Output: 2

Explanation: The immune cells remain unchanged, while infection still spreads through other reachable healthy cells over two days.

Input: (["I.I", "III"], 1)

Expected Output: 0

Explanation: There are no infected cells at all, so the grid is already stable.

Input: (["XI", ".I"], 2)

Expected Output: 0

Explanation: The only healthy cell has just 1 infected neighbor, which is below the threshold.

Input: (["X.I"], 1)

Expected Output: 1

Explanation: The middle healthy cell has one infected neighbor, so it becomes infected after one day.

Input: (["I"], 1)

Expected Output: 0

Explanation: A single immune cell never changes.

Hints

  1. Only '.' cells are candidates to change. 'I' cells should stay exactly as they are.
  2. When counting neighbors, only 'X' contributes to infection spread.

Part 3: Infection Spread with Recovery

You are given a grid containing '.', 'X', and 'I'. '.' means healthy, 'X' means infected, and 'I' means immune. Each infected cell also has an infection age. Initially infected cells start with age 0 on day 0. On each day, use the infected cells present at the start of the day to infect healthy cells that have at least T infected neighbors. Also on that same day, every currently infected cell increases its age by 1; if its age becomes D, it recovers and becomes immune at the end of the day. Newly infected cells appear at the end of the day with age 0 and do not age immediately. Return the number of days until there are no infected cells left.

Constraints

  • 0 <= len(grid) <= 30
  • 0 <= len(grid[0]) <= 30 if grid is non-empty
  • Each row has the same length
  • Grid characters are only '.', 'X', or 'I'
  • 1 <= T <= 8
  • 1 <= D <= 30

Examples

Input: (["X"], 1, 1)

Expected Output: 1

Explanation: The single infected cell recovers after one day, so there are no infected cells left on day 1.

Input: (["X..", "...", "..."], 1, 2)

Expected Output: 4

Explanation: The infection spreads outward for two days, then infected cells gradually recover until none remain after day 4.

Input: (["...", ".X.", "..."], 2, 2)

Expected Output: 2

Explanation: No healthy cell ever reaches the threshold of 2 infected neighbors, so the original infected cell simply recovers after two days.

Input: (["XI", ".I"], 1, 2)

Expected Output: 3

Explanation: The lower-left healthy cell is infected on day 1, then the original infected cell recovers on day 2, and the new infected cell recovers on day 3.

Input: (["..", "II"], 1, 3)

Expected Output: 0

Explanation: There are no infected cells initially.

Hints

  1. Store the infection age separately from the visible grid state.
  2. Be careful with simultaneity: newly infected cells should not age or recover on the same day they appear.

Part 4: Infection Spread with Recovery and Delayed Death

You are given a grid containing '.', 'X', and 'I'. '.' means healthy, 'X' means infected, and 'I' means immune. Initially infected cells have infection age 0. The simulation follows the Part 3 recovery rules, and adds a death rule. On a day, if a cell is neither immune nor already dead and has at least K infected neighbors, it gets a death timer if it does not already have one. The death timer behaves like infection age: it starts at 0 on the day the cell is scheduled, increases by 1 on each later day, and when it reaches D the cell dies at the end of that day. A scheduled cell may still be healthy, infected, or even recover before it dies. If a cell would both die and recover on the same day, death wins. Dead cells are inactive: they do not become infected, do not recover, and do not spread infection. Continue simulating until there are no infected cells and no pending death timers. Return a tuple (days_until_stable, total_deaths), where days_until_stable is the first day on which the number of infected cells becomes 0.

Constraints

  • 0 <= len(grid) <= 30
  • 0 <= len(grid[0]) <= 30 if grid is non-empty
  • Each row has the same length
  • Initial grid characters are only '.', 'X', or 'I'
  • 1 <= T <= 8
  • 1 <= K <= 8
  • 1 <= D <= 30

Examples

Input: (["..", "II"], 1, 2, 2)

Expected Output: (0, 0)

Explanation: There are no infected cells initially, so the stable day is 0 and nobody dies.

Input: (["X"], 1, 1, 2)

Expected Output: (1, 0)

Explanation: The infected cell recovers after one day. There is no death because the exposure threshold is never met.

Input: (["XX", "X."], 1, 1, 3)

Expected Output: (2, 1)

Explanation: The healthy cell is infected and scheduled to die on day 1. On day 2, it would recover and die at the same time, and death wins.

Input: (["XX", "X."], 4, 2, 3)

Expected Output: (2, 1)

Explanation: The healthy cell is scheduled to die because it has 3 infected neighbors, but it never becomes infected because T is 4. The original infected cells recover on day 2, so days_until_stable is 2. The scheduled healthy cell dies later, making total_deaths 1.

Input: (["I"], 1, 3, 1)

Expected Output: (0, 0)

Explanation: A single immune cell never changes and can never be scheduled to die.

Hints

  1. Track infection age and death-schedule age independently; they are two different timers.
  2. Use the current day's infected cells to decide both new infections and new death schedules, then apply deaths last so death can override recovery or infection.
Last updated: May 12, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • Careers
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Implement Social Follow Recommendations - OpenAI (medium)
  • Build a Compose Rating Card - OpenAI (medium)
  • Convert IPv4 Ranges to CIDR Blocks - OpenAI (medium)
  • Implement Persistent KV Store Serialization - OpenAI (hard)
  • Implement Social Graph Snapshot Queries - OpenAI (medium)