大手IT面接必須の15アルゴリズム問題：通過率順の問題リスト

大手IT面接必須の15アルゴリズム問題：通過率順の問題リスト

背景紹介

私はLeetCodeで400問以上を解き、ByteDance、Alibaba、Meituan、Kuaishou、Pinduoduoの面接を受けました。大手ITのアルゴリズム面接は問題が高度に集中していることが分かりました。1000問解く必要はありません——この15の最高頻度問題をマスターすれば、アルゴリズムの試験ポイントの80%以上をカバーできます。通過率の高い順に並べ、易から難へ、各問題にLeetCode番号、難易度、試験ポイント、解法アプローチを付けています。順番に解き、各問題を最低2回——1回目はアプローチの理解、2回目は記憶から書くことをお勧めします。

1. Two Sum（LeetCode #1、簡単、通過率52%）

試験ポイント：ハッシュテーブル、配列走査

問題：配列と目標値が与えられ、和が目標値になる2つの数のインデックスを見つける。

解法：総当たりO(n²)は通るが面接では不十分。ハッシュテーブルでO(n)に最適化：配列を走査し、各要素についてtarget-nums[i]がハッシュテーブルにあるか確認、あれば返す、なければ現在の要素を追加。ポイント：同じ要素を2回使わないよう先に確認してから保存。フォローアップ：複数の答えがある場合は？問題が一意解を保証。ソートされていない配列は？ハッシュテーブルは順序不要。

2. Reverse Linked List（LeetCode #206、簡単、通過率73%）

試験ポイント：リンクリスト操作、ポインタ

問題：単方向リンクリストを反転する。

解法：反復法——3つのポインタprev、curr、next。各ステップでcurr.nextをprevに向け、3つのポインタをそれぞれ前進。currがnullになるまで、prevを返す。再帰法——リストの末尾まで再帰、バックトラック時に方向を反転。必須知識：両方の計算量？どちらもO(n)時間、O(1)/O(n)空間。フォローアップ：リンクリストの一部を反転するには？92番、区間判定を追加。

3. Valid Parentheses（LeetCode #20、簡単、通過率41%）

試験ポイント：スタック、文字列処理

問題：括弧文字列が有効か判定する。

解法：スタックを使用。左括号はプッシュ、右括号はスタックトップが一致するか確認。走査後スタックが空なら有効。最適化：左括号に遭遇した時、対応する右括号をプッシュ——比較時に等価チェックだけで済む。フォローアップ：最長有効括弧部分文字列は？32番、スタックまたはDPを使用、難易度が2レベル跳ね上がる。

4. Maximum Subarray（LeetCode #53、中等、通過率55%）

試験ポイント：動的計画法、貪欲法

問題：連続部分配列の最大和を見つける。

解法：Kadaneアルゴリズム——現在の部分配列和curと最大和resを維持。cur<0なら破棄して再開（cur=nums[i]）；そうでなければ累積を続ける。各ステップでres=max(res,cur)を更新。時間O(n)空間O(1)。フォローアップ：部分配列の開始・終了位置も返す？2つのポインタを追加。全負の配列？Kadaneは自然に処理——最大の負数を返す。

5. Merge Two Sorted Lists（LeetCode #21、簡単、通過率67%）

試験ポイント：リンクリスト操作、再帰

問題：2つの昇順リンクリストを1つの昇順リストにマージする。

解法：反復法——ダミーヘッドを使用、両リストの現在ノードを比較、小さい方を結果リストに接続、ポインタを前進。一方が尽きたら残りを接続。再帰法——ヘッドを比較、小さい方のnextを再帰マージ結果に指す。フォローアップ：K個のソート済みリストのマージ？最小ヒープを使用、常に最小のヘッドを取得。時間O(nklogk)。

6. Binary Tree Level Order Traversal（LeetCode #102、中等、通過率65%）

試験ポイント：BFS、キュー

問題：二分木をレベルごとに走査し、各レベルのノード値を返す。

解法：BFSでキューを使用。ポイント：レベルごとにグループ化——各レベル開始時にキュー長を記録、その回数だけデキュー、子ノードをエンキュー。フォローアップ：下から上へのレベル順走査？結果をreverse。ジグザグ走査？偶数レベルをreverse。右側面図？各レベルの最後のノード。これらの変種は全て必要。

7. Climbing Stairs（LeetCode #70、簡単、通過率53%）

試験ポイント：動的計画法、漸化式

問題：1段または2段ずつ登る時、n段目に到達する方法は何通り？

解法：古典的DP。dp[i]=dp[i-1]+dp[i-2]、つまりフィボナッチ数列。空間最適化：前2つの値のみ保存、O(1)空間。フォローアップ：1〜m段ずつ登れる場合？完全ナップサック問題、dp[i]=sum(dp[i-j]) for j in 1..m。段にコストがある場合？746番、dp[i]=min(dp[i-1],dp[i-2])+cost[i]。

8. Best Time to Buy and Sell Stock（LeetCode #121、簡単、通過率58%）

試験ポイント：動的計画法、貪欲法

問題：1回の取引のみ許可、最大利益を求める。

解法：配列を走査、これまでの最低価格minPriceを維持、毎日の利益prices[i]-minPriceを計算、最大利益を更新。時間O(n)空間O(1)。必須質問シリーズ：2回の取引？123番。無制限？122番、貪欲法。クールダウンあり？309番、状態機械DP。手数料あり？714番。このシリーズ6問はまとめて解くことを推奨。

9. Longest Palindromic Substring（LeetCode #5、中等、通過率37%）

試験ポイント：動的計画法、中心拡張

問題：最長の回文部分文字列を見つける。

解法：中心拡張法——各文字（と各文字の間）を中心に両側へ拡張、最長回文を記録。時間O(n²)空間O(1)。DP法——dp[i][j]はs[i..j]が回文かを示す、dp[i][j]=dp[i+1][j-1]&&s[i]==s[j]。時間O(n²)空間O(n²)。ManacherアルゴリズムO(n)だが面接では不要。フォローアップ：回文部分文字列の数？647番、同じ中心拡張。

10. 3Sum（LeetCode #15、中等、通過率36%）

試験ポイント：ソート、双ポインタ、重複排除

問題：和が0になる3つ組を全て見つける。

解法：まずソートO(nlogn)、最初の数を固定、残り2つは双ポインタ。左ポインタはi+1から、右ポインタは末尾から、3つの和に基づいてポインタを移動。ポイント：重複排除——最初の数が前と同じならスキップ、答えを見つけた後も左右ポインタで重複値をスキップ。フォローアップ：4Sum？18番、ループを1つ追加。最も近い3Sum？16番、targetに最も近い値を記録。

11. Longest Substring Without Repeating Characters（LeetCode #3、中等、通過率39%）

試験ポイント：スライディングウィンドウ、ハッシュテーブル

問題：重複文字を含まない最長部分文字列の長さを見つける。

解法：スライディングウィンドウ——Mapで文字の最新出現位置を記録。右ポインタで文字列を走査、現在の文字がウィンドウ内にある場合（mapにあり位置>=左ポインタ）、左ポインタをその位置+1にジャンプ。各ステップで最大長を更新。時間O(n)。フォローアップ：小文字のみ？配列でMapより効率的。最大K種の異なる文字を含む最長部分文字列？340番、Mapでカウント。

12. Merge Intervals（LeetCode #56、中等、通過率49%）

試験ポイント：ソート、区間操作

問題：重複する区間を全てマージする。

解法：左端点でソート、区間を走査。現在の左端点<=結果の最後の右端点ならマージ（右端点をmaxに更新）；そうでなければ結果に追加。フォローアップ：区間の挿入？57番、3セグメントで処理。区間リストの積集合？986番、双ポインタで積を取得。会議室？252番、区間の重複を判定。

13. Number of Islands（LeetCode #200、中等、通過率59%）

試験ポイント：DFS/BFS、グリッド走査

問題：グリッド内の島の数を数える。

解法：グリッドを走査、'1'に遭遇したら島数+1、DFS/BFSで繋がる'1'を全て'0'に（沈島法）。DFS：4方向に再帰。BFS：キューを使用。時間O(mn)。フォローアップ：最大島面積？695番、DFSでカウント。囲まれた領域？130番、境界からDFS。島の周長？463番、数学的計算。

14. LRU Cache（LeetCode #146、中等、通過率42%）

試験ポイント：ハッシュテーブル+双方向リスト、設計

問題：getとputがO(1)のLRUキャッシュを実装する。

解法：ハッシュテーブルでkey→ノードのマッピング、双方向リストでアクセス順序を維持。get：ノードを見つけ、リスト先頭に移動。put：keyがあれば値を更新して先頭に移動；なければ新ノードを先頭に追加、容量超過なら末尾を削除。必須設計問題——ByteDance、Alibaba、Meituanで出題されました。フォローアップ：スレッドセーフなLRU？ロック追加またはConcurrentHashMapを使用。

15. Edit Distance（LeetCode #72、困難、通過率61%）

試験ポイント：動的計画法、文字列

問題：word1をword2に変換する最小操作数（挿入、削除、置換）を求める。

解法：古典的DP。dp[i][j]=word1の最初i文字をword2の最初j文字に変換する最小操作数。遷移：word1[i-1]==word2[j-1]ならdp[i][j]=dp[i-1][j-1]；そうでなければdp[i][j]=min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)がそれぞれ削除、挿入、置換に対応。時間O(mn)空間O(mn)、空間はO(min(m,n))に最適化可能。フォローアップ：挿入と削除のみ？置換操作を削除。2つの文字列の削除操作？583番。

実問題まとめ

面接での出題頻度統計：Two Sum、Reverse Linked List、LRU Cacheはほぼ毎回出題；Valid Parentheses、Maximum Subarray、3Sumは出現頻度70%以上；Edit Distanceは困難とマークされているが通過率が高く、ByteDanceとAlibabaが好んで出題。1から15の順番で解き、各問題を2-3回書くことを推奨。

心得とアドバイス

1. 質が量に勝る——15の高頻度問題をマスターする方が100問を流し見するより有益。各問題を最低2回書く、2回目は記憶から。

2. 変種を重視——面接官は原題を出すことは稀だが、変種は原題ベース。Reverse Linked List→Reverse Linked List II、Climbing Stairs→完全ナップサック、Stock Tradingシリーズなど。

3. コードを書く前にアプローチを説明——アルゴリズム面接は暗記ではなく対話。面接官と理解を確認、時間・空間計算量を説明してからコーディング。

4. 書き終わったらテスト——境界ケースで実行：空入力、単一要素、全同値、全負数など。面接官は検証習慣を重視。

5. 分からなくても慌てない——まず総当たり法を述べ、最適化を考える。総当たりでも得点になる、空白より10倍マシ。ByteDanceの3次面接でO(n²)の3Sumを先に書き、面接官がO(nlogn)への最適化をヒント。

FAQ

Q：どの程度の熟練度が必要？

A：簡単問題は5分以内、中等問題は15分以内で最適解、困難問題はアプローチを説明できること。大手は通常簡単〜中等、ByteDanceはたまに困難を出題。

Q：この15問だけで十分？

A：試験ポイントの80%をカバー、さらに15-20問の追加を推奨：クイックソート/マージソート、二分探索、累積和、トポロジカルソート、Union-Findなど。合計30-35問でほとんどの面接に対応可能。

Q：問題解決に何語を使う？

A：バックエンド：Java/Go/C++、フロントエンド：JavaScript/TypeScript。対象職種の主要言語を使用。

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

A：1）まず総当たり法を述べる；2）総当たり法の問題を分析；3）最適化の方向を試みる；4）疑似コードでも可。思考プロセスを見せることが沈黙より遥かに良い。