問題と適用シナリオ
固定長配列を使用して、get(index)、set(index, value)、append(value)を備えた動的配列を実装してください。満杯時のリサイズ、成長ポリシー、境界動作、appendの最悪計算量とならし計算量を説明し、線形増加と幾何学的増加を比較してください。
参照または固定サイズの値、0始まりのインデックス、範囲外アクセス時の例外、空の配列へのappendを前提とします。公開されている面接問題集では、動的配列／ベクターの実装がMicrosoft、メモリ管理、ならし解析と結びつけられています。MIT 6.006では動的配列のappendをならしΘ(1)として挙げています。
面接官が評価しているポイント
sizeとcapacityを区別し、有効な要素が先頭のsizeスロットを占めるという不変条件を維持しているか。- 1スロットずつ追加するのではなく、幾何学的増加を選択しているか。
- 単にO(1)と主張するのではなく、集約法、会計法、またはポテンシャル法を用いてならし計算量の上界を証明できるか。
- 容量ゼロ、整数オーバーフロー、メモリ割り当ての失敗、縮小、中間への挿入を網羅しているか。
回答前に確認すべき質問
- 末尾へのappendのみが必要ですか、それとも中間への挿入、削除、popも必要ですか？ これらは計算量の前提を変えます。
- 要素は固定サイズですか？ 参照セマンティクス、イテレータの無効化、スレッドセーフ性は必要ですか？
- 目標はコピー回数の削減、メモリオーバーヘッドの抑制、または厳格なレイテンシ上限の維持ですか？
- 縮小処理は必要ですか？ 必要な場合、スラッシングを避けるために成長閾値と縮小閾値を分けるべきですか？
30秒の回答フレームワーク
バッキング配列、size、capacityを保持します。Appendは空きスロットがある場合、直接書き込みます。満杯の場合は、より大きな配列を確保し、先頭のsize個の要素をコピーして新しい値を書き込みます。倍増などの幾何学的増加が重要です。n回のappend全体でコピーされる要素の総数は2n未満の等比級数となるため、総作業量はO(n)となり、appendのならし計算量はO(1)になります。リサイズ処理自体は依然としてO(n)であるため、これは1回の呼び出しあたりの最悪計算量O(1)を保証するものではありません。
ステップバイステップの詳細解説
状態と不変条件
3つのフィールドを保持します。バッキング配列data、有効な要素数size、確保されたスロット数capacityです。常にsizeを0以上かつcapacity以下に保ち、有効な要素は[0, size)を占めます。Appendはdata[size]に書き込み、sizeをインクリメントします。getとsetは[0, size)のみを受け付け、未初期化のcapacityスロットは受け付けません。
幾何学的増加ポリシー
size == capacityの場合、少なくともmax(1, capacity * 2)を割り当て、古い要素をコピーしてバッキング参照を置き換えます。容量ゼロは特殊ケースとして扱う必要があります。そうしないと掛け算をしてもゼロのままになります。倍増させることで、現在のサイズに見合った安価なappendの連続処理が可能になります。より大きな倍率にするとコピーの頻度は下がりますが、未使用の空き領域が増加します。
~~~java final class DynamicArray { private Object[] data = new Object[0]; private int size = 0;
public void append(Object value) { if (size == data.length) { int next = Math.max(1, data.length * 2); Object[] grown = new Object[next]; System.arraycopy(data, 0, grown, 0, size); data = grown; } data[size++] = value; }
public int size() { return size; }
public Object get(int index) { check(index); return data[index]; }
public void set(int index, Object value) { check(index); data[index] = value; }
private void check(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException(); } } ~~~
Object[]は、ジェネリックの型消去環境下での実装例として一般的です。本番環境のコードでは、null、割り当て失敗、並行処理に対する明示的なポリシーが依然として必要です。不変条件と計算量はJavaに依存しません。
ならし解析の証明
初期容量が1で、2倍ずつ増加すると仮定します。n回のappendにおいて、通常の書き込みにはn定数のコストがかかります。リサイズのコピーは容量1、2、4、8などで発生し、その合計は2n未満になります。したがって、総作業量は3n＋初期化未満となり、1操作あたりのならしコストはO(1)になります。
これはランダムな入力に対する平均ではなく、最悪ケースのシーケンスに対する保証です。リサイズをトリガーするappendは依然としてΘ(n)個の要素をコピーするため、1回の呼び出しの最悪計算量はO(n)です。getとsetは最悪ケースでO(1)であり、バッキングストレージはO(n)です。
線形増加と縮小
1回につきcスロットしか追加しない場合、コピーコストはおよそc + 2c + ...になります。n個の要素を挿入するコストはΘ(n²)となり、appendのならし計算量はΘ(n)に低下します。倍率を大きくするとピーク時の未使用領域が増えますが、通常は幾何学的増加の方が優れたトレードオフとなります。
popをサポートする場合は、一定の低水準を下回ったときに縮小します。appendとpopが交互に実行された際の頻繁な再配置を避けるため、成長閾値と縮小閾値は離しておきます（例：満杯時に2倍、1/4未満で半分）。縮小しても末尾操作のならしO(1)は維持されますが、メモリ解放とコピーによる一時停止が発生します。
テスト可能な境界条件
空の配列への最初のappend、ちょうど容量に達したときのappend、繰り返しの拡張、重複参照、負のインデックス、index == size、極端に大きな容量、オーバーフロー、メモリ割り当ての失敗をテストします。制御されたコピーカウンターを使用すると、n回のappendで合計Θ(n)回のコピーが実行されたかを検証できます。最終的な内容のみを検証した場合、線形増加による2次時間の実装も見逃されてしまいます。
質の高い模範解答
バッキング配列、size、capacityを分離し、有効な要素を常に先頭のsize位置に維持します。Appendは空き容量に書き込み、満杯時は2倍の容量を割り当て、古い要素をコピーしてから値を書き込みます。初期容量がゼロの場合は、1スロットの特殊ケースとして扱います。
倍増の証明が重要な部分です。n回のappendにおいて、リサイズによるコピーは2n未満にとどまります。n回の定数時間の書き込みを加えると総作業量はO(n)となり、appendのならし計算量はO(1)になります。リサイズ呼び出し自体はO(n)のままであるため、ならしコストは呼び出しごとのレイテンシ上限ではありません。線形増加ではコピーの総コストがΘ(n²)になります。縮小が必要な場合はヒステリシスを用い、空の入力、境界値、オーバーフロー、メモリ割り当て失敗をテストします。
よくある間違い
- 満杯になるたびに1スロット追加する → 総コピー回数が2次（quadratic）になる → 幾何学的増加を使用して級数を示す。
- appendを最悪ケースO(1)と呼ぶ → リサイズのコピーを無視している → 1回の呼び出しのO(n)とシーケンス全体のならしO(1)を区別する。
getを容量に対して検証する → 未初期化のスロットを返すリスクがある → インデックスが0以上かつsize未満であることを要求する。- 容量ゼロを2倍にする → 配列が成長しない → 最小容量を1にする。
- 使用率が低くなった直後に縮小する → appendとpopの交互実行で移動が頻発する → 成長閾値と縮小閾値を分離する。
フォローアップ質問と回答
すべてのappendで最悪計算量をO(1)にする必要がある場合はどうすればよいですか？
連続した配列のリサイズではO(n)のデータ移行が発生するため、そのままではその厳格な上限を保証できません。セグメント化された配列、インクリメンタルなデータ移行、または上限があらかじめ分かっている場合の事前確保を用いることでトレードオフを変更できますが、局所性、インデックス計算の定数倍、またはメモリ空間のコストが犠牲になります。まず、その要件が本当に最悪ケースを求めているか確認してください。
成長係数が2ではなく1.25の場合は何が変わりますか？
1より厳密に大きい係数であれば末尾appendのならしO(1)は維持されますが、コピーの発生頻度が高くなり、余剰空間は少なくなります。係数が1に近づくほど定数項が増加します。Big-Oだけでなく、メモリ予算、アロケータの挙動、レイテンシ目標に基づいて選択してください。
線形増加がO(n²)であることをどのように証明しますか？
各リサイズでcスロットを追加する場合、j回目のリサイズで約jc個の要素をコピーします。最初のn個の要素はおよそn/c回のリサイズを発生させるため、合計はc + 2c + ... + (n/c)c = Θ(n²)になります。したがって、ならしappendはΘ(n)になります。
中間への挿入によって複雑さはどう変わりますか？
空き容量があっても、中間への挿入は後続の要素をシフトするため最悪ケースでO(n)です。リサイズのコピーは追加の作業となります。動的配列はランダムアクセスと末尾の操作に最適化されており、あらゆる位置への挿入に最適化されているわけではありません。
並行appendはどのように動作しますか？
ロック、シングルスレッドによる所有権の保持、または連携リサイズを伴うアトミックインデックスプロトコルを使用します。sizeをアトミックにするだけでは、容量チェック、割り当て、コピー、公開という一連の処理全体を保護できません。並行性が不要な場合は、シングルスレッドの境界を明示的に述べてください。