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

题目与适用场景

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