题目重点：OA 题目给单调 timestamp、store/get/delete、compare-set、prefix scan 与两个 timestamp 的历史查询；按版本有效区间组织。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版 action timestamp 非递减，同时间戳操作按输入顺序；每个 key 的每次成功写入产生版本 (start,expiry,value/deleted)，TTL>0 的有效区间 [start,start+ttl)。
- history read 的 get_timestamp≤action timestamp；题目未明确未来读/早于建库时间等规则。过期版本不自动让更旧版本重新可见。
- storeItemIfMatch 比较 action 时刻的当前可见 value；value 类型/相等规则以具体题面为准。历史 prefix scan 若出现，也复用相同时间视图。
解题路线
- 每个 key 保留按 (timestamp,operationSequence) 排序的版本数组。当前写/删/条件覆盖先查 action 时刻可见状态，再 append 新版本或 tombstone；TTL 结束后返回缺失，不回退到旧 value。
- getItemAtTimestamp 对该 key 二分找最后一个 start≤get_timestamp 的版本，若是 tombstone 或 get_timestamp≥expiry 则返回缺失。action timestamp 只是当前操作的发生时间，不应覆盖被查询的历史时间。
- prefix scan 需列出匹配 keys，在 query time 对每个 key 查可见版本并按 key 排序；若 key 数大，可加有序 key 索引/Trie，但历史时间过滤仍要逐 key 判。
- 若同一 timestamp 有多次操作，版本用稳定 sequence 打破并列；历史 API 只给 timestamp 而不给 sequence 时同一时刻取最后一次结果。
- 测试 TTL 边界、条件覆盖旧值、删除后历史读、同 key 覆盖后旧 TTL 过期、空前缀与同时间戳次序。
手动走一遍
训练例 t=10 写 k=A,TTL=5；t=12 写 k=B 无 TTL。history(k,11)=A，history(k,13)=B，history(k,16)=B；旧 A 在 15 过期不应把 B 擦除。另一 key 在 t=10 写 A,TTL=5 且无覆盖时，history(k,15) 为缺失，半开右端不含 15。
规模与取舍
单 key H 个版本，history 二分 O(log H)；append 平均 O(1)，当前读若尾部版本即可 O(1)。朴素 prefix scan 需遍历 K 个 key、每 key 二分后排序匹配结果 O(K log H+M log M)，总历史空间 O(成功写/删次数)。
易错点与追问
容易失分的边界
- 把 action timestamp 与 get_timestamp 混为一个值，历史读返回当前状态。
- TTL 到期后复活之前被覆盖的旧版本。
- delete 物理清空 key 历史，后续历史查询失效。
- 在 action time 以外的时间做 CAS 比较。
- 把不同 Coinbase 内存 DB 变体与 xAI 的 field backup/restore 规格混写。
继续深挖
- 版本过多时如何压缩但仍支持历史查询？
- 如果 timestamp 乱序到达，数据结构如何改？
- 历史 prefix scan 如何避免全库扫描？
- 同时间戳两次写入按何顺序查询？
