コーディング試験の問題を見たとき、「どこから手をつければいいのかわからない」と途方に暮れた経験はありませんか。実は、コーディング試験に出題される問題の大半は、いくつかの定石パターンの組み合わせで解けるのです。将棋やチェスに定石があるように、アルゴリズムの世界にも「このタイプの問題にはこのアプローチ」という型が存在します。
定石パターンを知っていることの最大のメリットは、問題を見た瞬間にどのアプローチが有効かを素早く判断できるようになることです。試験の制限時間内で解法をゼロから考え出すのは至難の業ですが、パターンの引き出しがあれば、それをベースにカスタマイズするだけで済みます。この記事では、コーディング試験で特に頻出するアルゴリズムパターンを厳選して、それぞれの考え方と適用場面を詳しく解説していきます。
ハッシュマップで計算量を劇的に改善する
コーディング試験で最も汎用性が高いパターンのひとつが、ハッシュマップ（辞書、連想配列）を活用したアプローチです。配列の中から特定の条件を満たす要素のペアを見つけたり、重複を検出したり、要素の出現回数をカウントしたりする問題で威力を発揮します。ハッシュマップを使わなければ二重ループで O(n^2) かかる処理を、O(n) に削減できることが多いのです。
たとえば、有名な「Two Sum」問題を考えてみましょう。配列と目標の合計値が与えられ、合計が目標値になる二つの要素のインデックスを返す問題です。愚直に全ペアを調べると O(n^2) ですが、ハッシュマップを使えば配列を一回走査するだけで解けます。各要素を処理するとき、目標値との差（補数）がマップに既に存在するかをチェックし、存在すればペアが見つかったことになります。存在しなければ、現在の要素をマップに登録して先に進みます。
ところで、ハッシュマップパターンが適用できる問題の見分け方にはコツがあります。問題文に「ペアを見つける」「出現回数」「重複の検出」「グルーピング」といったキーワードが含まれていたら、ハッシュマップの出番だと考えてよいでしょう。面接官の前でこのパターンを適切に選択して適用できると、問題の本質を見抜く力があることを示せます。ハッシュマップは地味ですが、コーディング試験での出現頻度は他のパターンを圧倒しています。
アナグラム判定と文字頻度カウント
ハッシュマップが活躍する典型的な応用例が、文字列のアナグラム判定です。二つの文字列が同じ文字の組み合わせで構成されているかどうかを判定する問題は、面接でよく出題されます。解法は単純で、一方の文字列の各文字の出現回数をハッシュマップでカウントし、もう一方の文字列の各文字で対応するカウントを減らしていきます。最終的にすべてのカウントがゼロになればアナグラムです。
この解法の計算量は O(n) で、ソートを使ったアプローチの O(n log n) よりも効率的です。面接中に「ソートでも解けますが、ハッシュマップを使えば線形時間で処理できます」と両方のアプローチを提示できると、計算量に対する意識の高さをアピールできます。面接官はこのような比較分析ができる候補者を高く評価する傾向にあります。
そういえば、文字頻度カウントのパターンは、アナグラム以外にも多くの問題に応用できます。「文字列中で最も多く出現する文字を見つける」「ある文字列が別の文字列の順列（パーミュテーション）を含むかどうか」「最小ウィンドウ部分文字列の検出」など、文字の出現回数を管理する必要がある問題には、ほぼすべてこのパターンが使えます。ひとつのパターンを深く理解することで、多くのバリエーションに対応できるようになるのです。
二分探索で探索範囲を半分に絞り込む
二分探索は、ソート済みのデータから特定の値を効率的に見つけるためのアルゴリズムです。一見すると単純な概念ですが、コーディング試験では驚くほど多くの問題に応用されます。基本的な考え方は、探索範囲の中央値を確認し、目標値と比較して探索範囲を半分に絞り込む操作を繰り返すことです。計算量は O(log n) で、線形探索の O(n) と比較して格段に効率的です。
実は、二分探索の難しさは「適用できる場面を見抜くこと」にあります。配列が明示的にソートされている問題であれば気づきやすいのですが、二分探索が使えるのは整列されたデータに限りません。「答えが単調増加（または単調減少）の性質を持つ」場合にも適用できるのです。たとえば「最小値の最大化」や「最大値の最小化」を求める問題は、答えの候補に対して二分探索を適用する「答えに対する二分探索」というテクニックで解けることが多いです。
二分探索を実装する際に多くの人が苦労するのが、境界条件の処理です。左端と右端のポインタをどう更新するか、ループの終了条件を「左 < 右」にするか「左 <= 右」にするか、中央値の計算でオーバーフローが起きないかなど、細かいバグの温床になりやすいポイントがいくつもあります。これらの落とし穴を事前に把握しておくことで、面接中に冷静に実装を進められるようになります。
回転ソート配列での二分探索
二分探索の応用問題として面接でよく出題されるのが、回転されたソート済み配列からの値の検索です。たとえば「4, 5, 6, 7, 0, 1, 2」のように、もともとソートされていた配列がある位置で回転した配列が与えられます。この配列から特定の値を O(log n) で見つける問題です。
この問題の解法は、通常の二分探索に一工夫加えたものです。中央値で配列を分割すると、少なくとも片方はソートされた状態になっています。そのソートされた半分に目標値が含まれるかどうかを確認し、含まれていればその半分に探索範囲を絞り、含まれていなければもう一方に絞ります。この判断ロジックを正しく実装できるかどうかが、この問題のポイントです。
ところで、回転ソート配列の問題を面接中に出された場合、いきなりコーディングに入るのではなく、まず具体的な例を使って手動でアルゴリズムを追ってみると良いでしょう。ホワイトボードやエディタのコメント欄に配列の状態を書き出しながら、ステップごとにポインタがどう動くかを確認する姿勢を見せると、面接官は「この人は論理的に思考を進められる」と感じてくれます。
スライディングウィンドウで部分配列の問題を攻略する
スライディングウィンドウは、配列や文字列の連続する部分に対する問題を効率的に解くためのテクニックです。「長さ k の連続する部分配列の最大合計を求める」「条件を満たす最短の部分文字列を見つける」といった問題で活用されます。ウィンドウの右端を広げて要素を追加し、条件に応じて左端を縮めて要素を除外するという操作を繰り返すことで、全探索を避けて効率的に解を見つけられます。
スライディングウィンドウには大きく分けて固定長と可変長の二種類があります。固定長のウィンドウは、サイズが事前に決まっている場合に使います。ウィンドウを一つ右にずらすたびに、右端の新しい要素を追加し、左端の古い要素を除外します。可変長のウィンドウは、条件を満たす最小または最大の部分配列を求める場合に使います。右端を広げて条件を満たしたら、左端を縮めて最小化を試みるという流れです。
実は、スライディングウィンドウの問題を見分けるコツは問題文のキーワードにあります。「連続する部分配列」「部分文字列」「ウィンドウ」「最大/最小の長さ」といった表現が含まれていたら、スライディングウィンドウの適用を検討してみましょう。面接では「これはスライディングウィンドウで O(n) で解けますね」と即座にパターンを特定できると、パターン認識力の高さを印象づけることができます。
重複のない最長部分文字列
スライディングウィンドウの代表的な応用問題が「重複する文字を含まない最長の部分文字列の長さを求める」問題です。この問題は多くの企業の面接で出題されており、必ず解けるようにしておきたい定番中の定番です。
解法は、右端のポインタを一つずつ右に進めながら、現在のウィンドウ内の文字をハッシュセットで管理するアプローチです。新しい文字がセットに存在しなければウィンドウに追加し、存在すれば左端を縮めて重複がなくなるまで文字を除外します。各ステップでウィンドウの長さを記録し、最大値を更新していきます。この解法は O(n) で動作し、全部分文字列を調べるブルートフォースの O(n^3) と比較して圧倒的に効率的です。
そういえば、この問題はスライディングウィンドウとハッシュマップの二つのパターンを組み合わせて使う好例でもあります。コーディング試験の問題は、ひとつのパターンだけで解けるものよりも、複数のパターンを組み合わせる必要があるものの方が難易度が高い傾向にあります。定石パターンを個別に学ぶだけでなく、組み合わせて使う練習もしておくことが、中級以上の問題を攻略するカギとなります。
深さ優先探索と幅優先探索でグラフ・木を攻略する
グラフや木構造に関する問題は、コーディング試験で避けて通れないテーマです。これらの問題を解くための基本的なツールが、深さ優先探索（DFS）と幅優先探索（BFS）です。どちらもグラフのすべてのノードを訪問するためのアルゴリズムですが、探索の順序が異なるため、問題の性質に応じて使い分ける必要があります。
DFSは「行けるところまで行って、行き止まりになったら戻る」というアプローチです。再帰やスタックを使って実装し、経路の探索やバックトラッキングが必要な問題に適しています。たとえば、迷路のすべての経路を列挙する問題や、木構造の全ノードを特定の順序で訪問する問題はDFSの得意分野です。再帰で実装すると直感的でコードもシンプルになりますが、深い再帰でスタックオーバーフローが発生する可能性があることには注意が必要です。
BFSは「近いところから順番に探索する」というアプローチです。キューを使って実装し、最短経路を求める問題に特に適しています。グリッド上での最短距離や、グラフの最短パスを求める問題では、BFSを選択するのが定石です。DFSとBFSのどちらを使うべきかを正しく判断できることは、アルゴリズムの基礎力をアピールする重要なポイントです。
二分木の問題パターン
二分木はDFSが最も自然に適用されるデータ構造です。コーディング試験では、二分木に関連するさまざまな問題が出題されますが、その多くは再帰的なDFSの思考パターンで解くことができます。木の高さを求める、左右の部分木が対称かを判定する、特定の合計値になる経路を見つける、といった問題はすべてこのカテゴリーに属します。
二分木の問題を解く際のテンプレートとなる考え方は「現在のノードでの処理」と「再帰的に子ノードに委譲する処理」を明確に分けることです。たとえば木の高さを求める場合、現在のノードでは「左右の子の高さの大きい方に1を足す」という処理を行い、子の高さの計算は再帰に委ねます。この分割思考をマスターすれば、木の問題は格段に解きやすくなります。
実は、二分木の問題にはもうひとつ重要なパターンがあります。幅優先探索によるレベルオーダートラバーサル（階層ごとの走査）です。キューを使って各階層のノードを順番に処理する手法で、「各階層の最大値を求める」「木をジグザグ順に走査する」といった問題に使われます。DFSとBFSの両方を木の問題で使いこなせることが、面接での高評価につながります。
動的計画法で最適化問題に挑む
動的計画法（DP）は、コーディング試験の中でも特に苦手意識を持つ人が多いパターンです。しかし、基本的な考え方さえ掴めば、実は非常にシステマティックなアプローチで問題を解くことができます。DPの本質は、大きな問題を小さな部分問題に分解し、各部分問題の結果を記録（メモ化）して重複計算を避けることにあります。
DPが適用できる問題を見分けるポイントは二つあります。ひとつは「最適部分構造」を持つこと、つまり全体の最適解が部分問題の最適解から構成できることです。もうひとつは「重複する部分問題」が存在すること、つまり同じ部分問題が何度も計算される状況があることです。フィボナッチ数列の計算がDPの最もシンプルな例で、単純な再帰だと O(2^n) かかる計算が、メモ化により O(n) に削減されます。
ところで、DPの実装方法には「トップダウン（メモ化再帰）」と「ボトムアップ（テーブル法）」の二つがあります。トップダウンは再帰関数の結果をキャッシュする方法で、問題の構造をそのまま反映できるため理解しやすいです。ボトムアップは小さい部分問題から順番にテーブルを埋めていく方法で、再帰のオーバーヘッドがなく効率的です。面接では両方のアプローチを説明でき、状況に応じて使い分けられることを示すと、DPへの理解の深さをアピールできます。
ナップサック問題とその変形
動的計画法の代表的な問題が、ナップサック問題です。重さと価値が異なる複数のアイテムがあり、容量の限られたナップサックに入れるアイテムの組み合わせで価値を最大化する問題です。コーディング試験では、このナップサック問題の変形として「コイン交換問題」「部分和問題」「文字列の編集距離」など、さまざまな形で出題されます。
ナップサック問題の解法は、二次元のDPテーブルを使います。テーブルの各セルは「i番目までのアイテムを使って、容量jのナップサックに入る最大価値」を表します。各セルの値は「i番目のアイテムを入れない場合」と「入れる場合」のうち大きい方を選ぶことで計算できます。この考え方は一度理解すれば、他のDP問題にも応用が利くため、しっかりマスターしておきたいところです。
実は、面接でDP問題が出された場合、完璧な最適解を即座に出す必要はありません。まず再帰的なブルートフォースの解法を説明し、それを元にメモ化でどのように改善できるかを段階的に示すことで、思考の過程をアピールできます。面接官が見ているのは最終的なコードだけでなく、問題をどのように分解し最適化していくかという思考のプロセスです。
二つのポインタで配列を効率的に処理する
二つのポインタ（ツーポインタ）テクニックは、ソート済み配列やリンクリストに対する問題で頻繁に使われるパターンです。二つのポインタを配列の両端から中央に向かって動かしたり、一方を速く一方を遅く動かしたりすることで、二重ループを使わずに効率的に問題を解きます。計算量を O(n^2) から O(n) に改善できるケースが多く、面接でもよく出題されます。
代表的な応用例が、ソート済み配列で合計が特定の値になるペアを見つける問題です。左端と右端にそれぞれポインタを置き、二つのポインタが指す値の合計が目標値より小さければ左のポインタを右に動かし、大きければ右のポインタを左に動かします。合計が目標値に等しくなったときがペア発見のタイミングです。この手法はハッシュマップよりも空間計算量が小さく、追加のメモリを使わないという利点があります。
そういえば、二つのポインタには「対向ポインタ」と「同方向ポインタ（スロー・ファストポインタ）」の二つのバリエーションがあります。対向ポインタは両端から中央に向かう動き、同方向ポインタは両方とも同じ方向に進みつつ速度が異なる動きです。後者はリンクリストのサイクル検出や、配列内の重複除去などに使われます。どちらのバリエーションも面接で出題される可能性があるため、両方とも練習しておくことをおすすめします。
定石パターンを身につけるための効果的な学習法
定石パターンを知識として知っているだけでは、面接本番では使いこなせません。パターンを自分のものにするためには、段階的な学習と反復練習が必要です。ここでは、効率的にパターンを習得するための学習方法を紹介します。
おすすめの学習ステップは、パターンごとに集中的に練習する方法です。たとえば一週間をかけて二分探索の問題だけを10問解く、翌週はスライディングウィンドウの問題を10問解く、という形で進めます。パターンを一つずつ深く学ぶことで、「この問題はあのパターンだ」という認識が速くなります。ランダムに問題を解くよりも、パターンごとに集中した方が定着率が高いことが多くの学習者の経験から明らかになっています。
実は、問題を解くだけでなく、解いた後の振り返りが学習効果を大きく左右します。問題を解き終えたら、なぜそのパターンが適用できるのか、他にどのようなアプローチがあり得るか、計算量はどう変わるか、を自分の言葉でノートに書き出してみましょう。この振り返りの習慣が、パターンの理解を表面的な暗記から深い理解へと昇華させてくれます。面接では「なぜこのアプローチを選んだのか」を問われることが多いので、理由を言語化する練習は面接対策としても非常に有効です。
まとめ
コーディング試験で頻出するアルゴリズムパターンは、ハッシュマップ、二分探索、スライディングウィンドウ、DFS/BFS、動的計画法、ツーポインタの6つが特に重要です。これらのパターンを習得していれば、面接で出題される問題の大部分に対応できるようになります。
パターンを身につけるには、知識として覚えるだけでなく、実際にコードを書いて体に染み込ませることが不可欠です。パターンごとに集中的に練習し、解いた問題の振り返りを丁寧に行うことで、面接本番でもパターンの適用を素早く判断できるようになります。定石は制約ではなく武器であり、引き出しが多いほど面接での自由度が高まるのです。