Design a distributed tree node counter

Quick Overview

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.

Design a distributed tree node counter

Company: Snowflake

Role: Software Engineer

Category: System Design

Difficulty: medium

Interview Round: Technical Screen

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.

Quick Answer: 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.

|Home/System Design/Snowflake
Snowflake logo
Snowflake
Jul 26, 2025, 12:00 AM
mediumSoftware EngineerTechnical ScreenSystem Design
49
0

Design a distributed tree node counter

Distributed Tree Node Count with Two Messages

You are given an N-ary tree of machines (one process per node). Each node knows its parent (if any) and its list of children. Nodes communicate via asynchronous message passing.

Goal: Design the per-node logic so that when any node initiates a count, exactly two message types (REQUEST_COUNT and REPLY_COUNT) are used to compute the total number of nodes in the entire tree and return it to the initiator. Each node must contribute exactly once; no double counting; protect critical sections.

Assume the runtime invokes call(Node from, Message message) on a node upon message arrival, and the initiator can trigger the protocol locally (e.g., startCount()).

Specify:

(a) Message format and fields.

(b) Per-node state you maintain.

(c) How a node propagates requests to neighbors (parent/children) and aggregates replies.

(d) How you prevent duplicate propagation when a node receives multiple requests for the same traversal.

(e) How the initiator detects termination and returns the global count.

(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.

Clarifying Questions to Ask Guidance

  • Clarify users, core use cases, read/write patterns, scale, latency, availability, and data retention.
  • State explicit assumptions before making sizing or architecture decisions.
  • Prioritize the functional path first, then address reliability, security, observability, and rollout.

What a Strong Answer Covers Guidance

  • A scoped requirements summary with concrete non-goals and success metrics.
  • API, data model, architecture, consistency, capacity, and operations.
  • Reasoned trade-offs among simple and scalable designs, including bottlenecks and failure modes.
  • A validation, monitoring, migration, and launch plan appropriate for the risk level.

Follow-up Questions Guidance

  • What breaks first at 10x traffic or data volume?
  • How would you degrade gracefully during dependency failures?
  • What metrics and alerts would prove the design is healthy after launch?

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...