Coding 面試：實作按時間查詢的版本化鍵值儲存

題幹與適用場景

實作一個記憶體結構：set(key, value, timestamp) 寫入版本，get(key, timestamp) 回傳該 key 在給定時間點已生效的最新值；沒有符合條件的版本時回傳空值。先釐清時間戳是否嚴格遞增、同一時間戳是否允許覆蓋、讀寫是否並行，以及是否需要刪除或持久化。本題核心是把「每個 key 的歷史」組織成可驗證的不變量，而不是把所有記錄排序後逐次掃描。

面試官考察點

強回答會先給出 O(log m) 查詢目標，其中 m 是目標 key 的版本數，再說明如何在追加寫入和亂序寫入之間取捨。面試官會檢查候選人是否處理空 key、時間戳在兩端、重複時間戳、值為 null、未知 key，以及是否把「最新版本」誤寫成「最大時間戳之後的版本」。若聲稱執行緒安全，還要說明鎖的粒度和快照語意。

回答前需要釐清的問題

1. 時間戳是否按 key 單調遞增？ 若是，可追加並用一次反向掃描或二分；若否，要保持有序或拒絕亂序寫入。
2. 相同時間戳如何定義？ 採用 last-write-wins 時要保存寫入序號作為穩定 tie-breaker；若禁止覆蓋，應回傳錯誤。
3. 值能否為 null？ 能的話，未命中不能也用 null 表示，應回傳帶 found 的結果。
4. 是否需要並行？ 單執行緒題可先完成資料結構；並行版要定義 set 與 get 的可見性，再選擇讀寫鎖或不可變快照。
5. 歷史是否無限增長？ 若有保留窗口或最大版本數，過期策略會改變刪除和查詢不變量。

30 秒回答框架

「我按 key 保存按時間排序的版本陣列。查詢用 upper_bound(timestamp) 找到第一個大於目標時間的位置，回傳它前一個版本，因此查詢是 O(log m)。如果寫入時間戳不保證遞增，我會用二分插入並明確插入成本；如果規模要求高寫入吞吐，則改為先追加到日誌，再在批次或查詢層建立索引。相同時間戳用遞增序號決定覆蓋順序，未命中回傳明確狀態。最後用空 key、邊界時間、亂序和重複時間戳測試不變量。」

分步驟深入解答

先定義記錄 (timestamp, sequence, value)，並令每個 key 的陣列按 (timestamp, sequence) 非遞減排列。對 get(k, t)，尋找第一個 timestamp > t 的位置 i；若 i = 0 則沒有生效版本，否則回傳 records[i - 1]。這就是上界二分，避免把「等於 t」漏掉。

若寫入按 key 遞增，直接 append，set 均攤 O(1)，get 為 O(log m)。若允許亂序時間戳，二分定位後插入會移動陣列元素，單次最壞 O(m)；可以改用平衡樹，或接受寫入攤銷成本換取緊湊記憶體。不要只對全域陣列排序，因為不同 key 的查詢邊界彼此獨立。

重複時間戳必須有確定規則。last-write-wins 可給每次呼叫一個遞增 sequence，並按 (timestamp, sequence) 排序；查詢上界仍只比較 timestamp，落在同一 timestamp 的最後一條記錄自然勝出。若 timestamp 可能超過安全整數，使用語言提供的整數型別或字串比較器，不能靜默轉成浮點數。

並行時，最小實作可按 key 加鎖：寫入修改單個陣列，讀取在複製參照或持鎖期間執行二分。若要求讀不阻塞，可在寫入時複製該 key 的不可變陣列並原子替換；代價是寫放大。持久化版本則需要日誌、校驗和和復原指標，那已超出純記憶體題，應先確認面試官是否要擴展。

高品質示範回答

「我先假設同一 key 的時間戳可以亂序，重複時間戳採用後寫覆蓋，並且單執行緒。每個 key 對應一個按 (timestamp, sequence) 排序的陣列。get 做上界二分：找第一個時間戳大於查詢時間的位置，回傳前一項；這樣恰好包含等於查詢時間的版本，複雜度是 O(log m)。若面試官保證時間戳遞增，我會把 set 降到均攤 O(1)；若寫入量遠高於查詢，我會考慮追加日誌後非同步建立索引。測試會涵蓋未知 key、早於首版本、等於首尾時間、晚於末版本、亂序寫入、重複時間戳和 null 值。」

常見錯誤

• 錯誤表現 → 用線性掃描找最後版本；失敗原因 → 查詢退化為 O(m)，規模增長後不可控；修正方法 → 保持排序不變量並使用上界二分。
• 錯誤表現 → 用 timestamp < t；失敗原因 → 丟失恰好在 t 寫入的版本；修正方法 → 尋找第一個 timestamp > t。
• 錯誤表現 → 假設所有寫入遞增；失敗原因 → 亂序資料會破壞陣列順序；修正方法 → 明確約束，或執行有序插入/改用樹結構。
• 錯誤表現 → 用 null 同時表示未命中和值；失敗原因 → 呼叫方無法區分兩種狀態；修正方法 → 回傳 { found, value } 或明確 Optional。
• 錯誤表現 → 忽略重複時間戳；失敗原因 → 結果依賴實作細節；修正方法 → 引入 sequence 或拒絕衝突。

追問及應對

如果寫入時間戳保證遞增，如何最佳化？

每個 key 直接追加，寫入均攤 O(1)；查詢仍可二分，或者在查詢時間通常接近最新值時從尾部短掃。要說明尾掃只在存取分布支援時採用，不能把最壞複雜度寫成 O(1)。

如果要限制每個 key 只保留最近 30 天？

按事件時間或服務時間明確口徑，週期性刪除低於保留下界的前綴；刪除後仍保持排序。查詢早於下界回傳「歷史不可用」，不能偽裝成未命中。

如果多個執行緒同時讀寫怎麼辦？

先定義線性化點。簡單方案是每個 key 的讀寫鎖；追求無鎖讀時，寫入建構新陣列後原子替換參照，讀者看到舊快照或新快照，但不會看到半成品。

如果要持久化並支援崩潰復原？

追加寫前先記錄帶序號的日誌，定期生成索引快照；復原時重播快照之後的日誌並驗證序號。題目若只要求記憶體，不應未經確認加入完整資料庫設計。