この記事のまとめ
- コーディング面接では配列、ハッシュマップ、木、グラフの4つのデータ構造が圧倒的に頻出する
- アルゴリズムは二分探索、DFS/BFS、動的計画法、二つのポインタ、ソートの5つを優先的に学ぶべき
- 基礎的なデータ構造から段階的に積み上げ、3〜6か月で面接レベルの実力を目指すのが現実的
コーディング面接のトレンド - 何がどう問われるのか
テック企業のコーディング面接は、ここ数年で大きく様変わりした。かつては「ソートアルゴリズムを手書きで実装してください」のような知識確認型の問題が多かったが、現在は問題解決力とコミュニケーション力を同時に評価するスタイルが主流だ。面接官は、候補者が問題にどうアプローチし、どう考え、どう実装するかの全プロセスを見ている。
そういえば、「面接でアルゴリズムを聞くのはナンセンスだ」という議論は絶えない。日常の開発業務でDPやグラフ探索を使うことは少ないのに、なぜ面接で問うのかという批判だ。この議論にはもっともな面もあるが、現実として多くのテック企業がアルゴリズム面接を採用し続けている以上、対策しないわけにはいかない。アルゴリズム面接は「候補者の問題解決の思考プロセス」を短時間で評価する手段として、一定の合理性があると見なされているのだ。
面接で出題される問題には、明確なパターンがある。LeetCodeやGlassdoorの面接体験談を分析すると、出題されるアルゴリズムは驚くほど偏っている。頻出するデータ構造とアルゴリズムを重点的に学習し、それらのパターンを体に染み込ませることが、面接対策の最も効率的な戦略だ。全範囲をまんべんなく勉強するよりも、頻出パターンに集中したほうが投資対効果が高い。
必須データ構造その1 - 配列とハッシュマップ
配列（Array）は、コーディング面接で最も頻繁に登場するデータ構造だ。面接で出る配列問題の多くは、配列の中から特定の条件を満たす要素を見つける、配列を並べ替える、配列の部分区間に対する処理を行う、といったパターンに分類できる。Two Sum、Maximum Subarray、Product of Array Except Selfといった問題は、面接の鉄板中の鉄板だ。
配列の問題を効率よく解くための鍵は、「計算量を意識すること」と「適切な補助データ構造を選ぶこと」だ。たとえばTwo Sumをブルートフォースで解くとO(N^2)だが、ハッシュマップを補助に使うとO(N)に改善できる。この「ブルートフォースから最適解へのステップアップ」を説明できるかどうかが、面接での評価を分ける。
ハッシュマップ（Hash Map）は、配列と並んで使用頻度が非常に高いデータ構造だ。キーと値のペアをO(1)で読み書きできる特性は、多くの問題で計算量を劇的に改善する武器になる。要素の出現回数をカウントする、重複を検出する、2つの配列の共通要素を見つけるといった場面で、ハッシュマップは真っ先に検討すべき選択肢だ。面接官も「ハッシュマップを使った改善」を期待して問題を設計していることが多いので、ハッシュマップの使いどころを直感的に判断できるようになっておきたい。
必須データ構造その2 - スタックとキュー
スタック（Stack）は後入れ先出し（LIFO）の構造で、面接では括弧の対応チェック、式の評価、ヒストグラムの最大面積といった問題で頻出する。Valid Parenthesesは面接のウォーミングアップ問題として出されることが多い。スタックの本質は「直近の未処理データを保持しておき、後から処理する」という考え方にある。
ところで、スタックを使う問題には「モノトニックスタック（単調スタック）」というパターンがある。配列の各要素に対して「自分より大きい（または小さい）次の要素」を効率的に見つけたい場合に使うテクニックだ。Next Greater Element、Daily Temperaturesといった問題がこのパターンに当たる。モノトニックスタックは知っているか知らないかで解けるかどうかが決まるタイプの問題なので、パターンとして覚えてしまうのが早い。
キュー（Queue）は先入れ先出し（FIFO）の構造で、BFS（幅優先探索）の実装に欠かせない。面接でキュー単体が問われることは少ないが、BFSの問題を解く際には必ず登場する。また、優先度付きキュー（Priority Queue / Heap）は「常に最小値または最大値を効率的に取り出す」必要がある問題で活躍する。Merge K Sorted Lists、Top K Frequent Elementsといった問題で使われ、面接での出題頻度も高い。ヒープの仕組みを深く理解する必要はないが、「こういう場面ではヒープを使う」という判断ができるようになっておこう。
必須データ構造その3 - 木とグラフ
二分木（Binary Tree）は面接で最も頻出するデータ構造のひとつだ。面接官が木の問題を好む理由は、再帰的な思考力を測れるからだ。木の問題の大半は再帰で解けるが、再帰の基底条件（base case）と再帰呼び出しの関係を正しく設計する必要がある。Maximum Depth of Binary Tree、Lowest Common Ancestor、Serialize and Deserialize Binary Treeは面接での定番問題だ。
二分探索木（BST）は二分木の一種で、「左の子は親より小さく、右の子は親より大きい」という性質を持つ。この性質を利用して効率的な検索や挿入ができる。Validate BST、Kth Smallest Element in a BSTといった問題では、BSTの性質を活かした中順走査（in-order traversal）がポイントになる。中順走査するとBSTの要素がソート順に取り出せるという事実は、面接では非常に便利な性質だ。
グラフ（Graph）は木をさらに一般化した構造で、ノード同士が自由に接続される。面接でのグラフ問題は、大きく分けて「探索系」と「経路系」の2パターンがある。探索系はDFSやBFSを使って連結成分を数えたり、特定の条件を満たすノードを見つけたりする問題だ。Number of Islands、Course Scheduleが代表的。経路系は最短経路を求める問題で、ダイクストラ法やBFSが使われる。グラフの問題は一見難しそうに見えるが、DFSとBFSのテンプレートを身につけてしまえば、多くの問題に対応できるようになる。
必須アルゴリズムその1 - 二分探索
二分探索（Binary Search）は、ソートされたデータの中から目的の値をO(log N)で見つけるアルゴリズムだ。概念自体はシンプルだが、面接では「こんなところにも二分探索が使えるのか」と驚くような応用問題が出される。Search in Rotated Sorted Array、Find Minimum in Rotated Sorted Array、Koko Eating Bananasなどがその例だ。
二分探索の核心は「探索範囲を半分に絞り込む」という発想にある。配列のインデックスに対して適用するのが基本形だが、答えの範囲に対して二分探索を適用する「答えに対する二分探索」というテクニックも面接で頻出する。「最小値を最大化する」「最大値を最小化する」タイプの問題を見たら、答えに対する二分探索を疑ってみるとよい。
実は、二分探索の実装で多くの人がつまずくのは「境界条件」だ。ループの終了条件を left < right にするか left <= right にするか、中間値を mid = (left + right) / 2 で求めるか mid = left + (right - left) / 2 で求めるか。オーバーフローの問題もある。これらの細かい点を正確に実装できるかどうかが、面接でのAC（Accepted）とWA（Wrong Answer）を分ける。テンプレートを1つ確実に暗記し、そこから問題に応じてアレンジする方法が最も安全だ。
必須アルゴリズムその2 - DFSとBFS
DFS（深さ優先探索）とBFS（幅優先探索）は、木やグラフの走査に使われる2大アルゴリズムだ。面接ではこの2つのどちらか（あるいは両方）が関わる問題が非常に多い。大げさではなく、面接で出される問題の3〜4割はDFSかBFSで解けると言ってもよいだろう。
DFSはスタック（または再帰）を使って、ひとつの枝を深くまで探索してから次の枝に移る方法だ。木の走査、グラフの連結成分の探索、バックトラッキング（組み合わせの列挙）などで使われる。再帰で書くとコードが短くなるが、再帰の深さが大きいとスタックオーバーフローのリスクがある。面接では再帰版で書くことが多いが、反復版（明示的にスタックを使う）で書けることも示せると評価が上がる。
BFSはキューを使って、現在のノードから距離が近い順に探索する方法だ。「最短距離」や「最小ステップ数」を求める問題ではBFSが定石だ。グリッド上の最短経路問題（01 Matrix、Walls and Gates）やレベルごとの走査（Binary Tree Level Order Traversal）で頻出する。BFSのテンプレートは比較的固定的で、一度覚えてしまえば多くの問題に応用できる。キューに入れるもの、訪問済みの管理方法、終了条件の3点を問題に合わせて調整するだけだ。
必須アルゴリズムその3 - 動的計画法
動的計画法（DP）は、面接で最も「難しい」と感じる人が多いアルゴリズムだ。しかし、面接で出るDPの問題はパターンが限られているので、頻出パターンを押さえておけば恐れることはない。DPの核心は「大きな問題を小さな部分問題に分解し、部分問題の解を再利用する」ことだ。
面接で頻出するDPのパターンとしては、1次元DP（Climbing Stairs、House Robber）、2次元DP（Unique Paths、Longest Common Subsequence）、ナップサック問題（Partition Equal Subset Sum）、区間DP（Longest Palindromic Substring）がある。これらのパターンをそれぞれ2〜3問ずつ解いておけば、面接で未知のDP問題が出ても「あ、これはナップサック型だな」と見当がつくようになる。
そういえば、DP問題を解く際に意識すべきステップがある。「状態の定義」「遷移式の導出」「初期条件の設定」「計算順序の決定」の4ステップだ。たとえばClimbing Stairsなら、状態は「i段目に到達する方法の数」、遷移式は「dp[i] = dp[i-1] + dp[i-2]」、初期条件は「dp[0]=1, dp[1]=1」、計算順序は「iが小さい方から大きい方へ」となる。面接では、このステップを口に出して説明しながらコードを書くと、面接官に思考プロセスが伝わりやすい。
必須アルゴリズムその4 - 二つのポインタとスライディングウィンドウ
二つのポインタ（Two Pointers）は、配列や文字列の問題で劇的に計算量を改善できるテクニックだ。2つのインデックスを同時に動かすことで、ネストしたループを1つのループに置き換えられる場面がある。Two Sum II（ソート済み配列版）、3Sum、Container With Most Waterが代表的な問題だ。
スライディングウィンドウ（Sliding Window）は二つのポインタの派生形で、配列の連続する部分区間に対する処理を効率化するテクニックだ。ウィンドウの左端と右端を示す2つのポインタを動かしながら、ウィンドウ内の状態を更新していく。Minimum Window Substring、Longest Substring Without Repeating Characters、Maximum Average Subarrayといった問題で使われる。
ところで、二つのポインタとスライディングウィンドウは、「このテクニックを使う問題だ」と気づけるかどうかが勝負の分かれ目だ。使うべき場面のシグナルとしては、「ソート済み配列で条件を満たすペアを探す」（二つのポインタ）、「連続する部分配列で最大/最小の何かを求める」（スライディングウィンドウ）がある。こうしたシグナルを問題文から読み取る訓練を、LeetCodeの問題を通じて積み重ねていこう。
必須アルゴリズムその5 - ソートとその応用
ソート自体を面接で実装させることは少なくなったが、ソートの性質を利用した問題は頻繁に出る。「配列をソートしてから二分探索する」「ソートして重複を除去する」「ソートして貪欲法を適用する」といったパターンだ。Meeting Rooms、Merge Intervals、Valid Anagramなどがこれに当たる。
面接で知っておくべきソートの知識は、各ソートアルゴリズムの計算量と特徴だ。クイックソートは平均O(N log N)だが最悪O(N^2)、マージソートは常にO(N log N)で安定ソート、ヒープソートもO(N log N)だが実用上はクイックソートのほうが速いことが多い。面接でソートアルゴリズムの詳細を問われることは稀だが、「なぜこの問題でソートが有効なのか」を説明できる程度の理解は持っておきたい。
実は、カウンティングソートやバケットソートといった特殊なソートが面接で活きる場面もある。Top K Frequent Elements は、ヒープを使う解法（O(N log K)）が一般的だが、バケットソートを使えばO(N)で解ける。こうした「一般的な解法よりも効率的な方法を知っている」ことを示せると、面接官に好印象を与えられる。ただし、まずは一般的な解法を確実に書けることが前提だ。
学習の段階的な進め方 - 3か月プラン
コーディング面接の準備を体系的に進めるなら、3か月のタイムラインで計画を立てるのが現実的だ。
1か月目は基礎固めの期間だ。配列、文字列、ハッシュマップ、スタック/キューの問題をEasyとMediumで各10問ずつ解く。この段階ではアルゴリズムのパターンを暗記する必要はなく、問題を読んでアプローチを考え、コードに落とし込む一連の流れに慣れることが目標だ。1問あたり30分以内を目安にして、解けなければ解説を読んで理解し、翌日もう一度自力で解くサイクルを回す。
2か月目は応用の期間だ。二分探索、DFS/BFS、DP、二つのポインタのカテゴリに取り組む。各カテゴリで10〜15問をMedium中心に解いていく。この段階で大切なのは、「パターン認識」の感覚を養うことだ。問題を見たときに「これはスライディングウィンドウの問題だ」「これはBFSで最短経路を求める問題だ」と直感的に判断できるようになることを目指す。
3か月目は仕上げの期間だ。志望企業の頻出問題リストから問題をピックアップし、時間制限を設けて本番さながらの練習をする。解法を声に出して説明しながらコードを書く「モック面接」形式の練習を取り入れる。友人やオンラインのモック面接サービスを利用して、第三者からフィードバックをもらうのも有効だ。この段階では新しいパターンを学ぶよりも、これまで学んだパターンの精度とスピードを上げることに集中する。
練習量の目安 - どれだけ解けば十分か
コーディング面接の準備に必要な問題数については、さまざまな意見がある。ある人は「100問で十分」と言い、別の人は「300問は必要」と主張する。結論から言えば、量よりもカバー範囲とパターンの理解度のほうが重要だ。100問でも主要なパターンをすべてカバーしていれば面接に臨めるし、300問解いても同じパターンの問題ばかりなら偏った準備になる。
ひとつの目安として、「Blind 75」や「NeetCode 150」のような厳選問題リストをすべて解き切ることを推奨する。これらのリストは面接で頻出するパターンを網羅するように設計されているので、リストを完走すれば主要なパターンはほぼカバーできる。75問なら1日1〜2問のペースで2〜3か月、150問なら同じペースで4〜5か月だ。
ところで、「問題を解いた数」よりも「問題から学んだパターンの数」を指標にしたほうがよい。同じパターンの問題を10問解くよりも、異なるパターンの問題を各2問ずつ計10パターン解くほうが、面接での対応力は高くなる。解いた問題は必ず振り返りを行い、「この問題はどのパターンに分類されるか」「似たパターンの問題として他に何があるか」を意識的に整理しておこう。こうした「パターンの地図」を頭の中に構築することが、面接本番での即興対応力につながる。
まとめ
コーディング面接で求められるアルゴリズムとデータ構造は、数が限られている。配列、ハッシュマップ、スタック/キュー、木、グラフの5つのデータ構造と、二分探索、DFS/BFS、動的計画法、二つのポインタ、ソートの5つのアルゴリズムが核心だ。これらを体系的に学び、パターンとして身につけることが面接対策の王道だ。
学習は3か月を目安に段階的に進め、基礎固め、応用、仕上げの3フェーズで取り組もう。問題の量よりもパターンの網羅と理解度を重視し、解法を言語化しながら書く練習を日頃から取り入れてほしい。面接は「準備した人が報われる」場だ。この記事で紹介したアルゴリズムとデータ構造を着実に習得して、自信を持って面接に臨んでほしい。