Async N-ary Cluster Count

PracticalmediumPremium

45:00

Desktop only

Coding Challenges are optimized for Desktop

Come back on a wider screen - the live editor needs room to breathe. You can still read the problem brief above.

Problem

Distributed systems count live nodes for health checks, capacity estimates, and leader election. Each node knows only its direct children, so counting is a fan-out query that aggregates upward. The interesting constraint: child queries must run concurrently - sequential execution makes wall-clock time proportional to the total node count rather than tree depth.

Level 1 - Concurrent fan-out

Each node returns 1 + sum(child counts). Child counts must run concurrently - wall-clock time must be O(depth), not O(total nodes).

Example:

Node("root", [
    Node("a", []),
    Node("b", [Node("c", [])])
])
count() == 4   # root + a + b + c

Level 2 - Failure handling

Some children may fail (the underlying RPC raised). Add:

async def count_safe(self) -> int:
    """Skip failed subtrees and count what succeeded."""

Collect results from every child even when some raise - one failing subtree must not abort the others. Treat any exception as "this subtree contributes 0".

Example:

Node("root", [
    Node("alive", []),
    FailingNode("dead", [Node("lost1", []), Node("lost2", [])])
])
count_safe() == 2   # root + alive; the failing subtree contributes 0

Level 3 - Predicate-filtered count

async def count_where(self, predicate) -> int:
    """Count only nodes for which predicate(node) is True. Predicate is synchronous."""

Same fan-out shape; just skip adding 1 for the current node when the predicate rejects it.

Example:

tree = Node("root", [Node("a", []), Node("b", [Node("c", [])])])
# predicate: only count nodes named "a" or "c"
count_where(lambda n: n.name in {"a", "c"}) == 2

Patterns used

Foundations primers this challenge draws on.

DFS

Recursion

Trees

Loading editor...

The live editor for this challenge unlocks with Premium.

Browse free problems

0/0 passed