1. 題目
日誌平台持續收到事件鍵（例如 URL 或商品 ID），總量可能達到數十億筆。請在固定記憶體內實作 add(key) 與 estimate(key)，回傳鍵的近似出現次數；說明誤差、分片合併、計數器溢位，以及何時必須使用精確結構。
2. 約束與釐清
- 事件只能走過一次，不能把所有鍵放進雜湊表。
- 允許估計值偏大，但希望用參數控制誤差機率。
- 先討論非負計數；刪除、負權更新和依時間到期需要額外限制。
- 分片必須使用相同寬度、深度、雜湊種子和計數器編碼，才能直接合併。
3. 核心思路
Count-Min Sketch（CMS）維護 d 列、每列 w 欄的非負計數器。每列使用獨立雜湊函式把鍵映射到一欄；更新時所有對應計數器加一，查詢時取這些計數器的最小值。真實鍵的計數會出現在每列對應位置，其他鍵的碰撞只會增加計數，所以最小值是不會低估的上界。
常見參數以誤差 epsilon 和失敗機率 delta 表示：w = ceil(e / epsilon)，d = ceil(ln(1 / delta))。總更新量為 N 時，查詢值以至少 1 - delta 的機率不超過真實值加上 epsilon * N；這是機率誤差界，不是每次查詢的絕對保證。
4. 參考實作
init(epsilon, delta):
w = ceil(e / epsilon)
d = ceil(ln(1 / delta))
table = array(d, w, fill=0)
seeds = choose_d_independent_seeds()
add(key, weight=1):
require weight >= 0
for row in 0..d-1:
col = hash(key, seeds[row]) mod w
table[row][col] += weight
total += weight
estimate(key):
values = []
for row in 0..d-1:
col = hash(key, seeds[row]) mod w
values.append(table[row][col])
return min(values)
merge(other):
require same w, d, seeds, counter encoding
for each cell (r, c):
table[r][c] += other.table[r][c]
total += other.total5. 複雜度與正確性
每次更新和查詢都存取 d 個單元，時間複雜度為 O(d)；空間複雜度為 O(d * w)，與不同鍵的數量無關。非負更新下，查詢取最小值仍不低於真實頻率。增加寬度可減少碰撞偏差，增加深度可降低超過誤差界的機率，但會線性增加記憶體和雜湊成本。
計數器必須選擇足夠寬的整數，或明確採用飽和策略；無號溢位會讓「不會低估」的性質失效。分片合併應逐單元相加，且參數和雜湊映射完全一致；直接合併不同配置會得到無法解釋的結果。
6. 追問與陷阱
- CMS 能回答「某個已知鍵大約出現多少次」，不會自動列出 Top-K；需要另一個候選集合或 heavy-hitter 結構。
- 碰撞只造成高估，不能從估計值反推出精確頻率或精確去重集合。
- 負權更新會破壞單調性和簡單誤差證明；刪除與滑動視窗通常需要時間分桶或可衰減結構。
- 不同時間視窗不能只把舊計數減掉，除非同時保存可回滾的分桶狀態。
7. 延伸閱讀
可以比較 CMS 與精確雜湊表、Bloom filter、HyperLogLog 和 Frequent Items Sketch：它們分別解決頻率查詢、成員判斷、基數估計和高頻項目辨識。面試時應依查詢目標、誤差預算、是否需要刪除，以及是否要輸出候選鍵來選擇結構。
8. 面試評分點
能畫出二維計數器
應說明每列獨立雜湊、更新所有列、查詢取最小值，並能解釋碰撞為何只會抬高計數。
能給出誤差參數
應把 epsilon、delta、w、d 與總更新量 N 連結起來，區分機率界和絕對精確保證。
能處理工程邊界
應討論計數器溢位、分片參數一致性、合併時逐單元相加，以及負權和滑動視窗的額外設計。
能判斷結構是否匹配
應指出 CMS 不提供 Top-K、精確名單或精確基數；需求改變時能選擇精確表、HLL 或 heavy-hitter 結構。