題幹與適用場景
輸入只能順序讀取一次，長度 n 事先未知，目標是等機率選出 k 個不同元素。不能先把全部元素放入陣列，也不能讀完後才隨機選索引。Reservoir Sampling 用固定大小為 k 的 reservoir 解決：第 i 個元素抵達時，以 k/i 機率讓它進入樣本，並隨機替換目前樣本的一個位置。
這道題考察隨機化串流演算法。Vitter 論文研究未知總長度的單次抽樣，大學課程資料給出均勻性歸納證明。核心分類是 coding，考察機率不變量與空間約束，不因應用在日誌或資料平台改成 data。
面試官考察點
- 能否從「未知 n、單遍、固定記憶體」辨識 reservoir pattern。
- 能否先說清
k=1的1/i替換機率，再推廣到k。 - 能否證明處理完第
i個元素後，每個元素入樣機率都是k/i。 - 能否避免重複抽樣、錯誤的預知
k/n假設與有偏隨機數。 - 能否說明時間
O(n)、空間O(k)與加權抽樣邊界。
回答前需要釐清的問題
k是否為正整數？若k <= 0或超過流長度，回傳約定為何？- 元素是否可重複？「不同元素」是不同紀錄還是按值去重，必須先定義。
- 資料流可能為空、無限長或中途失敗嗎？輸出與可恢復策略不同。
- 需要最終樣本還是即時查看目前樣本？即時查看不應改變均勻性證明。
- 隨機數產生器提供
[0,1)還是無偏整數？不能直接假設取模無偏。 - 抽樣是否帶權或需要分層？加權目標不再是等機率 reservoir。
30 秒回答框架
「先處理前 k 個元素填滿 reservoir。第 i 個元素（從 1 開始）抵達後產生均勻整數 j，範圍 [0, i-1]；若 j < k，就用新元素替換 reservoir[j]，否則丟棄。處理完 i 個元素後，每個元素都以 k/i 機率在樣本中：新元素直接以 k/i 進入，舊元素以 k/(i-1) 留存並乘上 1 - 1/i。單遍時間 O(n)，空間 O(k)。」
分步驟深入解答
第一步：從 k=1 開始。
第一個元素必選；第 i 個元素以 1/i 機率替換目前候選。處理完 i 個元素後，每個元素留存機率相同，都是 1/i。
第二步：推廣到 k 個。
前 k 個元素先填入 reservoir。之後第 i 個元素以 k/i 機率進入；一旦進入，在 k 個槽位中均勻選一個替換。使用整數隨機數 j ∈ [0, i-1] 時，j < k 就替換槽位 j。
第三步：寫出偽程式。
reservoir = first k items
for i = k+1 .. n:
j = uniformInteger(0, i-1)
if j < k:
reservoir[j] = item i
return reservoir若資料流不能先填充，在 seen <= k 時追加元素，之後使用相同分支。整數隨機數必須涵蓋完整區間且無偏。
第四步：證明新元素機率。
處理第 i 個元素時，它被選入機率是 k/i。進入後不再被替換的機率是後續每一步都不替換它：第 t 步替換某個特定槽位的機率是 1/t，留存機率為 ∏(1 - 1/t) = i/n；最終機率為 k/i × i/n = k/n。
第五步：證明舊元素機率。
歸納假設第 i-1 步每個舊元素在 reservoir 的機率是 k/(i-1)。第 i 步它被保留機率為 1 - (k/i × 1/k) = 1 - 1/i，所以為 k/(i-1) × (i-1)/i = k/i。新舊元素都滿足同一不變量。
第六步：複雜度與隨機實作。
每個元素只處理一次，時間 O(n)；reservoir 存 k 個元素，額外空間 O(k)。i 超過安全整數範圍時，使用支援大整數範圍的無偏隨機 API，避免浮點精度破壞機率。
第七步：輸入邊界。
空流回傳空樣本；k = 0 回傳空樣本或拋出約定例外；k > n 在未知 n 的流中只能在結束後回傳實際數量或報錯。若按值去重，需要額外集合，空間可能不再是 O(k)。
第八步：加權與分散式擴充。
加權抽樣需按權重定義目標分布，不能沿用等機率替換；可討論 weighted reservoir 或 Efraimidis-Spirakis key。分散式場景要合併各分片樣本並攜帶數量/權重，直接串接各節點 reservoir 會產生偏差。
高品質示範回答
「我會維護容量為 k 的 reservoir。先填入前 k 個元素；從第 i = k+1 個開始，產生無偏整數 j ∈ [0, i-1]。若 j < k，就用目前元素替換第 j 個槽位，否則丟棄。第 i 個新元素進入機率是 k/i；進入後每個槽位等可能，因此任一舊元素在這一步被替換的機率是 1/i，留存機率為 (k/(i-1)) × (1-1/i) = k/i。歸納可得處理完 n 個元素後，每個元素都有 k/n 的入樣機率。演算法單遍 O(n) 時間、O(k) 空間。我會驗證空流、k=1、k=0、重複紀錄與多次模擬頻率，並明確加權或分散式擴充需要重新證明。」
常見錯誤
- 先存完整資料流再抽樣 → 違反未知長度與記憶體約束 → 邊讀邊維護 reservoir。
- 第 i 個元素總以
1/k進入 → 機率隨 i 變化而失真 → 使用k/i。 - 使用
random() % i→ 範圍不整除時有偏 → 使用無偏整數抽樣。 - 替換槽位不均勻 → 某些樣本組合機率較高 → 在 k 個槽位中均勻選擇。
- 把
k/n當作處理中的進入機率 → n 未知且每步不同 → 依目前計數 i 更新。 - 忽略重複值定義 → 「不同」可能指紀錄或數值 → 先釐清去重語義。
- 宣稱分片樣本直接串接仍均勻 → 分片大小不同造成偏差 → 攜帶數量並重新合併。
- 加權場景繼續用等機率演算法 → 目標分布改變 → 使用加權 reservoir 並給出新證明。
追問及應對
追問一：為什麼新元素的替換機率是 k/i？
第 i 個元素抵達時，演算法從 i 個位置中均勻選一個，前 k 個位置代表 reservoir；命中這 k 個位置的機率就是 k/i。
追問二：k=1 時如何證明公平？
第一個元素機率為 1；第 i 個新元素以 1/i 替換。任一舊元素以 (1/(i-1)) × (1-1/i) = 1/i 留存，因此歸納成立。
追問三：如何產生無偏整數隨機數？
使用語言提供的均勻整數 API，或採拒絕抽樣丟棄超出最大可整除區間的隨機值。不要假設簡單取模總是無偏。
追問四：如果流長度小於 k 怎麼辦？
讀到流結束時回傳所有實際元素，或依介面約定報錯。不能憑空填充樣本，並要在題目前說明行為。
追問五：如何抽取帶權樣本？
先定義每個元素的權重目標，再使用 weighted reservoir 的隨機 key 或指數/對數轉換；均勻 reservoir 的 k/i 證明不能直接沿用。
追問六：如何合併分散式 reservoir？
各分片需攜帶已讀數量及足夠的隨機優先級或權重，合併時按全域抽樣規則重新選擇。直接等量串接或隨機截斷會偏向小分片。
追問七：如何驗證均勻性？
對固定短流重複執行大量次，統計每個元素入樣頻率並與 k/n 比較；同時測邊界與隨機種子可重現性。統計檢驗只能發現實作偏差，不能取代機率證明。