Google VO 面試題：UDP 亂序數據包重組 Sequencer 設計（哈希表 + 序號推進）

Google VO 常考系統設計與編碼結合的題型。這道題考察在 UDP 不可靠傳輸場景下，如何實現一個能按序號嚴格連續輸出數據的 Sequencer 組件，背景來自日誌系統、實時流處理、分布式 replication 等真實場景。

---

題目背景

UDP 不保證順序，數據包可能亂序、重複或丟失。上游持續發送 (data, seq_num) 片段，需要在接收端實現 Sequencer：

• 嚴格按 seq_num 從小到大連續輸出。
• 中間序號未到達時，緩存後續數據，等缺失數據到達後再一併輸出。

---

思路

哈希表 + next_seq 指針

• dict 緩存已收到但暫時無法輸出的片段（key = seq_num，value = data）。
• next_seq 記錄當前期望輸出的序號。

每次收到新片段：

1. 存入哈希表（去重：seq < next_seq 或已存在則忽略）。
2. 循環：若 next_seq 在哈希表中，輸出並 next_seq += 1；否則停止。

---

程式碼

class Sequencer:
    def __init__(self):
        self.buffer = {}
        self.next_seq = 0
        self.output = []

    def receive(self, seq_num: int, data: str):
        if seq_num < self.next_seq or seq_num in self.buffer:
            return
        self.buffer[seq_num] = data
        while self.next_seq in self.buffer:
            self.output.append(self.buffer.pop(self.next_seq))
            self.next_seq += 1

    def get_output(self):
        return self.output

---

Dry Run

接收順序：(2,"C") → (0,"A") → (1,"B") → (3,"D")

操作	buffer	next_seq	output
receive(2,"C")	{2:"C"}	0	[]
receive(0,"A")	{2:"C"}	1	["A"]
receive(1,"B")	{}	3	["A","B","C"]
receive(3,"D")	{}	4	["A","B","C","D"]

最終有序輸出：A → B → C → D ✓

---

複雜度分析

• 時間：O(1) 均攤（每個包最多存取各一次），總體 O(n)。
• 空間：O(k)，k 為當前緩存的亂序包數量。

---

Follow-up：丟包處理策略

策略一：超時重傳請求（ARQ）

若 next_seq 等待超過閾值，向發送端發送重傳請求（NACK）。適合日誌、replication 等數據完整性優先場景。

import time

class SequencerWithTimeout(Sequencer):
    def __init__(self, timeout=5.0):
        super().__init__()
        self.wait_start = None
        self.timeout = timeout

    def receive(self, seq_num, data):
        super().receive(seq_num, data)
        if self.next_seq not in self.buffer:
            if self.wait_start is None:
                self.wait_start = time.time()
        else:
            self.wait_start = None

    def check_timeout(self):
        if self.wait_start and time.time() - self.wait_start > self.timeout:
            return self.next_seq  # 需要重傳的 seq
        return None

策略二：跳過丟失序號（Skip & Forward）

直播、實時音視頻等低延遲場景，等待不可接受。直接跳過丟失序號，插入佔位符，推進到下一個已緩存的序號。

def skip_missing(self):
    if not self.buffer:
        return
    next_available = min(self.buffer.keys())
    self.output.append(None)  # 佔位符，表示丟失
    self.next_seq = next_available
    while self.next_seq in self.buffer:
        self.output.append(self.buffer.pop(self.next_seq))
        self.next_seq += 1

策略對比

策略	適用場景	優點	缺點
超時重傳（ARQ）	日誌、replication	數據完整	延遲增加
跳過丟失（Skip）	直播、實時音視頻	低延遲	數據不完整

---

延伸討論

• 重複包：seq_num < next_seq or seq_num in buffer 已去重。
• 滑動窗口：可加入最大緩衝區限制，防止內存無限增長。
• 多線程：生產環境需對 buffer 和 next_seq 加鎖保護。

---

需要 VO 輔助？

Google、Amazon、TikTok、微軟、Meta、Uber 等方向 VO 實時輔助持續進行中。

微信：Coding0201

#轉碼 #Google面試 #26ng #sde找工 #西雅圖找工 #VO輔助 #面經

---

聯繫方式

Email: [email protected]
Telegram: @OAVOProxy