k個のソート済みリストをマージする面接問題を、k-way mergeとして見抜く考え方から解説。O(N log k)の根拠、min-heapと分割統治の使い分け、Pythonの注意点まで分かります。
この問題で固まってしまう候補者は、たいていコードの形自体は分かっています。k 個のソート済みリストをマージするという面接問題は謎ではありません。多くの人が失敗するのはヒープを書けないからではなく、なぜそれを使うのかを説明できないからです。面接官が「なぜヒープなのですか？」と聞いたとき、返ってくる答えが「効率が良いからです」だと、技術的には正しくても実用的にはほとんど意味がありません。面接官が求めているのは、これはなぜ k-way merge の問題なのか、それによって解法の形がどう変わるのか、そして選んだ手法がどうやってごまかしなしに O(N log k) に収まるのかを、20秒で説明できることです。
この記事は、そのギャップを埋めます。コードだけではなく、判断、根拠、そして脱線せずに口頭で伝えられる説明まで含めてです。
コードに触る前に k way merge を見抜く
なぜこれは単なる「2つのリストをマージする」に手順を足しただけではないのか
直感的には、2つのリストをマージする処理を繰り返すものだと考えがちです。リスト1とリスト2をマージし、その結果をリスト3とマージし、という具合です。これは動きます。ただし最悪ケースでは O(Nk) の時間計算量になり、しかも面接官には「問題の本質を外している」と伝わってしまいます。
構造上の違いはここです。2つのリストをマージする問題は、各ステップでの判断が双方向です。左のノードか、右のノードか。k 個のソート済みリストをマージする問題は、多方向の判断です。いま前面に出ている k 個の候補のうち、どれが最小のノードを持っているか。これは根本的に別の仕事で、別のデータ構造を必要とします。k 個のソート済みリストを k-way merge として認識できると、解法の候補はきれいに2つに絞られます。前線を明示的に追跡する min-heap か、ペアごとのマージをバランス良く積み上げる分割統治です。どちらも正解です。どちらも「2つのリストをマージする処理に手順を足しただけ」ではありません。
面接で流暢に話せる候補者は、コードを書く前にこの違いを言語化します。トリックではなく、パターンだからです。k-way merge が見えれば、残りは実装の詳細にすぎません。
面接問題が本当に見ているもの
面接官は同時に3つを見ています。パターン認識、計算量の管理、そして「次の最小ノードは k 個の現在の先頭のどれかからしか出てこない。各リストはすでにソート済みだから、どのリストの深いところからも出てこない」という説明力です。
最後の点が、解法全体を支える不変条件です。各ステップで、グローバルに最小の残りノードは、残っている k 個のリストのどれかの先頭です。どのリストの2番目のノードを見る必要もありません。走査する必要もありません。必要なのは、k 個の候補の中から最小値を効率よく見つけ、そのリストのポインタを進め、これを繰り返すことだけです。ヒープ、再帰、マージツリー――それ以外はすべて、その操作を高速化するための手段にすぎません。
実際にはどう見えるのか
3つのリスト `[1→4→7]`、`[2→5→8]`、`[3→6→9]` を考えてみます。最初の出力ノードは 1 である必要があり、これはリスト1の先頭です。1 を取り出したら、候補は `[4]`、`[2]`、`[3]` になります。次の出力はリスト2の 2 です。すると候補は `[4]`、`[5]`、`[3]`。次は 3、という流れです。
ここで起きているのは、各ステップでちょうど k 個の候補の中から選び、ちょうど1本のポインタを進めているということです。その判断の総数は N（全リストのノード総数）回です。各判断にかかるコストは N ではなく k に依存します。これが、O(N log k) という形が問題構造から直接現れる理由です。実装からではなく、問題が実際に要求していることから出てくるのです。
流暢な候補者は、1行も書く前にこれを口にします。merge-two-lists だけを暗記した候補者は、すぐに実装を始めて、あとで計算量を聞かれると説明できません。
O(N log k) を「目標」として扱う。推測ではなく
なぜ面接官は log の中の k を気にするのか
O(N log k) は、正しい解法と良い解法を分ける計算量の主張です。log に k が入るのは、ヒープも分割統治のマージツリーも、コストが全ノード数ではなくリスト数に比例する操作を行うからです。k が小さい場合、たとえば 10 本のリストなら log k は約 3.3 です。N が100万なら、それは 330万回の操作と10億回の操作の差になります。だから面接官はそこを気にします。『Introduction to Algorithms (CLRS)』(Introduction to Algorithms (CLRS)) にある通り、優先度付きキューを使った k-way merge はまさにこの上界を達成し、ヒープベースの選択問題の標準的なベンチマークです。
実際にはどう説明するのか
口頭で言える数え上げの説明はこうです。合計 N 個のノードがあります。各ノードはヒープにちょうど1回挿入され、ちょうど1回取り出されます。ヒープへの挿入や取り出しは O(log k) です。なぜなら、ヒープに入る要素数は最大でも k 個、つまり各リストから1個ずつだからです。したがって総作業量は、N 回の挿入 × 各 O(log k) = O(N log k) です。分割統治にも同じ考え方が当てはまります。マージツリーには log k 層あります（各層でリスト数を半分にしていくからです）。各層ではすべてのノードをちょうど1回処理するので、各層 O(N) × log k 層 = O(N log k) となります。
どちらの戦略でも最終的には同じ場所にたどり着きます。違うのは、仕事の量ではなく、その仕事をどう割り振るかです。
なぜ O(Nk) ではないのかと聞かれたときの答え
素朴な方法――各ステップで k 個の先頭を総当たりして最小値を探す方法――は、ノード1個を決めるたびに O(k) かかります。ノードは合計 N 個あるので、全体では O(Nk) です。k=2 なら問題ありません。k=1000 なら、ノード1個を取り出すために1000回比較し、それを100万回繰り返すことになります。k が意味のある変数として扱われるのが、まさに面接の状況です。そこでこの構造は破綻します。
ヒープは、その O(k) の走査を O(log k) のヒープ操作に置き換えます。ヒープ自体という追加の仕組みが価値を持つのは、線形走査を対数走査に変えられるからです。これがすべてです。美しさのために複雑さを増やしているのではなく、素朴な走査が本当に遅いから追加しているのです。k が無視できないなら、当然そうなります。
いちばん通りのよい回答が欲しいなら min heap を使う
なぜヒープ版は面接向きなのか
min-heap は、アクティブな各リストから常にちょうど1ノード、つまり現在の先頭だけを保持します。制御フローは1文で説明できます。最初の先頭をすべて入れ、あとは最小値を取り出して結果に追加し、そのノードに次があればそれを入れるだけです。再帰呼び出しも、添字計算も、マージツリーの管理もありません。時間制限のある場面では、この単純さに大きな価値があります。
ヒープ版は信頼しやすいのも利点です。ヒープ不変条件が常に最小値を先頭に保証するので、どこかにより小さいノードを見落としているかもしれない、といった不安を考える必要がありません。その判断はデータ構造が代わりにやってくれます。
実際にはどう見えるのか
3つの連結リスト `1→4→7`、`2→5→8`、`3→6→9` を考えます。まずヒープを先頭ノードで初期化します。`(1, node_1_4_7)`、`(2, node_2_5_8)`、`(3, node_3_6_9)` を push します。
ステップ1: `(1, node)` を pop します。ノード1を結果に追加します。ノードの次、`(4, node_4_7)` を push します。ヒープには `(2, ...)`、`(3, ...)`、`(4, ...)` が入っています。
ステップ2: `(2, node)` を pop します。ノード2を追加します。`(5, node_5_8)` を push します。ヒープは `(3, ...)`、`(4, ...)`、`(5, ...)`。
ステップ3: `(3, node)` を pop します。ノード3を追加します。`(6, node_6_9)` を push します。以下同様です。
ヒープのサイズは k を超えません。各ノードは1回 push され、1回 pop されます。常にグローバルな最小値を追加しているので、マージ後の連結は正しく構築されます。これは、コードを見なくてもその場で説明できるドライランです。
Python の厄介なヒープ問題
Python の `heapq` は、タプルを左から順に比較します。2つのノードの値が同じだと、`ListNode` オブジェクト同士を直接比較しようとします。そして `ListNode` は `__lt__` を実装していないので、`TypeError` になります。対策は3要素タプル `(node.val, index, node)` にすることです。ここで `index` はリストの添字（0 から k-1）です。添字は一意なので、比較が `ListNode` に到達しません。
Python の heapq ドキュメント にある通り、ヒープ要素は通常の Python の比較規則で比較されます。つまり、同値のときに使う要素も比較可能でなければなりません。index を使えばそれをきれいに保証できます。
もう1つの罠は null リストです。入力リストが `None` または空なら、そのまま push するとクラッシュするか、ヒープを静かに壊します。初期化前に取り除いてください。たった2行で、ロジックミスに見える実行時エラーを防げます。
各ノードは1回挿入され、1回削除されます。index `i` が、ノードオブジェクトに触れずに同値を解消します。
分割統治も、同じアイデアをより整然と並べたものとして扱う
なぜマージツリーは別の裏技ではないのか
分割統治によるマージは、同じ k-way merge の作業を別の順序で進めているだけです。ヒープが前線を動的に追う代わりに、リストをペアにしてマージし、その結果同士をまたペアにしてマージし、1本になるまで繰り返します。作っている構造はバランスの取れた二分マージツリーで、その深さは log k です。これはヒープの計算量に出てくる log k とまったく同じです。
重要なのは、各ペアのマージが O(n₁ + n₂) だということです。ここで n₁ と n₂ はマージする2つのリストのサイズです。ツリーの各層では、すべてのマージを通じた総作業量は O(N) です。なぜなら、各層で各ノードはちょうど1回だけマージに参加するからです。log k 層あるので、総作業量は O(N log k) です。CLRS のマージソート分析 も同じ再帰構造を示しています。これは、k 個の要素ではなく k 個のリストに対してマージソートを適用したものです。
実際にはどう見えるのか
8本のリストがあれば、1ラウンド目で4本のマージ済みリストができます。2ラウンド目で2本。3ラウンド目で1本です。3ラウンド = log₂(8) = 3 層です。各層で N 個のノードすべてを1回ずつ処理します。最初から外側から内側へペアにする（リスト0と1、2と3、というように）と、構造上バランスが保たれ、各ラウンドでリストサイズもおおむね揃います。
サイズが 3, 3, 3, 3 の4本のリストなら、1ラウンド目でサイズ6の2本に、2ラウンド目でサイズ12の1本になります。比較回数の合計は 6 + 6 + 12 = 24 = 12 × 2 = N × log k です。数学は合っています。各マージステップは、2つのソート済みリストのマージが帰納的に正しいので順序を保ちますし、各層では各ノードに1回ずつしか触れません。
面接でこの説明のほうが賢く聞こえる場面
面接官が再帰について明示的に聞いてくるとき、マージソートの直感を引き出したいとき、あるいは並列化可能性について話したいときには、分割統治のほうがきれいに聞こえます。さらに「これを分散システムでやるとしたら？」と聞かれた場合も、こちらのほうが良い答えです。マージツリーは複数ワーカーにまたがる reduce 操作にそのまま対応します。
ヒープの答えは実装が速いです。分割統治の答えは、概念的に守りやすいことが多いです。マージツリーはホワイトボードに10秒で描けるし、その図を指しながら計算量を説明できます。
いままでやった人のように、ヒープか分割統治かを選ぶ
面接官が本当に評価する判断基準
選択は、どちらが客観的に優れているかではありません。計算量は同じです。限られた時間で正しく実装でき、明快に説明できるほうを選ぶ、という話です。
min-heap を使う場面: Python で `heapq` をそのまま使いたい、面接がライブコーディングで単純さがバグを減らす、再帰について聞かれていない。ヒープ版は短く、構造が直線的で、ドライランでも追いやすいです。
分割統治 を使う場面: 面接官が再帰、マージソート、ツリー構造の解法に触れた。並列処理や分散処理について聞かれた。あるいは、再帰が自然でヒープライブラリの扱いがあまり快適でない言語を使っている。マージツリーの説明は、reduce 操作に慣れたシステム設計寄りの文脈でも受け入れられやすいです。
実際にはどう見えるのか
Python の電話面接なら、まずヒープを出します。「各リストの現在の先頭を追跡するために min-heap を使います。これで再帰なしで O(N log k) にできます」と言って、そのまま実装します。
面接官がツリーを描くホワイトボード面接なら、分割統治に切り替えます。「これもマージツリーとして考えられます。リストをペアにしてマージし、それを繰り返します。同じく O(N log k) で、今描かれたツリーにもそのまま対応します」と説明します。
どちらが好みかと聞かれたら、「Python なら実装が速いのはヒープです。分割統治は図で説明しやすく、並列マージにも自然につながります。どちらも正しいので、状況に合うほうを選びます」と答えればよいです。その答えは、見せかけの断言よりずっと印象が良いです。
自信ありげに聞こえるのに実は違う誤り
「ヒープが常に優れている」「分割統治のほうがきれいだ」といった断定を、条件なしで言うのは危険です。それは判断力ではなく、好みを暗記しただけだと伝わります。この問題をよく知る面接官なら、すぐに掘り下げてきます。「k が非常に大きい場合は？ リストが別々のマシンにある場合は？」と。暗記した好みには答えがありません。
正直な言い方はこうです。どちらの方法も同じ複雑度で同じ問題を解けます。適切な選択は、面接の文脈、言語、そして面接官が実際に何を見ているかで決まります。これは言うのが少し難しいですが、尊敬を得るのはその答えです。
いつもの落とし穴を踏まずに実装する
null リストと重複値の罠
k 個のソート済み連結リストをマージするコードを書く前に、3つの質問に答えてください。各リストは `None` になり得るか。各リストは空になり得るか（非 null のポインタが何も指していない場合）。そして、同じ値が複数のリストに現れることがあるか。
null リストは、チェックせずに push するとヒープ初期化時に落ちます。空リストは少しだけ見え方が違います。ポインタは存在するけれど `node` が falsy です。どちらもヒープ初期化前に除外する必要があります。重複値はバグではありません。正しくマージされます。ただし、前述の Python の比較問題を引き起こします。index によるタイブレークを使っていない場合です。
実際にはどう見えるのか
index によるタイブレークがないと何が起きるか。別のリストにある値 5 のノードが2つあるとします。Python はまず1つ目を pop し、その次（値 7）を push します。そして残っている `(5, ListNode)` と `(7, ListNode)` を比較しようとします。値は違うのでノード比較には到達せず、問題ありません。しかし後で別の 5 が来ると `(5, ListNode)` 同士を比較し、クラッシュします。タプルに index を入れれば、`(5, 0, node)` と `(5, 2, node)` は index で解決され、node に触れることはありません。
きれいな実装では、新しいノードを作らずに既存ノードをそのまま使います。`tail.next = node` です。これは、`tail` を再代入する前に `node.next` を進める限り正しいです。1回通しの不変条件は、`tail` が常にマージ済み連結リストの末尾を指し、その後ろに余計なポインタが残らないことです。
ポインタを壊さないための一回通しの考え方
各ノードはヒープに1回だけ入って、1回だけ取り出されます。ノードを取り出して `tail.next = node` としたら、そのノードはすでにマージ済みチェーンの一部です。`node.next` を push するのは、そのリストの次の候補をキューに入れているだけです。変更するポインタは `tail` だけです。今追加したノードへ進めます。他は何も変えません。
不変条件はこうです。ループの各ステップで、`dummy.next` は正しくマージされたチェーンの先頭であり、その終端は `tail` です。また、ヒープには未消費の各リストの現在の先頭だけが入っています。各反復の開始時にこの不変条件が成り立っていれば、終了時にも成り立ちます。各ノードは1回挿入され、1回削除され、1回追加されます。
面接官が割り込むのをやめるくらい、明確に言う
20秒の答え
口頭ではこう言えます。「これは k-way merge の問題です。各ステップで次に出力されるノードは、k 個の各リスト先頭の最小値です。これを効率よく追跡するために min-heap を使えば、取り出しごとに O(log k)、全体で O(N log k) になります。null リストはヒープ初期化前に処理し、Python では同値比較エラーを避けるために index をタイブレークとして使います。」
これで終わりです。30秒で、パターン、方針、計算量、エッジケースまで入っています。面接官は、あなたが1行も書く前に問題を理解していると分かります。
実際にはどう見えるのか
面接で k 個のソート済みリストをどう説明するかの、モデルとなる始め方です。「コードを書く前に、制約を確認させてください。入力リストは null や empty になり得ますか？ リスト間で重複値はありますか？ それと、ノードをそのまま再利用する in-place 方式でよいですか、それとも新しいノードを作成する必要がありますか？」
この3つの質問は10秒で済み、単なるハッピーパス以上に考えていることを示せます。そのあとでこう続けます。「分かりました。min-heap を使います。各 non-null リストの先頭を `(value, index, node)` のタプルとしてヒープに入れ、同値を処理します。そのあと最小値を pop して結果に追加し、次があれば successor を push します。これで時間計算量は O(N log k)、ヒープの空間計算量は O(k) です。」
それからコードを書きます。始める許可を求める必要はありません。書きながら短く説明するのはよいですが、1行ごとに止まって説明する必要はありません。
なぜその選択が正しいのかを詰められたとき
圧力をかけられても通る答えはこうです。「この場合ヒープが適切なのは、実装が直線的で、不変条件を確認しやすいからです。ヒープには最大でも k 個の要素しか入らないので各操作は O(log k) で、しかもそれをちょうど N 回行います。分割統治ももちろん説明できます。マージツリーを使う別の形で同じ O(N log k) に達し、並列化もしやすいです。ただ、Python で単一マシン実装を時間内に正確に仕上げるなら、ヒープのほうが簡単です。」
この返答は、代替案を切り捨てずに選択を擁護し、最後に O(N log k) に話を戻します。面接官の注意はそこに着地すべきです。
強い候補者は、聞かれる前に計算量を口にします。弱い候補者は、聞かれるまで待ち、根拠のない数字を出します。違いは知識ではありません。考えながら話す習慣があるかどうかです。コードを書いた後ではなく、書きながら説明することです。
Verve AI が、k 個のソート済みリストのマージ面接対策をどう助けるか
この問題の準備で構造的に厄介なのは、ヒープ vs 分割統治を読むだけでは、面接が本当に試しているスキル――20秒の説明を、圧力のある状況で、しかも突っ込みを返してくる相手に向かって口に出す力――が身につかないことです。ネット上の解説をすべて読んでも、面接官に「なぜ O(Nk) ではないのですか？」と聞かれた瞬間に頭が真っ白になることはあります。リアルタイムでその質問に答えた経験がなければ、なおさらです。
Verve AI Interview Copilot は、まさにそのギャップのために作られています。あなたの口頭回答をリアルタイムで聞き取り、事前に考えていた内容ではなく、実際に話している内容を見て、ズレた箇所に対して具体的に返します。一般的なルーブリックではありません。ヒープの説明は正しくても計算量の根拠でつまずいたなら、Verve AI Interview Copilot はそのギャップをすぐに拾います。すでに話を進めてしまった後ではなく、その場でです。20秒の説明が2分に伸びているなら、それも検出します。
本当に役立つ練習は、アルゴリズムを読み返すことではありません。3つの連結リストでヒープの push と pop を口に出しながらドライランを行い、最後に誰かが反論してきたときに O(N log k) を دفاعすることです。Verve AI Interview Copilot は、面接前夜の23時に人間の練習相手を用意しなくても、その圧力を再現する模擬面接を実行できます。メモを見ずに計算量の説明がすらすら出るまで、この問題の口頭説明の練習に使ってください。
結論
これは、ヒープを書けるかどうかの問題ではありませんでした。k 個のソート済みリストのマージという面接問題は、k-way merge を見抜けるか、2つの正しい戦略から選べるか、そして面接官が次に進むか掘り下げるかを決める時間の中で、その選択を説明できるかを試しています。
一度内在化してしまえば、判断は難しくありません。きれいで直線的な実装を素早く書きたいならヒープ。再帰、マージツリーの考え方、並列思考を面接官が求めているなら分割統治。どちらも O(N log k) に着地します。どちらも正当化できます。間違っているのは、説明できないほうです。
次の面接の前に、2つやってください。まず、20秒の説明――パターン、方針、計算量、エッジケース――を、考えずに言えるまで練習すること。次に、3つの連結リストで1回、ポインタレベルのドライランをして、各ヒープの push と pop を声に出して説明すること。この2つがメモなしでできるなら、この問題の準備はできています。どちらかでつまずくなら、直すべきはコードではなく、説明です。
Verve AI
コンテンツ