OpenAI Software Engineer Interview Experience — Distributed Node-Counting System Design Question

I've interviewed with OpenAI several times recently.

This question gives you a root node and an initial API, sendAsyncMessage(nodeId, message). You need to implement receiveMessage(fromNodeId, message) yourself, and ultimately count how many nodes exist in the whole network.

On the surface it looks a bit like DFS, but it's dressed up as a more realistic distributed scenario. Each node can be thought of as a separate machine — you can't just access node.children like you would on LeetCode, you can only query child nodes through the given async message API.

The core difficulty is that every operation has to go through sendAsyncMessage, so you need to design your own message protocol and distinguish between requests coming down from the parent and responses coming back up from children. Each node also has to track which children it's still waiting on a response from, and how many partial results it has collected so far. The root is a special case — once it has received all the aggregated results, it outputs the final answer directly instead of forwarding anything further up.

The follow-ups lean more toward systems design:

1. Report the topology, i.e. output the entire tree structure. This isn't very different from part one — it's essentially the same message coordination mechanism, except the final output isn't a sum but something like 1(2(4,5),3(6)).

2. How do you handle a node crashing or failing? If a node goes down you need to retry, but retrying introduces the problem of double-counting — for example the same child's response getting counted twice, which throws off the final sum. The fix is to add idempotency: every request carries a request_id, and each node keeps a set of requests it has already processed. Duplicate requests get dropped, or the node just returns the cached historical result. You also need timeout-based retries and response caching to make this work.

3. What about concurrency? If multiple requests hit the same node at the same time, they can't share the same state. The more solid approach is to isolate state by request_id, so each request has its own independent pending_children and partial_result. In a multithreaded environment you also need to think about locks and atomic updates.

4. A rarer follow-up: implement sendAsyncMessage itself. Since this question is mostly about system design, the API is usually assumed to already exist. But if the interviewer keeps pushing, they might send you back to actual coding — implementing the async message-sending logic for real and writing a few test cases to get the whole thing running end to end.