FAANG コーディング面接完全攻略: バックトラッキング、ヒープ、高度なパターン

このガイドでは FAANG 面接で頻繁に出題されるバックトラッキング、ヒープ / 優先度キュー、単調スタック、トライ、ビット操作のパターンを解説します。

1. バックトラッキングのパターン

バックトラッキングのコアテンプレート

バックトラッキングは決定木を探索して、制約を満たすすべての解を見つける手法です。

def backtrack(state, choices):
    # 基底ケース: 有効な解が見つかったら結果に追加
    if is_solution(state):
        result.append(state[:])  # コピーを保存 (参照ではなく)
        return

    for choice in choices:
        # 選択 (Choose)
        make_choice(state, choice)

        # 探索 (Explore) - 再帰
        backtrack(state, remaining_choices)

        # 元に戻す (Unchoose) - これが重要！
        undo_choice(state, choice)

核心原則:

状態のコピーを結果に保存する (参照ではなく値)
再帰呼び出しの前後で状態が同一でなければならない
枝刈り (Pruning) で不要な探索を早期に除去する

Subsets (LeetCode 78)

def subsets(nums: list) -> list:
    result = []

    def backtrack(start, current):
        result.append(current[:])  # 現在の部分集合を保存
        for i in range(start, len(nums)):
            current.append(nums[i])    # 選択
            backtrack(i + 1, current)  # 探索
            current.pop()              # 元に戻す

    backtrack(0, [])
    return result

時間計算量: O(n * 2^n)
空間計算量: O(n) (再帰スタック)

Subsets II — 重複処理 (LeetCode 90)

def subsetsWithDup(nums: list) -> list:
    nums.sort()  # 重複処理のためにソート
    result = []

    def backtrack(start, current):
        result.append(current[:])
        for i in range(start, len(nums)):
            # 同じ再帰レベルで重複をスキップ
            if i > start and nums[i] == nums[i-1]:
                continue
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()

    backtrack(0, [])
    return result

Permutations (LeetCode 46)

def permute(nums: list) -> list:
    result = []

    def backtrack(current, remaining):
        if not remaining:
            result.append(current[:])
            return
        for i in range(len(remaining)):
            current.append(remaining[i])
            backtrack(current, remaining[:i] + remaining[i+1:])
            current.pop()

    backtrack([], nums)
    return result

# 訪問配列を使う方法 (より効率的)
def permute_v2(nums: list) -> list:
    result = []
    visited = [False] * len(nums)

    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return
        for i in range(len(nums)):
            if visited[i]:
                continue
            visited[i] = True
            current.append(nums[i])
            backtrack(current)
            current.pop()
            visited[i] = False

    backtrack([])
    return result

Permutations II — 重複処理 (LeetCode 47)

def permuteUnique(nums: list) -> list:
    nums.sort()
    result = []
    visited = [False] * len(nums)

    def backtrack(current):
        if len(current) == len(nums):
            result.append(current[:])
            return
        for i in range(len(nums)):
            if visited[i]:
                continue
            # 同じ値の前の要素がまだ未訪問ならスキップ
            if i > 0 and nums[i] == nums[i-1] and not visited[i-1]:
                continue
            visited[i] = True
            current.append(nums[i])
            backtrack(current)
            current.pop()
            visited[i] = False

    backtrack([])
    return result

Combination Sum (LeetCode 39)

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

    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        if remaining < 0:
            return
        for i in range(start, len(candidates)):
            current.append(candidates[i])
            backtrack(i, current, remaining - candidates[i])  # 同じ要素を再利用可能
            current.pop()

    backtrack(0, [], target)
    return result

Combination Sum II (LeetCode 40)

def combinationSum2(candidates: list, target: int) -> list:
    candidates.sort()
    result = []

    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            if i > start and candidates[i] == candidates[i-1]:
                continue
            current.append(candidates[i])
            backtrack(i + 1, current, remaining - candidates[i])
            current.pop()

    backtrack(0, [], target)
    return result

N-Queens (LeetCode 51)

def solveNQueens(n: int) -> list:
    result = []
    cols = set()
    diag1 = set()  # row - col (右下がり対角線)
    diag2 = set()  # row + col (左下がり対角線)

    def backtrack(row, board):
        if row == n:
            result.append([''.join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            board[row][col] = 'Q'
            backtrack(row + 1, board)
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
            board[row][col] = '.'

    board = [['.' for _ in range(n)] for _ in range(n)]
    backtrack(0, board)
    return result

Word Search (LeetCode 79)

def exist(board: list, word: str) -> bool:
    rows, cols = len(board), len(board[0])

    def backtrack(r, c, idx):
        if idx == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if board[r][c] != word[idx]:
            return False

        temp = board[r][c]
        board[r][c] = '#'  # 訪問済みマーク

        found = (
            backtrack(r+1, c, idx+1) or
            backtrack(r-1, c, idx+1) or
            backtrack(r, c+1, idx+1) or
            backtrack(r, c-1, idx+1)
        )

        board[r][c] = temp  # 復元
        return found

    for r in range(rows):
        for c in range(cols):
            if backtrack(r, c, 0):
                return True
    return False

2. ヒープ / 優先度キューのパターン

Python heapq 完全ガイド

import heapq

# 最小ヒープ (デフォルト)
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 2)
print(heapq.heappop(min_heap))  # 1 (最小値)

# 最大ヒープ (値を負数に変換)
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -2)
print(-heapq.heappop(max_heap))  # 3 (最大値)

# リストからヒープを構築
nums = [3, 1, 4, 1, 5, 9]
heapq.heapify(nums)  # O(n)

# n 番目の大きい/小さい値
heapq.nlargest(3, nums)   # 上位 3 つ
heapq.nsmallest(3, nums)  # 下位 3 つ

# タプルヒープ: (優先度, 値)
heap = [(1, 'task_a'), (3, 'task_b'), (2, 'task_c')]
heapq.heapify(heap)
priority, task = heapq.heappop(heap)  # (1, 'task_a')

Kth Largest Element (LeetCode 215)

def findKthLargest(nums: list, k: int) -> int:
    # サイズ k の最小ヒープを維持
    min_heap = []
    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)
    return min_heap[0]  # k 番目に大きい値

# QuickSelect O(n) 平均
import random

def findKthLargest_quickselect(nums: list, k: int) -> int:
    def quickselect(left, right, k_smallest):
        pivot = nums[random.randint(left, right)]
        lo, hi, mid = left, right, left
        while mid <= hi:
            if nums[mid] < pivot:
                nums[lo], nums[mid] = nums[mid], nums[lo]
                lo += 1
                mid += 1
            elif nums[mid] > pivot:
                nums[hi], nums[mid] = nums[mid], nums[hi]
                hi -= 1
            else:
                mid += 1
        if k_smallest < lo:
            return quickselect(left, lo - 1, k_smallest)
        elif k_smallest >= mid:
            return quickselect(mid, right, k_smallest)
        else:
            return nums[lo]

    return quickselect(0, len(nums) - 1, len(nums) - k)

Top K Frequent Elements (LeetCode 347)

from collections import Counter

def topKFrequent(nums: list, k: int) -> list:
    count = Counter(nums)
    # (頻度, 値) のペアで最小ヒープを維持
    heap = []
    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [num for freq, num in heap]

# バケットソート O(n)
def topKFrequent_bucket(nums: list, k: int) -> list:
    count = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)
    result = []
    for i in range(len(buckets) - 1, -1, -1):
        result.extend(buckets[i])
        if len(result) >= k:
            return result[:k]
    return result

Merge K Sorted Lists (LeetCode 23)

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

def mergeKLists(lists: list) -> ListNode:
    heap = []
    # 各リストの最初のノードをヒープに追加
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = ListNode(0)
    curr = dummy

    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

時間計算量: O(N log k)、N = 総ノード数、k = リスト数

Find Median from Data Stream (LeetCode 295)

2 つのヒープを使うパターンは面接の重要なテクニックです。

class MedianFinder:
    def __init__(self):
        self.small = []  # 最大ヒープ (下半分、負数で格納)
        self.large = []  # 最小ヒープ (上半分)

    def addNum(self, num: int) -> None:
        # small ヒープに追加後、バランス調整
        heapq.heappush(self.small, -num)
        # small の最大値 > large の最小値なら移動
        if self.small and self.large and (-self.small[0] > self.large[0]):
            heapq.heappush(self.large, -heapq.heappop(self.small))
        # サイズバランス調整
        if len(self.small) > len(self.large) + 1:
            heapq.heappush(self.large, -heapq.heappop(self.small))
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

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

Task Scheduler (LeetCode 621)

from collections import Counter

def leastInterval(tasks: list, n: int) -> int:
    count = Counter(tasks)
    max_heap = [-c for c in count.values()]
    heapq.heapify(max_heap)

    time = 0
    queue = []  # (count, available_time)

    while max_heap or queue:
        time += 1
        if max_heap:
            cnt = 1 + heapq.heappop(max_heap)
            if cnt:
                queue.append((cnt, time + n))
        if queue and queue[0][1] == time:
            heapq.heappush(max_heap, queue.pop(0)[0])

    return time

3. 単調スタックのパターン

単調スタックの概念

単調スタックはスタック内の要素が単調増加または単調減少を維持するスタックです。

単調増加スタック: より小さいか等しい要素が来るとポップ (次に小さい要素の問題)
単調減少スタック: より大きいか等しい要素が来るとポップ (次に大きい要素の問題)

Daily Temperatures (LeetCode 739)

def dailyTemperatures(temperatures: list) -> list:
    n = len(temperatures)
    result = [0] * n
    stack = []  # インデックスを格納

    for i, temp in enumerate(temperatures):
        # 現在の気温がスタックのトップより高ければポップ
        while stack and temperatures[stack[-1]] < temp:
            idx = stack.pop()
            result[idx] = i - idx
        stack.append(i)

    return result

Next Greater Element (LeetCode 496)

def nextGreaterElement(nums1: list, nums2: list) -> list:
    next_greater = {}
    stack = []

    for num in nums2:
        while stack and stack[-1] < num:
            next_greater[stack.pop()] = num
        stack.append(num)

    # スタックに残った要素は次に大きい要素がない
    while stack:
        next_greater[stack.pop()] = -1

    return [next_greater[n] for n in nums1]

Largest Rectangle in Histogram (LeetCode 84)

def largestRectangleArea(heights: list) -> int:
    stack = []  # 単調増加スタック (インデックス)
    max_area = 0
    heights = heights + [0]  # スタックを空にするためのセンチネル

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    return max_area

Trapping Rain Water — スタック方式 (LeetCode 42)

def trap(height: list) -> int:
    stack = []  # 単調減少スタック
    water = 0

    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()
            if not stack:
                break
            bounded_height = min(height[stack[-1]], h) - height[bottom]
            width = i - stack[-1] - 1
            water += bounded_height * width
        stack.append(i)

    return water

4. トライ (Prefix Tree) のパターン

トライの実装

class TrieNode:
    def __init__(self):
        self.children = {}  # または [None] * 26 (小文字アルファベット用)
        self.is_end = False

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

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

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

Design Add and Search Words (LeetCode 211)

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

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

    def search(self, word: str) -> bool:
        def dfs(node, i):
            if i == len(word):
                return node.is_end
            char = word[i]
            if char == '.':
                # ワイルドカード: すべての子を探索
                for child in node.children.values():
                    if dfs(child, i + 1):
                        return True
                return False
            if char not in node.children:
                return False
            return dfs(node.children[char], i + 1)

        return dfs(self.root, 0)

Word Search II (LeetCode 212)

def findWords(board: list, words: list) -> list:
    # 単語リストからトライを構築
    root = TrieNode()
    for word in words:
        node = root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    rows, cols = len(board), len(board[0])
    result = set()

    def dfs(r, c, node, path):
        if node.is_end:
            result.add(path)
            # より長い単語のために探索を継続

        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        char = board[r][c]
        if char not in node.children or char == '#':
            return

        board[r][c] = '#'  # 訪問済みマーク
        for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
            dfs(r+dr, c+dc, node.children[char], path+char)
        board[r][c] = char  # 復元

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root, '')

    return list(result)

5. ビット操作のパターン

XOR トリックとビット演算の基礎

# 基本ビット演算
a = 0b1010  # 10
b = 0b1100  # 12

print(a & b)    # AND: 0b1000 = 8
print(a | b)    # OR:  0b1110 = 14
print(a ^ b)    # XOR: 0b0110 = 6
print(~a)       # NOT: -11 (2の補数)
print(a << 1)   # 左シフト: 0b10100 = 20
print(a >> 1)   # 右シフト: 0b0101 = 5

# 便利なビット操作トリック
n = 12
print(n & (n-1))    # 最下位ビットを除去: 8
print(n & (-n))     # 最下位セットビットのみ残す: 4
print(n ^ n)        # 自分自身と XOR = 0
print(0 ^ n)        # 0 と XOR = n

Single Number (LeetCode 136)

def singleNumber(nums: list) -> int:
    # すべての数を XOR: 偶数回現れる数はキャンセルされる
    result = 0
    for num in nums:
        result ^= num
    return result

Counting Bits (LeetCode 338)

def countBits(n: int) -> list:
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        # i の 1 ビット数 = (i >> 1) の 1 ビット数 + 最下位ビット
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

Reverse Bits (LeetCode 190)

def reverseBits(n: int) -> int:
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

Number of 1 Bits — ハミング重み (LeetCode 191)

def hammingWeight(n: int) -> int:
    count = 0
    while n:
        n &= (n - 1)  # 最下位の 1 ビットを除去
        count += 1
    return count

# Python 組み込み関数
def hammingWeight_v2(n: int) -> int:
    return bin(n).count('1')

6. 面接の実践戦略

詰まったときのヒントの求め方

黙ってしまうことが最も悪い対応です。以下のように会話しましょう。

「現在このアプローチで [具体的な問題] が発生しています。
何か見落としていることはあるでしょうか？」

「[特定のデータ構造/アルゴリズム] を使おうと考えていますが、
正しい方向に進んでいますか？」

隠れたルール: 面接官がヒントを出したとき、それをどう活用するかも評価されます。

コードの最適化についての話し方

最適化を求められたとき:

「現在のソリューションは O(n^2) の時間計算量と O(n) の空間計算量を使っています。
[特定のデータ構造/アルゴリズム] を使えば O(n log n) に改善できると思います。
実装してみてもよいでしょうか？」

時間/空間計算量の説明方法

常に根拠とともに説明しましょう。

「時間計算量は O(n log n) です。
外側のループが n 回実行され、各反復でヒープ操作が O(log n) かかるためです。

空間計算量は O(k) です。
サイズ k のヒープを維持するためです。」

面接進行フレームワーク

1. 問題理解 (5 分)
   - 自分で例を作って確認
   - エッジケースを質問

2. アプローチの説明 (5 分)
   - まずブルートフォースを説明
   - 最適化の方向を述べる

3. コーディング (15-20 分)
   - 話しながらコーディング
   - 意味のある変数名を使う

4. テスト (5 分)
   - 自分で作った例でトレース
   - エッジケースを確認

7. 練習問題クイズ

クイズ 1: Subsets II で重複を除去するために「i > start」という条件が必要な理由は？

答え: 同じ再帰レベル (深さ) でのみ重複をスキップする必要があるからです。

解説: 「i > 0」という条件にすると、親の呼び出しで使用した要素を子ノードでもスキップしてしまい、有効な組み合わせが失われます。「i > start」は現在の再帰呼び出しの開始インデックス以降でのみ重複をスキップするため、同じレベルで同じ値が 2 回選ばれる場合のみを除去します。

クイズ 2: Find Median from Data Stream で 2 つのヒープを使う理由は？

答え: 中央値を O(1) で取得し、挿入を O(log n) で処理するためです。

解説: ソートされた配列を維持すると挿入が O(n)、ソートのみでは取得が O(n) になります。2 つのバランスの取れたヒープ (下半分の最大ヒープ + 上半分の最小ヒープ) を維持すると、中央値は 2 つのヒープのトップを見るだけなので O(1)、挿入はヒープ操作なので O(log n) になります。

クイズ 3: Largest Rectangle in Histogram で heights 配列の末尾に 0 を追加する理由は？

答え: ループ終了後にスタックに残っている要素をすべて処理するためです。

解説: 末尾に 0 を追加すると、すべての前の高さより小さいため、スタックのすべての要素がポップされます。これにより、ループ後に別途処理するコードを書かずにスタックを空にできます。ループ後に後処理ループを書いても同じ効果が得られます。

クイズ 4: Single Number で XOR を使う数学的な原理は何ですか？

答え: XOR の 2 つの核心的な性質: a XOR a = 0 (同じ数を 2 回 XOR すると 0)、a XOR 0 = a (0 と XOR すると自分自身)

解説: 配列で 2 回現れる数字をすべて XOR すると 0 になります。1 回だけ現れる数字を XOR すると、その数字が残ります。XOR は交換法則と結合法則が成り立つため、順序に関係なく同じ結果が得られます。

クイズ 5: Word Search II でトライを使う理由は何ですか？

答え: 複数の単語を同時に探索し、共通のプレフィックスを共有することで効率を高めるためです。

解説: 各単語を個別に DFS で探索すると O(words _ cells _ 4^L)（L は単語長）の計算量になります。トライを使うと共通プレフィックスを持つ単語の探索を共有でき、現在のパスがどの単語のプレフィックスにもならない場合に即座に枝刈りができます。

まとめ

計算量の参考表:

パターン	時間	空間
バックトラッキング Subsets	O(n * 2^n)	O(n)
バックトラッキング Permutations	O(n * n!)	O(n)
ヒープ — k 番目の要素	O(n log k)	O(k)
Merge K Lists	O(N log k)	O(k)
単調スタック	O(n)	O(n)
トライ Insert/Search	O(L)	O(ALPHABET _ N _ L)
ビット XOR トリック	O(n)	O(1)

面接準備ロードマップ:

バックトラッキング: Subsets → Permutations → Combination Sum → N-Queens
ヒープ: Kth Largest → Top K → Merge K Lists → Median Finder
単調スタック: Daily Temperatures → Largest Rectangle
トライ: Implement Trie → Word Search II
ビット操作: Single Number → Counting Bits → Power of Two