プロンプトとスコープ
add(task, priority)、update(task, priority)、remove(task)、pop() を備えた優先度付きキューを実装してください。同一の優先度は挿入順に返される必要があり、update と remove はならし O(log n) である必要があります。ヒープ内の古い（stale）エントリがどのように処理されるかを説明してください。
これは単にヒープ API を呼び出せるかだけでなく、可変優先度付きキューの正しさをテストします。Python の heapq ドキュメントでは、安定した順序付け、比較不可能なタスク、優先度の更新、保留中の削除が難しい点として強調されています。一般的な設計では、タイ解決のためのカウンタ、位置特定のためのマップ、およびヒープの不変条件を維持するための遅延削除を使用します。
面接官がテストしていること
第1に、優先度、挿入順序シーケンス、タスクという完全なヒープキーを記述できるか？ 第2に、更新と削除でヒープを直接破壊することを回避できるか？ 第3に、重複タスク、空のキュー、古いルート、長期間残るガベージエントリを適切に処理できるか？
回答前に明確にすべき質問
- 優先度は数値ですか、それとも比較可能なオブジェクトですか？ 小さい値が先に来る、比較可能な整数を想定します。
- タスク ID は一意ですか？ はいと想定します。重複した
addは更新であるか、明示的なエラーのいずれかです。 - 安定した順序付けは必須ですか？ 同一優先度の場合は最初の挿入順を使用すると想定します。
- 遅延削除によって一時的にメモリが保持されることは許容されますか？ クリーンアップおよび再構築（rebuild）ポリシーがあれば許容されます。
- 呼び出しはスレッドセーフ（並行）である必要がありますか？ 単一スレッドを想定します。並行性には外部ロックまたは安全なコンテナが必要です。
30秒で答えるフレームワーク
「[priority, sequence, task] を最小ヒープ（min-heap）に格納し、各タスク ID をその現在の有効なエントリにマップします。更新時は古いエントリを削除済みとしてマークし、新しいシーケンスで新しいエントリを挿入します。remove もエントリを古い（stale）としてマークします。pop は現在のエントリが見つかるまで古いエントリをスキップします。シーケンスによって安定したタイ解決が実現され、マップによって O(1) の検索が可能になり、ヒープ操作は O(log n) であり、定期的な再構築によって遅延エントリの領域を制限します。」
ステップごとの詳細解説
ステップ 1: 不変条件と操作の規約を定義する
ルートは、有効なエントリの中で最小の (priority, sequence) である必要があります。マップは各タスクの現在のエントリを格納します。タスクには最大で1つの有効なエントリが存在します。古いエントリはヒープ内に残る可能性がありますが、返されることは決してありません。空の pop がエラーを発生させるか、空の値を返すかを定義します。
ステップ 2: 比較可能なヒープエントリを選択する
[priority, sequence, task] を使用します。単調増加する sequence により、タスクオブジェクト同士を比較することなく、同一優先度を比較可能にします。ビジネス上の優先度の方向が逆の場合は、値を反転させるか、コンパレータを一貫してラップします。操作間でルールを混在させないでください。
ステップ 3: add と update を実装する
最初の add はシーケンスを割り当て、マップとヒープの両方にエントリを書き込みます。update は存在を確認し、古いエントリを REMOVED としてマークし、新しいエントリを挿入して、マップのポインタを置き換えます。ヒープ検索や手動の sift は行われないため、操作は O(log n) のままです。
add(task, priority):
if task is active: mark old entry removed
entry = [priority, next(sequence), task]
current[task] = entry
heappush(heap, entry)ステップ 4: 遅延削除を用いた remove を実装する
remove はマップからタスクを削除し、ヒープエントリ内のタスクフィールドを REMOVED に置き換えます。配列から直接削除するとヒープが破損し、余分な修復が必要になります。遅延削除は変更ごとに1つの既知のエントリを操作するため、一時的なガベージと引き換えに済みます。
ステップ 5: pop で古いエントリをスキップさせる
ルートを繰り返し pop します。REMOVED とマークされている場合は、処理を続行します。マップが pop されたエントリそのものを指していない場合、そのエントリは更新によって無効化されているためスキップします。有効なエントリの場合は、マップのキーを削除してタスクを返します。ヒープが完全に空になった後にのみ、キューが空であるエラーを発生させます。
ステップ 6: 計算量とならし計算量の限界を証明する
add、update、remove は、1回のヒープ挿入または定数時間のマーキングを実行するため、O(log n) または O(1) のマーキングとなります。各古いエントリが pop されるのは最大でも1回であるため、スキップされた作業はそれを作成した更新または削除にならし計算されます。pop を行わずに更新が続くと空間が肥大化するため、再構築が必要になります。
ステップ 7: 再構築と空間制御を設計する
ヒープの長さが有効なエントリの固定倍数（例えば2倍）を超えた場合、または古いエントリが閾値を超えた場合、マップから現在のエントリを保持してヒープを再構築します。再構築には O(n) のコストがかかりますが、頻度の低いトリガーにより、ならしコストは制限された状態を維持できます。既知のタスク上限がある場合、一連の更新バッチの後にクリーンアップを実行することもできます。
ステップ 8: 境界テストを網羅する
空のキュー、安定した同一優先度、繰り返しの更新、remove 後の pop、更新された古いエントリがルートに到達するケース、すべてのエントリが古くなるケース、比較不可能なタスクオブジェクト、再構築の前後で同一の結果が得られることをテストします。単純な辞書＋ソート済みリストモデルに対して、ランダムな操作による差分テストを実施します。
トレードオフと境界
トレードオフ 1: 遅延削除かインデックス付きヒープか
遅延削除は、一般的な実装においてコードが短くリスクが低いです。インデックス付きヒープは即座に削除して空間を制御しますが、スワップ中の位置管理はバグが発生しやすくなります。削除頻度とメモリ制約によって正当化される場合にのみ、インデックス付きヒープを選択してください。
トレードオフ 2: シーケンスがオーバーフローする可能性はあるか？
固定幅の整数はラップアラウンドして安定した順序付けを壊す可能性があります。無制限の整数を使用するか、安全な再構築中にすべてのアクティブなエントリに番号を付け直します。アクティブなエントリがまだ古い値に依存している間は、カウンタをリセットしないでください。
トレードオフ 3: エラーか空の値か
ライブラリでは一般に、呼び出し元が「タスクがない」ことと「タスクの値が null である」ことを区別できるように、明確なキューが空である例外を発生させます。API が空の値を返す場合は、曖昧さを文書化し、競合するタスク値を許可しないようにしてください。
障害訓練と発展計画
訓練 1: 1つのタスクを繰り返し更新する
1つのタスクを 10,000 回更新してから pop し、最新の優先度が正確に1回だけ返されることを確認します。古いエントリの増加を観察し、再構築をトリガーしてヒープの不変条件を再確認します。
訓練 2: ランダムな混合操作
ランダムな add、update、remove、pop 操作を生成し、辞書＋ソート済みリストモデルと比較します。同一優先度のシーケンス順序と、更新された古いエントリが絶対に漏洩しないことに注目します。
訓練 3: エラーとリソース制限
存在しないタスクに対して update/remove を呼び出し、空のキューを pop し、メモリ閾値で再構築をトリガーします。安定したエラー型、タスクの消失がないこと、部分的に再構築された状態が呼び出し元に公開されないことを確認します。
よくある間違いとフォローアップ
間違い 1: 優先度とタスクのみを格納する
タスクオブジェクトが比較不可能である可能性があり、同一優先度の比較が失敗します。安定したシーケンスまたは比較不可能なラッパーを追加してください。
間違い 2: update のためにヒープエントリをインプレースで変更する
エントリが正しい位置にとどまらなくなり、ヒープの不変条件に違反する可能性があります。古いエントリを古いものとしてマークし、新しいエントリを挿入してください。
間違い 3: 削除のために配列の remove を呼び出す
探索が O(n) となり、その後にヒープの修復が必要です。マップを使用してエントリを特定し、古いものとしてマークしてください。
間違い 4: pop でタスクフィールドのみをチェックする
更新された古いエントリでも同じタスク ID を保持している可能性があります。pop されたオブジェクトが現在のマップエントリであることを確認してください。
間違い 5: 古いエントリの空間を無視する
遅延削除は依然としてメモリを消費します。再構築の閾値を設定し、ヒープの長さ、有効なエントリ数、古いエントリの比率を監視してください。
間違い 6: 優先度の方向を暗黙のままにする
最小ヒープは最小の値を最初に返します。数値が大きいほどビジネス上の優先度が高いことを意味する場合は、add と pop の規約で整合性が取れるように変換を定義してください。