プロンプトと適用可能なコンテキスト
整数配列 nums と整数 k が与えられたとき、重複を除いた k 番目に異なる値ではなく、ソート順で k 番目に大きい要素を返してください。1 <= k <= nums.length <= 100,000 かつ -10,000 <= nums[i] <= 10,000 であると仮定します。
例えば、nums = [3, 2, 1, 5, 6, 4] と k = 2 では 5 を返します。nums = [3, 2, 3, 1, 2, 4, 5, 5, 6] と k = 4 の場合、答えは 4 です。重複する値は個別の順位を占めます。
これは、コーディング面接における代表的な順序統計量の問題です。完全なソート、サイズ k の最小ヒープ、クイックセレクトのいずれも、異なる制約のもとで有効な解法となります。以下の主な解答では、入力がインメモリの変更可能な配列であり、1つの順位のみが求められているため、ランダム化3-wayクイックセレクトを採用しています。これは nums を変更するため、呼び出し元が入力の保持を要求する場合は、あらかじめ配列をコピーしてください。
面接官が評価するポイント
第1の評価基準は、仕様（コントラクト）の正確さです。「k 番目に大きい」とは、重複を含めて降順にソートしたときの位置 k を意味します。k 番目に異なる一意な値、上位 k 個の値、あるいは0-indexed配列のインデックス k を意味するわけではありません。昇順では、求められている要素の0-indexedインデックスは n - k になります。
第2の評価基準は、単にクイックセレクトを暗記して暗唱するのではなく、代替案を導出できるかどうかです。ソートは O(n log n) で最も安全なベースラインです。サイズ k の最小ヒープは時間 O(n log k)、空間 O(k) を要し、ストリーミング入力にも対応します。クイックセレクトはターゲットを含み得ないパーティションを破棄し、期待計算時間は O(n) ですが、ランダムピボットを用いても最悪ケースの O(n^2) を完全に排除できるわけではありません。
第3の評価基準は、明確に言語化されたパーティション不変条件（invariant）です。「クイックソートのように見える」コードだけでは不十分です。候補者は、lt より前、lt と i の間、i と gt の間、および gt より後ろの要素について何が言えるかを説明でき、次の探索区間に目的の順位がまだ含まれている理由を明確に説明できる必要があります。
最後に、面接官は重複の処理、配列の破壊的変更の明記、無効な入力に対する挙動、再帰の深さのリスクを回避する反復制御、そしてシンプルなオラクル（検証ロジック）と結果を比較するテストを確認します。証明境界や敵対的テストのない最適化アルゴリズムは不完全です。
回答前に確認すべき質問
- k 番目に大きい要素は重複をカウントしますか？ この解答はソートされた位置に従うため、
[5, 5, 4]でk = 2の場合は5を返します。重複を除外した一意な順位が必要な場合は、重複排除や出現頻度を考慮した選択が必要になります。 kは常に有効であることが保証されていますか？また配列が空になることはありますか？ 面接で提示された前提条件では1 <= k <= nが保証されています。実装では、単体での挙動を明確にするため、この範囲外に対してValueErrorを送出します。- 関数が入力を変更（破壊）してもよいですか？ インプレースのパーティションにより補助空間は
O(1)になります。変更が禁止されている場合は、最初にコピーして追加のO(n)空間を受け入れます。 - 入力は完全にメモリ上に揃っていますか、それともストリーミングですか？ クイックセレクトにはランダムアクセスと変更が必要です。制限のないストリームの場合は、代わりにサイズ
kの最小ヒープを保持します。 - 同じデータに対して1回のクエリですか、それとも多数の順位クエリが発生しますか？ 1つの順位を求める場合はクイックセレクトが有利です。後続の多数のクエリによって最初の
O(n log n)の作業が正当化される場合は、一度ソートしておく方が優れている場合があります。 - 値の範囲は実際に小さく固定されていますか？ 提示された範囲には20,001通りの整数値しかないため、カウントソートの手法も有効な代替案です。範囲の幅を
Rとすると、時間O(n + R)、空間O(R)がかかりますが、値の範囲が無制限の場合は汎用的な解法として提示すべきではありません。 - 最悪計算時間を制限する必要がありますか？ ランダム化クイックセレクトは期待線形時間を実現しますが、決定論的な最悪線形時間ではありません。厳密な最悪ケースの保証が必要な場合は、中央値の中央値法（median-of-medians）を議論するか、予測可能な
O(n log k)時間を持つヒープを選択します。
30秒の回答フレームワーク
「重複をカウントした場合、k 番目に大きい要素は昇順インデックス n - k にある要素です。ソートはシンプルな O(n log n) のベースラインを提供し、サイズ k の最小ヒープはストリーミングや非破壊入力に対して O(n log k) の時間を実現します。この問題は変更可能なインメモリ配列内の単一の順位を求めるものであるため、反復的なランダム化クイックセレクトを採用します。アクティブな区間を、ランダムなピボットより小さい値、等しい値、大きい値の3つに分割します。n - k が等しい値の領域にあればピボットが答えとなり、そうでなければそのインデックスを含む側のみを残します。3-wayパーティションにより、等しい値を繰り返し1つずつ剥がす無駄を回避できます。期待計算時間は O(n)、最悪ケースは O(n^2)、補助空間は O(1) です。ランダムな配列に加えて、すべて同じ値、ソート済み、逆順ソート、重複が多いケース、および k の境界ケースでソート結果と照合して検証します。」
ステップバイステップの詳細な回答
まずはオラクル（正解基準）から始めます。昇順にソートして sorted(nums)[len(nums) - k] を返す方法は説明しやすく、誤りが起きにくいです。順位の変換関係を確立し、テスト用の参照結果を提供します。元の入力をコピーで保持する場合、そのコストは時間 O(n log n)、空間 O(n) です。
サイズ制限付きヒープは、k が小さい場合やデータが段階的に届く場合に効率的です。各値を最小ヒープにプッシュし、サイズが k を超えるたびに最小値を削除します。すべての値を処理した後、ルートは上位 k 個の要素の中で最小のもの、つまり k 番目に大きい要素になります。ヒープは k 個の値を保持するため、コストは時間 O(n log k)、空間 O(k) です。k が n に近く、配列全体がすでに利用可能な場合、この優位性は小さくなります。
クイックセレクトは、最終的な1つの位置のみが重要であるという事実を利用します。降順の順位を target = len(nums) - k に変換します。各アクティブ区間 [left, right] において、ランダムなピボット値を選択し、ダッチ・ナショナル・フラッグ（オランダ国旗）パーティションを実行します。走査中は以下を維持します：
[left, lt)にはピボットより小さい値が含まれる。[lt, i)にはピボットと等しい値が含まれる。[i, gt]は未分類である。(gt, right]にはピボットより大きい値が含まれる。
走査が終了すると、[lt, gt] が完全に等しい値の帯になります。target < lt の場合は、より小さい値の側で処理を継続します。target > gt の場合は、より大きい値の側で処理を継続します。それ以外の場合、ターゲットは等しい値の帯の中に収まっているため、ピボット値が答えになります。この処理は [7, 7, 7, 7] のような配列で重要です。2-wayパーティションではほぼ変わらない作業を繰り返す可能性がありますが、3-way版は1回の走査で完了します。
import random
def find_kth_largest(nums: list[int], k: int) -> int:
if not 1 <= k <= len(nums):
raise ValueError("k must be between 1 and len(nums)")
target = len(nums) - k
left = 0
right = len(nums) - 1
while left <= right:
pivot = nums[random.randrange(left, right + 1)]
lt = left
i = left
gt = right
while i <= gt:
if nums[i] < pivot:
nums[lt], nums[i] = nums[i], nums[lt]
lt += 1
i += 1
elif nums[i] > pivot:
nums[i], nums[gt] = nums[gt], nums[i]
gt -= 1
else:
i += 1
if target < lt:
right = lt - 1
elif target > gt:
left = gt + 1
else:
return pivot
raise RuntimeError("unreachable for a valid k")i のインクリメントは意図的に非対称になっています。ピボットより大きい値を nums[gt] と交換した後、i に新しく入ってきた値はまだ分類されていないため、i はその場にとどまります。小さい値を左に移動した後は、交換された両方の位置の分類が確定しているため、lt と i の両方が進みます。
正当性は、不変条件と順位の絞り込みから導かれます。パーティションはすべての入力要素を保持し、等しい値の帯の前にすべての小さい値、後ろにすべての大きい値を配置して終了します。したがって、[lt, gt] のすべてのインデックスは、ソート順においてピボット値を持ちます。ターゲットがその帯の外側にある場合、破棄された側と等しい帯にはターゲットのインデックスを占める要素は含まれず、保持された区間に依然として含まれます。各反復はリターンするか、区間を厳密に縮小するため、有効なターゲットがいずれ必ず返されます。
各パーティションは現在の区間を1回走査します。ランダムなピボットを使用した場合、順次保持される区間にわたる期待合計作業量は O(n) です。極端なピボットが連続して選ばれると、区間のサイズが n - 1、n - 2 のようになり、最悪計算時間 O(n^2) が発生する可能性があります。実装は反復的であり、インプレースでパーティションを実行するため、補助空間は O(1) です。乱数生成器の状態および入力配列自体は補助ストレージとしてカウントされません。
固定された例だけでなく、シンプルなソートによるオラクルを使用してテストします：
def oracle(nums: list[int], k: int) -> int:
return sorted(nums)[len(nums) - k]
cases = [
([3, 2, 1, 5, 6, 4], 2),
([3, 2, 3, 1, 2, 4, 5, 5, 6], 4),
([1], 1),
([7, 7, 7, 7], 3),
([-5, -1, -3, -1], 2),
(list(range(1000)), 1),
(list(range(1000)), 1000),
]
for values, rank in cases:
assert find_kth_largest(values.copy(), rank) == oracle(values, rank)多数の重複値を含む生成配列を追加し、すべての有効な k をオラクルと比較します。また、k = 0、k > n、および空の配列がドキュメント通りのエラーを送出することをアサートします。乱数生成器にシードを設定することで、失敗したプロパティテストを再現可能にします。複数のシードを実行することで、さまざまなパーティションパスを検証します。
高品質な回答例
「重複は個別のソート位置として扱い、k が有効であると仮定します。配列が昇順にソートされている場合、答えはインデックス n - k にあります。ベースラインはソートしてインデックス参照する方法で、O(n log n) です。サイズ k の最小ヒープは O(n log k) であり、ストリーミングデータにはこれを選択します。
ここではクエリが1回のみであり、配列を変更できるため、ランダム化クイックセレクトを使用します。アクティブな範囲内でランダムなピボットを選択し、値をピボット未満、等しい、より大きいに分割します。重複が複数の順位を占めるべきであり、すべて等しい入力が1回のパーティションで完了する必要があるため、3-way分割が重要です。パーティション後、n - k が等しい範囲内にある場合はピボットを返します。そうでない場合は、そのインデックスを含み得ない側を破棄し、反復的に繰り返します。
不変条件は、lt より前のすべてがピボット未満、lt から i までが等しく、gt より後ろがより大きく、中央の未知のセクションが未分類であることです。これにより、最終的な等しい帯がソート時の正しい順位区間を持つことが証明されます。したがって、保持された側に依然として答えが含まれます。
ランダムなピボットは通常、かなりの割合を排除するため、期待実行時間は O(n) ですが、最悪ケースは依然として O(n^2) です。ループとインプレースパーティションは O(1) の補助空間を使用します。関数が入力を変更することを明記し、生成された配列に対してソートオラクルと比較し、重複、すべて等しいデータ、ソート済みおよび逆順ソート配列、負の値、k = 1、k = n をテスト対象に含めます。」
よくある間違い
- k 番目に異なる一意な値を返してしまう → 仕様上、重複は個別の位置として扱われます → 重複排除を行わずに、直接昇順インデックス
n - kに変換してください。 - 昇順でインデックス
kまたはk - 1を使用してしまう → 方向の変換が間違っています →k = 1がn - 1に、k = nが0に対応することを確認してください。 - 最小ヒープ解法が
O(n log n)であると主張してしまう → ヒープの要素数はkを超えません → 時間O(n log k)、空間O(k)と述べてください。 - 両方のパーティションに対して再帰してしまう → それはクイックソートの処理であり、単一順位を求める目的を無視しています →
targetを含む区間のみで継続してください。 - 常に先頭または末尾をピボットとして選択してしまう → ソート済みまたは意図的に作られた入力により、サイズ
n - 1の区間が繰り返し作られる可能性があります → ピボットをランダム化し、最悪ケースの注意点を述べてください。 - 重複について言及せずに2-wayパーティションを使用してしまう → 等しい値が多い配列では処理がほとんど進まない場合があります → 1つの等しい値の帯を作成し、ターゲットがその中に収まった時点でリターンしてください。
gtと交換した後にiをインクリメントしてしまう → 新しく入ってきた値が未分類のままスキップされる可能性があります → その値が分類されるまでiを固定したままにしてください。- ランダム化によって線形時間が保証されると主張してしまう → 運悪く極端なピボットが選ばれる可能性は残ります → 期待値は
O(n)、最悪ケースはO(n^2)と述べてください。 - 入力の変更（破壊）を隠してしまう → 呼び出し元が元の順序に依存している可能性があります → 変更する契約を明記するか、コピーを作成して空間
O(n)を計上してください。 - 2つのテストケースしか確認しない → オフバイワン、重複、パーティションのバグが見落とされます → 境界値、構造化されたケース、生成された入力全体でソート結果と比較してください。
フォローアップの質問と対処法
フォローアップ1：入力が無制限のストリームである場合は何が変わりますか？
完全なランダムアクセス配列が存在しないため、クイックセレクトは適用できなくなります。最大 k 個の値を保持する最小ヒープを維持します。サイズが k に達するまでプッシュし、その後はより大きい値が届いた場合にのみルートを置き換えます。ルートがこれまでに現れた中で k 番目に大きい値になります。更新コストは O(log k)、クエリコストは O(1)、メモリは O(k) です。k 自体が任意に変更される場合、この状態保持だけでは不十分となり、より高度な順序構造またはデータの保持が必要になります。
フォローアップ2：関数が元の入力を保持しなければならない場合はどうしますか？
最もシンプルな適合策は、working = nums.copy() を行ってから working に対してクイックセレクトを実行することであり、補助空間は O(n) に変わります。サイズ k のヒープは O(k) の空間で入力を保持するため、k が小さい場合に有利です。n が比較的小さい場合や、多数の順位クエリでソート結果を再利用する場合は、コピーを完全にソートする方がシンプルです。
フォローアップ3：最悪ケースの線形時間を保証できますか？
中央値の中央値法（Median-of-medians）は、最悪ケースでも一定割合を破棄するピボットを選択するため、決定論的に O(n) の選択が可能です。実装が複雑で定数倍も大きいため、要件で明示的に最悪ケースの保証が求められない限り、面接ではランダム化クイックセレクトが実用的な選択肢となります。サイズ制限付きヒープは、よりシンプルで予測可能な O(n log k) の代替手段を提供します。
フォローアップ4：狭い整数範囲をどのように活用しますか？
-10,000 から 10,000 までの値に対する度数配列を作成し、nums を走査した後、度数を大きい方から小さい方へ走査しながら k からカウントを減算します。残りの順位を包含する最初のバケットが答えになります。範囲の幅を R = 20,001 とすると、時間 O(n + R)、空間 O(R) がかかります。これは決定論的で重複も自然に処理できますが、範囲が広い場合や無制限の場合には適しません。
フォローアップ5：面接官がソートされた上位 k 個の要素を求めた場合はどうしますか？
単一の順序統計量だけでは出力全体を満たせなくなります。サイズ k のヒープを作成した後にそのヒープをソートすると、時間 O(n log k + k log k)、空間 O(k) がかかります。クイックセレクトで順位 n - k の前後をパーティション分割し、その後選択された k 個の値をソートすると、期待計算時間は O(n + k log k) です。配列の変更可否、メモリ、最悪ケース要件、および出力順序が必要かどうかに基づいて選択してください。
フォローアップ6：ランダム化テストの失敗をどのように再現可能にしますか？
外部から注入された乱数生成器を受け取るか、各テストの前に生成器のシードを設定します。失敗時にはシード、入力、k を記録します。複数の固定シードに対して同じ入力を実行し、すべての答えをソートオラクルと比較します。これにより、特定のピボットパスによるものとアルゴリズム自体のエラーを切り分けつつ、CI（継続的インテグレーション）での再現性を維持できます。