PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • medium
  • OpenAI
  • Coding & Algorithms
  • Software Engineer

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.

Input: (7, {7: []})

Expected Output: 1

Explanation: A single-node tree has count 1.

Input: (None, {1: [2], 2: []})

Expected Output: 0

Explanation: No root means no traversal.

Hints

  1. Model two message types: a request that asks a child for its subtree count, and a response that returns that count.
  2. 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.

Input: (7, {})

Expected Output: '7'

Explanation: A missing key means node 7 is a leaf.

Input: (1, {1: [2], 2: [], 9: [10], 10: []})

Expected Output: '1(2)'

Explanation: Unreachable nodes 9 and 10 are ignored.

Input: (None, {1: [2], 2: []})

Expected Output: ''

Explanation: No root means no topology string.

Hints

  1. This is the same bottom-up aggregation pattern as subtree counting, but now each child returns a string instead of an integer.
  2. 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.

Input: (1, {1: [2, 3], 2: [], 3: []}, {}, {}, {3: 1}, 1)

Expected Output: 3

Explanation: Node 3 ignores the first delivered request, then succeeds on the retry.

Input: (1, {1: [2], 2: []}, {(1, 2): 2}, {}, {}, 1)

Expected Output: -1

Explanation: Two lost requests require three total attempts, but only two are allowed.

Input: (None, {1: [2], 2: []}, {}, {}, {}, 5)

Expected Output: 0

Explanation: No root means nothing to count.

Hints

  1. Use the same request id on every retry of the same parent-to-child request.
  2. 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.

Input: ({10: [11], 11: [], 20: []}, [('X', 10), ('Y', 20)])

Expected Output: [('X', 2), ('Y', 1)]

Explanation: Requests may target unrelated parts of the network.

Input: ({}, [])

Expected Output: []

Explanation: No requests means no work.

Input: ({7: []}, [('N', None), ('S', 7)])

Expected Output: [('N', 0), ('S', 1)]

Explanation: The None-root request returns 0, while a leaf root returns 1.

Hints

  1. A single pending set per node is not enough. Key the state by both node id and request id.
  2. 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.

Input: (None, {}, {}, {})

Expected Output: (0, 0)

Explanation: If there is no root, there are no nodes to count and no time passes.

Input: (5, {}, {}, {})

Expected Output: (1, 0)

Explanation: A single root node already knows its subtree size immediately at time 0.

Input: (1, {1: [2, 3], 2: [4]}, {(1, 2): 0, (1, 3): 0, (2, 4): 0}, {(4, 2): 0, (2, 1): 1, (3, 1): 0})

Expected Output: (4, 1)

Explanation: Several messages are delivered at time 0, so insertion order matters. Node 2 still needs 1 time unit to send its final response to the root, so the root finishes at time 1.

Input: (10, {10: [20], 20: [30], 99: [100]}, {(10, 20): 3}, {(30, 20): 2})

Expected Output: (3, 7)

Explanation: Only nodes reachable from 10 are counted. Delays are: 10->20 = 3, 20->30 = 1 (default), 30->20 = 2, 20->10 = 1 (default), so the root finishes at time 7 with count 3.

Hints

  1. Use a min-heap of scheduled events like (time, sequence_number, message).
  2. A parent's completion time depends on the latest child response delivery, not just on the number of children.
Last updated: May 16, 2026

Loading coding console...

PracHub

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

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • 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 a Distributed Rate Limiter - OpenAI (medium)
  • Compute Plant Infection Time - OpenAI (medium)
  • Implement IP Address Arithmetic - OpenAI (hard)
  • Simulate Infection Spread on a Grid - OpenAI (hard)
  • Implement Social Follow Recommendations - OpenAI (medium)