Skip to content
Published on

コーディング面接パターン完全攻略：FAANG合格のためのアルゴリズム15パターン＋75問ロードマップ

🇰🇷KO🇺🇸EN🇯🇵JA
Split View✨Start Quiz
Authors

1. 2025年コーディング面接の現状

FAANG出題頻度とトレンド

2025年のFAANG（Meta、Apple、Amazon、Netflix、Google）コーディング面接は、以前よりパターンベースの問題出題比率が高くなっています。単純な暗記問題よりも、既存パターンの変形や組み合わせ問題が主流となり、特にGraph＋DP複合問題、Sliding Window＋Hash Map組み合わせ問題が頻出しています。

2025年基準の主要出題頻度は以下の通りです。

パターンGoogleMetaAmazonAppleMicrosoft
Arrays/Hashing25%30%35%20%28%
Trees/Graphs22%18%15%25%20%
Dynamic Programming18%15%12%18%15%
Two Pointers/Sliding Window12%15%18%10%12%
Binary Search8%7%8%10%10%
その他（Stack、Heap、Trie等）15%15%12%17%15%

AI対応コーディングラウンドの登場

2025年から一部の企業はAIコパイロット使用を前提としたコーディング面接を導入し始めました。単純な実装能力よりも問題分析、最適アルゴリズム選択、コードレビュー能力を評価する方向へ変化しています。しかし依然として伝統的なホワイトボードコーディングが主流であり、アルゴリズムパターンの理解は必須です。

NeetCode 150 vs Blind 75 vs Grind 75 比較

特性Blind 75NeetCode 150Grind 75
問題数7515075（カスタム可能）
難易度分布Easy 20%、Medium 55%、Hard 25%Easy 25%、Medium 50%、Hard 25%Easy 25%、Medium 55%、Hard 20%
パターンカバレッジ13個15個14個
最終更新202120242023
推奨対象時間が限られた経験者体系的学習を望む方カスタムスケジュールを望む方

本記事ではNeetCode 150をベースに厳選75問を選定し、各パターンごとに必ず解くべき問題をまとめます。

言語選択：Python vs Java vs TypeScript

  • Python：コードが簡潔で素早い解法が可能。FAANG面接で最も人気のある言語。内蔵ライブラリ（heapq、collections、itertools）が強力
  • Java：型安全性とパフォーマンスが利点。AmazonやGoogleで好まれる。TreeMap、PriorityQueue等のデータ構造が豊富
  • TypeScript：フロントエンド職の面接で有利。しかしアルゴリズム問題ではPythonに比べ利点が少ない

本記事のコード例はPythonを基本とします。

12週間学習ロードマップ概要

週パターン1日の問題数
1-2週Arrays/Hashing、Two Pointers2問
3-4週Sliding Window、Stack、Binary Search2問
5-6週Linked List、Trees2問
7-8週Tries、Heap、Backtracking2問
9-10週Graphs、1D DP2-3問
11-12週2D DP、Greedy、Intervals、総合復習2-3問

2. Pattern 1 — Arrays and Hashing

核心アイデア

配列とハッシュマップはすべてのアルゴリズムの基礎です。ハッシュマップによるO(1)ルックアップでbrute forceのO(n^2)をO(n)に削減することが核心です。頻度カウント、重複検出、グルーピング問題に必須で使われます。

時間/空間計算量

  • ハッシュマップ挿入/検索：O(1)平均、O(n)最悪
  • ソートベースアプローチ：O(n log n)
  • 空間：O(n) — ハッシュマップ格納

代表問題

  1. Two Sum (LeetCode 1) — Easy
  2. Contains Duplicate (LeetCode 217) — Easy
  3. Valid Anagram (LeetCode 242) — Easy
  4. Group Anagrams (LeetCode 49) — Medium
  5. Top K Frequent Elements (LeetCode 347) — Medium

Python解法 — Two Sum (LeetCode 1)

def twoSum(nums: list[int], target: int) -> list[int]:
    # ハッシュマップ：値 -> インデックスのマッピング
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# 時間：O(n)、空間：O(n)
# 核心：complementをハッシュマップでO(1)で検索

変形問題とヒント

  • Three Sum (LeetCode 15)：ソート後にTwo Pointersを組み合わせる
  • Product of Array Except Self (LeetCode 238)：prefix/suffix積パターン
  • 面接のヒント：常にハッシュマップでO(n)解法が可能かを最初に考えましょう

3. Pattern 2 — Two Pointers

核心アイデア

ソート済み配列や文字列で二つのポインタを両端から内側に移動させ、条件を満たすペアを見つけます。または同じ方向に移動するfast/slowポインタパターンもあります。O(n^2)のbrute forceをO(n)に最適化できます。

時間/空間計算量

  • 時間：O(n)（ソート済みの場合）またはO(n log n)（ソートが必要な場合）
  • 空間：O(1) — 追加空間不要

代表問題

  1. Valid Palindrome (LeetCode 125) — Easy
  2. Two Sum II - Sorted Array (LeetCode 167) — Medium
  3. 3Sum (LeetCode 15) — Medium
  4. Container With Most Water (LeetCode 11) — Medium
  5. Trapping Rain Water (LeetCode 42) — Hard

Python解法 — Container With Most Water (LeetCode 11)

def maxArea(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    max_water = 0

    while left < right:
        # 現在の二つの壁で作れる水の量を計算
        width = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, width * h)

        # より低い壁のポインタを移動
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water

# 時間：O(n)、空間：O(1)
# 核心：低い壁を移動することで面積が増加する可能性がある

変形問題とヒント

  • Trapping Rain Water：両側の最大高さを追跡する変形
  • 面接のヒント：入力がソート済みならTwo Pointersを最初に検討しましょう
  • 3Sumは一つを固定し、残りの二つをTwo Pointersで処理

4. Pattern 3 — Sliding Window

核心アイデア

固定または可変サイズのウィンドウを配列/文字列上でスライドさせ、ウィンドウ内の最適値（最大和、最小長、条件を満たす部分文字列等）を見つけます。新しい要素を追加し古い要素を除去しながらO(n)で処理します。

時間/空間計算量

  • 時間：O(n) — 各要素がウィンドウに最大1回入り、1回出る
  • 空間：O(k) — ウィンドウサイズまたは文字種類数

代表問題

  1. Best Time to Buy and Sell Stock (LeetCode 121) — Easy
  2. Longest Substring Without Repeating Characters (LeetCode 3) — Medium
  3. Longest Repeating Character Replacement (LeetCode 424) — Medium
  4. Minimum Window Substring (LeetCode 76) — Hard
  5. Sliding Window Maximum (LeetCode 239) — Hard

Python解法 — Longest Substring Without Repeating Characters (LeetCode 3)

def lengthOfLongestSubstring(s: str) -> int:
    char_index = {}  # 文字 -> 最後に出現したインデックス
    left = 0
    max_len = 0

    for right in range(len(s)):
        if s[right] in char_index and char_index[s[right]] >= left:
            # 重複発見時、ウィンドウ左端を重複の次に移動
            left = char_index[s[right]] + 1
        char_index[s[right]] = right
        max_len = max(max_len, right - left + 1)

    return max_len

# 時間：O(n)、空間：O(min(n, 26))
# 核心：ハッシュマップで重複位置を追跡しウィンドウサイズを更新

変形問題とヒント

  • Minimum Window Substring：必要な文字カウントをハッシュマップで管理しながら縮小
  • 固定サイズウィンドウ：ウィンドウサイズkが与えられたらright - left + 1 == kを維持
  • 面接のヒント：連続する部分配列/文字列の条件がある場合、Sliding Windowを検討しましょう

5. Pattern 4 — Stack（Monotonic Stack）

核心アイデア

LIFO（Last In First Out） 特性を活用します。括弧のマッチングや数式計算には基本スタックを、Next Greater/Smaller Element問題には単調スタック（Monotonic Stack）を使用します。単調スタックはスタック内の要素が常に増加または減少の順序を維持するように管理します。

時間/空間計算量

  • 時間：O(n) — 各要素が最大1回push、1回pop
  • 空間：O(n) — スタック格納

代表問題

  1. Valid Parentheses (LeetCode 20) — Easy
  2. Min Stack (LeetCode 155) — Medium
  3. Evaluate Reverse Polish Notation (LeetCode 150) — Medium
  4. Daily Temperatures (LeetCode 739) — Medium
  5. Largest Rectangle in Histogram (LeetCode 84) — Hard

Python解法 — Daily Temperatures (LeetCode 739)

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack = []  # 単調減少スタック：インデックスを格納

    for i in range(n):
        # 現在の温度がスタックのtopより高ければpopして回答を記録
        while stack and temperatures[i] > temperatures[stack[-1]]:
            prev_idx = stack.pop()
            answer[prev_idx] = i - prev_idx
        stack.append(i)

    return answer

# 時間：O(n)、空間：O(n)
# 核心：単調減少スタックで次のより大きい要素までの距離をO(n)で計算

変形問題とヒント

  • Largest Rectangle in Histogram：単調増加スタックで高さごとの最大幅を計算
  • Next Greater Element：循環配列の場合は2n回繰り返す
  • 面接のヒント：現在の要素と前の要素の大小関係が重要な問題は単調スタックを考えましょう

6. Pattern 5 — Binary Search

核心アイデア

ソート済みデータで探索範囲を半分ずつ縮小してO(log n)で答えを見つけます。配列探索だけでなく、決定問題（最適化問題を二分探索に変換） にも活用されます。「最小値の最大化」や「最大値の最小化」パターンが代表的です。

時間/空間計算量

  • 時間：O(log n)
  • 空間：O(1)反復 / O(log n)再帰

代表問題

  1. Binary Search (LeetCode 704) — Easy
  2. Search a 2D Matrix (LeetCode 74) — Medium
  3. Koko Eating Bananas (LeetCode 875) — Medium
  4. Find Minimum in Rotated Sorted Array (LeetCode 153) — Medium
  5. Median of Two Sorted Arrays (LeetCode 4) — Hard

Python解法 — Koko Eating Bananas (LeetCode 875)

import math

def minEatingSpeed(piles: list[int], h: int) -> int:
    # 二分探索：食べる速度の範囲 [1, max(piles)]
    left, right = 1, max(piles)

    while left < right:
        mid = (left + right) // 2
        # 速度midで全バナナをh時間以内に食べられるか確認
        hours_needed = sum(math.ceil(pile / mid) for pile in piles)

        if hours_needed <= h:
            right = mid  # より遅い速度も可能か確認
        else:
            left = mid + 1  # より速い速度が必要

    return left

# 時間：O(n * log(max(piles)))、空間：O(1)
# 核心：「最小速度」を二分探索で求める決定問題パターン

変形問題とヒント

  • Rotated Sorted Array：中間値と両端を比較してソート済み側を判別
  • 決定問題パターン：条件関数canDo(x)が単調的なら二分探索を適用可能
  • 面接のヒント：ソートされていなくても、答えの範囲が単調的なら二分探索を検討しましょう

7. Pattern 6 — Linked List

核心アイデア

連結リストはポインタ操作が核心です。逆順、マージ、サイクル検出、中間ノード検索等の問題で繰り返し登場します。fast/slowポインタ（Floydアルゴリズム）はサイクル検出と中間ノード検索に必須です。

時間/空間計算量

  • 走査：O(n)時間、O(1)空間
  • 再帰方式：O(n)時間、O(n)スタック空間

代表問題

  1. Reverse Linked List (LeetCode 206) — Easy
  2. Merge Two Sorted Lists (LeetCode 21) — Easy
  3. Linked List Cycle (LeetCode 141) — Easy
  4. Reorder List (LeetCode 143) — Medium
  5. Merge k Sorted Lists (LeetCode 23) — Hard

Python解法 — Reverse Linked List (LeetCode 206)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head: ListNode) -> ListNode:
    prev = None
    current = head

    while current:
        next_node = current.next  # 次のノードを保存
        current.next = prev       # 現在のノードの方向を逆転
        prev = current             # prevを一つ前進
        current = next_node        # currentを一つ前進

    return prev

# 時間：O(n)、空間：O(1)
# 核心：3つのポインタ（prev、current、next）でその場で逆転

変形問題とヒント

  • Reorder List：中間検索＋後半逆転＋マージの3段階
  • Merge k Sorted Lists：最小ヒープでk個のリストのheadを管理
  • 面接のヒント：dummyノードを活用するとエッジケースの処理が容易になります

8. Pattern 7 — Trees（BFS/DFS）

核心アイデア

木の問題は再帰的DFS（前順/中順/後順走査）とBFS（レベル順走査）に分かれます。多くの二分木問題は**「現在のノードで何をし、子ノードに何を委任するか」** を定義すれば解けます。

時間/空間計算量

  • DFS：O(n)時間、O(h)空間（h = 木の高さ、最悪O(n)）
  • BFS：O(n)時間、O(w)空間（w = 最大レベル幅）

代表問題

  1. Maximum Depth of Binary Tree (LeetCode 104) — Easy
  2. Invert Binary Tree (LeetCode 226) — Easy
  3. Binary Tree Level Order Traversal (LeetCode 102) — Medium
  4. Validate Binary Search Tree (LeetCode 98) — Medium
  5. Binary Tree Maximum Path Sum (LeetCode 124) — Hard

Python解法 — Binary Tree Level Order Traversal (LeetCode 102)

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def levelOrder(root: TreeNode) -> list[list[int]]:
    if not root:
        return []

    result = []
    queue = deque([root])

    while queue:
        level_size = len(queue)
        level = []

        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        result.append(level)

    return result

# 時間：O(n)、空間：O(n)
# 核心：BFSでレベルサイズ分ずつ処理しレベル別にグループ化

変形問題とヒント

  • BST検証：中順走査がソート順序かを確認するか、範囲を渡すDFS
  • Maximum Path Sum：後順走査で子の最大貢献値を計算
  • 面接のヒント：木の問題ではベースケース（nullノード）を最初に処理しましょう

9. Pattern 8 — Tries

核心アイデア

Trie（トライ、接頭辞木） は文字列を文字単位で格納する木構造です。接頭辞検索がO(m)（m = 文字列長）で可能であり、オートコンプリート、辞書検索、ワイルドカードマッチングに活用されます。

時間/空間計算量

  • 挿入/検索：O(m) — mは文字列長
  • 空間：O(総文字数 * アルファベットサイズ)

代表問題

  1. Implement Trie (Prefix Tree) (LeetCode 208) — Medium
  2. Design Add and Search Words (LeetCode 211) — Medium
  3. Word Search II (LeetCode 212) — Hard

Python解法 — Implement Trie (LeetCode 208)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self._find(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        return self._find(prefix) is not None

    def _find(self, prefix: str) -> TrieNode:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

# 時間：挿入/検索 O(m)、空間：O(総文字数)
# 核心：各ノードが子ディクショナリと終了フラグを保持

変形問題とヒント

  • Word Search II：Trie＋DFSバックトラッキングの組み合わせ
  • Design Add and Search Words：ワイルドカード . に対して再帰DFS
  • 面接のヒント：複数文字列の接頭辞を繰り返し検索する必要がある場合、Trieが効率的です

10. Pattern 9 — Heap / Priority Queue

核心アイデア

ヒープ（Heap） は最大/最小値をO(1)で取得し、O(log n)で挿入/削除するデータ構造です。Top K問題、ストリーミングデータの中央値、タスクスケジューリング等に核心的に使われます。

時間/空間計算量

  • 挿入/削除：O(log n)
  • 最大/最小取得：O(1)
  • ヒープ構築（heapify）：O(n)

代表問題

  1. Kth Largest Element in a Stream (LeetCode 703) — Easy
  2. Last Stone Weight (LeetCode 1046) — Easy
  3. K Closest Points to Origin (LeetCode 973) — Medium
  4. Task Scheduler (LeetCode 621) — Medium
  5. Find Median from Data Stream (LeetCode 295) — Hard

Python解法 — Find Median from Data Stream (LeetCode 295)

import heapq

class MedianFinder:
    def __init__(self):
        # max_heap：小さい側の半分（Pythonでは負数で最大ヒープを実装）
        # min_heap：大きい側の半分
        self.max_heap = []  # 左半分
        self.min_heap = []  # 右半分

    def addNum(self, num: int) -> None:
        # 常にmax_heapに先に追加
        heapq.heappush(self.max_heap, -num)
        # max_heapの最大値をmin_heapに移動
        heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))

        # サイズのバランス：max_heapがmin_heap以上のサイズを維持
        if len(self.min_heap) > len(self.max_heap):
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))

    def findMedian(self) -> float:
        if len(self.max_heap) > len(self.min_heap):
            return -self.max_heap[0]
        return (-self.max_heap[0] + self.min_heap[0]) / 2

# 時間：addNum O(log n)、findMedian O(1)
# 核心：二つのヒープでデータを半分に分けて中央値を効率的に維持

変形問題とヒント

  • Task Scheduler：最大ヒープで最も頻度が高いタスクからスケジューリング
  • Pythonのheapqは最小ヒープなので、最大ヒープが必要なら負数に変換
  • 面接のヒント：Top K問題はサイズKの最小ヒープでO(n log k)で解決可能

11. Pattern 10 — Backtracking

核心アイデア

可能なすべての組み合わせ/順列/部分集合を探索しつつ、無効なパスを早期に枝刈り（pruning） します。再帰呼び出し＋選択/取消パターンが基本であり、時間計算量が指数的なため、枝刈りがパフォーマンスに決定的です。

時間/空間計算量

  • 部分集合：O(2^n)
  • 順列：O(n!)
  • 空間：O(n) — 再帰の深さ

代表問題

  1. Subsets (LeetCode 78) — Medium
  2. Combination Sum (LeetCode 39) — Medium
  3. Permutations (LeetCode 46) — Medium
  4. Word Search (LeetCode 79) — Medium
  5. N-Queens (LeetCode 51) — Hard

Python解法 — Combination Sum (LeetCode 39)

def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    result = []

    def backtrack(start: int, current: list[int], remaining: int):
        if remaining == 0:
            result.append(current[:])  # 現在の組み合わせを結果に追加
            return
        if remaining < 0:
            return  # 枝刈り

        for i in range(start, len(candidates)):
            current.append(candidates[i])
            # 同じ要素の再使用が可能 -> startをiに維持
            backtrack(i, current, remaining - candidates[i])
            current.pop()  # 選択取消（バックトラッキング）

    backtrack(0, [], target)
    return result

# 時間：O(2^t)（t = target / min(candidates)）、空間：O(target)
# 核心：選択 -> 再帰 -> 取消パターンと枝刈り

変形問題とヒント

  • Subsets：各段階で現在の状態を結果に追加
  • Permutations：visited配列またはswap技法を使用
  • N-Queens：行/列/対角線の衝突をsetで追跡
  • 面接のヒント：バックトラッキング問題は決定木を描くとパターンが見えます

12. Pattern 11 — Graphs（BFS/DFS/Union-Find）

核心アイデア

グラフ問題は連結成分、最短経路、サイクル検出、トポロジカルソート等に分かれます。BFSは最短経路に、DFSは経路探索とサイクル検出に、Union-Findは連結成分管理に適しています。

時間/空間計算量

  • BFS/DFS：O(V + E)時間、O(V)空間
  • Union-Find：O(alpha(n))ほぼO(1) per operation
  • トポロジカルソート：O(V + E)

代表問題

  1. Number of Islands (LeetCode 200) — Medium
  2. Clone Graph (LeetCode 133) — Medium
  3. Course Schedule (LeetCode 207) — Medium（トポロジカルソート）
  4. Pacific Atlantic Water Flow (LeetCode 417) — Medium
  5. Graph Valid Tree (LeetCode 261) — Medium（Union-Find）

Python解法 — Number of Islands (LeetCode 200)

def numIslands(grid: list[list[str]]) -> int:
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r: int, c: int):
        # 範囲外または水ならリターン
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'  # 訪問済みマーク（島を水に変更）
        # 上下左右を探索
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)

    return count

# 時間：O(m * n)、空間：O(m * n)最悪の再帰深さ
# 核心：新しい島を発見するたびにDFSで全体を訪問処理

Union-Find実装

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # 連結成分数

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # パス圧縮
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        # ランクベースの結合
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.count -= 1
        return True

変形問題とヒント

  • Course Schedule：トポロジカルソート（Kahnアルゴリズム）でサイクル検出
  • Pacific Atlantic Water Flow：逆方向BFS — 海から内陸へ開始
  • 面接のヒント：グラフ問題はまず隣接リスト/行列の表現を決め、BFS/DFS/Union-Findの中から適切なものを選択しましょう

13. Pattern 12 — Dynamic Programming（1D）

核心アイデア

1次元DPは単一変数に対する最適部分構造を活用します。漸化式dp[i]を定義し、以前の状態（dp[i-1]、dp[i-2]等）から現在の状態を計算します。フィボナッチ、階段上り、泥棒問題が典型的です。

時間/空間計算量

  • 時間：O(n) 〜 O(n * k)
  • 空間：O(n)（テーブル）またはO(1)（空間最適化時）

代表問題

  1. Climbing Stairs (LeetCode 70) — Easy
  2. House Robber (LeetCode 198) — Medium
  3. Coin Change (LeetCode 322) — Medium
  4. Longest Increasing Subsequence (LeetCode 300) — Medium
  5. Word Break (LeetCode 139) — Medium

Python解法 — Coin Change (LeetCode 322)

def coinChange(coins: list[int], amount: int) -> int:
    # dp[i] = 金額iを作るための最小コイン数
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # 0円は0枚のコインで可能

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] != float('inf'):
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

# 時間：O(amount * len(coins))、空間：O(amount)
# 核心：各金額に対して全コインを試し、最小値を更新

変形問題とヒント

  • House Robber：dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — 隣接する家の条件
  • LIS：O(n log n)解法は二分探索＋補助配列を活用
  • Word Break：dp[i] = あるjに対してdp[j] and s[j:i] in wordSet
  • 面接のヒント：1D DPは空間をO(1)に削減できる場合が多いので、最適化も言及しましょう

14. Pattern 13 — Dynamic Programming（2D）

核心アイデア

2次元DPは二つの変数（二つの文字列、グリッド座標等）に対する状態を定義します。dp[i][j]が最初の入力のi番目まで、二番目の入力のj番目まで考慮した結果を表します。

時間/空間計算量

  • 時間：O(m * n)
  • 空間：O(m * n)またはO(min(m, n))（行圧縮時）

代表問題

  1. Unique Paths (LeetCode 62) — Medium
  2. Longest Common Subsequence (LeetCode 1143) — Medium
  3. Best Time to Buy and Sell Stock with Cooldown (LeetCode 309) — Medium
  4. Target Sum (LeetCode 494) — Medium
  5. Edit Distance (LeetCode 72) — Medium

Python解法 — Longest Common Subsequence (LeetCode 1143)

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    # dp[i][j] = text1の最初のi文字とtext2の最初のj文字のLCS長
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

# 時間：O(m * n)、空間：O(m * n)
# 核心：文字が同じなら対角線+1、異なれば上/左の最大値

変形問題とヒント

  • Edit Distance：挿入/削除/置換の3つの操作をそれぞれ考慮
  • Target Sum：ナップサック問題（Knapsack）に変換して解法
  • 空間最適化：前の行だけ必要なら1D配列に圧縮可能
  • 面接のヒント：2D DPの漸化式を明確に定義してからコーディングを始めましょう

15. Pattern 14 — Greedy

核心アイデア

各段階で局所的に最適な選択が全体的にも最適な結果を保証する問題に適用します。DPと異なり以前の選択を覆さず、正しいGreedy戦略を立てることが核心です。証明が難しい場合が多いため、パターンを覚えることが効率的です。

時間/空間計算量

  • 通常O(n)またはO(n log n)（ソートが必要な場合）
  • 空間：O(1) 〜 O(n)

代表問題

  1. Maximum Subarray (LeetCode 53) — Medium
  2. Jump Game (LeetCode 55) — Medium
  3. Jump Game II (LeetCode 45) — Medium
  4. Gas Station (LeetCode 134) — Medium
  5. Hand of Straights (LeetCode 846) — Medium

Python解法 — Jump Game (LeetCode 55)

def canJump(nums: list[int]) -> bool:
    # goal：到達すべき位置（後ろから前へ）
    goal = len(nums) - 1

    for i in range(len(nums) - 2, -1, -1):
        if i + nums[i] >= goal:
            goal = i  # 現在位置からgoalに到達可能ならgoalを更新

    return goal == 0

# 時間：O(n)、空間：O(1)
# 核心：後ろから到達可能性をGreedyに判断

変形問題とヒント

  • Maximum Subarray（Kadane）：現在までの合計が負なら捨てて新しく開始
  • Jump Game II：BFS方式でレベルごとの最小ジャンプ数を計算
  • 面接のヒント：Greedyが正しいか確信がなければ、小さな反例で検証しましょう

16. Pattern 15 — Intervals and Math

核心アイデア

区間（Interval）問題は開始点/終了点でソートした後、重なりを処理することが核心です。マージ、挿入、最小会議室数等が代表的です。数学問題はビット演算、剰余演算、幾何学的計算等が含まれます。

時間/空間計算量

  • ソート：O(n log n)
  • スキャン：O(n)
  • 空間：O(n)（結果格納）

代表問題

  1. Merge Intervals (LeetCode 56) — Medium
  2. Insert Interval (LeetCode 57) — Medium
  3. Non-overlapping Intervals (LeetCode 435) — Medium
  4. Meeting Rooms II (LeetCode 253) — Medium
  5. Rotate Image (LeetCode 48) — Medium

Python解法 — Merge Intervals (LeetCode 56)

def merge(intervals: list[list[int]]) -> list[list[int]]:
    # 開始点でソート
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        # 現在の区間が前の区間と重なれば統合
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])

    return merged

# 時間：O(n log n)、空間：O(n)
# 核心：ソート後、重なる区間を順次統合

変形問題とヒント

  • Meeting Rooms II：開始/終了時刻を分離してソートしカウント
  • Non-overlapping Intervals：終了点でソート後にGreedyで最小除去
  • Rotate Image：転置（transpose）後に左右反転
  • 面接のヒント：区間問題はまずソート基準（開始点 vs 終了点）を決めましょう

17. 75問厳選チェックリスト

以下はNeetCode 150ベースで厳選した核心75問のチェックリストです。

#問題難易度パターン頻出企業
1Two Sum (1)EasyArrays/HashingGoogle, Amazon, Meta
2Contains Duplicate (217)EasyArrays/HashingAmazon, Apple
3Valid Anagram (242)EasyArrays/HashingMeta, Microsoft
4Group Anagrams (49)MediumArrays/HashingAmazon, Google
5Top K Frequent Elements (347)MediumArrays/HashingAmazon, Meta
6Valid Palindrome (125)EasyTwo PointersMeta, Microsoft
7Two Sum II (167)MediumTwo PointersAmazon, Google
83Sum (15)MediumTwo PointersMeta, Google, Amazon
9Container With Most Water (11)MediumTwo PointersAmazon, Google
10Trapping Rain Water (42)HardTwo PointersGoogle, Amazon, Meta
11Best Time to Buy and Sell Stock (121)EasySliding WindowAmazon, Meta
12Longest Substring Without Repeating (3)MediumSliding WindowAmazon, Google, Meta
13Longest Repeating Character Replacement (424)MediumSliding WindowGoogle, Microsoft
14Minimum Window Substring (76)HardSliding WindowMeta, Google, Amazon
15Valid Parentheses (20)EasyStackAmazon, Meta
16Min Stack (155)MediumStackAmazon, Google
17Evaluate Reverse Polish Notation (150)MediumStackAmazon, Microsoft
18Daily Temperatures (739)MediumStack (Monotonic)Google, Amazon
19Largest Rectangle in Histogram (84)HardStack (Monotonic)Google, Amazon
20Binary Search (704)EasyBinary SearchGoogle, Microsoft
21Search a 2D Matrix (74)MediumBinary SearchAmazon, Microsoft
22Koko Eating Bananas (875)MediumBinary SearchGoogle, Amazon
23Find Min in Rotated Sorted Array (153)MediumBinary SearchMeta, Amazon
24Search in Rotated Sorted Array (33)MediumBinary SearchMeta, Google, Amazon
25Reverse Linked List (206)EasyLinked ListAmazon, Microsoft
26Merge Two Sorted Lists (21)EasyLinked ListAmazon, Meta
27Linked List Cycle (141)EasyLinked ListAmazon, Microsoft
28Reorder List (143)MediumLinked ListMeta, Amazon
29Merge k Sorted Lists (23)HardLinked List / HeapAmazon, Google
30Invert Binary Tree (226)EasyTreesGoogle, Amazon
31Maximum Depth of Binary Tree (104)EasyTreesAmazon, Meta
32Binary Tree Level Order Traversal (102)MediumTrees (BFS)Amazon, Meta
33Validate Binary Search Tree (98)MediumTrees (DFS)Amazon, Meta
34Binary Tree Maximum Path Sum (124)HardTrees (DFS)Meta, Google
35Lowest Common Ancestor (236)MediumTrees (DFS)Meta, Amazon, Google
36Implement Trie (208)MediumTriesAmazon, Google
37Design Add and Search Words (211)MediumTriesMeta, Amazon
38Word Search II (212)HardTries + BacktrackingAmazon, Google
39Kth Largest Element in Stream (703)EasyHeapAmazon, Meta
40Last Stone Weight (1046)EasyHeapGoogle, Amazon
41K Closest Points to Origin (973)MediumHeapAmazon, Meta
42Task Scheduler (621)MediumHeapMeta, Amazon
43Find Median from Data Stream (295)HardHeapAmazon, Google
44Subsets (78)MediumBacktrackingMeta, Amazon
45Combination Sum (39)MediumBacktrackingAmazon, Google
46Permutations (46)MediumBacktrackingMeta, Amazon
47Word Search (79)MediumBacktrackingAmazon, Meta
48N-Queens (51)HardBacktrackingGoogle, Amazon
49Number of Islands (200)MediumGraphs (DFS)Amazon, Google, Meta
50Clone Graph (133)MediumGraphs (BFS/DFS)Meta, Amazon
51Course Schedule (207)MediumGraphs (Topological)Amazon, Google
52Pacific Atlantic Water Flow (417)MediumGraphs (DFS)Google, Amazon
53Number of Connected Components (323)MediumGraphs (Union-Find)Google, Meta
54Graph Valid Tree (261)MediumGraphs (Union-Find)Google, Meta
55Climbing Stairs (70)EasyDP (1D)Amazon, Google
56House Robber (198)MediumDP (1D)Amazon, Google
57House Robber II (213)MediumDP (1D)Amazon, Google
58Coin Change (322)MediumDP (1D)Amazon, Google, Meta
59Longest Increasing Subsequence (300)MediumDP (1D)Google, Amazon
60Word Break (139)MediumDP (1D)Meta, Amazon, Google
61Unique Paths (62)MediumDP (2D)Amazon, Google
62Longest Common Subsequence (1143)MediumDP (2D)Google, Amazon
63Best Time Buy/Sell Stock Cooldown (309)MediumDP (2D)Amazon, Google
64Target Sum (494)MediumDP (2D)Meta, Google
65Edit Distance (72)MediumDP (2D)Google, Amazon
66Maximum Subarray (53)MediumGreedyAmazon, Google, Meta
67Jump Game (55)MediumGreedyAmazon, Google
68Jump Game II (45)MediumGreedyAmazon, Google
69Gas Station (134)MediumGreedyAmazon, Google
70Hand of Straights (846)MediumGreedyGoogle, Amazon
71Merge Intervals (56)MediumIntervalsGoogle, Meta, Amazon
72Insert Interval (57)MediumIntervalsGoogle, Meta
73Non-overlapping Intervals (435)MediumIntervalsGoogle, Amazon
74Meeting Rooms II (253)MediumIntervalsGoogle, Meta, Amazon
75Rotate Image (48)MediumMath/MatrixAmazon, Microsoft

18. 実践面接のヒント

45分の時間配分

段階時間活動
問題理解5分要件確認、例題レビュー、質問
アプローチ議論10分brute forceに言及後、最適解法を説明
コーディング20分クリーンコードの作成
テスト5分例題実行、エッジケース確認
質疑応答5分計算量分析、最適化の議論

UMPIREメソッド

コーディング面接で体系的に問題を解くためのフレームワークです。

  1. U - Understand：問題を完全に理解します。入出力例を確認し、曖昧な点を質問します。
  2. M - Match：知っているパターンとマッチングします。この15パターンのどれが適切か判断します。
  3. P - Plan：具体的な解法計画を立てます。擬似コードを作成します。
  4. I - Implement：計画に従いきれいにコーディングします。
  5. R - Review：コードを一行ずつレビューしバグを探します。
  6. E - Evaluate：時間/空間計算量を分析し、最適化の可能性を議論します。

エッジケースチェックリスト

面接で見落としやすいエッジケースです。

  • 空入力（空配列、空文字列、null/None）
  • 単一要素の入力
  • すべての要素が同じ場合
  • 負の値が含まれる場合
  • 非常に大きな入力（オーバーフロー確認）
  • ソートされていない入力（ソートを前提としない）
  • 重複要素がある場合

AIコパイロット時代の面接変化

2025年コーディング面接で注目すべき変化です。

  1. システム設計の比重増加：AIがコーディングを代替できるため、アーキテクチャ設計能力がより重要に
  2. コードレビュー能力の評価：与えられたコードのバグ/パフォーマンス問題を見つける問題タイプの増加
  3. 変形問題の増加：既存問題の条件を変え、暗記した解法が通用しないようにする
  4. リアルタイム協業コーディング：面接官とペアプログラミング形式で進行するケースの増加
  5. アルゴリズム＋システム設計の複合問題：アルゴリズム最適化をシステムレベルで議論

19. クイズ

学んだ内容を確認しましょう。

Q1. Two Sum問題でハッシュマップを使うと時間計算量はいくらですか？

正解：O(n)

配列を1回走査しながら、各要素に対してcomplement（target - num）がハッシュマップにあるかをO(1)で確認します。全体の時間計算量はO(n)で、空間計算量もO(n)です。brute forceのO(n^2)に比べて大きな改善です。

Q2. Sliding Windowパターンが適した問題の特徴は何ですか？

正解：連続する部分配列または部分文字列に対する最適値を求める問題

Sliding Windowは配列や文字列で連続する区間（subarray/substring）の最大値、最小値、特定条件を満たす長さ等を求める時に使います。「連続的」条件が核心であり、各要素がウィンドウに1回入り1回出るためO(n)で解決されます。

Q3. 単調スタック（Monotonic Stack）はどのタイプの問題に使われますか？

正解：Next Greater Element / Next Smaller Elementタイプの問題

単調スタックは各要素に対して次により大きい（または小さい）要素を見つける問題に使われます。スタック内の要素が常に増加または減少の順序を維持するよう管理し、O(n)で全要素のNext Greater/Smallerを計算します。Daily TemperaturesやLargest Rectangle in Histogramが代表的な問題です。

Q4. Union-Findで「パス圧縮（Path Compression）」と「ランクベースの結合（Union by Rank）」を両方適用すると、操作時間計算量はどうなりますか？

正解：ほぼO(1) — 正確にはO(alpha(n))

alpha(n)はアッカーマン関数の逆関数で、実質的にすべての入力に対して5以下の値を持ちます。パス圧縮はfind時に親をルートに直接接続し、ランクベースの結合は木の高さが低い方を高い方に結合します。二つの最適化を同時に適用するとほぼ定数時間で動作します。

Q5. UMPIREメソッドの6段階を順番に挙げてください。

正解：Understand、Match、Plan、Implement、Review、Evaluate

  1. Understand：問題を完全に理解し明確化の質問をする
  2. Match：知っているアルゴリズムパターンとマッチングする
  3. Plan：具体的な解法計画と擬似コードを作成する
  4. Implement：計画に従いきれいにコーディングする
  5. Review：コードをレビューしバグを見つける
  6. Evaluate：時間/空間計算量を分析する

20. 参考資料

  1. NeetCode 150ロードマップ — パターン別体系的問題分類
  2. Blind 75問題リスト — 元祖キュレーションリスト
  3. Grind 75 by Yangshun — カスタムスケジューリング
  4. LeetCode — オンラインコーディング問題プラットフォーム
  5. Introduction to Algorithms (CLRS) — アルゴリズムのバイブル
  6. Grokking the Coding Interview — パターンベースの学習
  7. Tech Interview Handbook — 面接全般ガイド
  8. Competitive Programmer's Handbook (Antti Laaksonen) — 無料アルゴリズム教材
  9. VisuAlgo — アルゴリズム可視化ツール
  10. Big-O Cheat Sheet — 時間/空間計算量まとめ
  11. Python collections公式ドキュメント — Counter、deque、defaultdict
  12. Python heapq公式ドキュメント — ヒープ操作
  13. Back to Back SWE (YouTube) — アルゴリズム解説
  14. Abdul Bari Algorithms (YouTube) — アルゴリズム講義
  15. System Design Interview by Alex Xu — システム設計面接ガイド
  16. プログラミングコンテストチャレンジブック — 日本語アルゴリズム競技プログラミング教材
Discuss on Twitter • View on GitHub