1. 題目
廣告系統有 N 個候選項目，每個選項的權重表示被抽中的相對機率。初始化後會執行數百萬次單項取樣，要求每次取樣盡量為 O(1)，並允許批次更新權重。請設計並實作 alias table，說明零權重、浮點誤差和亂數邊界。
2. 約束與釐清
- 先討論有放回的單項取樣；不放回取樣和動態單項更新是延伸。
- 權重必須非負且總和大於零；零權重選項不應被抽到。
- 取樣器可以使用均勻亂數整數與
[0, 1)的均勻亂數。 - 權重變更後可以接受
O(N)重建，但不能假裝舊表仍代表新分布。
3. 核心思路
把每個權重正規化為 p_i = w_i * N / sum(w)，平均值為 1。維護長度為 N 的 prob 和 alias 陣列：每個桶先以機率 prob[i] 回傳自身，否則跳轉到 alias[i]。預處理時將小於 1 的桶放入 small，大於 1 的桶放入 large；從兩邊取出一對，把大桶剩餘容量填入小桶，直到所有桶完成。
取樣先均勻選桶 i，再用一次均勻小數與 prob[i] 比較。每個原始選項在多個桶中占據的面積總和等於其正規化機率，因此長期頻率與目標權重成比例。
4. 參考實作
build(weights):
n = len(weights)
scale = n / sum(weights)
scaled = [w * scale for w in weights]
prob = array(n)
alias = array(n)
small, large = [], []
for i, value in enumerate(scaled):
(small if value < 1 else large).append(i)
while small and large:
s = small.pop()
l = large.pop()
prob[s] = scaled[s]
alias[s] = l
scaled[l] -= 1 - scaled[s]
(small if scaled[l] < 1 else large).append(l)
for i in small + large:
prob[i] = 1
alias[i] = i
return prob, alias
sample(prob, alias, rng):
i = rng.uniform_int(0, len(prob))
return i if rng.uniform01() < prob[i] else alias[i]5. 複雜度與正確性
預處理時間和空間都是 O(N)；每次取樣只需一次均勻桶選擇、一次比較和最多一次陣列存取，時間為 O(1)。prob 應限制在 [0, 1]，剩餘浮點誤差可在建立結束時鉗位；亂數整數上界必須明確為半開區間，避免漏掉最後一個桶。
驗證不能只抽幾次觀察結果。應執行足夠樣本，比較每個選項的觀測頻率與目標 w_i / sum(w_i)，使用信賴區間或卡方檢定發現明顯偏差。重建時要原子替換整張表，避免取樣執行緒看到混合版本。
6. 追問與陷阱
- Alias Method 適合靜態或批次更新分布；單個權重頻繁變化時，Fenwick tree 或 segment tree 可能更合適。
- 正規化前總權重溢位會破壞比例，應使用更寬精度或先縮放。
- 「O(1)」不包含重建成本，也不代表亂數生成器本身沒有成本。
- 非負權重總和為零時分布未定義，應拒絕輸入，而不是平均回傳所有選項。
7. 延伸閱讀
可以比較前綴和二分、Fenwick tree、reservoir sampling 和 alias table：前綴結構支援動態更新但取樣為 O(log N)，reservoir 適合串流樣本，alias table 則以 O(N) 預處理換取高吞吐 O(1) 取樣。
8. 面試評分點
能建構 small/large 桶
應說明縮放權重、平均容量為 1，以及如何用小桶和大桶互相填補容量。
能證明取樣機率
應解釋「均勻選桶加一次別名跳轉」如何讓每個選項取得目標總面積，而不是只背程式碼。
能處理數值與邊界
應涵蓋零權重、總和為零、浮點鉗位、亂數整數半開區間和表版本原子替換。
能判斷資料結構取捨
應比較批次重建與動態更新成本，說明何時選 Fenwick tree 或前綴和，而非盲目使用 alias table。