コーディング面接問題集

パターン： ツーポインター·計算量： 時間 O(n)、空間 O(1)

ソート済みの配列の両端にポインターを置きます。和が小さすぎれば左のポインターを進め、大きすぎれば右のポインターを戻します。配列がソートされているので、条件を満たすペアを飛ばすことはありません。この不変条件こそ、面接官があなたに声に出して説明してほしいことです。

パターン： ハッシュマップ／出現回数のカウント·計算量： 時間 O(n)、空間 O(1)（文字の種類が固定の場合）

1つ目の文字列の文字の出現回数を数え、2つ目の文字列を走査しながら減らし、すべての回数がゼロに戻るかを確かめます。聞かれる前に発展問題にも触れましょう。Unicode全体を扱うなら、26要素の固定配列ではうまくいかないので、ハッシュマップを使います。

パターン： フロイドの循環検出（低速・高速ポインター）·計算量： 時間 O(n)、空間 O(1)

一方のポインターを1ノードずつ、もう一方を2ノードずつ進めます。両者が出会えば閉路があります。定番の発展問題である閉路の入口の特定にも備えましょう。一方のポインターを先頭に戻し、再び出会うまで両方を1ノードずつ進めます。

パターン： ボイヤー・ムーアの多数決アルゴリズム·計算量： 時間 O(n)、空間 O(1)

候補とカウンターを持ちます。一致すれば増やし、一致しなければ減らし、カウンターがゼロになったら候補を入れ替えます。過半数要素はn/2回より多く現れるので、必ず最後まで残ります。「なぜ」残るのかを説明することこそが、この面接の核心です。

パターン： 1回の走査と、それまでの最小値の保持·計算量： 時間 O(n)、空間 O(1)

それまでに見た最安値と、今日売った場合の最大の利益を記録します。走査は1回、変数は2つです。これは「最良の途中状態を持ち回る」という考え方の最も小さな例で、のちにKadaneのアルゴリズムにも登場します。そのつながりに触れると評価が上がります。

パターン： ソート＋線形走査·計算量： 時間 O(n log n)、空間 O(n)

区間を開始位置でソートし、順に走査します。現在の区間が、最後にマージした区間の終了より後に始まるなら追加し、そうでなければマージした区間の終了を両者の大きいほうまで延ばします。実際の仕事をしているのはソートです。そう明言し、比較のエッジケース（端が接する区間）を正しく扱いましょう。

パターン： ハッシュセット＋連続列の始点·計算量： 時間 O(n)、空間 O(n)

すべての数をセットに入れ、1つ前の数がセットにない数（連続列の始点）からだけ数え始めて、前へ進みます。各要素を訪れるのは多くても2回です。これが、「でもループが入れ子になっていますよね」という指摘に対して、O(n)だと説明する根拠になります。

パターン： 前方・後方からの累積積·計算量： 時間 O(n)、出力以外の追加空間 O(1)

割り算を使わずに2回走査します。まず各要素に、その左側すべての積を入れ、次に右から走査しながら、右側すべての積を掛けていきます。割り算を使う解法はゼロを含む場合に失敗するため、面接官はたいてい割り算の使用をはっきり禁止します。

パターン： 補助スタックによる不変条件·計算量： 1操作あたり O(1)、空間 O(n)

値のスタックと並べて、先頭が常にそれより下のすべての要素の最小値になる最小値スタックを持ちます。min(新しい値, 現在の先頭)をプッシュし、ポップは両方同時に行います。これは設計の問題です。評価されるのはコードの量ではなく、不変条件です。

パターン： ハッシュマップ＋双方向連結リスト·計算量： get/putごとに O(1)、空間 O(capacity)

ハッシュマップで、最近使った順に並べた双方向連結リストのノードをO(1)で参照します。アクセスしたらノードを先頭に移し、容量を超えたら末尾から追い出します。先頭と末尾に番兵ノードを置くと、nullチェックのエッジケースがすべてなくなります。コードを書き始める前に触れておきましょう。

パターン： グリッド上のBFS/DFSによる塗りつぶし·計算量： 時間 O(rows × cols)

グリッドを走査し、未訪問の陸地のセルを見つけるたびに、その島全体を訪問済みにする塗りつぶし（DFSまたはBFS）を始め、その開始回数を数えます。訪問済みの印のつけ方（その場で海に変えるか、別のセットを使うか）と、巨大なグリッドでの再帰の深さのリスクを説明しましょう。そこにシニアらしさが表れます。

パターン： トポロジカルソート／閉路検出·計算量： 時間 O(V + E)

前提条件を有向グラフとして表します。「すべて履修できるか」という問いは、まさに「グラフに閉路がないか」という問いです。Kahnのアルゴリズム（入次数ゼロのノードを繰り返し取り除く）でも、DFSによる3色塗り分けでも解けます。どちらかを選び、ノードが残ることがなぜ閉路を意味するのかを説明しましょう。

パターン： レベルごとにキューの長さを記録するBFS·計算量： 時間 O(n)、空間 O(width)

キューを使ったBFSですが、各回の始めにキューの長さを記録して、レベルごとに1つのリストを出力します。この長さを記録する工夫が使い回せる核心部分で、ジグザグ走査や右側から見たビューも、集め方が違うだけの同じループです。

パターン： 値の範囲の伝播／中間順走査·計算量： 時間 O(n)、空間 O(height)

各ステップで狭まっていく許容範囲(min, max)を持って再帰するか、中間順走査を行って値が狭義単調増加になっているかを確かめます。定番の落とし穴は、子を親とだけ比較することです。面接官より先に、自分で反例を作ってみせましょう。

パターン： 双方向のハッシュマップ（全単射）·計算量： 時間 O(n)、空間 O(n)

パターンの文字から単語への対応と、単語から文字への対応の「両方」を持ちます。片方向だけだと、"dog dog"に対してパターン"ab"を受け入れてしまいます。両方向で全単射を確かめることがこの問題のすべてです。「全単射」という言葉を使い、コードを書く前に長さが一致しない場合を処理しましょう。

パターン： 隠れた数列での循環検出·計算量： 1ステップあたり O(log n)、Floydなら空間 O(1)

数を各桁の2乗の和に置き換え続けると、1に到達するか、ループに入るかのどちらかです。つまり、これは姿を変えたLinked List Cycleです。訪問済みのセットでループを検出するか、Floydの低速・高速ポインターでO(1)の空間にして感心させましょう。循環検出に帰着できると指摘するのが、シニアらしい一手です。

パターン： 正しさの証明が必要な貪欲法·計算量： 時間 O(n)、空間 O(1)

ガソリンの合計 ≥ コストの合計なら、答えは存在し、しかも一意です。タンクの残量を追いながら1回走査し、マイナスになったら、その失敗した区間のどのスタンドも出発点にはなりえないので、次のスタンドからやり直します。面接で問われるのはループそのものではなく、この飛ばし方の正当性です。

パターン： 貪欲法／暗黙的なBFSの層·計算量： 時間 O(n)、空間 O(1)

k回のジャンプで到達できるインデックスを、BFSのひとつの層とみなします。現在の層の右端と、それまでに到達できる最も遠い位置を記録し、右端を越えたらジャンプ回数を増やして、右端をその最も遠い位置まで広げます。キューを使わないBFSとして説明すると、ここで貪欲法が最適である「理由」がわかります。

パターン： 3段階の線形マージ·計算量： 時間 O(n)、空間 O(n)

新しい区間が始まる前に終わる区間を出力し、次に重なるすべての区間を新しい区間に取り込み（開始は最小、終了は最大）、最後に残りを出力します。入力がソート済みなので、ソートし直さずに1回の走査で済みます。なぜこちらのほうが簡単なのかを聞かれたら、Merge Intervalsと比べて説明しましょう。

パターン： 行列のインプレース変換·計算量： 時間 O(n²)、空間 O(1)

時計回りに90°回転＝転置してから各行を反転、です。追加の空間O(1)できれいに2回走査するほうが、プレッシャーの中で4要素の循環スワップを手で導くよりも確実です。ただし、面接官がこの工夫の先まで突っ込んできたら、座標の対応 (i,j) → (j, n−1−i) を説明できるようにしておきましょう。

パターン： 既存の領域を借りたインプレースの印付け·計算量： 時間 O(m×n)、空間 O(1)

どの行・列をゼロにすべきかを記録する場所として、先頭の行と先頭の列を使い、それら自身の状態は2つの真偽値で覚えておきます。空間の段階を声に出して順にたどりましょう。O(mn)のコピー → O(m+n)のセット → O(1)の借用領域です。試されているのは、この段階そのものだからです。

パターン： ソート／カウント用のバケット·計算量： ソートなら O(n log n)、バケットなら O(n)

降順にソートして、citations[i] ≥ i+1 となる最大のiを求めます。あるいは、上限をnにしたカウント用のバケットを使えば、ソートせずにO(n)で解けます。コードを書く前に定義を正確に述べましょう。この問題での失敗の多くは、アルゴリズムではなく、「h回以上引用された論文がh本ある」という定義の読み違いによるものです。

パターン： トポロジカルソート（順序を出力）·計算量： 時間 O(V + E)

Course Scheduleと同じグラフですが、ここでKahnのアルゴリズムが真価を発揮します。入次数ゼロのノードがキューから出ていく順序が、そのまま正しい履修順序「そのもの」になります。出力した順序がコース数より短ければ閉路があるので、空を返します。別解として、DFSの帰りがけ順を逆にする方法にも触れましょう。

パターン： 条件充足カウンター付きのスライディングウィンドウ·計算量： 時間 O(n)、空間 O(alphabet)

ウィンドウが必要な文字をすべて含むまで右端を広げ（毎回マップ全体を比較するのではなく、「満たした数と必要な数」のカウンターを追います）、条件を満たしたまま左端を最小まで縮めて、最良の結果を記録します。O(n)を保てるのは、この満たした数のカウンターによる最適化のおかげです。はっきり説明しましょう。

パターン： 左右の最大値を保持するツーポインター·計算量： 時間 O(n)、空間 O(1)

各棒の上にたまる水の量は min(max-left, max-right) − height です。両端から内側に進む2つのポインターを使えば、それまでの最大値が低いほうの側から確定させられます。その側の上限は、すでに確定しているからです。なぜそう確定できるのかを順に説明しましょう。それこそがこの問題のすべてです。