Katkat
Back

Implement node messaging and path discovery

OpenAISoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates skills in distributed systems and algorithms, including reliable message-passing between adjacent nodes, graph traversal and path discovery, fault-tolerant protocol design, and message/time complexity analysis.

You have a network where each node knows only its parent and its children and can send messages to its parent and children.

  1. Implement a sendMessage interface that allows reliable delivery between adjacent nodes.
  2. Using only message passing, design an algorithm to count the total number of nodes in the network; state the assumptions (tree vs. general graph) and analyze message/time complexity.
  3. Design a protocol to return the path: (a) from any node to the root, and (b) between two arbitrary nodes.
  4. The network can experience failures (message loss, duplication, reordering, or node crashes). Explain how you would handle failures with timeouts, retries, acknowledgments, idempotent operations, and termination detection; discuss correctness and complexity.