Constraints

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

Examples

Solution

def solution(events, max_retries):
    delivered = False
    app_deliveries = 0
    attempts = 0
    for i in range(max_retries):
        attempts += 1
        msg_delivered, ack_delivered = events[i] if i < len(events) else (False, False)
        if msg_delivered:
            if not delivered:
                delivered = True
                app_deliveries = 1
            if ack_delivered:
                return (True, attempts, app_deliveries)
    return (False, attempts, app_deliveries)

Time complexity: O(max_retries). Space complexity: O(1).

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.

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

Solution

def solution(n, edges, root):
    if n <= 0 or root < 0:
        return (0, 0, 0)
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    stack = [(root, -1, 0)]
    count = 0
    height = 0
    while stack:
        node, parent, depth = stack.pop()
        count += 1
        if depth > height:
            height = depth
        for nei in adj[node]:
            if nei != parent:
                stack.append((nei, node, depth + 1))
    messages = 0 if count <= 1 else 2 * (count - 1)
    rounds = 0 if count <= 1 else 2 * height
    return (count, messages, rounds)

Time complexity: O(n). Space complexity: O(n).

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.

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

Solution

def solution(parent, start):
    if not parent or start == -1:
        return []
    path = []
    node = start
    while node != -1:
        path.append(node)
        node = parent[node]
    return path

Time complexity: O(length of path). Space complexity: O(length of path).

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.

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

Solution

def solution(parent, u, v):
    if not parent or u == -1 or v == -1:
        return []
    path_u = []
    node = u
    while node != -1:
        path_u.append(node)
        node = parent[node]
    path_v = []
    node = v
    while node != -1:
        path_v.append(node)
        node = parent[node]
    i = len(path_u) - 1
    j = len(path_v) - 1
    while i >= 0 and j >= 0 and path_u[i] == path_v[j]:
        i -= 1
        j -= 1
    return path_u[:i + 2] + path_v[:j + 1][::-1]

Time complexity: O(height(u) + height(v)). Space complexity: O(height(u) + height(v)).

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.

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

Solution

def solution(commands, events, max_retries):
    if not commands:
        return (True, 0, [], 0)
    valid = set(commands)
    applied_seen = set()
    applied_order = []
    attempts = 0
    event_idx = 0
    cmd_idx = 0
    retries_for_current = 0
    crashed = False

    while cmd_idx < len(commands):
        if crashed or retries_for_current == max_retries:
            return (False, cmd_idx, applied_order, attempts)

        current = commands[cmd_idx]
        attempts += 1
        retries_for_current += 1

        if event_idx < len(events):
            received_ids, ack_current, crash = events[event_idx]
        else:
            received_ids, ack_current, crash = ([], False, False)
        event_idx += 1

        for cmd in received_ids:
            if cmd in valid and cmd not in applied_seen:
                applied_seen.add(cmd)
                applied_order.append(cmd)

        if crash:
            crashed = True
            return (False, cmd_idx, applied_order, attempts)

        if ack_current and current in received_ids:
            cmd_idx += 1
            retries_for_current = 0

    return (True, cmd_idx, applied_order, attempts)

Time complexity: O(total_attempts_used + total number of IDs across processed received_ids). Space complexity: O(len(commands)).

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.