演算法面試：如何實作快照陣列？

題目與適用場景

實作一個長度固定、所有位置初始值均為 0 的陣列，並支援三種操作：

• set(index, value)：修改目前尚未拍攝快照的版本中的一個元素。
• snap()：保存目前版本並回傳其 ID。ID 從 0 開始，每次遞增 1。
• get(index, snapId)：回傳快照 snapId 建立時，index 位置的值。

假設 1 <= length <= 50,000、0 <= value <= 10^9，索引和快照 ID 均合法，所有操作的呼叫總數不超過 50,000 次。答案既要說明 API 語意，也要解釋為什麼保存的狀態足以回答任意歷史查詢。

這是一道演算法與資料結構題。目前公開面試練習題庫仍收錄了這道題。真正的考點是能否用不可變的變更紀錄 取代完整陣列副本，再透過前驅查詢找到正確的歷史紀錄。

面試官在考察什麼

第一，能否準確計算代價。每次 snap 都複製全部 length 個元素很容易理解，但即使只修改一個索引， 每個快照仍要花 O(length) 時間和空間。在 50,000 個元素和 50,000 次操作的限制下，這個最壞方向過大。

第二，能否讓索引結構貼合查詢。get 總會給出陣列索引，因此可以為每個索引保存一條有序變更歷史。 紀錄 [s, v] 表示從快照 ID s 開始，該位置的值變為 v。答案就是滿足 s <= snapId 的最大 s， 也就是標準的前驅查詢。

第三，能否處理快照語意。下一次 snap 之前，同一索引可能被多次 set，但這個版本只應保留最後一個值。 為同一快照 ID 反覆追加紀錄既浪費空間，也讓歷史不變量更難表述。合併這些寫入後，ID 可以保持嚴格遞增。

最後，高品質答案會寫出不變量，證明二分搜尋，並涵蓋時間邊界：初始 0、同一快照前多次寫入、快照後的寫入、 從未修改的索引，以及跨越稀疏變更的查詢。

回答前應確認的問題

• snap() 是先回傳 ID 還是先遞增？ 先回傳目前 ID，再進入下一個工作版本。
• 一次 snap 前能否多次呼叫 set？ 可以；同一版本內，對同一索引最後一次寫入生效。
• get 能否讀取尚未拍攝的目前狀態？ 不能；它接收的是先前 snap() 回傳的合法 ID。
• 長度和索引範圍是否固定？ 固定；不支援插入、刪除或擴容。
• 快照 ID 會跳號嗎？ 全域 ID 連續，但某個索引可以連續很多個快照都沒有變更。
• 是否需要執行緒安全？ 這道記憶體資料結構題不要求。並行修改時，需要在 set 和 snap 外部加同步機制。
• 從未修改的索引回傳什麼？ 在任意快照中都回傳 0。
• 是否需要程序重新啟動後復原？ 不需要；否則還要增加序列化和持久性限制，已超出本題範圍。

30 秒回答框架

「我不會在每次快照時複製整個陣列，而是為每個索引維護一條有序歷史，並用 [0, 0] 初始化。目前快照 ID 從 0 開始。呼叫 set 時，如果最後一條紀錄已屬於目前 ID，就覆蓋其值；否則追加 [currentId, value]。呼叫 snap 時回傳目前 ID 並遞增。呼叫 get 時，在該索引的歷史中二分搜尋第一條 ID 大於 snapId 的紀錄，再回傳前一條紀錄的值。歷史 ID 嚴格遞增，哨兵保證前驅一定存在。初始化為 O(length)，set 和 snap 均攤 O(1)，get 為 O(log h)，空間為 O(length + u)，其中 u 是保留的變更數。」

分步深入分析

步驟 1：先量化，再排除完整複製。

直接方案維護一個目前陣列，每次 snap 都把它完整複製到列表中。這樣 set 和 get 是 O(1)，但 snap 是 O(length)，每個快照還要保存 length 個值，未變化的索引也會重複付費。

一條全域事件日誌雖然避免了複製，但 get(index, snapId) 可能向前掃過大量其他索引的更新。查詢已經給出了 索引，因此依索引拆分歷史可以排除無關事件。

步驟 2：定義一條歷史紀錄的含義。

假設某個索引的保留歷史為：

[[0, 0], [2, 7], [5, 4]]

它在快照 0 和 1 中為 0，在快照 2 到 4 中為 7，從快照 5 開始為 4。每條紀錄是一個變更點， 並非只服務於某一個快照的副本。因此，查詢快照 t 時，要找 ID 不大於 t 的最右紀錄。

每個索引都用 [0, 0] 初始化。這個哨兵同時表達初始值，並保證每個合法快照查詢都有前驅，get 不需要 為空歷史另寫分支。

步驟 3：合併目前版本內的寫入。

第一次 snap 前，目前 ID 是 0。如果先執行 set(3, 5)，再執行 set(3, 8)，快照 0 中必須是 8。 第二次呼叫應把 [0, 5] 覆蓋為 [0, 8]。等 snap() 推進目前 ID 後，下一次寫入再追加新紀錄。

這樣可以維持不變量：每條歷史中的快照 ID 嚴格遞增，每個 ID 最多一條紀錄。保留的變更數不會超過 set 呼叫次數。

步驟 4：實作上界二分與前驅查詢。

type Version = [snapId: number, value: number];

class SnapshotArray {
  private readonly histories: Version[][];
  private currentSnapId = 0;

  constructor(length: number) {
    this.histories = Array.from({ length }, () => [[0, 0]]);
  }

  set(index: number, value: number): void {
    const history = this.histories[index];
    const latest = history[history.length - 1];

    if (latest[0] === this.currentSnapId) {
      latest[1] = value;
    } else {
      history.push([this.currentSnapId, value]);
    }
  }

  snap(): number {
    return this.currentSnapId++;
  }

  get(index: number, snapId: number): number {
    const history = this.histories[index];
    let left = 0;
    let right = history.length;

    while (left < right) {
      const middle = left + Math.floor((right - left) / 2);
      if (history[middle][0] <= snapId) {
        left = middle + 1;
      } else {
        right = middle;
      }
    }

    return history[left - 1][1];
  }
}

二分搜尋使用半開區間 [left, right)。結束時，left 是第一條 ID 大於 snapId 的紀錄位置，前一條就是 ID 不大於 snapId 的最右紀錄。這正是標準二分函式庫所定義的上界分區。

步驟 5：從不變量證明正確性。

對每個索引，紀錄 ID 嚴格遞增。一條 [s, v] 會在快照 s 建立前寫入或最終確定，並持續生效，直到 該索引出現下一條紀錄。因此，在 ID 不超過目標快照的所有紀錄中，ID 最大的紀錄正好是該快照可見的最後一次寫入。

二分搜尋回傳合法前綴之後的第一條紀錄，所以 left - 1 選中的正是其中最大 ID。哨兵 [0, 0] 保證 對每個合法快照 ID，這個前綴都非空。因此，get 回傳題目要求的值。

步驟 6：分析複雜度並驗證邊界。

建立歷史需要 O(length) 時間和空間。set 只讀取或追加一條歷史的尾部，均攤時間為 O(1)；snap 為 O(1)。如果某個索引有 h 條保留紀錄，get 為 O(log h)。整個物件占用 O(length + u) 空間， 其中 u 是不含哨兵的保留變更數，且不超過 set 呼叫次數。

至少涵蓋以下案例：

還可以做隨機差分測試，把這套結構與完整複製方案比較。完整複製不適合目標限制，卻很適合作為簡單可信的測試預言機。

高品質示範回答

「查詢總會給出具體索引，因此我會為每個索引保存一條有序變更歷史。每條歷史從 [0, 0] 開始； [s, v] 表示從快照 s 起，這個位置的值為 v，直到下一條紀錄出現。

目前 ID 從 0 開始。set 只看最後一條紀錄。如果它已經使用目前 ID，就覆蓋值，因為同一快照前最後一次寫入生效； 否則追加新紀錄。snap 回傳目前 ID，然後將其遞增。

執行 get(index, snapId) 時，我在該索引的歷史中做上界二分：找到第一條 ID 大於目標 ID 的紀錄，並回傳 前一條的值。每個索引內的 ID 嚴格遞增，初始哨兵保證前驅存在。這個前驅正是目標快照之前最後生效的值。

初始化為 O(length)；set 和 snap 均攤 O(1)；對有 h 條紀錄的索引，get 為 O(log h)； 總空間為 O(length + u)。我會測試初始 0、同一快照前多次 set、跨多個快照的稀疏變更、後續寫入後的歷史讀取、 未修改索引，並用完整複製方案對隨機操作序列做差分測試。」

常見錯誤

• 每次快照都複製完整陣列 → 時間和空間都隨全部索引增長，包括未改變的位置 → 只保存每個索引的變更點。
• 維護一條全域更新日誌 → 一次讀取可能掃過其他索引的更新 → 依每次查詢都會提供的索引拆分歷史。
• 每次 set 都追加 → 同一版本的重複寫入產生重複 ID 和無效紀錄 → 尾紀錄屬於目前 ID 時直接覆蓋。
• 只搜尋相等的快照 ID → 該索引在目標快照可能沒有變化 → 搜尋不大於目標 ID 的最大紀錄。
• 使用下界並直接回傳 → 它可能指向未來的變更 → 查詢目標 ID 的上界，再回傳前驅。
• 讓歷史從空陣列開始 → 從未修改的索引需要特殊處理 → 為每條歷史預置 [0, 0]。
• snap 先遞增再回傳 → 第一個回傳 ID 變成 1，所有紀錄版本錯位 → 先回傳目前 ID，再遞增。
• 聲稱 get 是 O(log length) → 它搜尋的是單一索引的變更紀錄 → 寫成 O(log h) 並定義 h。
• 只測試公開範例 → 同版本覆蓋和稀疏歷史仍未驗證 → 補充邊界案例和差分預言機。

追問與回答

追問 1：快照必須不可變，snap() 還能是 O(1) 嗎？

可以。這裡是邏輯不可變：某個 ID 回傳後，未來寫入只會以更大的 ID 追加，絕不會修改舊 ID 的紀錄。 snap() 只推進版本邊界，無需具體建立完整副本。

追問 2：為什麼依索引保存歷史，而不是為每個快照保存一個 Map？

每個快照一個 Map，會讓點查詢不斷向前檢查多個快照，直到找到該索引。依索引保存歷史後，get 只搜尋相關變更。 如果主要查詢變成「列出快照 s 中的全部變更」，依快照組織的 Map 才更貼合那個不同的契約。

追問 3：get 能否使用標準函式庫的二分搜尋？

可以，前提是語言提供的正好是依鍵查詢上界的契約。例如，右二分位置位於所有等於 snapId 的既有 ID 之後， 減一就是前驅。應核對標準函式庫對鍵提取和並行修改的說明，不能假設所有二分輔助函式回傳同一種邊界。

追問 4：如果允許刪除快照，需要改變什麼？

先定義刪除一個 ID 後，後續快照是否仍可存取，以及 ID 是否保持穩定。穩定 ID 通常需要引用計數或壓縮演算法， 同時保留每個仍可存取快照能看到的值。直接刪除一條紀錄可能改變後續快照繼承到的值。

追問 5：如何持久化這套結構？

可以用 (array_id, index, snap_id) 為鍵保存只追加的變更紀錄，並在此前寫入全部提交後，再發布持久化的快照邊界。 讀取需要 (array_id, index, snap_id) 上的前驅索引。復原、交易和壓縮會成為儲存系統問題，超出記憶體實作範圍。

追問 6：如果陣列很小，而且讀遠多於寫呢？

當陣列很小且 O(1) 讀取比快照成本更重要時，完整副本可能更合適。應比較實際長度、快照數量、讀取頻率和記憶體預算。 變更歷史方案最佳化的是稀疏寫入與建立快照的成本，並非在所有負載下都必然最優。