FastPrepAggregate Machine Topology
Problems/Aggregate Machine Topology

Aggregate Machine Topology

OpenAI logoOpenAI● MediumFULLTIMEINTERNNEW GRADPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The reports establish cluster-tree node counting and topology aggregation. The recovered report explicitly names asynchronous send/receive callbacks, pending-child aggregation, a topology string, retries with request IDs and cached responses, concurrent-request isolation, and sender implementation with tests. The judged core capabilities are an approximately 90% match. The retained snapshot input, sorted preorder matrix output, numeric bounds, node-local bootstrap, message format, and logical failure schedule are practice adapters, not an original interview signature or wire protocol. An independent new-grad report supplies both sendAsyncMessage() and receiveMessage() methods. Its candidate proposes a TreeNode-like returned root for topology and a visited/processed-node set to avoid processing a retried contribution twice. These are alternative representations of the existing node-local reports and per-request pending-child logic; a single global visited set shared by concurrent requests would not preserve independent results. The judged snapshot/matrix interface remains the FastPrep practice adapter.

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 parentIds is -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.

More OpenAI problems

  • Determine the Winner of Three-Card HandsPHONE SCREEN · Seen Nov 2026
  • Sparse Plant Infection SimulationPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Light Source Hits: Sample, Compare, and FitPHONE SCREEN · Seen Nov 2026
All OpenAI interview questionsSee OpenAI hiring insights
Saved
class Solution {
    public int[][] aggregateMachineTopology(int[] machineIds, int[] parentIds) {
        // Write your code here.
    }
}
Checking account…