How should I practice Distributed Tree Counting State Machine?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Snowflake phone screen problems in FastPrep.

Is Distributed Tree Counting State Machine associated with Snowflake?

FastPrep tags this as a Snowflake phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Tree

Distributed Tree Counting State Machine

Learn this problem

● Medium

SnowflakeFULLTIMEPHONE SCREEN

See Snowflake hiring insights

Problem statement

Simulate a nonblocking count protocol over a rooted tree. Node i knows only its parent, its direct children, and local aggregation state. The array parent defines the tree: node 0 is the root, and for each i > 0, parent[i] is its parent.

The harness starts one GET_COUNT request at the root. An internal node that receives GET_COUNT asynchronously sends the same request to each child in increasing node-id order. A leaf immediately reports 1 to its parent. An internal node waits without blocking across separate message deliveries, then reports 1 plus all child counts after every child has responded. The root exposes that total instead of sending it upward.

Messages are delivered exactly once by one FIFO queue. Record each call to sendAsync as from->to:GET_COUNT or from->to:REPORT_COUNT:value. After the root completes, append ROOT_COUNT:value. Return the complete trace.

Unreliable-network follow-up

In a real unreliable network, attach a request identifier to every message, make reports idempotent per child and request, acknowledge messages, retry unacknowledged messages with a bounded policy, and retain completed-request state long enough to answer duplicates. These reliability mechanisms are discussion requirements and do not change the judged FIFO outputs.

Function

simulateTreeCount(parent: int[]) → String[]

Examples

Example 1

parent = [-1,0,0,1,1]return = ["0->1:GET_COUNT","0->2:GET_COUNT","1->3:GET_COUNT","1->4:GET_COUNT","2->0:REPORT_COUNT:1","3->1:REPORT_COUNT:1","4->1:REPORT_COUNT:1","1->0:REPORT_COUNT:3","ROOT_COUNT:5"]

The root first contacts nodes 1 and 2. FIFO delivery lets node 1 enqueue requests to its children before node 2 reports. Node 1 reports only after both child reports arrive, and the root then completes with all five nodes.

Example 2

parent = [-1]return = ["ROOT_COUNT:1"]

The root is also a leaf, so it completes immediately without sending a message.

Constraints

1 <= parent.length <= 500
parent[0] == -1.
For every i > 0, 0 <= parent[i] < i, so the input is one rooted tree and children are discovered in increasing node-id order.
The judged base simulation has one active request and delivers each emitted message exactly once in FIFO order.