問題と適用コンテキスト
すべてのインデックスが 0 で初期化される固定長配列を実装し、次の 3 つの操作をサポートします：
set(index, value)は、現在の（まだスナップショットが作成されていない）バージョンの 1 つの要素を変更します。snap()は、現在のバージョンを保存してその ID を返します。ID は0から始まり、1 ずつ増加します。get(index, snapId)は、スナップショットsnapIdが取得された時点のindexにおける値を返します。
1 <= length <= 50,000、0 <= value <= 10^9、インデックス、およびスナップショット ID はすべて有効であり、全操作を通じて最大 50,000 回の呼び出しが行われると仮定します。解決策では、API の動作と、保存された状態があらゆる履歴クエリに対して十分である理由の両方を説明する必要があります。
これはコーディングおよびデータ構造に関する問題です。この出題は一般的な面接練習問題集にも掲載されており、評価のポイントは、候補者が完全なスナップショットのコピーをイミュータブルな変更レコードに置き換え、先行要素クエリを用いて正しい履歴レコードを特定できるかどうかです。
面接官が見ているポイント
第 1 のシグナルはコストモデルの理解です。snap のたびに length 個のすべての値をコピーする方法は直感的ですが、変更されたインデックスが 1 つだけでもスナップショットごとに O(length) の時間と空間がかかります。要素数が 50,000 で操作数が 50,000 の場合、その最悪計算量は無駄に大きくなります。
第 2 のシグナルは、クエリに応じたインデックスの選択です。get は常に配列のインデックスを指定するため、インデックスごとにソートされた変更履歴を保持します。履歴エントリ [s, v] は、スナップショット ID s 以降で値 v が有効になったことを意味します。答えは s <= snapId を満たす最大のエントリであり、これは標準的な先行要素探索（predecessor search）です。
第 3 のシグナルはスナップショットのセマンティクスです。次の snap の前に同一インデックスに対して複数回 set を呼び出した場合、それらは同一バージョンに属するため、最後の値のみを残すべきです。同じスナップショット ID で重複エントリを追加すると空間を浪費し、履歴の不変条件（invariant）の表現が難しくなります。これらを結合（coalesce）することで、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 では、currentId を返してそれをインクリメントします。get では、そのインデックスの履歴を二分探索して ID が snapId より大きい最初のエントリを見つけ、その直前の値を返します。履歴の ID は厳格に単調増加し、番兵によって先行要素が保証されます。構築は O(length)、set と snap はならし O(1)、get は O(log h)、空間計算量は保持される変更数を u として O(length + u) です。」
ステップごとの詳細解説
ステップ 1：定量的評価に基づいて完全コピー方式を棄却する
直接的な実装では、可変配列を保持し、snap のたびにその全体をリストにコピーします。これにより set と get は O(1) になりますが、snap に O(length) のコストがかかり、各スナップショットで length 個の値を保持することになります。これでは変更されていないインデックスに対してもコストを支払うことになります。
単一のグローバルなイベントログを使えばコピーを回避できますが、get(index, snapId) において無関係なインデックスの更新を後方へ走査することになります。クエリには最初からインデックスが指定されているため、履歴をインデックスごとに分割することで無関係なイベントを排除できます。
ステップ 2：1つの履歴エントリの意味を定義する
あるインデックスについて、保持されている履歴が以下のような場合を考えます：
[[0, 0], [2, 7], [5, 4]]この場合、値はスナップショット 0 と 1 では 0、スナップショット 2 から 4 では 7、スナップショット 5 以降では 4 になります。各エントリは変更点（チェンジポイント）を表すものであり、スナップショットごとのコピーではありません。したがって、スナップショット t に対する対象レコードは、ID が t 以下である最も右側のレコードとなります。
すべてのインデックスを [0, 0] で初期化します。この番兵（sentinel）は初期値を表すとともに、有効なスナップショットクエリには必ず先行要素が存在することを保証するため、get で履歴が空の場合の分岐処理が不要になります。
ステップ 3：同一バージョン内での書き込みを結合する
最初の snap の前、現在の ID は 0 です。set(3, 5) の後に set(3, 8) が続いた場合、スナップショット 0 は 8 を含んでいる必要があります。2 回目の呼び出しでは、[0, 5] を [0, 8] で上書きします。snap() によって現在の ID が進んだ後、次の書き込みで新しいレコードが追加されます。
これにより、各履歴内のスナップショット ID が厳格に単調増加し、各履歴には任意の ID に対して最大 1 つのレコードしか含まれないという不変条件が維持されます。保持される変更レコード数は、set の呼び出し回数以下となります。
ステップ 4：上限値先行要素探索（upper-bound predecessor search）の実装
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 以下である最も右側のエントリです。これは、標準的な二分探索ライブラリで規定されている upper_bound の分割動作と同じです。
ステップ 5：不変条件に基づく正当性の証明
各インデックスにおいて、レコードの ID は厳格に単調増加します。レコード [s, v] はスナップショット s が取得される前に作成または確定され、そのインデックスに次のレコードが追加されるまで有効な値として残ります。したがって、要求されたスナップショット ID を超えないレコードの中で最大の ID を持つレコードこそが、そのスナップショットから参照可能な最後の書き込みとなります。
二分探索はその対象プレフィックスの直後のレコードを返すため、left - 1 によって最大 ID が選択されます。番兵 [0, 0] があることで、任意の有効なスナップショット ID に対して対象プレフィックスは常に空になりません。これにより、get は正しい値を返します。
ステップ 6：計算量の分析と境界値の検証
履歴の作成には O(length) の時間と空間がかかります。set は 1 つの履歴の末尾を読み取るか追加するだけなので、ならし計算量は O(1) です。snap は O(1) です。あるインデックスに h 個の保持レコードがある場合、get のコストは O(log h) です。オブジェクト全体での空間計算量は O(length + u) です。ここで u は番兵以外の保持された変更レコード数であり、u は最大でも set の呼び出し回数です。
最低限、以下のテストを行います：
| シーケンス | 期待される結果 |
|---|---|
snap(); get(0, 0) | 0 |
set(0, 5); snap(); set(0, 6); get(0, 0) | 5 |
set(0, 5); set(0, 8); snap(); get(0, 0) | 8 |
set(1, 9); snap(); snap(); get(1, 1) | 9 |
set(0, 3); snap(); set(0, 4); snap(); get(0, 0) | 3 |
| インデックス 0 を更新後、未変更のインデックス 1 を取得 | 0 |
ランダム化された差分テストを用いて、この構造を完全コピー方式のベースラインと比較検証できます。ベースラインは本番の制約下では重すぎますが、シンプルで信頼性の高いテストオラクルとして機能します。
質の高い模範回答
「主なクエリは特定のインデックスに対する履歴の検索であるため、インデックスごとに順序付けられた変更履歴を保持します。すべての履歴は [0, 0] から始まります。ペア [s, v] は、スナップショット s から次のペアが追加されるまで v が有効であることを意味します。
現在の ID は 0 から始まります。set は最後のペアのみを確認します。そのペアがすでに現在の ID を使用している場合、スナップショット前の最後の書き込みが優先されるため値を置き換えます。そうでなければ新しいペアを追加します。snap は現在の ID を返してからインクリメントします。
get(index, snapId) については、そのインデックスの履歴に対して upper-bound 探索を実行します。要求された ID より大きい ID を持つ最初のペアを見つけ、その直前のペアの値を返します。インデックスごとの ID は厳格に単調増加しており、初期の番兵によって先行要素が必ず存在します。この先行要素こそが、要求されたスナップショット以前に書き込まれた最新の値となります。
構築のコストは O(length) です。set と snap はならし O(1)、get はそのインデックスの変更レコード数を h として O(log h)、合計空間計算量は O(length + u) です。テストとしては、初期値 0、同一スナップショット前での重複 set、複数スナップショットにまたがる疎な変更、以降の書き込み後の過去読み取り、未変更インデックス、および完全コピーのオラクルに対するランダムトレースなどを実施します。」
よくある間違い
- スナップショットごとに配列全体をコピーする → 変更のないインデックスも含めて時間と空間が増大する → インデックスごとの変更点のみを保存する。
- 1つのグローバルな更新ログを保持する → 読み取り時に無関係なインデックスまで走査してしまう → 各クエリで提供されるインデックスごとに履歴を分割する。
- すべての
setを常に追加する → 同一バージョン内での重複書き込みにより ID の重複とレコードの無駄が発生する → 末尾が現在の ID を持っている場合は上書きする。 - スナップショット ID の完全一致を探索する → そのスナップショットでインデックスに変更がない場合がある → 要求値以下で最大の記録 ID を見つける。
- lowerbound を使用してそれをそのまま返す → より後の変更を指してしまう可能性がある → 要求値に対して upperbound を適用し、その直前の要素（predecessor）を返す。
- 履歴を空で初期化する → 未変更のインデックスに特別な処理が必要になる → 各履歴に
[0, 0]を初期値として設定する。 snapで値を返す前にインクリメントしてしまう → 最初に返される ID が 1 になり、レコードのバージョンがずれる → 現在の ID を返してからインクリメントする。getがO(log length)であると主張する → 探索するのは 1 つのインデックスの変更レコードである →O(log h)と記述し、hを定義する。- 公開されているサンプルケースのみをテストする → 同一バージョンの上書きや疎な履歴が未検証のままになる → 境界ケースと差分オラクルを追加する。
フォローアップ質問と回答
フォローアップ 1：スナップショットをイミュータブルにする必要がある場合でも snap() は O(1) にできますか？
はい。イミュータビリティは論理的なものです。ID が返された後、以降の書き込みはより大きな ID のもとに追加され、古い ID に属するレコードを変更することはありません。snap() はバージョンの境界を進めるだけであり、完全なコピーを実体化する必要はありません。
フォローアップ 2：スナップショットごとのマップではなく、インデックスごとの履歴を使用するのはなぜですか？
スナップショットごとのマップを使用すると、ポイントルックアップの際にそのインデックスが見つかるまでスナップショットを過去へ遡って走査する必要があります。インデックスごとの履歴にすれば、最初のクエリキーでレコードが整理されるため、get は関連する変更のみを探索できます。スナップショット指向のマップは、「スナップショット s で変更されたすべての要素を列挙する」といったクエリが主である場合に有用であり、これは異なる要件です。
フォローアップ 3：get で標準ライブラリの二分探索を使用できますか？
言語がキーに対する正確な upper-bound の仕様を提供している場合は可能です。たとえば、right-bisection の位置は snapId と等しい既存 ID の直後の挿入ポイントとなり、そこから 1 を引くことで先行要素が得られます。すべての二分探索ヘルパーが同じ境界を返すと思い込まず、キーの抽出方法や並行性の挙動をライブラリのドキュメントで確認してください。
フォローアップ 4：スナップショットの削除が可能な場合、どのような変更が必要ですか？
まず、ある ID を削除したときに以降のスナップショットもアクセス不能になるのか、それとも ID は安定したままなのかを定義します。ID が安定している場合、通常は保持されているスナップショットから到達可能なすべての値を維持するための参照カウントやコンパクション（圧縮）が必要になります。レコードを無差別に削除すると、以降のスナップショットが継承する値が変わってしまう可能性があります。
フォローアップ 5：この構造を永続化するにはどうしますか？
(array_id, index, snap_id) をキーとする追記専用（append-only）の変更レコードを保存し、先行するすべての書き込みがコミットされた後にのみ永続的なスナップショット境界を公開します。読み取りには (array_id, index, snap_id) 上の先行要素インデックスが必要です。リカバリ、トランザクション、およびコンパクションは、面接でのインメモリ実装を超えたストレージシステムの課題となります。
フォローアップ 6：小さな固定配列で読み取りが書き込みを大幅に上回る場合はどうなりますか？
配列が小さく、スナップショットのコストよりも O(1) の読み取り性能が重視される場合は、完全コピー方式が合理的になることがあります。実際の配列長、スナップショット数、読み取りレート、メモリバジェットを比較検討してください。変更履歴設計は疎な書き込みとスナップショット作成を最適化するものであり、あらゆるワークロードに対して自動的に最適になるわけではありません。