Count Nodes Using Asynchronous Messages
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given the identifier of a root node in a distributed network. Each node represents a separate machine. A node cannot directly inspect another node's children; the only communication primitive is an asynchronous API:
```text
sendAsyncMessage(nodeId, message)
```
Calling this API eventually delivers `message` to the target node by invoking that node's handler:
```text
receiveMessage(fromNodeId, message)
```
Implement the logic for `receiveMessage(fromNodeId, message)` so that, starting from the root node, the system can discover the entire reachable network and compute the total number of nodes.
Assume each node locally knows only its own node id and the ids of its direct children. It does not have global access to the graph or tree. All traversal, aggregation, and coordination must happen through asynchronous messages.
Your implementation should address:
1. How the root initiates the counting process.
2. How a node asks its children for their subtree counts.
3. How a node distinguishes request messages from response messages.
4. How each node tracks which child responses are still pending.
5. How partial counts are aggregated.
6. How the root detects completion and outputs the final node count.
Follow-up questions:
1. Instead of returning only the count, output the full topology in a nested string format, for example: `1(2(4,5),3(6))`.
2. How would you handle node crashes or message failures? Discuss retries, duplicate responses, idempotency, request ids, and cached results.
3. How would you handle multiple concurrent traversal requests hitting the same node? Discuss per-request state isolation and thread safety.
4. Implement `sendAsyncMessage(nodeId, message)` in a local test environment and write tests that exercise the full asynchronous counting flow.
Quick Answer: This question evaluates skills in distributed systems and asynchronous message-passing, specifically decentralized graph traversal, aggregation, concurrency control, and fault-tolerant coordination across independent nodes.
Part 1: Count Total Reachable Nodes Using Asynchronous Messages
You are given the id of a root node in a rooted network and a dictionary that maps each node to the list of its direct children. Conceptually, nodes may only communicate by asynchronous request and response messages: a node asks each child for its subtree size, waits for all replies, adds 1 for itself, and responds to its parent. Implement a local simulator of that message flow and return the total number of nodes reachable from the root. Ignore nodes that are not reachable from the root. If root is None, return 0.
Constraints
- 0 <= number of reachable nodes <= 100000
- The reachable portion from root forms a tree: no cycles and no node has two different parents
- Each child list contains distinct node ids
Examples
Input: (1, {1: [2, 3], 2: [4, 5], 3: [6], 4: [], 5: [], 6: []})
Expected Output: 6
Explanation: All 6 nodes are reachable from the root.
Input: (1, {1: [2], 2: [3], 3: [], 99: [100], 100: []})
Expected Output: 3
Explanation: Nodes 99 and 100 are not reachable from root 1, so they are ignored.
Hints
- Model two message types: a request that asks a child for its subtree count, and a response that returns that count.
- A node can reply to its parent only after it has received responses from all of its children.
Part 2: Build the Full Topology String Using Asynchronous Messages
You are given the id of a root node in a rooted network and a dictionary of direct children. Instead of returning only the number of nodes, simulate asynchronous request and response messages so that each node returns the full topology of its subtree as a nested string. A leaf node x is represented as 'x'. A non-leaf node x with child strings c1, c2, ... is represented as 'x(c1,c2,...)'. Preserve the child order exactly as it appears in the input lists. Ignore nodes that are not reachable from the root. If root is None, return an empty string.
Constraints
- 0 <= number of reachable nodes <= 100000
- The reachable portion from root forms a tree
- Child order in each list must be preserved in the output
Examples
Input: (1, {1: [2, 3], 2: [4, 5], 3: [6], 4: [], 5: [], 6: []})
Expected Output: '1(2(4,5),3(6))'
Explanation: Each node wraps the string representations of its children.
Input: (1, {1: [3, 2], 2: [], 3: []})
Expected Output: '1(3,2)'
Explanation: The output must preserve the input child order.
Hints
- This is the same bottom-up aggregation pattern as subtree counting, but now each child returns a string instead of an integer.
- Store child results by child id, then rebuild them in the original child-list order when the parent finishes.
Part 3: Reliable Asynchronous Counting with Retries, Request IDs, and Caching
You are given a rooted tree and must compute the number of nodes reachable from the root, but messages and nodes are unreliable. A parent asks a child for its subtree count using a request id. The first request_failures[(parent, child)] request attempts are lost. The first response_failures[(child, parent)] response attempts are lost. The first crash_failures[node] delivered requests to that node are ignored because the node crashes before processing them. A parent may make at most max_retries retries after the first attempt for each child. Retries must reuse the same request id. A node should cache the final result for each request id so duplicate requests can be answered idempotently without recomputing the whole subtree. Return the final count, or -1 if the traversal cannot complete within the retry budget. If root is None, return 0.
Constraints
- 0 <= number of reachable nodes <= 100000
- The reachable portion from root forms a tree
- 0 <= max_retries <= 50, and all failure counts are non-negative integers
Examples
Input: (1, {1: [2, 3], 2: [4], 3: [], 4: []}, {}, {}, {}, 0)
Expected Output: 4
Explanation: No failures occur, so normal subtree counting works.
Input: (1, {1: [2, 3], 2: [4], 3: [], 4: []}, {(1, 2): 1}, {(4, 2): 1}, {}, 2)
Expected Output: 4
Explanation: The first request to 2 is lost, and the first response from 4 to 2 is lost, but retries succeed.
Hints
- Use the same request id on every retry of the same parent-to-child request.
- Cache only completed results; if a subtree never finishes, a later retry may need to recompute it.
Part 4: Concurrent Traversal Requests with Per-Request State Isolation
You are given a rooted network as a children dictionary and several traversal requests that arrive at the same time. Each request is a pair (request_id, root). Conceptually, all requests run concurrently and their request/response messages may interleave. A node can therefore be waiting on different children for different request ids at the same time. Implement a local asynchronous simulator that processes messages in FIFO order and returns the final node count for every request. Your logic must isolate per-request state so that one traversal cannot corrupt another. Actual threading is not required; interleaved message processing is enough to model concurrency.
Constraints
- 0 <= number of requests <= 10000
- The reachable portion from any requested root forms a tree
- Request ids are unique, and each child list contains distinct node ids
Examples
Input: ({1: [2, 3], 2: [4, 5], 3: [], 4: [], 5: []}, [('A', 1), ('B', 2)])
Expected Output: [('A', 5), ('B', 3)]
Explanation: Request A counts the full tree under 1, while request B independently counts the subtree rooted at 2.
Input: ({1: [2], 2: []}, [('R1', 1), ('R2', 1)])
Expected Output: [('R1', 2), ('R2', 2)]
Explanation: Two concurrent requests can ask for the same root and still must remain independent.
Hints
- A single pending set per node is not enough. Key the state by both node id and request id.
- This is the same message protocol as one traversal, but now several independent traversals share the same nodes.
Part 5: Local sendAsyncMessage Simulator with End-to-End Async Completion Time
Implement a local test environment for asynchronous counting. You are given a root node, a children dictionary, and per-edge message delays. A request from parent p to child c takes request_delay[(p, c)] time units; a response from child c to parent p takes response_delay[(c, p)] time units. Missing delay entries default to 1. The root starts at time 0. When a node receives a request, it immediately sends requests to all children. When it has received all child responses, it immediately sends its own response to its parent. Messages scheduled for the same time are delivered in the order they were scheduled. Return both the final node count and the time when the root learns that final answer. If root is None, return (0, 0).
Constraints
- 0 <= number of reachable nodes <= 100000
- All delays are non-negative integers, and missing delays default to 1
- The reachable portion from root forms a tree
Examples
Input: (1, {1: [2, 3], 2: [4]}, {(1, 2): 2, (1, 3): 1, (2, 4): 1}, {(2, 1): 2, (3, 1): 4, (4, 2): 2})
Expected Output: (4, 7)
Explanation: Node 3 responds to the root at time 5. Node 4 responds to node 2 at time 5, then node 2 responds to the root at time 7. The total subtree size is 4.
Input: (1, {1: [2, 3]}, {}, {})
Expected Output: (3, 2)
Explanation: Both children receive the request at time 1 and respond at time 2 using default delays. The root learns the total count 3 at time 2.
Hints
- Use a min-heap of scheduled events like (time, sequence_number, message).
- A parent's completion time depends on the latest child response delivery, not just on the number of children.