大手IT企業の技術面接でよく出るアルゴリズム問題30選：カテゴリ別完全収集

なぜこの30問をまとめたのか

昨年の後半、面接に集中して臨み、楽天、NTT、ソニー、富士通、ホンダなど大手IT企業を7〜8社受けました。アルゴリズムのラウンドはほぼ全社で出題されました。面接が終わって振り返ってみると、高頻度問題の重複率が驚くほど高いことに気づきました。そこで2日間かけて、面接で遭遇した問題や友人たちと確認した高頻度アルゴリズム問題を分類整理し、合計30問をまとめました。面接準備中の方の参考になれば幸いです。

配列/文字列、リンクリスト、ツリー、動的計画法、グラフ理論、設計問題の6つのカテゴリに分け、各問題にLeetCode番号、評価ポイント、難易度、解法のポイントを記載しています。これらは全て実際の面接で出題された問題であり、問題バンクから適当に選んだものではありません。

一、配列/文字列（6問）

1. Two Sum（LeetCode #1）

難易度：簡単 | 評価ポイント：ハッシュマップの使用

この問題は面接のオープニングの定番です。楽天と富士通の両方で最初の問題として出題されました。アプローチはシンプル：ハッシュマップで既に訪問した要素を保存し、1回の走査で補数を見つける——O(n)時間。面接官は必ず「配列がソートされていたら？」とフォローアップし、二重ポインタのアプローチにつなげます。

ポイント：簡単な問題を甘く見ないでください。3Sum、4Sum、全ての有効なペアを返すバリエーションなど、多くの派生問題の出発点になります。

2. 3Sum（LeetCode #15）

難易度：中程度 | 評価ポイント：ソート+二重ポインタ、重複排除

NTTの面接で出題されました。配列をソートし、1つの数を固定し、残りの部分で二重ポインタを使って合計が目標値になるペアを見つけます。重要な難所は重複排除——面接官は重複するトリプレットの処理を特に気にします。最初の提出で重複処理を忘れ、面接官に指摘されてから追加しました。少し恥ずかしかったです。

ポイント：ソートO(nlogn)、二重ポインタ走査O(n²)。重複要素をスキップするロジックに注意。

3. Longest Substring Without Repeating Characters（LeetCode #3）

難易度：中程度 | 評価ポイント：スライディングウィンドウ

ソニーの二次面接で出題。古典的なスライディングウィンドウ問題：二重ポインタで重複文字のないウィンドウを維持し、右ポインタで拡張、左ポインタで縮小。フォローアップは「文字セットが小文字のみの場合、最適化できるか？」——答えはハッシュマップの代わりに配列を使って文字の出現位置を記録することです。

ポイント：スライディングウィンドウは配列/文字列問題の核心パターン。徹底的にマスターしてください。

4. Merge Intervals（LeetCode #56）

難易度：中程度 | 評価ポイント：ソート+貪欲法

富士通の一次面接で出題。開始点でソートし、現在の区間が結果セットの最後の区間と重なるか順次判定。面接官は比較器を手書きするよう求めました——ラムダ式で書き、頷いてもらえました。難しくはないですが、境界条件で間違いやすい——端点が等しい場合に重複とみなすかどうかは、必ず面接官に確認してください。

5. Sliding Window Maximum（LeetCode #239）

難易度：難しい | 評価ポイント：単調デック

楽天の二次面接で出題。最初は力ずくの解法しか知らず、面接官の誘導で単調デックを思いつきました。先頭が常に現在のウィンドウの最大値になるよう、減少するデックを維持。難しいのは「期限切れの要素を先頭からポップし、小さい要素を末尾からポップする理由」を理解することです。

ポイント：単調デックは高頻度トピック。「ヒストグラム中の最大長方形」と一緒に練習することをお勧めします。

6. Rotate Array（LeetCode #189）

難易度：中程度 | 評価ポイント：配列反転テクニック

ホンダの一次面接で出題。最もエレガントな解法は3回の反転：配列全体を反転し、最初のk個を反転し、残りのn-k個を反転。面接官はO(1)空間を求め、3回反転アプローチがぴったり合います。循環置換の解法もありますが、間違いやすいので面接ではお勧めしません。

二、リンクリスト（4問）

7. Reverse Linked List（LeetCode #206）

難易度：簡単 | 評価ポイント：ポインタ操作

この問題は5回以上聞かれ、ほぼ全社で出題されました。反復法と再帰法の両方を書けるようにしてください。面接官はよく「Reverse Linked List II（指定範囲の反転）」とフォローアップするので、一緒に準備することをお勧めします。反復法は3つのポインタ（prev、curr、next）を順次進め、再帰法はバックトラック時のポインタ再接続を理解する必要があります。

8. Merge Two Sorted Lists（LeetCode #21）

難易度：簡単 | 評価ポイント：マージソートの考え方

NTTの一次面接で出題。ダミーヘッドでロジックを簡略化し、二つのポインタで両方のリストを走査し、常に小さいノードを選択。フォローアップは「K個のソート済みリストのマージ」——最小ヒープで最適化し、時間計算量O(NlogK)。

9. Linked List Cycle（LeetCode #141/142）

難易度：簡単/中程度 | 評価ポイント：高速・低速ポインタ

ソニーがサイクルの検出（#141）を出題、ホンダがサイクルの入口を見つける（#142）をフォローアップ。高速・低速ポインタが標準的な解法。面接官は「なぜ高速ポインタと低速ポインタが必ずサイクル内で出会うのか」の証明を求めました——高速ポインタが2歩、低速ポインタが1歩進むと、サイクル内での相対速度は1なので、必ず追いつきます。

ポイント：#142でサイクルの入口を見つける方法：出会った後、一方のポインタを先頭に戻し、両方を同じ速度で進めると、次の出会う場所が入口。

10. Reverse Nodes in k-Group（LeetCode #25）

難易度：難しい | 評価ポイント：リンクリスト操作の総合

楽天の一次面接で出題。リンクリスト反転の応用版。核心的な考え方：k個のノードを数え、そのグループを反転し、残りを再帰的に処理。難しいのはポインタの接続——反転後の先頭と末尾を元のリストに正しく接続すること。最初の提出で末尾ポインタが間違っており、デバッグに時間がかかりました。

三、ツリー（5問）

11. Binary Tree Level Order Traversal（LeetCode #102）

難易度：中程度 | 評価ポイント：BFS

NTTとソニーの両方で出題。キューでBFSを行い、レベルごとにグループ化して出力するのがポイント。面接官はnullをセパレータにするのではなく、size変数で各レベルの走査範囲を制御しているかを確認します——前者がより標準的です。バリエーションとしてジグザグ順序走査（#103）と右側ビュー（#199）があります——一緒に練習してください。

12. Maximum Depth of Binary Tree（LeetCode #104）

難易度：簡単 | 評価ポイント：再帰/DFS

ウォームアップ問題——再帰で1行のコード。面接官が単独で出題することは少なく、通常は「平衡二分木の判定」や「最小深さ」など後続問題の足がかりとして使われます。再帰と反復の両方の書き方をマスターしてください。

13. Path Sum III（LeetCode #437）

難易度：中程度 | 評価ポイント：累積和+再帰

ホンダの二次面接で出題。合計が目標値になる全てのパスを見つける問題。重要な最適化は累積和を使うこと——O(n²)からO(n)に削減。Two Sumの考え方と同様に、ハッシュマップで累積和の出現回数を記録。面接官は「この問題を解ける人は少ない」と言っていました——差別化問題です。

14. Lowest Common Ancestor of a Binary Tree（LeetCode #236）

難易度：中程度 | 評価ポイント：再帰的な後順走査

楽天とNTTの両方で出題。後順走査の典型的な応用：左右の部分木でそれぞれpとqが見つかれば、現在のノードがLCA。フォローアップは「BSTの場合は？」（#235）——BST版は順序付けを利用した剪定ができ、よりシンプル。再帰ロジックは非常に明確にする必要があります——書きながら説明してください。

15. Validate Binary Search Tree（LeetCode #98）

難易度：中程度 | 評価ポイント：中間順走査/再帰的検証

富士通の二次面接で出題。二つのアプローチ：中間順走査で厳密に増加しているか判定する方法と、再帰で最小/最大境界を渡す方法。面接官は後者を好みます——追加のスペースが不要だからです。最初は中間順走査で書き、面接官に再帰的境界アプローチに書き直すよう求められ、修正後に満足してもらえました。

四、動的計画法（6問）

16. Climbing Stairs（LeetCode #70）

難易度：簡単 | 評価ポイント：DP入門

動的計画法の古典的な入門問題。dp[i] = dp[i-1] + dp[i-2]——本質的にフィボナッチ数列。面接官はこの問題から始め、「1〜m段ずつ登れる場合」「最小コストで階段を登る」などのバリエーションにエスカレートします。空間は最後の2つの状態だけを保持すればO(1)に最適化できます。

17. Longest Increasing Subsequence（LeetCode #300）

難易度：中程度 | 評価ポイント：DP + 二分探索

ソニーの二次面接で出題。標準的なDPはO(n²)、dp[i]でnums[i]で終わる最長増加部分列の長さを表します。面接官はO(nlogn)の解法をフォローアップ——ソート済みのtails配列を維持し、二分探索で更新。この最適化の考え方は重要で、ロシア人形封筒問題（#354）でも使われます。

18. Edit Distance（LeetCode #72）

難易度：難しい | 評価ポイント：2次元DP

NTTの二次面接で出題。dp[i][j]はword1の最初のi文字をword2の最初のj文字に変換する最小操作数を表します。状態遷移では挿入、削除、置換の3つの操作を考慮し、最小値を取ります。難しいのは初期化：dp[i][0] = i、dp[0][j] = jは空文字列から目標文字列への操作コストを表します。面接ではDPテーブルを描くことをお勧めします。

19. Coin Change（LeetCode #322）

難易度：中程度 | 評価ポイント：無制限ナップサック

ホンダの一次面接で出題。dp[i]は金額iを作るのに必要な最小硬貨数を表し、各硬貨の額面で更新を試みます。これは無制限ナップサック問題のバリエーション——各硬貨を無限に使用できます。フォローアップは「全ての組み合わせを出力」——バックトラッキングが必要です。dp[0] = 0で初期化し、残りは無限大に注意。

20. 0-1ナップサック問題

難易度：中程度 | 評価ポイント：古典的DPモデル

楽天の一次面接で出題。品物の重さと価値が与えられ、容量制限内で最大価値を求める。dp[i][j]は最初のi個の品物を容量jで使う場合の最大価値——各品物を選ぶか選ばないか。1次元に最適化する場合、逆順で走査することが重要——そうしないと重複選択になります。面接官は分割等和部分集合（#416）も聞きました——本質的に0-1ナップサックです。

21. Longest Common Subsequence（LeetCode #1143）

難易度：中程度 | 評価ポイント：2次元DP

ソニーの一次面接で出題。dp[i][j]はtext1の最初のi文字とtext2の最初のj文字のLCS長を表します。文字が一致すればdp[i][j] = dp[i-1][j-1] + 1、そうでなければ上と左の最大値を取ります。面接官は実際のLCSを復元するよう求めました——DPテーブルをバックトラックする必要があります。この問題のDP構造は編集距離と非常に似ています——比較して学ぶことをお勧めします。

五、グラフ理論（4問）

22. Number of Islands（LeetCode #200）

難易度：中程度 | 評価ポイント：DFS/BFS/Union-Find

NTTと楽天の両方で出題。グリッドを走査し、'1'に遭遇したらDFS/BFSを開始して繋がっている'1'を全て'0'にマークし、カウントを増やす。フォローアップは「最大島面積」。Union-Findでも解けますが、コード量が増えるため、面接ではDFSが最も確実です。

23. Course Schedule（LeetCode #207）

難易度：中程度 | 評価ポイント：トポロジカルソート/サイクル検出

ホンダの二次面接で出題。本質的に有向グラフにサイクルがあるかを判定する問題。BFS+入次数配列でトポロジカルソートするか、DFSでサイクル検出。フォローアップは「履修順序を出力」（#210）——完全なトポロジカルソート。グラフ構築の段階で間違いが起きやすい——隣接リストと入次数配列の対応に注意。

24. 最短経路（ダイクストラ法）

難易度：中程度 | 評価ポイント：貪欲法+優先度付きキュー

ソニーの三次面接でNetwork Delay Time（LeetCode #743）が出題——本質的にダイクストラ法。優先度付きキューで最適化すると時間計算量O(ElogV)。面接官はヒープの手書きを求めました——簡略版の優先度付きキューを書きました。ダイクストラ法は非負重みグラフにのみ適用——負の重みの辺がある場合はBellman-Fordを使用。

25. トポロジカルソートの応用

難易度：中程度 | 評価ポイント：BFSトポロジカルソート

楽天の二次面接でAlien Dictionary（LeetCode #269）が出題——単語の順序から文字の順序を推導する問題で、本質的にトポロジカルソート。難しいのはグラフ構築——隣接する単語から部分順序関係を抽出する方法。面接中にグラフ構築ロジックを間違え、面接官のヒントで修正しました。この問題はグラフ構築の段階でつまずきやすいです。

六、設計問題（5問）

26. LRU Cache（LeetCode #146）

難易度：中程度 | 評価ポイント：ハッシュマップ+双方向リンクリスト

大手IT企業で最もよく聞かれる設計問題——楽天、NTT、ソニーの3社で出題されました。核心的なデータ構造はハッシュマップ+双方向リンクリスト：ハッシュマップでO(1)検索、双方向リンクリストでO(1)順序調整。getでノードを先頭に移動、putで容量超過時に末尾を削除。面接官はスレッドセーフティ、分散キャッシュなどの拡張問題をフォローアップします。

27. Min Stack（LeetCode #155）

難易度：中程度 | 評価ポイント：補助スタック

富士通の一次面接で出題。二つのスタック：データ用と現在の最小値追跡用。pushで補助スタックに現在の最小値をプッシュ、popで両方のスタックからポップ。フォローアップは「1つのスタックだけでできるか？」——差分ベースのアプローチで現在値と最小値の差を保存できますが、可読性が低下。面接ではお勧めしません。

28. Implement Queue using Stacks（LeetCode #232）

難易度：簡単 | 評価ポイント：二重スタックシミュレーション

ホンダの一次面接で出題。二つのスタック：入力用と出力用。pushは入力スタックへ、popで出力スタックが空なら入力スタックの全てを出力スタックに移動。面接官は償却時間計算量を聞きました——各要素は最大2回移動されるため、償却O(1)。バリエーションはキューでスタックを実装（#225）。

29. Implement Trie（Prefix Tree）（LeetCode #208）

難易度：中程度 | 評価ポイント：ツリーデータ構造の設計

NTTの二次面接で出題。各ノードには26個の子ポインタとisEndフラグが含まれます。insertは文字ごとに挿入、searchは文字ごとに検索。フォローアップは「オートコンプリートの実装」——プレフィックスノードからDFSでそのプレフィックスで始まる全ての単語を出力。コード量が多いため、面接では先にアプローチを説明してからコードを書くことをお勧めします。

30. スキップリスト（Skip List）

難易度：難しい | 評価ポイント：確率的データ構造

楽天の三次面接で出題。スキップリストはRedisのソート済みセットの基盤実装の一つ。面接官は「スキップリストの挿入操作を手書きで」と直接聞きました。核心的な考え方は、多段インデックスでO(logn)検索を実現し、各ノードが確率pで上のレベルに昇格。理論は理解していましたが実装経験がなく、現場ではたどたどしくなりましたが、面接官は「アプローチは合っている」と言ってくれました。

ポイント：スキップリストはLeetCodeにありませんが、大手IT企業の面接では确实に聞かれます。特にRedis関連のポジションで。原理を理解し、少なくとも挿入と削除のプロセスを図示できるようにしてください。

面接問題クイックリファレンス

以下は30問のクイックスキャンテーブルで、弱点の特定に役立ててください：

配列/文字列：Two Sum(#1,簡単)、3Sum(#15,中程度)、最長部分文字列(#3,中程度)、区間マージ(#56,中程度)、スライディングウィンドウ最大値(#239,難しい)、配列回転(#189,中程度)

リンクリスト：リンクリスト反転(#206,簡単)、ソート済みリストマージ(#21,簡単)、サイクル検出(#141/142,簡単/中程度)、kグループ反転(#25,難しい)

ツリー：レベル順走査(#102,中程度)、最大深さ(#104,簡単)、パス合計III(#437,中程度)、LCA(#236,中程度)、BST検証(#98,中程度)

動的計画法：階段登り(#70,簡単)、LIS(#300,中程度)、編集距離(#72,難しい)、硬貨両替(#322,中程度)、0-1ナップサック(中程度)、LCS(#1143,中程度)

グラフ理論：島の数(#200,中程度)、コーススケジュール(#207,中程度)、最短経路(#743,中程度)、トポロジカルソート(#269,中程度)

設計：LRUキャッシュ(#146,中程度)、最小スタック(#155,中程度)、スタックでキュー(#232,簡単)、Trie(#208,中程度)、スキップリスト(難しい)

心得とアドバイス

1. 戦略的に問題を解く——量を盲目的に追わない。初期は200問以上解きましたが、同じタイプの重複練習が多かったです。カテゴリ別に切り替え、各タイプで3〜5問の古典的問題に集中した方が効果的でした。30問の高頻度問題を深く理解することが、100問を適当に解くより役立ちます。

2. コードを書く前にアプローチを説明する。痛い目を見ました——楽天の二次面接でいきなり書き始め、途中でアプローチの欠陥に気づき、書き直す時間がなくなりました。今は必ず2〜3分かけて面接官とアプローチを確認してから書くようにしています。

3. バリエーションとフォローアップを重視する。面接官が元の問題だけを聞くことは稀です。Two Sumから3Sum、リンクリスト反転から範囲反転、レベル順走査からジグザグ走査。一般的なバリエーションを各問題と一緒に練習してください。

4. 簡単な問題も真剣に準備する。簡単な問題は練習不要と思う人が多いですが、面接ではオープニングとして出題されることが多く、スムーズに書けないと面接官の第一印象に直結します。また、簡単な問題のフォローアップは難しい問題よりも意地悪な場合があります。

5. 時間・空間計算量を自発的に分析する。コードを書いた後、面接官に聞かれるのを待たず、自発的に計算量を説明し、最適化の可能性に言及する。これは明確な差別化ポイントです。

よくある質問FAQ

Q：30問で十分ですか？大手IT企業の面接に対応するには何問必要？

A：30問の高頻度問題が核心ですが、一般的なパターンをカバーするために合計80〜100問程度をお勧めします。量より質——答えを暗記するのではなく原理を理解してください。

Q：どの順序で解くべき？

A：配列/文字列→リンクリスト→ツリー→動的計画法→グラフ理論→設計問題。各カテゴリで簡単→難しいの順に——まず簡単な問題で自信をつけてください。

Q：面接中にアルゴリズム問題が解けない場合は？

A：絶対に黙らないでください。まず思いつく力ずくの解法を説明し、面接官と最適化の方向を議論してください。面接官は通常ヒントをくれます——ヒントに従って最終的な解法にたどり着いても問題ありません。

Q：LeetCodeの週間コンテストに参加すべき？

A：時間があれば、制限時間内の問題解決能力を鍛えるのに役立ちます。ただし、コンテスト問題は競技プログラミングスタイルに偏り、面接問題のスタイルとは完全には一致しないため、高頻度問題を優先してください。

Q：動的計画法の状態遷移方程式がいつも思いつかない場合は？

A：これは正常です。最も簡単な階段登りから始め、徐々にナップサックや部分列問題に進んでください。各DP問題で状態遷移テーブルを描く——dp配列の意味と遷移ロジックを理解することが、テンプレートを暗記するより効果的です。