Aggregate Machine Topology
Problem statement
A cluster snapshot contains one report from every machine. For each index i, machineIds[i] is a unique machine ID and parentIds[i] is the parent machine's ID. Exactly one machine has parent -1; it is the root. The remaining parent relationships form one rooted tree.
Return a canonical topology summary. Each output row is [machineId, parentId, depth, subtreeSize], where depth counts edges from the root and subtreeSize counts the machine itself and every descendant.
Rows must use preorder traversal. When a machine has multiple children, visit them in increasing machine-ID order. The root row therefore exposes the total machine count in its subtreeSize field.
Reported asynchronous form
The report gives a root machine and sendAsyncMessage(nodeId, message), and asks candidates to implement receiveMessage(fromNodeId, message). Machines coordinate requests and responses rather than directly inspecting remote node.children. Each machine tracks pending child replies and a partial count; the root emits the completed aggregate. A topology follow-up produces a structure such as 1(2(4,5),3(6)).
The callable above is the existing FastPrep practice adapter: its finite input describes the network, and its output combines count and topology in rows. The message-based implementation shows a compatible asynchronous simulation. For this exercise, assume setup distributes each machine's own child IDs, while all count and topology information is then exchanged through queued messages. The root reconstructs its rows only from reported node-local descriptors. Queuing a send does not recursively invoke a receiver.
Reported failure and concurrency follow-ups
- Handle node failures with timeout retries, request identifiers, duplicate suppression, and cached responses. A parent's pending-child set ensures a repeated child response contributes only once.
- Keep each request's pending children, partial result, and root reports separate. In a multithreaded environment, synchronize updates to each machine's request state and to the sender queue.
- Implement the asynchronous sender and write tests for the full coordination path.
The practice helper uses explicit logical timeout ticks, re-sends requests only to pending children, and replays completed nodes' cached reports and responses on a logical tick or repeated request. Its tests inject lost messages, duplicate replies, and a transient non-root restart while the root remains alive. An incomplete query remains pending and never returns a partial count as a complete answer. The source does not specify wire fields, timeout durations, storage durability, root-restart recovery, or permanently failed-node results; these demonstration mechanics are authored practice. The public callable runs a healthy finite snapshot and keeps its established output contract.
Function
aggregateMachineTopology(machineIds: int[], parentIds: int[]) → int[][]Examples
Example 1
machineIds = [30,10,20]parentIds = [10,-1,10]return = [[10,-1,0,3],[20,10,1,1],[30,10,1,1]]Machine 10 is the root. Its children are visited as 20 and then 30. The root subtree contains all three machines.
Example 2
machineIds = [7,2,9,1,5,3]parentIds = [3,1,3,-1,2,1]return = [[1,-1,0,6],[2,1,1,2],[5,2,2,1],[3,1,1,3],[7,3,2,1],[9,3,2,1]]The root has children 2 and 3. Machine 2 owns a two-machine subtree, while machine 3 owns a three-machine subtree. Preorder visits each parent's increasing-ID children before returning to later siblings.
Example 3
machineIds = [1,2,3,4,5,6]parentIds = [-1,1,1,2,2,3]return = [[1,-1,0,6],[2,1,1,3],[4,2,2,1],[5,2,2,1],[3,1,1,2],[6,3,2,1]]The original report illustrates topology 1(2(4,5),3(6)). This practice adapter represents that same structure as rows. The root count is 6; machine 2 has subtree size 3, and machine 3 has subtree size 2.
Constraints
1 <= machineIds.length == parentIds.length <= 100000.- Every machine ID is unique and lies in
[0, 10^9]. - Exactly one value in
parentIdsis-1. - Every other parent ID occurs in
machineIds, and all parent relationships form one rooted tree. - The output rows use deterministic preorder with children sorted by increasing machine ID.
Source note: Original new-grad phone-screen report: node counting, topology and retry follow-ups. The image preserves the task text; the callable uses the described FastPrep practice adapter.