1. 題目與適用場景
資料流中的每筆記錄都有正權重，但總筆數和總權重未知。請實作容量為 k 的無放回帶權樣本：每筆記錄最多出現一次，記錄進入最終樣本的機會與其權重成正比，演算法只能單次掃描資料流。說明隨機 key 的構造、如何維護候選集、如何處理極端權重，以及怎樣測試分布是否正確。
2. 面試官考察點
- 是否區分有放回和無放回抽樣，並理解「機率與權重成正比」的定義。
- 是否能用隨機優先級或指數變數把帶權抽樣轉化為保留 top-k key。
- 是否選擇大小為
k的最小堆，給出單筆記錄的O(log k)更新時間。 - 是否處理權重為零、極大或極小、隨機數邊界、重複 ID 和可重現種子。
3. 回答前需要釐清的問題
- 權重是否保證為有限的正數，零權重要丟棄還是保留？
- 需要無放回樣本還是允許同一筆記錄多次出現？
- 只要求最終樣本，還是每個前綴都要保持正確分布？
- 是否需要合併多個分片、持久化狀態或提供可重現的隨機結果？
4. 30 秒回答框架
對每筆權重為 w 的記錄產生獨立隨機 key，並保留最大的 k 個 key。一個穩定做法是抽取 u 屬於 (0, 1] 的均勻隨機數，計算 key = log(u) / w；因為值為負，等價於保留最接近零的 k 個 key。使用大小為 k 的最小堆保存目前樣本，堆頂是最小 key；新 key 更大時替換堆頂。單次掃描時間 O(n log k)，空間 O(k)，權重必須先驗證，隨機來源要可測試。
5. 分步驟深入解答
第一步：明確分布目標
無放回帶權抽樣不是獨立地按 w / total 選擇 k 次，因為那會產生重複記錄。目標是從所有記錄中抽出大小為 k 的集合，其順序統計分布等價於依次從尚未抽中的記錄按剩餘權重抽取。演算法必須讓每個前綴都能解釋為目前資料的樣本，而不是等讀完整個流後再回放。
第二步：生成數值穩定的隨機 key
指數競賽提供一種方便實作：從均勻隨機數 u 生成 key = log(u) / w，再選最大的 key。u 越接近零，log(u) 越負；更大的權重使 key 更接近零，因此更容易進入 top-k。不要直接計算 u ** (1 / w)，極大或極小權重可能導致下溢或失去區分度。
sample_key(weight):
require finite(weight) and weight > 0
u = uniform_random_open_interval()
return log(u) / weight第三步：用最小堆維護 top-k
堆中保存 (key, sequence, item)，其中 sequence 用來打破完全相同的 key。樣本未滿時直接入堆；樣本已滿時比較新 key 與堆頂，只有更大才替換。若 k 為零則直接丟棄所有記錄。不要用排序陣列在每筆記錄後重新排序，否則更新時間會變成 O(k log k)。
第四步：處理輸入和隨機性邊界
拒絕 NaN、無窮和負權重；零權重記錄不會被正權重樣本選中，可直接跳過。隨機來源應避免返回零，否則 log(0) 不可用；可以把零重抽或鉗制到最小正浮點數。重複 ID 仍按記錄出現次數處理，除非題目明確要求按 ID 去重。測試時注入偽隨機來源，讓失敗樣本可重現。
第五步：複雜度、驗證與分散式擴展
n 筆記錄的單機實作時間為 O(n log k)，額外空間為 O(k)。用固定權重的模擬檢驗邊際頻率是否隨權重上升，並檢查樣本沒有重複。分散式情境可以讓每個分片生成同一規則的 key，再由協調器合併各分片的 top-k；但需要明確隨機種子、分片狀態、更新刪除和通訊成本，不能簡單把各分片樣本再次均勻抽樣。
6. 高品質示範回答
我會為每筆正權重記錄生成key = log(u) / w，其中u是開區間上的均勻隨機數，然後保留最大的k個 key。因為 key 為負，權重越大越容易接近零。用容量為k的最小堆保存樣本，堆頂是目前最小 key；新 key 更大時替換堆頂。權重非法、隨機數為零、k 為零和重複記錄都要有明確規則。掃描n筆記錄的時間是O(n log k)，空間是O(k)；用蒙地卡羅頻率和無重複斷言驗證分布，分散式時按相同 key 規則合併 top-k。
7. 常見錯誤
- 每次按
w / total獨立抽取 → 產生重複且不是無放回分布 → 使用隨機 key 的 top-k 方法。 - 直接計算
u ** (1 / w)→ 極端權重下數值下溢 → 使用對數形式比較 key。 - 用最大堆保存 top-k → 還要遍歷堆找最小值 → 使用最小堆讓替換點在堆頂。
- 允許
u = 0→log(0)變成負無窮 → 使用開區間隨機來源或重抽。 - 只測試一組輸出 → 看不出長期偏差 → 做固定權重的多輪模擬並檢查無重複。
8. 追問及應對
追問一：為什麼 key = log(u) / w 能按權重抽樣？
把 -log(u) 看作速率為 1 的指數變數後，除以權重相當於得到速率為 w 的指數變數。最小的指數時間最可能來自更大的速率；把符號取反後就是保留最大的 key，因此 top-k 對應無放回的帶權抽樣。
追問二：如何支援可重現結果？
注入帶明確種子的偽隨機來源，並把記錄唯一識別、權重版本和演算法版本納入實驗元資料。不要依賴執行緒排程或全域隨機狀態，否則同一輸入可能得到不同樣本。
追問三：可以合併兩個已經生成的 reservoir 嗎？
如果兩個分片對各自記錄使用獨立且同分布的 key，可以把兩邊候選的 key 合併並取全域 top-k；直接把兩個最終樣本當作普通資料再次抽樣會遺失被淘汰記錄的資訊。還要處理分片增量、刪除和 key 的持久化。
追問四：權重隨時間變化怎麼辦？
權重變化會改變抽樣分布，舊 key 不能繼續代表新權重。可以重新生成受影響記錄的 key，或把權重版本作為新事件重新進入資料流；更新策略要說明是否接受短暫近似，以及如何回收舊樣本。