課題とスコープ
set(key, value, timestamp) と get(key, timestamp) を備えたインメモリ構造を実装します。get は、タイムスタンプがクエリ時刻以下であるそのキーの最新バージョンを返します。存在しない場合は明示的なミス（未検出）を返します。タイムスタンプがキーごとに単調増加であるか、同一タイムスタンプで上書きされるか、読み取りと書き込みが並行して行われるか、削除や永続化が必要かを確認してください。肝心なのは、すべてのレコードを繰り返しソートして走査するのではなく、キーごとの履歴の不変条件（invariant）を維持することです。
面接官が評価するポイント
優れた回答では、m をキーのバージョン数とした O(log m) の検索を目指し、追記専用（append-only）と順不同の入力との間における書き込みのトレードオフを説明します。面接官は、空のキー、両端の時間境界、重複したタイムスタンプ、null 値、存在しないキー、およびクエリ時刻における最新の有効なバージョンとクエリ時刻より後のバージョンの違いについて掘り下げてきます。スレッドセーフを主張する場合は、ロックの粒度とスナップショットのセマンティクスを含める必要があります。
コーディング前の確認事項
- タイムスタンプはキーごとに単調増加ですか？ もしそうなら、末尾に追加して短い逆方向スキャンまたは二分探索を使用します。そうでなければ、順序を維持するか、順不同の書き込みを拒否します。
- 同一タイムスタンプは何を意味しますか？ Last-Write-Wins（最終書き込み優先）の場合は、安定したタイブレークとして単調増加するシーケンスを保持します。そうでなければ競合を拒否します。
- 値は null になり得ますか？ その場合、ミスを null で表すことはできません。明示的な
foundフラグを含む結果を返します。 - 並行性は必要ですか？ まずシングルスレッドでの不変条件を完成させ、その後に可視性を定義してキーごとのロックまたはイミュータブルなスナップショットを選択します。
- 履歴は無制限ですか？ 保持期間やバージョン上限があると、エビクション（破棄）処理や古いクエリの意味合いが変わります。
30秒の回答フレームワーク
「各キーに対して時間順にソートされたバージョン配列を保持します。get は upper_bound(timestamp) を使用してクエリより大きい最初のバージョンを見つけ、その直前のエントリを返すため、検索は O(log m) になります。書き込みが単調増加でない場合は順序付き挿入を使用し、そのコストを説明します。書き込みスループットが支配的である場合は、ログに追記してバッチでインデックスを構築します。シーケンス番号により同一タイムスタンプを決定論的に処理し、ミスには明示的な状態を持たせます。空のキー、境界値、順不同の書き込み、重複タイムスタンプをテストします。」
ステップごとの解決策
各レコードを (timestamp, sequence, value) として表現し、各キーの配列を (timestamp, sequence) に基づいて非減少順に維持します。get(k, t) では、timestamp > t を満たす最初の位置 i を見つけます。i が 0 の場合、有効なバージョンは存在しません。それ以外の場合は records[i - 1] を返します。この upper-bound ルールにより、ちょうど t の書き込みも含まれます。
タイムスタンプがキーごとに単調増加する場合、末尾追加により set はならし O(1)、get は O(log m) になります。順不同のタイムスタンプの場合、挿入位置の特定は対数時間ですが、配列の要素シフトは最悪の場合 O(m) になります。平衡木を使用すればシフトは回避できますが、メモリ割り当てとポインタのオーバーヘッドが増加します。クエリの境界はキーごとに独立しているため、単一のグローバルなソート済み配列を使用するのは不適切です。
重複するタイムスタンプには決定論的なルールが必要です。Last-Write-Wins の場合、各呼び出しに増加するシーケンスを割り当て、(timestamp, sequence) でソートします。upper-bound はタイムスタンプのみを比較するため、そのタイムスタンプにおける最後のレコードが優先されます。タイムスタンプが言語の安全な整数範囲を超える可能性がある場合は、暗黙的に浮動小数点数に変換するのではなく、適切な整数型またはコンパレータを使用してください。
並行性については、最もシンプルな拡張として、配列の置換や二分探索の実行中に単一のキーをロックする方法があります。読み取りをノンブロッキングに保つには、ライターが新しいイミュータブルな配列を構築し、参照をアトミックに差し替えます。リーダーは古いスナップショットか新しいスナップショットのいずれかを参照し、不完全な配列を見ることはありません。永続化にはログ、チェックサム、リカバリカーソルが追加されますが、これらは面接官がスコープを広げた場合にのみ議論すべきです。
質の高い模範解答
「タイムスタンプは順不同で到着する可能性があり、同一タイムスタンプには Last-Write-Wins を適用し、最初のバージョンはシングルスレッドであると想定します。各キーは (timestamp, sequence) でソートされた配列にマッピングされます。get はクエリより大きい最初のタイムスタンプに対して upper-bound 探索を実行し、直前のバージョンを返すことで、O(log m) の検索と正確な等価比較の振る舞いを実現します。タイムスタンプの増加が保証されている場合、set はならし O(1) になります。読み取りより書き込みが多い場合は、ログに追記して非同期でインデックスを構築します。テストでは、存在しないキー、最初のバージョンより前、最初および最後のバージョンと同一、最後のバージョンより後、順不同の書き込み、重複タイムスタンプ、null 値を網羅します。」
よくある間違い
- 間違い → 最新バージョンを線形探索する。失敗する理由 → 検索が
O(m)になりスケールしない。対策 → ソートされた履歴を維持し、upper-bound 探索を使用する。 - 間違い →
timestamp < tを使用する。失敗する理由 → ちょうどtでの書き込みが除外される。対策 → 最初のtimestamp > tを見つける。 - 間違い → すべての書き込みが増加順であると仮定する。失敗する理由 → 順不同のイベントによって配列の不変条件が崩れる。対策 → 制約を明示し、順序付き挿入または木構造を使用する。
- 間違い → ミスと格納された値の両方に null を使用する。失敗する理由 → 呼び出し側が状態を区別できない。対策 →
{ found, value }または明示的な Optional 型を返す。 - 間違い → 同一タイムスタンプを無視する。失敗する理由 → 結果が偶発的な順序に依存する。対策 → シーケンスを追加するか、競合を拒否する。
フォローアップへの回答
タイムスタンプが確実に増加する場合はどのように最適化しますか？
ならし O(1) の書き込みのためにキーごとに追加します。予測可能な O(log m) の読み取りのために二分探索を維持するか、アクセスパターンからクエリが通常最新バージョン付近であることが示されている場合にのみ後方スキャンを行います。後方スキャンが最悪計算量で定数時間であると主張してはいけません。
キーごとに過去30日分のみを保持するにはどうしますか？
カットオフがイベント時刻かサービス時刻かを定義し、順序を維持しながら古いプレフィックスを定期的に削除します。カットオフより前のクエリは、通常のミスを装うのではなく、「履歴が利用不可」であることを返すべきです。
並行リーダーとライターに対しては何を変更しますか？
まず線形化ポイント（linearization point）を定義します。直接的な設計としては、キーごとの読み取り/書き込みロック（Read-Write Lock）を使用します。ノンブロッキングな読み取りを行うには、新しい配列を構築してその参照をアトミックにスワップし、リーダーが完全な古いスナップショットまたは新しいスナップショットを観測できるようにします。
クラッシュ後の永続化とリカバリはどのように行いますか？
書き込みを承認する前にシーケンス付きログに追記し、定期的にインデックスのスナップショットを実体化し、リカバリ後にシーケンス番号を検証しながらサフィックスを再生します。設問がメモリのみを求めている場合は、完全なデータベース設計まで追加しないでください。