プロンプトと適用可能なコンテキスト
このセットは、要素の存在確認、挿入、削除、および現在の要素を一様ランダムに返す操作をサポートする必要があります。ハッシュマップは高速な検索を提供し、動的配列はランダムなインデックスアクセスを提供します。途中の要素を削除する際の処理が設計上のトレードオフとなります。
面接官が評価するポイント
- 1つのデータ構造にすべてを強制するのではなく、ハッシュマップと配列を適切に組み合わせているか。
- 値から配列インデックスへのマップを維持し、スワップのたびに正しく更新しているか。
- 平均O(1)および動的配列の償却（アモルタイズ）された拡張を理解しているか。
- 一様なgetRandomと重複値のセマンティクスを明確に定義しているか。
- 空のセット、存在しない要素の削除、および並行性の境界を処理できているか。
回答前の確認質問
- 値は一意（ユニーク）ですか？重複がある場合、値をインデックスのセットにマッピングする必要があります。
- getRandomは厳密に一様である必要がありますか、それとも任意のランダムな要素を返せばよいですか？受け入れテストの基準が変わります。
- O(1)は償却平均ですか、それとも厳密な最悪計算量ですか？ハッシュの衝突処理ポリシーによって保証内容が変わります。
- APIは値そのものを返しますか、それともハンドルを返しますか？ミュータブルなオブジェクトの場合、等価性とハッシュのルールが必要になります。
- スレッドセーフ性、固定メモリ制約、または再現可能な乱数生成は必要ですか？
30秒の回答フレームワーク
「items 配列と indexOf ハッシュマップを保持します。insert は新しい値を末尾に追加してそのインデックスを記録し、getRandom は配列から一様ランダムなインデックスをサンプリングします。remove は対象のインデックスを見つけ、末尾の要素をそのスロットに移動し、移動した要素のインデックスを更新して配列の末尾を pop し、対象のマッピングを削除します。これにより O(n) のシフトを回避できます。ハッシュ操作と動的配列の拡張は平均償却 O(1) です。空のセットの場合は取り決めたエラーを返し、重複がある場合はインデックスセットへのマッピングが必要です。」
ステップごとの詳細解説
ステップ 1: 不変条件の確立。 各値 v について、indexOf[v] は items 内の一意な位置を指します。配列に隙間（ホール）はなく、すべてのインデックスは有効な範囲内に収まります。
ステップ 2: insert の実装。 マップに既にその値が含まれている場合は、仕様に従って false を返します。含まれていない場合は末尾に追加し、新しいインデックスを平均 O(1) で格納します。
ステップ 3: remove の実装。 削除対象のインデックス i と末尾のインデックス last を取得します。i !== last の場合、末尾の値を items[i] に書き込み、そのマップエントリを i に変更します。その後、末尾のスロットを pop して対象のエントリを削除します。
ステップ 4: getRandom の実装。 空でない配列から一様ランダムなインデックスをサンプリングします。Python の choice のドキュメントでは等確率なシーケンス選択が定義されています。ハッシュの反復順序はランダム性の保証にはなりません。
ステップ 5: 計算量の明示。 ハッシュ検索、末尾追加、スワップ、pop はすべて平均償却 O(1) であり、配列とマップの空間計算量は O(n) です。最悪ケースのハッシュ衝突やリサイズによる一時停止については、別途 SLO として議論する必要があります。
ステップ 6: 重複の処理。 indexOf[v] をインデックスのセットに変更します。1つのインスタンスを削除する際は、そのインデックスを取り出して同様の末尾スワップを適用し、両方のインデックスセットを更新します。
ステップ 7: 境界条件の検証。 空のセット、要素が1つの場合、連続削除、末尾要素の削除、繰り返しの拡張、および固定シードでのテストを行います。要素の存在確認だけでなく、出現頻度を検証するために多数の getRandom 呼び出しを実行します。
模範解答
「現在の値を配列に格納し、各値の配列インデックスをハッシュマップに格納します。途中の要素を削除するには、末尾の要素をそのスロットに移動し、その要素のインデックスを更新した上で末尾を pop するため、要素のシフトは発生しません。getRandom は一様に選択された配列インデックスを読み取るため、各一意な値が等しい確率で選ばれます。O(1) の主張は、ハッシュ操作および動的配列の拡張に対する平均償却計算量です。重複が許可される場合は、単一のインデックスをインデックスセットに置き換え、削除を1つのインスタンスの削除として定義します。」
よくある間違い
- ハッシュマップのみを使用する → getRandom がすべてのキーを走査することになる → コンパクトな配列を追加する。
- 削除後に要素をシフトする → delete が O(n) になる → 末尾要素とスワップする。
- 移動した値のインデックス更新を忘れる → 以降の削除で誤ったスロットを対象にしてしまう → マップの更新をスワップの一部として扱う。
- ハッシュイテレータからサンプリングする → イテレーション順序は一様性を保証しない → 配列インデックスをサンプリングする。
- 平均 O(1) を最悪ケースの O(1) と呼ぶ → 衝突やリサイズのコストが無視される → 償却の前提条件を明示する。
フォローアップの質問と回答
フォローアップ 1: 配列の最後の要素を削除する場合はどうなりますか？
対象のインデックスが末尾のインデックスと一致するため、スワップを行わずに pop し、そのマップエントリを削除します。
フォローアップ 2: 重複値はどのようにサポートしますか？
各値をインデックスのセットにマッピングします。末尾を移動した後、その古いインデックスを削除して新しいインデックスを追加し、削除対象のセットから1つのインデックスを削除します。
フォローアップ 3: getRandom が一様であることをどのように証明しますか？
現在の各インスタンスは配列の1つのスロットを占有しており、インデックスは 0..n-1 上で一様です。したがって、一意な値はそれぞれ等しい確率の位置を1つずつ占有します。
フォローアップ 4: ハッシュの衝突によって O(1) が損なわれることはありますか？
平均計算量は負荷率（ロードファクタ）とハッシュの品質に依存します。厳密な最悪ケースの保証が必要な場合は、ツリー化されたバケット（treeified buckets）、ランダム化ハッシュ、または他のデータ構造が必要です。
フォローアップ 5: 並行した読み取りと削除はどのように処理しますか？
ランダムインデックスの読み取りと削除のスワップを1つのロックまたはバージョンチェックで保護します。そうしないと、リーダーが既に pop されたインデックスを参照する可能性があります。
フォローアップ 6: 分布はどのようにテストしますか？
固定されたセットに対して多数の試行を実行し、各値の出現回数をカウントして統計的許容範囲を設定します。また、返されたすべての値がセット内に存在し続けていることもアサートします。