算法面试：如何实现快照数组？

题目与适用场景

实现一个长度固定、所有位置初始值均为 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) 读取比快照成本更重要时，完整副本可能更合适。应比较实际长度、快照数量、读取频率和内存预算。 变更历史方案优化的是稀疏写入与创建快照的成本，并非在所有负载下都必然最优。