如何設計動態 Top-K 高頻項目的資料結構？

題目與適用情境

一個整數 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 後都要顯示排行榜，反覆掃描 D 個鍵會成為瓶頸，頻次 bucket 才值得承擔較高的實作複雜度。

第二步：建立頻次 bucket 不變量

bucket 鏈結串列按頻次由小到大排列；每個 bucket 保存該頻次的一組 ID。另一個雜湊表把 ID 直接定位到 bucket。新增 ID 進入頻次 1 bucket；既有 ID 從 f bucket 移到 f + 1 bucket。因為一次更新只增加 1，新 bucket 只可能位於原 bucket 和其後繼之間，不需要搜尋整條鏈結串列。舊 bucket 變空時立即刪除。

三個不變量足以證明結果：

1. locations 中每個 ID 恰好出現在一個 bucket 的集合裡。
2. 每個非空 bucket 的 frequency 等於其中所有 ID 的真實頻次。
3. 從 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 抵達且計數器已滿時，取代目前最小估計頻次為 c_min 的 ID，把新 ID 的估計值設為 c_min + 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 可能在每個分片都略低於局部門檻，彙總後卻進入全域前列。精確方案需要彙總所有相關頻次，或維護可證明涵蓋的候選上界；近似方案則合併可合併摘要，並把額外誤差和延遲寫入契約。