プロンプトとコンテキスト
下位半分用の最大ヒープ（max-heap）と上位半分用の最小ヒープ（min-heap）を持つ MedianFinder を引き継ぎました。これは 1, 2, 3 では正常に動作しますが、10, 1, 9, 2、重複が多い入力、極端な整数などのシーケンスで失敗します。課題は既存の実装をデバッグすることであり、標準的なデータ構造を一から導出することではありません。
面接官が評価するポイント
- コードを変更する前に不変条件（invariants）を明示しているか。
- 失敗するシーケンスを縮小し、最初の無効な状態を特定できるか。
- 修正によって空のクエリ、重複、および偶数長でのオーバーフローが適切に処理されているか。
- 証明と計算量がコードと一致しているか。
確認すべき明確化の質問
- 最初の挿入前に
findMedian()を呼び出した場合、どう動作すべきですか？ - 余分な要素を保持できるのはどちらのヒープですか？
- APIが受け付ける整数のビット幅と、中央値が返す型は何ですか？
- 重複値は出現し得ますか？また、並行アクセスは対象範囲内ですか？
重複値は有効であり、下位ヒープが1つ余分に要素を持つことができ、クエリは浮動小数点値を返し、空のルックアップはドキュメント化されたエラーを送出すると仮定します。並行処理はこのコーディング課題の対象外です。
30秒での回答
「私なら各挿入後に両方のヒープを計測し、2つの不変条件をアサートします。すなわち、両ヒープのサイズの差が最大で1であり下位ヒープの方が大きいこと、そして下位のすべての値が上位のすべての値以下であること（これはヒープのトップで確認可能）です。最初に失敗した入力を最小化し、下位ヒープへ push し、その最大値を上位ヒープへ移動し、上位ヒープの方が大きくなった場合にのみ上位の最小値を下位へ戻すという手順で挿入を修正します。中央値のルックアップでは、奇数サイズの場合は下位のトップを使用し、偶数サイズの場合は両方のトップのオーバーフローを防ぐ平均を使用します。最後に、網羅的な短いシーケンスと敵対的な極端な値に対して、ソート済み配列のオラクルを実行します」
ステップごとの詳細解説
1. 失敗を観測可能にする
各挿入後に、入力のプレフィックス、両ヒープのサイズ、および両ヒープのトップを記録します。最初に破られた不変条件の時点で停止します。失敗が再現する限り値を削除していくことで、シーケンスのデルタデバッグを行います。1000個のランダムな値よりも、4つの値からなる反例の方が有用です。
2. 単一の決定論的な挿入パスで修正する
下位ヒープをエントリポイントとして使用します。x を push し、その最大値を上位ヒープへ移動し、上位ヒープの方が大きくなった場合は上位の最小値を戻します。このシーケンスにより、サイズの前に順序が復元されます。最小ヒープのみを提供する言語ライブラリの場合、下位ヒープには符号を反転した値を格納し、境界部分で符号変換を維持します。
3. ルックアップを安全にする
両方のヒープが空の場合はルックアップを拒否します。要素数が奇数の場合は、下位の最大値を返します。要素数が偶数の場合は、加算する前に両方の端点をより広い型または浮動小数点型に変換します。(a + b) / 2 は、中央値が表現可能であっても固定幅整数型でオーバーフローする可能性があります。
4. 修正を証明しテストする
下位の最大値を上位側に移動することで、下位に残った値が移動した境界を超えないことが保証されます。上位の最小値を1つ戻すことで、順序を崩さずに選択したサイズ規則が復元されます。各挿入では一定回数のヒープ操作が実行されるため O(log n) となり、ルックアップは1つまたは2つのトップを読み取るため O(1)、ストレージは O(n) です。
すべてのプレフィックスの後にソート済みリストのオラクルを使用します。空のルックアップ、1つの値、2つの極端な値、昇順、降順、低/高の交互、すべて重複、負の値、および奇数サイズと偶数サイズの間の多数の遷移をカバーします。
優れた模範回答
「偶然失敗した分岐場当たり的に修正することはしません。まず、lower.size == upper.size または lower.size == upper.size + 1、および両方が存在する場合には常に max(lower) <= min(upper) をアサートします。各 add において、下位に push し、その最大値を上位に移動し、上位の方が大きい場合にのみ上位の最小値を戻します。これにより、順序の復元が以前の入力パターンから独立します。
findMedian は空の構造を拒否します。奇数サイズのストリームは下位のトップを返します。偶数サイズのストリームは、極端な整数がオーバーフローしないように平均を取る前に両方のトップを型変換します。負の値、ゼロ、重複、および極端な値から抽出された網羅的な短いシーケンスに対して、すべてのプレフィックスをソート済み配列オラクルと比較します。コア実装は、追加ごとに O(log n)、クエリごとに O(1)、空間は O(n) のまま維持されます」
よくある間違い
- サイズのみを平衡化する → ヒープ間で値の順序が逆転する可能性があります → トップの順序を独立した不変条件としてアサートする。
- 入力値のみに基づいて分岐を選択する → 以前のヒープ状態が依然として無効である可能性があります → ヒープ間を移動する決定論的なシーケンスを使用する。
- 入力整数型で平均を計算する → 極端な端点がオーバーフローする可能性があります → 加算前により広い型へ変換する。
- ソート済みの重複のない値のみをテストする → 重複や極端な値の交互配置によって分岐エラーが隠れてしまいます → プレフィックスオラクルと敵対的シーケンスを使用する。
O(1)の挿入を主張する → ヒープの push と pop は対数時間です → 実際のヒープ操作回数をカウントする。
フォローアップの質問と回答
最小の失敗入力をどのように見つけますか？
1つの要素または連続した1つのチャンクを削除し続け、不変条件チェックを再実行します。最終的な挿入で順序またはサイズに最初に違反する最短のプレフィックスを保持し、その遷移のみを調査します。
なぜ重複値に特別な処理が必要ないのですか？
不変条件では <= を使用しているため、等しい値はどちら側に存在してもかまいません。ヒープサイズによって、等しいコピーのどれが中央値に寄与するかが決定されます。値の同一性は問題になりません。
別のヒープ実装を信頼せずにテストするにはどうすればよいですか？
小さな入力の場合、プレフィックスをコピーしてソートし、数学的な中央値を直接計算します。小さな文字セット（値の集合）上のすべてのシーケンスを網羅し、次に固定幅の極端な値とより大きなランダムケースを追加します。
これはスライディングウィンドウをサポートしていますか？
いいえ。期限切れとなった任意の値を削除するには、インデックス付きの削除、または両方のヒープでの遅延削除（lazy-deletion）カウンターが必要です。それは別の課題であり、この修正の中に暗黙的に含めるべきではありません。