Openai·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Interviewed for a SWE role at OpenAI and got a graph propagation problem about simulating infection spread across a network. Pretty classic BFS territory but the exact rules were left vague, which made it a bit of a guessing game.

Questions Asked (1)

Given a graph and a set of initially infected nodes, simulate how an infection spreads through the network according to a set of propagation rules. Return the requested output, such as the earliest time each node gets infected, which nodes are infected by step T, or whether a specific target node ever gets infected.

Algorithms & Data StructuresSystem Design

Author's notes

My first instinct was BFS and I just went with it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a graph traversal where infection spreads in discrete time steps, using BFS from all initially infected nodes simultaneously. Clarify the propagation rules (e.g., threshold, probabilistic, or deterministic) and the exact output required, then simulate step-by-step until the target time or until no new infections occur.

Pro tip: Explicitly state the time and space complexity (O(V+E) for BFS) and discuss how you would handle large graphs or probabilistic rules, showing awareness of scalability and edge cases.

1. Clarify rules and output

Ask clarifying questions to confirm the propagation model (e.g., independent cascade, threshold, deterministic), whether infection happens simultaneously per step, and the exact output format (earliest time per node, infected set at time T, or target reachability).

2. Choose data structures

Represent the graph as an adjacency list for efficient traversal. Use a queue for BFS, a distance array to record infection times, and a set or boolean array to track infected nodes.

3. Initialize and simulate

Initialize the queue with all initially infected nodes at time 0 and mark them infected. Process nodes level by level (time step by time step), infecting susceptible neighbors according to the rules, and record the time when each node becomes infected.

4. Handle termination and output

Stop when the queue is empty or when the desired time T is reached. Then produce the requested output: earliest infection times, the set of infected nodes at time T, or a boolean indicating if the target node was infected.

5. Analyze and optimize

Discuss time and space complexity, and consider optimizations for large graphs (e.g., early termination, parallel processing, or probabilistic sampling if rules are stochastic).

Key Points to Mention

BFS with multiple sources to simulate simultaneous spread in discrete time steps.
Time complexity O(V+E) and space complexity O(V) for the queue and distance array.
Handling different propagation rules: deterministic (e.g., all neighbors infected), threshold-based, or probabilistic.
Edge cases: disconnected graph, no initial infected nodes, target already infected, or infection never reaches target.
Output variations: earliest infection time per node, infected set at time T, or reachability of a specific node.
Scalability considerations for large graphs, such as using distributed BFS or sampling for probabilistic models.

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