How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at OpenAI.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at OpenAI during technical interviews.

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.

Hints

Track whether the receiver has already accepted the message once.
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.

Hints

In a tree protocol like this, each edge carries one request downward and one reply upward.
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.

Hints

Keep following parent[start] until you reach -1.
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.

Hints

Build each node's path to the root, then find where those two paths stop matching.
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.

Hints

Keep separate state for what the sender is waiting for and what the receiver has already applied.
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.

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.