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 完全ガイド
最小ヒープ (デフォルト)
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) 平均
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. 練習問題クイズ
**答え**: 同じ再帰レベル (深さ) でのみ重複をスキップする必要があるからです。
**解説**: 「i > 0」という条件にすると、親の呼び出しで使用した要素を子ノードでもスキップしてしまい、有効な組み合わせが失われます。「i > start」は現在の再帰呼び出しの開始インデックス以降でのみ重複をスキップするため、同じレベルで同じ値が 2 回選ばれる場合のみを除去します。
**答え**: 中央値を O(1) で取得し、挿入を O(log n) で処理するためです。
**解説**: ソートされた配列を維持すると挿入が O(n)、ソートのみでは取得が O(n) になります。2 つのバランスの取れたヒープ (下半分の最大ヒープ + 上半分の最小ヒープ) を維持すると、中央値は 2 つのヒープのトップを見るだけなので O(1)、挿入はヒープ操作なので O(log n) になります。
**答え**: ループ終了後にスタックに残っている要素をすべて処理するためです。
**解説**: 末尾に 0 を追加すると、すべての前の高さより小さいため、スタックのすべての要素がポップされます。これにより、ループ後に別途処理するコードを書かずにスタックを空にできます。ループ後に後処理ループを書いても同じ効果が得られます。
**答え**: XOR の 2 つの核心的な性質: a XOR a = 0 (同じ数を 2 回 XOR すると 0)、a XOR 0 = a (0 と XOR すると自分自身)
**解説**: 配列で 2 回現れる数字をすべて XOR すると 0 になります。1 回だけ現れる数字を XOR すると、その数字が残ります。XOR は交換法則と結合法則が成り立つため、順序に関係なく同じ結果が得られます。
**答え**: 複数の単語を同時に探索し、共通のプレフィックスを共有することで効率を高めるためです。
**解説**: 各単語を個別に 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) |
**面接準備ロードマップ**:
1. バックトラッキング: Subsets → Permutations → Combination Sum → N-Queens
2. ヒープ: Kth Largest → Top K → Merge K Lists → Median Finder
3. 単調スタック: Daily Temperatures → Largest Rectangle
4. トライ: Implement Trie → Word Search II
5. ビット操作: Single Number → Counting Bits → Power of Two
현재 단락 (1/500)
このガイドでは FAANG 面接で頻繁に出題されるバックトラッキング、ヒープ / 優先度キュー、単調スタック、トライ、ビット操作のパターンを解説します。