Implement node messaging and path discovery
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
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.
Quick Answer: 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.