这是一道来自 Amazon 的系统设计型编程题。题目模拟内部消息服务中的数据包传输场景，重点考察候选人如何处理乱序到达、数据包丢失、连续确认以及缺失数据识别。

英文原题

Reliable Packet Delivery System

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:

1. Keeps track of received packets by their sequence numbers
2. Determines the highest consecutive packet received for acknowledgment
3. 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:

1. ReceivePacket(packet): Process a newly received packet
2. GetAcknowledgment(): Return the highest consecutive packet sequence number 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

• 0 ≤ sequence_number ≤ 10^5
• The data payload is a string with length between 1 and 1000
• The number of operations is between 1 and 10^4

题目思路

这道题的核心不是保存数据内容，而是维护两个状态：

一个是当前已经连续收到的位置，例如已经收到 0、1、2，那么最高连续序号就是 2；另一个是目前见过的最大序号，用来判断中间有哪些数据包缺失。

例如数据包按照下面的顺序到达：

0 → 2 → 4 → 1

收到 0 后，最高连续序号是 0。

收到 2 后，因为 1 还没有到达，所以最高连续序号仍然是 0，缺失的数据包是 [1]。

收到 4 后，缺失列表变成 [1, 3]。

收到 1 后，0、1、2 已经全部收到，因此最高连续序号可以直接推进到 2，此时只剩下数据包 3 需要重传。

实现时可以使用集合或布尔数组记录已经收到的序号，同时维护一个指针，表示下一个期望收到的数据包。每当新数据包到达，就检查这个指针是否可以继续向后移动。

容易出错的地方

很多候选人会把“收到的最大序号”和“最高连续序号”混为一谈。

例如已经收到：

0, 1, 2, 5

最大序号是 5，但最高连续序号只能是 2。因为 3 和 4 尚未收到，系统不能直接确认到 5。

另外还需要考虑重复数据包。真实网络环境中，同一个数据包可能因为重传而被多次接收，程序不能因此重复更新状态或产生错误结果。

如果每次调用 GetAcknowledgment() 都从 0 开始扫描所有序号，虽然可能通过基础测试，但在数据量增大后效率会明显下降。更好的方案是持续维护连续确认指针和缺失集合。

面试官关注点

这道题主要考察候选人是否能够把网络传输场景转化为清晰的数据结构问题，以及是否能正确区分：

• 最大已接收序号
• 最大连续确认序号
• 当前缺失序号
• 重复和乱序数据包

进一步讨论时，面试官还可能追问线程安全、内存限制、缺失列表过大、确认信息压缩，以及如何支持多个独立的数据传输会话。

类似 Amazon 这类题目，真正的难点通常不是写出基础代码，而是在面试过程中快速理解规则、发现边界条件，并清楚解释自己的方案。

CSOAHELP 提供海外科技公司面试实时文本辅助和 Mock Interview 服务，覆盖 Amazon、Google、Meta、TikTok、Stripe 等公司。面试过程中可通过纯文本实时获得题意分析、解题思路、复杂度优化和追问应对建议，帮助候选人更稳定地完成技术面试。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~