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

題目與適用場景

實作一個長度固定、所有位置初始值均為 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：如何持久化這套結構？

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

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

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