プロンプトとユースケース
ストリームは1回しか読み取ることができません。その長さ n は未知であり、等確率で k 個の異なる要素が必要です。ストリームを保存したり、最後のランダムなインデックスを待ったりすることはできません。リザーバーサンプリングは、サイズ k の固定リザーバーを維持します。要素 i が到着すると、確率 k/i でリザーバーに入り、一様に選択されたリザーバーのスロットを置き換えます。
この設問は、ランダム化ストリーミングアルゴリズムをテストします。Vitterの論文では、母集団のサイズが未知である場合の1パスサンプリングを研究しており、大学の講義ノートでは一様性の帰納法が示されています。中心となるカテゴリは coding であり、データプラットフォームの実装ではなく、メモリ制限下の確率の不変条件です。
面接官が評価するポイント
- 未知のサイズ、1パス、固定メモリのリザーバーパターンを認識しているか。
kに一般化する前に、k=11/iの置換ルールを説明できるか。- 要素
iの後、すべての要素がサンプルに含まれる確率がk/iであることを証明できるか。 - 重複サンプル、既知の
nという誤った前提、および偏りのあるランダム整数を回避しているか。 O(n)時間、O(k)空間、および重み付きサンプリングの境界を述べられるか。
回答前の確認事項
kは正の整数ですか？k <= 0またはストリームの要素がk未満の場合はどうすべきですか？- 「異なる」とは、異なるレコードを意味しますか、それとも値による重複排除を意味しますか？
- ストリームは空、無限、または中断される可能性がありますか？ 出力と復旧方法が異なります。
- 最終的なリザーバーが出力のすべてですか、それともスキャン中に観察可能である必要がありますか？
- ランダムAPIは、必要な範囲にわたって偏りのない整数を提供しますか？
- 対象は一様サンプリングですか、それとも重み付き／層化サンプリングですか？ 重み付きサンプリングには異なる不変条件が必要です。
30秒の回答フレームワーク
「リザーバーを最初の k 個の要素で満たします。1から始まる要素 i については、[0, i-1] 内で偏りのない整数 j を生成します。j < k の場合は reservoir[j] を置き換え、そうでない場合はその要素を破棄します。要素 i の後、すべての要素の確率は k/i になります。新しい要素は k/i で入り、古い要素は k/(i-1) × 1 - 1/i で残ります。このアルゴリズムは1パス、時間 O(n)、追加空間 O(k) です。」
ステップごとの詳細な回答
ステップ 1: k=1 から始める。
最初の要素を保持します。要素 i については、確率 1/i で現在の候補を置き換えます。i 個の要素を処理した後、各要素が保持されている確率は 1/i です。
ステップ 2: k に一般化する。
最初の k 個のスロットを埋めます。要素 i については、確率 k/i で入ります。入る場合は、k 個のスロットの1つを一様に選択します。[0, i-1] 内の整数 j がこれを実装します。j < k はスロット j を置き換えることを意味します。
ステップ 3: 疑似コードを書く。
reservoir = first k items
for i = k+1 .. n:
j = uniformInteger(0, i-1)
if j < k:
reservoir[j] = item i
return reservoirストリームを事前に埋めることができない場合は、seen <= k の間追加し、その後同じ分岐を使用します。整数生成器は、偏りなく完全な範囲をカバーする必要があります。
ステップ 4: 新しい要素の確率を証明する。
要素 i において、その含有確率は k/i です。一度含まれると、特定のスロットが置き換えられる確率は 1/t であるため、その後の各ステップで残る確率は ∏(1 - 1/t) = i/n です。したがって、最終的な確率は k/i × i/n = k/n になります。
ステップ 5: 古い要素の確率を証明する。
要素 i-1 の後、各古い要素の確率が k/(i-1) であると仮定します。ステップ i において、それが置き換えられる確率は k/i × 1/k = 1/i であるため、残る確率は 1 - 1/i です。その新しい確率は k/(i-1) × (i-1)/i = k/i です。新しい要素と古い要素は同じ不変条件を満たします。
ステップ 6: 計算量とランダム生成を分析する。
各要素は1回処理されます：時間 O(n)。リザーバーは k 個の要素を保持します：追加空間 O(k)。安全な整数精度を超えるカウントの場合は、必要な範囲をサポートする偏りのない整数APIを使用します。
ステップ 7: 入力の境界条件を処理する。
空のストリームは空のサンプルを返します。k = 0 は空のサンプルを返すか、ドキュメントに記載されたエラーを発生させます。到着した要素が k 未満の場合は、実際の要素を返すか、仕様に従って失敗させます。値による重複排除には追加の状態が必要であり、O(k) に違反する可能性があります。
ステップ 8: 重み付きおよび分散拡張を説明する。
重み付きサンプリングでは対象の分布が変わるため、等確率の置換は無効になります。Efraimidis–Spirakis などの重み付きリザーバーキーについて議論します。分散リザーバーを正しくマージするには、カウントと優先度／重みが必要です。シャードサンプルの単純な連結には偏りがあります。
質の高い模範解答
「容量 k のリザーバーを維持します。最初の k 個の要素でそれを満たします。要素 i = k+1 以降は、[0, i-1] 内で偏りのない整数 j を取得します。j < k の場合はスロット j を置き換え、それ以外の場合は破棄します。新しい要素は確率 k/i で入ります。特定の古い要素が置き換えられる確率は 1/i であるため、その確率は k/(i-1) から k/(i-1) × (1-1/i) = k/i に変化します。数学的帰納法により、すべての要素の最終確率は k/n になります。このアルゴリズムは1パス、時間 O(n)、空間 O(k) です。空の入力、k=1、k=0、重複レコード、反復シミュレーションをテストし、重み付きまたは分散バリアントの不変条件を明示的に再導出します。」
よくある間違い
- ストリーム全体を最初に保存する → 未知のサイズおよびメモリ制約に違反する → リザーバーをオンラインで更新する。
- すべての新しい要素に対して
1/kを使用する → 確率がiに適応しない →k/iを使用する。 random() % iを使用する → 剰余演算に偏りが生じる可能性がある → 偏りのない整数サンプリングを使用する。- 置換スロットを非一様に選択する → 一部の組み合わせの確率が高くなる → k 個のスロットから一様に選択する。
- スキャン中に
k/nを使用する →nは未知であり、確率は各ステップで変化する → 現在のカウントiを使用する。 - 重複のセマンティクスを無視する → 異なるレコードと異なる値は異なる → 最初に重複排除を明確にする。
- シャードリザーバーを連結する → シャードサイズが不均一な場合、結果に偏りが生じる → カウントと優先度を用いてマージする。
- 重みに一様アルゴリズムを再利用する → 対象の分布が変化している → 新しい証明とともに重み付きリザーバーサンプリングを使用する。
フォローアップの質問と回答
フォローアップ 1: なぜ新しい要素の置換確率は k/i なのですか？
要素 i において、アルゴリズムは i 個の位置から1つを一様に選択します。最初の k 個の位置がリザーバーを表すため、いずれかに当たる確率は k/i です。
フォローアップ 2: k=1 の公平性はどのように証明しますか？
最初の要素は確率1で保持されます。要素 i はそれを 1/i で置き換えます。任意の古い要素は (1/(i-1)) × (1-1/i) = 1/i で残り、帰納法が成立します。
フォローアップ 3: 偏りのない整数をどのように生成しますか？
一様整数APIを使用するか、最大の割り切り可能な範囲外のランダム値を破棄する棄却サンプリングを使用します。単純な剰余演算が常に偏りがないとは仮定しないでください。
フォローアップ 4: ストリームが k 個の要素未満で終了した場合はどうなりますか？
実際の要素を返すか、ドキュメントに記載されたエラーを発生させます。決して要素を捏造してはならず、コーディング前に挙動を明記してください。
フォローアップ 5: 重み付きサンプリングはどのように行いますか？
重み付きの対象分布を定義し、重み付きリザーバーのランダムキーまたは指数／対数変換を使用します。一様な k/i の証明は直接適用できなくなります。
フォローアップ 6: 分散リザーバーをどのようにマージしますか？
各シャードは、要素数と十分なランダム優先度または重み情報を保持します。グローバルサンプリングルールに従ってマージします。直接の連結やランダムな切り捨ては、小さなシャードを有利にしてしまいます。
フォローアップ 7: 一様性をどのように検証しますか？
固定された短いストリームで多数の試行を実行し、各要素の含有頻度を k/n と比較し、境界条件や再現可能なシードをテストします。統計は偏りを明らかにすることができますが、確率の証明に代わるものではありません。