Amazon OA 面试真题解析：Reliable Packet Delivery System（可靠包传输与 ACK 追踪）

Reliable Packet Delivery System

Problem Statement

You are designing a reliable packet delivery system for Amazon’s internal messaging service.

In this system, packets may arrive out of order or some packets may be lost during transmission. Your task is to implement a packet tracking mechanism that:

• Keeps track of received packets by their sequence numbers
• Determines the highest consecutive packet received (for acknowledgment)
• Identifies missing packets that need to be resent

Each packet contains:

• sequence_number: A unique integer identifying the packet’s position in the sequence (starting from 0)
• data: The actual payload of the packet

You need to implement two main functions:

• ReceivePacket(packet): Process a newly received packet
• GetAcknowledgment(): Return the highest consecutive packet sequence received and a list of missing packets that need to be resent

The acknowledgment system follows these rules:

• The highest consecutive packet is the highest sequence number N such that all packets with sequence numbers 0 to N have been received
• Missing packets are those with sequence numbers between 0 and the highest received packet that have not yet been received

Constraints

• Sequence numbers are non-negative integers: 0 <= sequence_number <= 10^5
• The data payload is a string with length between 1 and 1000
• The number of operations will be between 1 and 10^4

这题要求设计一个可靠的包接收与确认机制：每个包有唯一的 sequence number 和 payload，可能乱序到达，也可能缺失。实现时通常用哈希集合或布尔数组记录已收到的序号，再维护当前连续前缀的上界；每次收到新包后，尽可能向前推进“已连续收到的最大序号”，同时在 GetAcknowledgment 中返回最高连续包号以及当前最高收到包号之前尚未到达的缺失序号列表。题目的核心是正确处理乱序、重复包和缺包，数据结构选择上要兼顾 O(1) 级别查询与增量更新。