プロンプトとコンテキスト
配列 words と整数 k が与えられたとき、最も頻出する k 個の単語を返します。同点の場合は辞書順の昇順で並べます。
この面接では、サイズ k の候補セットを維持すること、およびヒープのルートが最悪の候補と最良の候補のどちらを表すかを決定することに焦点を当てます。Java はコンパレータを示すためだけに使用されており、アルゴリズム自体は言語に依存しません。
面接官がテストしていること
カウント
ハッシュマップを使用して各単語をカウントし、配列の長さ n とユニーク単語数 m を区別します。
順序付けルール
頻度が高い方が優先されます。頻度が同じ場合は辞書順で小さい方を優先します。余分なエントリを削除できるように、最小ヒープのルートは「より劣る候補」にする必要があります。
計算量
完全なソートは O(m log m) です。サイズ k のヒープは O(n + m log k) であり、k がユニーク単語数よりもはるかに小さい場合に役立ちます。
正確性
エビクション（追い出し）用のヒープ順序が最終的な出力順序と異なる理由を説明します。ヒープは最悪の候補を削除するのに対し、回答では最良の候補を最初にリストする必要があるためです。
確認すべき明確化の質問
- 単語は小文字の英単語で、大文字・小文字は区別されますか？
- k は 1 からユニーク単語数の間であることが保証されていますか？
- 辞書順は ASCII、Unicode、それとも特定のビジネスロケールですか？
- 入力はストリームとして処理する必要がありますか？
- 出力は安定している必要がありますか、それとも任意の順序が許容されますか？
- 頻度が 32 ビット整数を超える可能性はありますか？
30秒の回答フレームワーク
「ハッシュマップで頻度をカウントします。各ユニーク単語について、ルートがより劣る候補（頻度が低い、または同点の場合は辞書順で大きい）となるサイズ k の最小ヒープを維持します。挿入後、ヒープが k を超えたらポップします。最後に、頻度の降順かつ辞書順の昇順でヒープのエントリを出力します。カウントのコストは O(n)、ヒープの維持は O(m log k)、空間計算量は O(m) です。」
ステップバイステップの詳細解説
ステップ 1: 頻度をカウントする
各単語をその出現回数にマッピングします。ストリーミングログの場合は外部集約や近似カウンタを使用することもありますが、この問題ではユニーク単語マップがメモリに収まると想定します。
ステップ 2: 最悪の候補を定義する
候補 A が B より劣るのは、A の頻度が低い場合です。同点の場合、A の辞書順が大きい方が劣ります。コンパレータはこの候補をヒープのルートに配置します。
ステップ 3: サイズ k を維持する
頻度マップから各エントリを挿入し、ヒープが k を超えたらポップします。これにより、ヒープには最終的な回答に属する可能性が最も高い k 個のエントリが保持されます。
ステップ 4: 出力を生成する
ヒープのポップは最悪から最良の順に行われるため、そのまま返すことはできません。収集したエントリを反転するか、頻度の降順かつ辞書順の昇順でソートします。
ステップ 5: 正確性を証明する
サイズが k を超えるたびに、現在のセットの中で最悪の要素を削除します。その要素が保持された k 個の要素のいずれかを上回ることはありません。帰納法により、最終的なヒープには全体の Top K が含まれます。
ステップ 6: 境界ケースを処理する
k=1、等しい頻度、ユニーク単語が1つ、大量の重複、および k=m をテストします。コンパレータが誤って同点の順序を反転させないようにする必要があります。
質の高い模範解答
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> count = new HashMap<>();
for (String word : words) {
count.merge(word, 1, Integer::sum);
}
PriorityQueue<String> heap = new PriorityQueue<>((a, b) -> {
int byFrequency = Integer.compare(count.get(a), count.get(b));
if (byFrequency != 0) return byFrequency;
return b.compareTo(a); // larger lexicographic value is worse
});
for (String word : count.keySet()) {
heap.offer(word);
if (heap.size() > k) heap.poll();
}
List<String> answer = new ArrayList<>();
while (!heap.isEmpty()) answer.add(heap.poll());
Collections.reverse(answer);
return answer;
}
}カウントのコストは O(n) です。ユニーク単語数を m とすると、ヒープ操作のコストは O(log k) であり、合計時間は O(n + m log k)、空間は O(m) となります。
よくあるミス
- 最良の候補をヒープのルートに置く → 正しい回答が追い出される → 最悪の候補をルートに置く。
- 同点時のコンパレータを反転させる → 出力順序が誤る → 頻度が等しい場合は辞書順で小さい単語を優先して保持する。
- ヒープからポップしたものをそのまま返す → 出力が最悪から最良の順になる → 反転するか最終ソートを行う。
- 完全ソートを行った後に O(n log k) と主張する → 計算量が誤り → 完全ソートのコストは O(m log m)。
- 異なる頻度のみをテストする → 同点時の挙動が未テストになる → すべての頻度が等しい場合や多数の同点ケースを含める。
- k=m を無視する → 不要なエビクションや境界エラーが発生する → ヒープがすべてのユニーク単語を保持できるようにする。
- 誤ってロケール依存の順序付けを使用する → 環境によって結果が異なる → 要求される順序を明示的に指定する。
- 空間分析なしでハッシュマップを挙げる → スケールが不明確になる → n、m、k の計算量を明記する。
フォローアップの質問と回答
フォローアップ 1: k が m に近い場合でもヒープを使用しますか？
完全なソートの方が定数項が小さく、コードがシンプルになる場合があります。ヒープも引き続き有効ですが、O(m log k) は O(m log m) に近づきます。
フォローアップ 2: 入力が無制限のストリームの場合はどうしますか？
正確なカウントには依然として状態が必要です。ウィンドウ処理、外部集約、または近似を使用します。正確な Top K には、十分な頻度状態を保持する必要があります。
フォローアップ 3: ユニーク単語がメモリを超える場合はどうしますか？
ディスクにハッシュパーティション分割し、各パーティションをカウントして候補をマージするか、外部ソートを使用します。配列全体をメモリにロードしてはいけません。
フォローアップ 4: 大文字と小文字を区別しない単語をどのようにサポートしますか？
カウントする前に明示的なロケールで正規化します。出力が元のスペルを保持するかどうかを定義し、同等の形式を2回カウントしないようにします。
フォローアップ 5: コンパレータをどのようにテストしますか？
等しい頻度で逆の辞書順、k=1、k=m、および重複が多い入力でアサートします。ランダムなケースを完全ソートの参照実装と比較します。
出典 1: LeetCode 692
この問題は、頻度の降順、同点時の辞書順昇順、および O(n log k) のフォローアップを定義しており、出力と計算量の目標を確立しています。
出典 2: NeetCode Top K
NeetCode は頻度マップと Top K のアプローチを示し、コンパレータおよびヒープ対ソートのトレードオフを強調しています。
出典 3: Oracle PriorityQueue
Oracle は自然順序付けまたは Comparator による PriorityQueue の順序付けを文書化しており、カスタム最小ヒープのコンパレータと poll のセマンティクスを裏付けています。