LabHub

ブログ

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

2026-03-23 · 42 分で読めます · #algorithm#coding-test#interview#leetcode#data-structure#faang#blind-75#neetcode#2026-03

한국어English日本語

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を基本とします。

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)に削減することが核心です。頻度カウント、重複検出、グルーピング問題に必須で使われます。

時間/空間計算量

代表問題

  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)で検索

変形問題とヒント

3. Pattern 2 — Two Pointers

核心アイデア

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

時間/空間計算量

代表問題

  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)
# 核心：低い壁を移動することで面積が増加する可能性がある

変形問題とヒント

4. Pattern 3 — Sliding Window

核心アイデア

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

時間/空間計算量

代表問題

  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))
# 核心：ハッシュマップで重複位置を追跡しウィンドウサイズを更新

変形問題とヒント

5. Pattern 4 — Stack（Monotonic Stack）

核心アイデア

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

時間/空間計算量

代表問題

  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)で計算

変形問題とヒント

6. Pattern 5 — Binary Search

核心アイデア

ソート済みデータで探索範囲を半分ずつ縮小して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)
# 核心：「最小速度」を二分探索で求める決定問題パターン

変形問題とヒント

7. Pattern 6 — Linked List

核心アイデア

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

時間/空間計算量

代表問題

  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）でその場で逆転

変形問題とヒント

8. Pattern 7 — Trees（BFS/DFS）

核心アイデア

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

時間/空間計算量

代表問題

  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でレベルサイズ分ずつ処理しレベル別にグループ化

変形問題とヒント

9. Pattern 8 — Tries

核心アイデア

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

時間/空間計算量

代表問題

  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(総文字数)
# 核心：各ノードが子ディクショナリと終了フラグを保持

変形問題とヒント

10. Pattern 9 — Heap / Priority Queue

核心アイデア

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

時間/空間計算量

代表問題

  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)
# 核心：二つのヒープでデータを半分に分けて中央値を効率的に維持

変形問題とヒント

11. Pattern 10 — Backtracking

核心アイデア

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

時間/空間計算量

代表問題

  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)
# 核心：選択 -> 再帰 -> 取消パターンと枝刈り

変形問題とヒント

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

核心アイデア

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

時間/空間計算量

代表問題

  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

変形問題とヒント

13. Pattern 12 — Dynamic Programming（1D）

核心アイデア

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

時間/空間計算量

代表問題

  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)
# 核心：各金額に対して全コインを試し、最小値を更新

変形問題とヒント

14. Pattern 13 — Dynamic Programming（2D）

核心アイデア

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

時間/空間計算量

代表問題

  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、異なれば上/左の最大値

変形問題とヒント

15. Pattern 14 — Greedy

核心アイデア

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

時間/空間計算量

代表問題

  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に判断

変形問題とヒント

16. Pattern 15 — Intervals and Math

核心アイデア

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

時間/空間計算量

代表問題

  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)
# 核心：ソート後、重なる区間を順次統合

変形問題とヒント

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：時間/空間計算量を分析し、最適化の可能性を議論します。

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

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

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. プログラミングコンテストチャレンジブック — 日本語アルゴリズム競技プログラミング教材

コメント

まだコメントはありません。

ログインするとコメントできます