題目與適用情境
一個整數 ID 串流持續抵達。add(x) 記錄 ID x 新出現一次；topK(k) 回傳目前頻次最高的至多 k 個不同 ID 及其頻次，同頻 ID 的順序不限，k 每次查詢可以不同。請為讀多寫少和寫多讀少兩種負載設計精確方案，分析時間與空間複雜度；若不同 ID 數量可能無限增長且記憶體固定，再提出近似方案及其誤差意義。
這道題適用於軟體工程和演算法職缺。精確部分只處理頻次遞增，不包含刪除、滑動視窗或分散式合併。令 N 為累計更新數，D 為不同 ID 數，且通常 k << D。公開面試題原文同時要求比較讀寫負載，並把有限記憶體串流近似列為延伸，因此不能只背「雜湊表加最小堆積」。
面試官評估重點
第一，候選人是否先確認操作契約和負載比例。只在串流結束時查詢一次的工作，與每次寫入後都查詢的線上排行榜，不該使用同一種維護成本。
第二，能否提出複雜度和狀態一致的方案。雜湊表計數後在查詢時建立大小為 k 的最小堆積，add 的期望時間為 O(1)，topK 為 O(D log k)；若宣稱每次更新堆積都是 O(log k)，還必須維護堆積內位置，並解釋堆積外元素何時進入。
第三，能否證明動態結構正確。強回答會說清楚三個不變量：每個 ID 只屬於一個頻次 bucket；bucket 頻次嚴格遞增且沒有空 bucket；ID 所在 bucket 的頻次等於它的真實累計次數。複雜度結論必須依賴這些不變量。
第四，能否區分精確 top-k、高頻項目與頻次估計。Space-Saving 可以在固定計數器下提供候選項目及上下界；Count-Min Sketch 主要回答指定 ID 的近似頻次，本身不保存可列舉的 ID 集合。把 sketch 單獨當成 top-k 清單，會漏掉「候選鍵從哪裡取得」這一步。
回答前需要釐清的問題
k固定還是每次可變？ 固定K可以維護帶位置索引的大小K堆積；任意k更適合按頻次排序的結構。- 更新和查詢比例是多少？ 寫多查少時把工作延後到查詢比較省維護成本；查詢頻繁時值得在每次
add中維護順序。 - 同頻項目需要固定順序嗎？ 本題允許任意順序，所以 bucket 內用雜湊集合即可；若要求 ID 升冪，bucket 內要換成有序集合，更新成本不再是期望
O(1)。 - 是否有刪除或時間視窗？ 只有遞增時，元素只從頻次
f移到相鄰的f + 1；刪除會增加反向移動，視窗還需要保存過期事件。 D是否放得進記憶體？ 一般分布下的精確答案需要保留所有不同 ID 的頻次。記憶體固定時必須接受近似結果，或增加可重播的第二遍。- 允許哪一種誤差？ 「大致正確」無法驗收。應明確是頻次加性誤差、候選集合可能不確定，或是在頻次間隔夠大時保證 top-k。
- 計數會不會溢位？ 長期服務需要 64 位或更寬的計數器；範例使用 JavaScript
number，只在安全整數範圍內保證精確計數。
30 秒回答架構
「我會先確認 k 是否可變、讀寫比例、同頻排序和記憶體上限。寫多查少時，用雜湊表做期望 O(1) 的 add，查詢時掃描 D 個頻次並維護大小 k 的最小堆積，成本 O(D log k)。若任意 k 的查詢很頻繁，我會維護按頻次遞增的雙向 bucket 鏈結串列和 ID → bucket 雜湊表；一次更新只把 ID 從 f bucket 移到相鄰的 f + 1 bucket，所以期望 O(1)，從尾端取 k 個結果為 O(min(k, D))，空間 O(D)。若 D 無法放入記憶體，我會用 Space-Saving 保留固定數量的帶誤差計數器，只在上下界分離時宣稱 top-k 有保證；Count-Min Sketch 還需要額外候選集合才能列舉答案。」
分步深入解析
第一步：先列出隨負載改變的精確方案
| 方案 | add | topK(k) | 空間 | 適用條件 | |---|---:|---:|---:|---| | 雜湊計數，查詢時建立最小堆積 | 期望 O(1) | O(D log k) | O(D + k) | 寫多查少，實作最簡單 | | 帶位置索引的固定 K 最小堆積 | O(log K) | O(K)，若需排序則為 O(K log K) | O(D + K) | 查詢永遠使用同一個 K | | 平衡樹按 (頻次, ID) 排序 | O(log D) | O(k + log D) | O(D) | 需要固定同頻順序或最壞界限 | | 雜湊定位 + 雙向頻次 bucket | 期望 O(1) | O(min(k, D)) | O(D) | k 可變且查詢頻繁 |
「雜湊表 + 最小堆積」不是唯一答案。它把排序成本放在查詢端，正好適合寫多查少。若每次 add 後都要顯示排行榜，反覆掃描 D 個鍵會成為瓶頸，頻次 bucket 才值得承擔較高的實作複雜度。
第二步：建立頻次 bucket 不變量
bucket 鏈結串列按頻次由小到大排列；每個 bucket 保存該頻次的一組 ID。另一個雜湊表把 ID 直接定位到 bucket。新增 ID 進入頻次 1 bucket；既有 ID 從 f bucket 移到 f + 1 bucket。因為一次更新只增加 1，新 bucket 只可能位於原 bucket 和其後繼之間，不需要搜尋整條鏈結串列。舊 bucket 變空時立即刪除。
三個不變量足以證明結果：
locations中每個 ID 恰好出現在一個 bucket 的集合裡。- 每個非空 bucket 的
frequency等於其中所有 ID 的真實頻次。 - 從
head到tail的頻次嚴格遞增。
因此從 tail 往前列舉時，任何尚未輸出的 ID 都不會比已輸出的 ID 更高頻；同頻順序由題目允許任意。每個經過的 bucket 至少輸出一個元素，所以查詢拜訪的 bucket 數不超過輸出數，時間為 O(min(k, D))。
第三步：實作精確的任意 k 查詢
interface Bucket {
frequency: number;
values: Set<number>;
prev: Bucket | null;
next: Bucket | null;
}
interface TopKEntry {
value: number;
count: number;
}
class FrequencyIndex {
private readonly locations = new Map<number, Bucket>();
private head: Bucket | null = null;
private tail: Bucket | null = null;
add(value: number): void {
const source = this.locations.get(value);
if (!source) {
let target = this.head;
if (!target || target.frequency !== 1) {
target = this.insertBefore(this.head, 1);
}
target.values.add(value);
this.locations.set(value, target);
return;
}
let target = source.next;
if (!target || target.frequency !== source.frequency + 1) {
target = this.insertAfter(source, source.frequency + 1);
}
source.values.delete(value);
target.values.add(value);
this.locations.set(value, target);
if (source.values.size === 0) {
this.removeBucket(source);
}
}
topK(k: number): TopKEntry[] {
if (!Number.isInteger(k) || k < 0) {
throw new RangeError("k must be a non-negative integer");
}
const result: TopKEntry[] = [];
let bucket = this.tail;
while (bucket && result.length < k) {
for (const value of bucket.values) {
result.push({ value, count: bucket.frequency });
if (result.length === k) break;
}
bucket = bucket.prev;
}
return result;
}
private insertBefore(next: Bucket | null, frequency: number): Bucket {
const bucket: Bucket = {
frequency,
values: new Set<number>(),
prev: next?.prev ?? null,
next,
};
if (bucket.prev) bucket.prev.next = bucket;
else this.head = bucket;
if (next) next.prev = bucket;
else this.tail = bucket;
return bucket;
}
private insertAfter(prev: Bucket, frequency: number): Bucket {
const bucket: Bucket = {
frequency,
values: new Set<number>(),
prev,
next: prev.next,
};
if (prev.next) prev.next.prev = bucket;
else this.tail = bucket;
prev.next = bucket;
return bucket;
}
private removeBucket(bucket: Bucket): void {
if (bucket.prev) bucket.prev.next = bucket.next;
else this.head = bucket.next;
if (bucket.next) bucket.next.prev = bucket.prev;
else this.tail = bucket.prev;
}
}程式碼的複雜度採用 Map 與 Set 常見的期望常數時間假設，不是 JavaScript 規範承諾的嚴格最壞 O(1)。topK(0) 回傳空陣列，k > D 回傳所有 ID，非法負數或非整數 k 會拋出錯誤。
第四步：記憶體固定時說清楚近似保證
精確雜湊表的空間會隨 D 增長。Space-Saving 改為只維護 m 個「ID、估計頻次、最大誤差」計數器，並要求 m > k 才能比較第 k + 1 個邊界候選：已監控 ID 抵達時遞增；未監控 ID 抵達且計數器已滿時，取代目前最小估計頻次為 cmin 的 ID，把新 ID 的估計值設為 cmin + 1，誤差記為 c_min。
對每個仍被監控的 ID，真實頻次位於 [估計值 - 誤差, 估計值]；論文給出的最大高估不超過 N / m。若前 k 個候選的最小下界都不小於第 k + 1 個候選的估計上界，就能依目前摘要證明 top-k 集合；邊界重疊時只能回報近似候選，不能把估計排序包裝成精確答案。若整個串流的 D <= m，沒有發生取代，計數就是精確的。
Count-Min Sketch 使用固定的 width × depth 計數陣列。取 width = ceil(e / ε)、depth = ceil(ln(1 / δ)) 時，對只增不減的串流，指定 ID 的估計值不會低於真實值，並以至少 1 - δ 的機率不超過 真實值 + εN。它不保存 ID，因此還要搭配候選堆積、候選集合或可列舉範圍；只建立 sketch 無法直接回答「有哪些 top-k」。
第五步：用對照實作驗證，不只測範例
先用序列 [1, 2, 1, 3, 2, 1] 驗證 topK(2) 回傳頻次 3 和 2 的兩個 ID。再覆蓋空結構、k = 0、k > D、全部同頻、單一熱門項目加大量只出現一次的 ID，以及一個 ID 連續跨越多個 bucket。
最後產生隨機更新串流，以樸素雜湊計數加完整排序作為 oracle。每隔若干次更新比較：回傳長度為 min(k, D)；ID 不重複；每個頻次正確；任何未選 ID 的頻次不高於已選集合的最小頻次。本文實作已用 10,000 次確定性隨機更新和多個 k 值完成這項對照。
高品質示範回答
「我先把契約限定為只增不減、k 每次可變、同頻任意順序。若寫入很多而查詢很少，我只維護 ID → 頻次 雜湊表，add 期望 O(1)；查詢時掃描 D 個 ID，用大小 k 的最小堆積，時間 O(D log k)、額外空間 O(k)。
如果排行榜查詢頻繁，我會用雙向頻次 bucket。bucket 由低頻到高頻排列，每個 bucket 放同頻 ID，再用雜湊表把 ID 定位到 bucket。一次 add 只會從 f 移到 f + 1，所以只檢查相鄰 bucket，空 bucket 立即刪除。這樣更新是期望 O(1)，從尾端 bucket 往前取結果為 O(min(k, D))，總空間 O(D)。正確性依賴每個 ID 唯一歸 bucket、bucket 值等於真實頻次、bucket 順序嚴格遞增。
若 D 無法放進記憶體，精確契約必須改變。我會用 m 個 Space-Saving 計數器保存候選和誤差區間，最大高估由 N / m 控制；只有前 k 個下界與後續上界分離時才宣稱集合有保證。Count-Min Sketch 可以估計指定 ID 的頻次，但還需要候選發現結構。上線前我會用樸素完整排序做隨機差分測試，並單獨測試同頻、非法 k 和計數器溢位邊界。」
常見錯誤
- 不問負載就固定使用最小堆積 → 查詢頻繁時每次掃描全部
D個 ID，寫多查少時又可能過度維護 → 先依更新與查詢比例決定把成本放在哪一端。 - 把可變
k當成固定K維護 → 大於預先維護K的查詢沒有完整候選 → 明確定義k上限，或使用能按任意k走訪的頻次 bucket 或有序結構。 - 直接修改堆積中的頻次 → 一般堆積不知道元素位置，舊鍵會破壞堆積順序或產生大量過期紀錄 → 維護
ID → 堆積位置，或刪除舊鍵後重新插入，並寫清楚複雜度。 - 頻次 bucket 變空後不刪除 → 查詢可能走過從 1 到最大頻次的大量空洞 → 每次移動後立即摘除空 bucket，只連結非空頻次。
- 宣稱雜湊操作嚴格
O(1)→ Map 與 Set 只支援常見期望複雜度分析 → 說明雜湊假設；需要最壞界限時選平衡樹並接受O(log D)。 - 使用 Count-Min Sketch 後直接回傳 top-k → sketch 只接受指定鍵查詢，不能列舉未知 ID → 同時維護候選發現結構，或改用保存候選鍵的 Space-Saving。
- 回報近似結果卻不附誤差 → 面試官無法判斷第
k與第k + 1是否可區分 → 回傳估計值、誤差上下界和能否保證集合的結論。 - 只測固定範例 → 鏈結斷裂、空 bucket 和同頻邊界常在長更新序列中出現 → 用樸素排序 oracle 做隨機差分測試並檢查不變量。
追問與應對
追問一：如果 topK 永遠只查詢 K = 100，還需要頻次 bucket 嗎？
不一定。維護雜湊頻次、大小 100 的最小堆積和 ID → 堆積位置，每次更新後調整堆積內元素或比較堆頂，成本 O(log 100)，實作和記憶體布局可能更簡單。它不能回答 topK(1000)；頻次 bucket 的價值在於任意 k 和期望常數更新。
追問二：同頻時必須按 ID 升冪怎麼辦？
把 bucket 內 Set 換成有序集合，或在查詢時只排序被截斷的邊界 bucket。前者讓每次移動增加 O(log s)，其中 s 是 bucket 大小；後者只在查詢時支付邊界 bucket 排序成本。應依固定順序是否每次都需要來選擇。
追問三：增加 remove(x) 後如何修改？
ID 的頻次從 f 降到 f - 1，對稱地檢查前一個 bucket，降為 0 時從 locations 刪除。還要定義刪除不存在 ID 是報錯或忽略。若同時存在並行 add/remove，需要把「定位、移動 bucket、刪除空 bucket」放在同一個原子臨界區，否則同一 ID 可能出現在兩個 bucket。
追問四：要求最近 10 分鐘的 top-k 呢？
頻次不再單調。除了 bucket 結構，還要保存帶時間的事件或分段計數，以便過期時執行反向更新。逐事件佇列精確但空間隨視窗事件數成長；時間分段降低狀態量，卻把邊界精度變成明確誤差。Space-Saving 的全歷史摘要不能直接減去任意過期事件。
追問五：Space-Saving 回傳的第 k 與第 k + 1 區間重疊怎麼辦？
增加計數器 m、接受「候選集合尚未確定」，或在資料可重播時對候選再做一遍精確計數。第二遍只能校準已保留候選；若摘要容量不足以保證真實 top-k 已進入候選集，重播前必須先擴大候選集合。
追問六：資料分布在多個分片，如何取得全域 top-k？
任意分布下，各分片的局部 top-k 不能直接合併成精確全域 top-k，因為某個 ID 可能在每個分片都略低於局部門檻，彙總後卻進入全域前列。精確方案需要彙總所有相關頻次，或維護可證明涵蓋的候選上界；近似方案則合併可合併摘要，並把額外誤差和延遲寫入契約。