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

题目描述

设计 Amazon 内部消息服务的可靠包传输系统：发送方按序发送数据包，接收方返回 ACK。需要追踪每个包「已发送、已确认、待重传」的状态，处理丢包、乱序 ACK 和重复 ACK。

解题思路

为每个包记录确认状态，用一个集合或位图标记已 ACK 的包序号。收到 ACK 就标记；超时未确认的包触发重传。滑动窗口只允许窗口内的包在途，窗口随 ACK 前进。重复 ACK 用集合去重，不重复推进。

class ReliableSender:
    def __init__(self, window):
        self.window = window
        self.acked = set()
        self.next_seq = 0
        self.base = 0

    def on_ack(self, seq):
        if self.base <= seq < self.next_seq:
            self.acked.add(seq)
            while self.base in self.acked:
                self.acked.discard(self.base)
                self.base += 1

    def in_flight(self):
        return self.next_seq - self.base <= self.window

复杂度与易错点

状态操作 O(1)，空间 O(窗口大小)。重复 ACK 必须幂等，不能重复推进 base；乱序 ACK 先缓存，等 base 连续确认后再整体推进，避免漏掉中间未确认的包。

FAQ

为什么要等 base 连续确认才推进窗口？

滑动窗口按最小未确认序号推进，只有 base 被确认后窗口才能前移；中间若缺一个 ACK，跳过它会误判该包已送达。

参考来源

• LeetCode 239 — Sliding Window Maximum
• LeetCode 622 — Design Circular Queue

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

• 微信：Coding0201
• 邮箱：[email protected]
• Telegram：@OAVOProxy
• WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。