PracHub
QuestionsCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • medium
  • OpenAI
  • Coding & Algorithms
  • Software Engineer

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.

Part 1: Reliable Adjacent sendMessage

Two adjacent nodes communicate over an unreliable link. For the i-th send attempt, events[i] = (msg_delivered, ack_delivered). The sender uses stop-and-wait for one message and retries up to max_retries times. The receiver is idempotent: it delivers the message to the application only the first time it receives it. If a packet is not delivered, no ACK can help. If the sender needs more attempts than there are entries in events, all missing attempts behave like (False, False). Return whether the sender eventually gets an ACK, how many attempts were used, and how many times the application received the message.

Constraints

  • 0 <= max_retries <= 200000
  • 0 <= len(events) <= 200000
  • Each events[i] contains exactly two booleans

Examples

Input: ([(True, True)], 3)

Expected Output: (True, 1, 1)

Explanation: The message and ACK both succeed on the first attempt.

Input: ([(True, False), (True, True)], 3)

Expected Output: (True, 2, 1)

Explanation: The first ACK is lost, so the sender retries. The receiver sees a duplicate but delivers to the application only once.

Input: ([(False, False), (False, False)], 2)

Expected Output: (False, 2, 0)

Explanation: The message never reaches the receiver.

Input: ([], 3)

Expected Output: (False, 3, 0)

Explanation: Edge case: no event data is provided, so every attempt fails.

Input: ([(True, False), (False, False), (True, False)], 3)

Expected Output: (False, 3, 1)

Explanation: The receiver gets the message, but the sender never receives an ACK before retries run out.

Hints

  1. Track whether the receiver has already accepted the message once.
  2. The sender stops immediately on the first attempt where both the message reaches the receiver and the ACK reaches the sender.

Part 2: Count Total Nodes with Tree Message Passing

Assume the network is a rooted tree. The root sends COUNT_REQ to every child. Each node forwards COUNT_REQ to its children, waits for all child replies, then sends its subtree size to its parent. Given n, the undirected tree edges, and the root, return (total_nodes, total_messages, total_rounds), where total_messages counts both downward requests and upward replies, and total_rounds is the number of synchronous rounds until the root learns the final answer. For this coding problem, general graphs are out of scope; you may assume the input is a tree.

Constraints

  • 0 <= n <= 200000
  • If n > 0, edges has length n - 1
  • 0 <= root < n when n > 0
  • The input graph is a tree

Examples

Input: (0, [], -1)

Expected Output: (0, 0, 0)

Explanation: Edge case: empty network.

Input: (1, [], 0)

Expected Output: (1, 0, 0)

Explanation: A single-node tree needs no messages.

Input: (5, [(0, 1), (1, 2), (2, 3), (3, 4)], 0)

Expected Output: (5, 8, 8)

Explanation: A chain of height 4 uses 2*(5-1)=8 messages and 2*4=8 rounds.

Input: (7, [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)], 0)

Expected Output: (7, 12, 4)

Explanation: A complete binary tree of height 2 uses 12 messages and 4 synchronous rounds.

Input: (4, [(1, 0), (1, 2), (1, 3)], 1)

Expected Output: (4, 6, 2)

Explanation: The root need not be node 0.

Hints

  1. In a tree protocol like this, each edge carries one request downward and one reply upward.
  2. The completion time in synchronous rounds is determined by the farthest leaf from the root.

Part 3a: Path from a Node to the Root

You are given a rooted tree as a parent array, where parent[i] is the parent of node i and the root has parent -1. Return the path from a given start node up to the root, inclusive. For an empty tree, return an empty list.

Constraints

  • 0 <= len(parent) <= 200000
  • If parent is non-empty, it represents a valid rooted tree
  • If parent is empty, start will be -1

Examples

Input: ([-1, 0, 0, 1, 1], 4)

Expected Output: [4, 1, 0]

Explanation: Node 4 goes to 1, then to root 0.

Input: ([-1], 0)

Expected Output: [0]

Explanation: Edge case: a single-node tree.

Input: ([], -1)

Expected Output: []

Explanation: Edge case: empty tree.

Input: ([2, 2, -1, 1], 3)

Expected Output: [3, 1, 2]

Explanation: The root is node 2, not node 0.

Hints

  1. Keep following parent[start] until you reach -1.
  2. You do not need DFS or BFS because every node already knows its parent.

Part 3b: Path Between Two Arbitrary Nodes

You are given a rooted tree as a parent array, where parent[i] is the parent of node i and the root has parent -1. Return the unique simple path from node u to node v, inclusive. For an empty tree, return an empty list.

Constraints

  • 0 <= len(parent) <= 200000
  • If parent is non-empty, it represents a valid rooted tree
  • If parent is empty, u and v will both be -1

Examples

Input: ([-1, 0, 0, 1, 1, 2], 3, 5)

Expected Output: [3, 1, 0, 2, 5]

Explanation: The path goes up from 3 to the root and then down to 5.

Input: ([-1, 0, 1, 2], 3, 1)

Expected Output: [3, 2, 1]

Explanation: One node is an ancestor of the other.

Input: ([-1, 0, 0, 1], 2, 2)

Expected Output: [2]

Explanation: Edge case: the path from a node to itself is just that node.

Input: ([], -1, -1)

Expected Output: []

Explanation: Edge case: empty tree.

Input: ([2, 2, -1, 1, 1], 4, 0)

Expected Output: [4, 1, 2, 0]

Explanation: The root is node 2.

Hints

  1. Build each node's path to the root, then find where those two paths stop matching.
  2. The last common node on the two root-paths is the lowest common ancestor.

Part 5: Simulate Failure Handling with Retries, ACKs, Idempotency, and Termination

A sender must deliver a sequence of distinct command IDs to one adjacent receiver over an unreliable link. The sender uses stop-and-wait: it keeps retrying the current command until it gets an ACK, then moves to the next command. The receiver is idempotent: each command is applied at most once, even if duplicates arrive. The receiver may also crash permanently. You are given a scripted list of attempt outcomes. For attempt i, events[i] = (received_ids, ack_current, crash). During that attempt, the receiver sees the IDs in received_ids, in order, and applies each unseen valid command once. Then, if crash is True, the receiver crashes permanently before any ACK can reach the sender. Otherwise, ack_current only helps if the sender's current command actually appears in received_ids. If the sender needs more attempts than there are entries in events, missing attempts behave like ([], False, False). Return whether the whole protocol terminates successfully, the index of the first unacknowledged command when it stops, the list of commands actually applied at the receiver in first-application order, and the total number of attempts used.

Constraints

  • 0 <= len(commands) <= 100000
  • 0 <= len(events) <= 100000
  • 0 <= max_retries <= 100000
  • All command IDs are distinct
  • Each ID in received_ids belongs to commands and is either the current command or an older command

Examples

Input: ([], [], 3)

Expected Output: (True, 0, [], 0)

Explanation: Edge case: there is nothing to send, so the protocol is already finished.

Input: ([7], [([7], False, False), ([7, 7], True, False)], 3)

Expected Output: (True, 1, [7], 2)

Explanation: The first ACK is lost, so the sender retries. The receiver applies command 7 only once.

Input: ([1, 2], [([1], True, False), ([1, 1, 2], False, False), ([1, 2], True, False)], 3)

Expected Output: (True, 2, [1, 2], 3)

Explanation: Command 2 is applied before it is ACKed, and stale duplicates of command 1 are ignored.

Input: ([5, 6], [([5], True, False), ([6], True, True)], 3)

Expected Output: (False, 1, [5, 6], 2)

Explanation: The receiver applies command 6 and then crashes before the ACK can be observed.

Input: ([42], [], 2)

Expected Output: (False, 0, [], 2)

Explanation: The sender exhausts retries because no attempt delivers the command.

Hints

  1. Keep separate state for what the sender is waiting for and what the receiver has already applied.
  2. A crash after processing received_ids still means the current command is unacknowledged unless the ACK was observed before the crash, which this model does not allow.
Last updated: May 1, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Consistent Hashing Ring with Virtual Nodes for Shard Rebalancing - OpenAI (hard)
  • Infection Spread Simulation with Death Threshold - OpenAI (medium)
  • Spreading Contagion on a Grid - OpenAI (medium)
  • Streaming Entropy with Numerical Stability - OpenAI (hard)
  • Implement a Distributed Rate Limiter - OpenAI (medium)