Design a distributed tree node counter
SnowflakeSoftware Engineer · Technical ScreenLast updated
Design a distributed tree node counter evaluates requirements, scale assumptions, API/data design, architecture, trade-offs, failure modes, and rollout in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Consider an N-ary tree where each node runs on a separate machine and represents a distributed component. Each node knows its parent (if any) and its list of children. Implement in the Node class a method call(Node from, Message message) that, using asynchronous message passing, ultimately returns the total number of nodes in the tree to the initiating node. The protocol must use exactly two message types (REQUEST_COUNT and REPLY_COUNT), avoid double counting, protect any critical section, and ensure each node contributes exactly once. Specify: (a) the message format and fields; (b) the per-node state you maintain; (c) how a node propagates requests to children and aggregates replies; (d) how you prevent duplicate propagation when a node receives multiple requests; (e) how termination is detected at the initiator so it can return the global count; and (f) assumptions about concurrency and delivery (e.g., out-of-order messages, at-most-once vs. at-least-once) and the time/message complexity of your approach.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.