問題と背景
元の順序を復元する reset() と、一様なランダム順列を返す shuffle() を実装します。この問題では、乱択アルゴリズム、インプレーススワップ、乱数の境界、およびテスト容易性が問われます。同様のパターンはサンプリング、抽選、テストフィクスチャでも見られます。
面接官が見ているポイント
- 任意のランダムな位置を繰り返しスワップするのではなく、Fisher–Yates法を選択しているか。
- 未確定の部分からのみインデックス
iをサンプリングしているか。 - 偏りやオーバーフローを避けるために、両端を含むAPIと半開区間APIを区別しているか。
- シャッフルによって
reset()が影響を受けないよう、不変のベースラインを保持しているか。 - O(n)時間、O(1)の追加空間、および一様性について説明できるか。
- シード付きPRNG、空配列、重複する値、および統計的テストの限界について議論できるか。
確認すべき明確化のための質問
shuffle()は新しい配列を返すべきですか、それとも作業用配列を変更して返すべきですか？- 呼び出し元が内部状態を変更できないように、
reset()は防御的コピーを返す必要がありますか？ - 乱数ソースは注入（DI）可能ですか、それとも暗号学的に安全なソースが必要ですか？
- 重複する値は許可されますか？また、異なる位置にある同一の値は別個の順列とみなしますか？
- スレッドセーフ性、再現可能なシード、または暗号論的な予測不可能性は必要ですか？
- 入力はストリーミングまたは定数の補助空間を必要としますか？
30秒の回答フレームワーク
「元のスナップショットと作業用配列を保持します。i を最後のインデックスから1まで減算させながら、[0, i] 内で一様な j をサンプリングし、a[i] と a[j] をスワップします。各パスで1つの位置が確定するため、実行時間はO(n)、補助空間はO(1)です。reset() はスナップショットのコピーを返します。再現性と統計テストのために乱数ソースを注入できます。」
ステップバイステップの詳細解説
ステップ 1: 状態の分離。 入力を original と working にコピーします。外部参照がベースラインを変更できないように、reset() は original を再度コピーします。
ステップ 2: ランダム境界の定義。 i を n - 1 から 1 まで減少させます。半開区間APIの場合は randomInt(i + 1) を呼び出して 0..i を取得し、両端を含むAPIの場合は 0 と i を明示的に渡します。
ステップ 3: インプレースでのスワップ。 working[i] と working[j] をスワップします。位置 i が確定し、同じサイズのテンポラリ配列は作成されません。
ステップ 4: 一様性の説明。 最初に確定される位置には等確率の選択肢が n 通りあり、次には n-1 通り、というように続き、n! 通りの等確率な選択パスが生成されます。乱数ソースは各候補インデックスに対して一様でなければなりません。
ステップ 5: 重複の処理。 このアルゴリズムは要素の位置に対して一様です。重複した値が存在する場合、複数の位置順列が同じ値の並びとして現れることがありますが、目に見える並びと位置順列は同じではありません。
ステップ 6: resetの実装。 original のコピーを返して working を再構築します。内部配列を公開すると、呼び出し元がエイリアスを作成してベースラインを破壊する恐れがあります。
ステップ 7: 検証と計算量の明示。 再現性のために固定シードを使用し、小さめの配列の頻度を列挙して一様性を近似的に確認し、空配列や1要素の配列をテストします。各シャッフルはO(n)時間かつO(1)の補助空間です。保存されたスナップショット自体はO(n)の状態を使用します。
模範解答
「original 配列と working 配列を保持します。shuffle は i = n-1..1 を反復処理し、一様な j ∈ [0,i] を抽出して2つのエントリをスワップします。reset は original のコピーを返して working を再構築します。任意のランダムな位置を繰り返しスワップすると、以前の位置が書き換えられ、偏った順列が生成される可能性があります。Fisher–Yates法は未確定のプレフィックスからのみサンプリングするため、すべての位置順列が等確率になります。これはO(n)時間で実行され、状態スナップショット以外の追加配列を必要としません。シード付きテスト用に乱数ソースを注入し、結果がセキュリティや公平性に影響を与える場合はCSPRNGに置き換えます。」
よくある間違い
- 各ラウンドで
[0,n-1]をサンプリングする → 確定した位置が再び変更される →[0,i]を使用する。 floor(random * i)を計算する → インデックスiが選択されない → 半開区間の境界としてi + 1を使用する。- 任意のランダムなペアをn回スワップする → 順列の一様性が保証されない → Fisher–Yatesのステップごとに1つの位置を確定する。
- resetから同じ内部参照を返す → 呼び出し元がベースラインを破壊する可能性がある → 防御的コピーを返す。
- PRNGを安全な乱数として扱う → 抽選結果が予測可能になる可能性がある → 脅威モデルに応じてCSPRNGを選択する。
フォローアップ質問と回答
フォローアップ 1: なぜループを前方に向かって実行することもできるのですか？
前方への形式は [i,n-1] からサンプリングすることで i を確定します。証明は対称です。不変条件は、各選択が未確定の領域からのみ行われることです。
フォローアップ 2: 一様性をどのように証明しますか？
位置 n-1 には n 通りの等確率な選択肢があり、位置 n-2 には n-1 通り、というようになります。したがって、すべての完全な選択パスの確率は 1/n! となります。
フォローアップ 3: ランダム性をどのようにテストしますか？
小さな配列で多数の試行を実行し、許容範囲を設定して順列の出現頻度を比較し、固定シードを使用して再現性を確認します。有限のサンプルは証拠であり、証明ではありません。
フォローアップ 4: 通常の疑似乱数では不十分なのはどのような場合ですか？
抽選、トークン、またはシャッフルがセキュリティや権利付与に影響を与える場合は、システムのCSPRNGを使用してください。シード設定可能なPRNGはシミュレーション、ゲーム、テストに適しています。
フォローアップ 5: 入力が連結リストの場合はどうなりますか？
配列への変換にはO(n)の空間がかかります。ノードのスワップによりストレージは節約できますが、ランダムアクセスが高コストになるため、制約を再交渉する必要があります。
フォローアップ 6: 並行呼び出しをどのように処理しますか？
各インスタンスに分離された状態を与えて変更をロックするか、不変のスナップショットを返します。別のスレッドがリセットを行っている最中に、呼び出し元が不完全なスワップを観測してはなりません。
フォローアップ 7: Java標準ライブラリはこの考え方を使用していますか？
Oracleのドキュメントには、ランダムな要素を現在の位置にスワップする後方トラバーサルが記載されています。公平な乱数ソースを使用すれば、すべての順列が等確率で発生します。