コーディング面接：重み付きリザーバーサンプリングの実装

1. 問題と背景

ストリーム内の各レコードは正の重みを持ちますが、アイテム数も総重みも不明です。サイズ k の非復元重み付きサンプルを実装してください。各レコードは最大1回しか出現せず、抽出される確率はその重みに比例し、ストリームは1回だけスキャンされます。キー生成、候補の維持、極端な重みの扱い、および分布のテストについて説明してください。

2. 面接官が見ているポイント

復元抽出と非復元抽出を区別し、重みに比例する確率を理解しているか。
重み付きサンプリングを、上位 k 個のランダム優先度または指数キーの保持に変換できるか。
サイズ k の最小ヒープ（min-heap）を選択し、レコードあたり O(log k) の更新を行えるか。
重みが0、極大、または極小の場合、乱数の境界値、重複ID、再現可能なシードを適切に処理できるか。

3. 回答前の明確化のための質問

重みは有限の正の数ですか？また、重みが0のレコードは破棄すべきですか、それとも保持すべきですか？
サンプリングは非復元抽出ですか？それとも同じレコードが複数回出現してもよいですか？
最終的なサンプルのみが必要ですか？それともすべてのプレフィックス（途中経過）で正しい分布になっている必要がありますか？
複数のシャードのマージ、状態の永続化、または結果の厳密な再現性が必要ですか？

4. 30秒の回答フレームワーク

重み w の各レコードに対して独立したランダムキーを生成し、最大の k 個のキーを保持します。数値的に安定した方法では、(0, 1] から一様に u を抽出し、key = log(u) / w を計算します。キーは負の値であるため、これは0に最も近い k 個のキーを保持することと同等です。現在のサンプルを、ルートが最小キーであるサイズ k の最小ヒープに格納し、新しいキーの方が大きい場合にのみ置き換えます。1回のパスで O(n log k) の時間と O(k) の追加空間を消費します。重みを検証し、乱数ソースを注入（DI）可能にします。

5. ステップごとの詳細解説

ステップ 1: 分布を定義する

非復元重み付きサンプリングは、確率 w / total による k 回の独立な抽出ではありません。同じレコードが重複して選ばれる可能性があるためです。目標は、残りの重みに比例して未選択のアイテムを繰り返し抽出することと同等の順序統計量分布を持つ、サイズ k の集合です。リザーバーは、ストリーム終了時だけでなく、すべてのプレフィックスの後でも有効なサンプルである必要があります。

ステップ 2: 数値的に安定したキーを生成する

指数競合（Exponential race）を用いると簡潔に実装できます。一様乱数 u を抽出し、key = log(u) / w を計算して、最大キーを保持します。u が0に近づくほど log(u) はより大きな負の値になります。重みが大きいほどキーは0に近くなり、上位 k に入る確率が高くなります。極端な重みでアンダーフローを起こしたり差が失われたりする可能性がある u ** (1 / w) は避けてください。

text

sample_key(weight):
    require finite(weight) and weight > 0
    u = uniform_random_open_interval()
    return log(u) / weight

ステップ 3: 最小ヒープでトップkを維持する

キーの完全一致によるタイを解消するためのシーケンス番号とともに、(key, sequence, item) をヒープに格納します。リザーバーがいっぱいになるまではプッシュします。いっぱいになったら、新しいキーをルートと比較し、新しいキーの方が大きい場合にのみ置き換えます。k が0の場合は、すべてのレコードを破棄します。レコードごとに配列を再ソートすると、更新計算量が O(log k) ではなく O(k log k) になってしまいます。

ステップ 4: 入力と乱数の境界値を処理する

NaN、無限大、負の重みは拒否します。重み0のレコードは正の重みのサンプルで選択されることはないため、スキップできます。乱数ソースは0を返してはなりません。さもないと log(0) が使用不能になります。再生成するか、最小の正の浮動小数点数値にクランプします。問題で明示的にIDの重複排除が求められていない限り、重複するIDは個別のレコードとして扱います。テストで失敗を再現できるように、疑似乱数ソースを注入できるようにします。

ステップ 5: 計算量、検証、および分散拡張

n 個のレコードに対して、単一マシンでの実装は O(n log k) の時間と O(k) の追加空間を消費します。固定重みのモンテカルロシミュレーションを使用して、重みに応じて周辺含有確率が上昇することを確認し、サンプルに重複がないことをアサートします。分散ストリームでは、各シャードが同じルールでキーを生成し、コーディネーターがシャードのトップk候補をマージできます。ただし、状態、更新、削除、シード、および通信コストの明示的な設計が必要です。シャードのリザーバーから単純に一様サンプリングを行うと、破棄されたレコードの情報が失われます。

6. 高評価な回答の例

正の重みを持つレコードごとに key = log(u) / w を生成します（ここで u は開区間上の一様乱数）。そして、最大の k 個のキーを保持します。キーは負の値であるため、重みが大きいほど0に近づきやすくなります。容量 k の最小ヒープにサンプルを保持し、満杯時は新しいキーが最小ルートより大きい場合にのみ置き換えます。無効な重み、0の乱数値、k = 0、重複レコードに対する動作も定義します。スキャンは計算時間 O(n log k)、空間計算量 O(k) です。重みを固定したシミュレーションの反復実行で分布を検証し、同じグローバルトップkキーのルールに従って分散候補をマージします。

7. よくある間違い

w / total による独立抽出を行う → 重複が発生し、非復元抽出にならない → ランダムキーとトップkを使用する。
u ** (1 / w) を直接計算する → 極端な重みでアンダーフローが発生する → 対数キーを比較する。
トップkの管理に最大ヒープ（max-heap）を使用する → 最小値を探索する必要が生じる → 置換対象がルートになるよう最小ヒープを使用する。
u = 0 を許可する → log(0) が負の無限大になる → 開区間の乱数ソースを使用するか再生成する。
1回きりの出力のみをテストする → 長期的なバイアスを見逃す → 重みを固定したモンテカルロテストを実行し、重複がないことをアサートする。

8. フォローアップ質問と回答

なぜ key = log(u) / w で重み付きサンプリングになるのか？

-log(u) をレート1の指数乱数とみなします。w で割ると、レート w の指数時間になります。最も小さい指数時間はレートが大きいものから生じる確率が高くなります。これに負の符号をつけることは最大キーを保持することを意味し、非復元重み付きサンプリングが得られます。

結果を再現可能にするにはどうすればよいか？

明示的なシードを持つ疑似乱数ソースを注入し、アイテム識別子、重みバージョン、アルゴリズムバージョンを実験メタデータに記録します。スレッドのスケジューリングやグローバルな乱数状態に依存しないようにします。依存すると、同一の入力でも異なるサンプルが生成される可能性があります。

すでに構築された2つのリザーバーをマージできるか？

両方のシャードが同じルールで独立したキーを生成している場合、それらの候補キーをマージしてグローバルトップ k を取得できます。2つの最終リザーバーのみを通常のデータとして扱って再度サンプリングすると、破棄されたレコードの情報が失われます。永続化されたキーや、シャードの更新・削除についても動作を定義する必要があります。

時間の経過とともに重みが変化した場合はどうするか？

重みを変更するとターゲット分布が変わるため、古いキーは新しい重みを表さなくなります。影響を受けるレコードのキーを再生成するか、重みバージョン付きのイベントをストリームに再投入します。短期的な近似が許容されるかどうか、また古いサンプルをどのように破棄・退役させるかを定義します。