FAAANGコーディング面接完全攻略：配列と文字列の核心パターン
FAANG（Facebook/Meta、Apple、Amazon、Netflix、Google）のコーディング面接では、配列と文字列の問題が全出題の40%以上を占めます。本記事では面接で頻出の6つの核心パターンを、動作するPythonコードと詳細な分析を交えて完全解説します。
1. Two Pointers パターン
概念と使用タイミング
Two Pointersパターンは、ソートされた配列や連結リストで2つのポインタを使い、線形時間で問題を解くテクニックです。
**使用条件:**
- ソートされた配列で2要素の和・差を求める場合
- 配列の両端から条件を満たすペアを探す場合
- 重複除去やパーティショニングが必要な場合
**核心アイデア:** O(n^2)のブルートフォースをO(n)に削減できます。
問題 1: Two Sum II (LeetCode 167)
ソートされた配列で、合計がtargetになる2つの数のインデックスを見つけよ。
def twoSum(numbers: list[int], target: int) -> list[int]:
left, right = 0, len(numbers) - 1
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [left + 1, right + 1] # 1-indexed
elif current_sum < target:
left += 1
else:
right -= 1
return []
例
入力: numbers = [2,7,11,15], target = 9
出力: [1,2]
**時間計算量:** O(n) — 各ポインタは最大n回移動
**空間計算量:** O(1) — 追加スペース不要
**FAAANGのヒント:** ソートされていない配列ならHashMapを使ったO(n)解法を先に提示し、ソート済み配列ではTwo Pointersが空間効率的であることを説明しましょう。
問題 2: 3Sum (LeetCode 15)
配列で合計が0になる3要素の組み合わせをすべて見つけよ（重複なし）。
def threeSum(nums: list[int]) -> list[list[int]]:
nums.sort()
result = []
for i in range(len(nums) - 2):
重複をスキップ
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
重複をスキップ
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return result
例
入力: nums = [-1, 0, 1, 2, -1, -4]
出力: [[-1, -1, 2], [-1, 0, 1]]
**時間計算量:** O(n^2) — ソートO(n log n) + 二重ループO(n^2)
**空間計算量:** O(1) 〜 O(n)（ソートアルゴリズムによる）
**FAAANGのヒント:** Metaの面接で頻出です。重複処理のロジックを忘れないように注意しましょう。
問題 3: 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
current_water = width * min(height[left], height[right])
max_water = max(max_water, current_water)
より低い側のポインタを移動（より高い壁を探す）
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_water
例
入力: height = [1,8,6,2,5,4,8,3,7]
出力: 49
**時間計算量:** O(n)
**空間計算量:** O(1)
**なぜこの方法が最適か?** より高い壁側を移動すると、幅は減り高さも減る（または同じ）ため、絶対に水量は増えません。
問題 4: Trapping Rain Water (LeetCode 42)
高難度問題。バーの間に溜まる雨水の総量を求めよ。
def trap(height: list[int]) -> int:
if not height:
return 0
left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
water = 0
while left < right:
if left_max <= right_max:
left += 1
left_max = max(left_max, height[left])
現在位置で溜まる水 = 左側最大 - 現在高さ
water += left_max - height[left]
else:
right -= 1
right_max = max(right_max, height[right])
water += right_max - height[right]
return water
例
入力: height = [0,1,0,2,1,0,1,3,2,1,2,1]
出力: 6
**時間計算量:** O(n)
**空間計算量:** O(1) — プレフィックス最大配列不要
**FAAANGのヒント:** GoogleとAmazonの定番問題です。DP解法（O(n)スペース）も知っておき、Two Pointersがなぜより効率的かを説明できるようにしましょう。
2. Sliding Window パターン
概念
連続した部分配列/文字列で最適解を見つけるパターンです。ウィンドウをスライドさせながら全体を1回だけ走査します。
**Fixed Window:** ウィンドウサイズが固定
**Variable Window:** 条件によってウィンドウサイズが変化
問題 5: 最長の重複文字なし部分文字列 (LeetCode 3)
def lengthOfLongestSubstring(s: str) -> int:
char_set = set()
left = 0
max_length = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_length = max(max_length, right - left + 1)
return max_length
HashMapを使った最適化版
def lengthOfLongestSubstringOptimized(s: str) -> int:
char_index = {}
left = 0
max_length = 0
for right, char in enumerate(s):
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1
char_index[char] = right
max_length = max(max_length, right - left + 1)
return max_length
例
入力: "abcabcbb"
出力: 3 ("abc")
**時間計算量:** O(n)
**空間計算量:** O(min(n, 文字セットサイズ))
問題 6: 最小ウィンドウ部分文字列 (LeetCode 76)
文字列sの中でtの全文字を含む最小ウィンドウを見つけよ。
from collections import Counter
def minWindow(s: str, t: str) -> str:
if not t or not s:
return ""
need = Counter(t)
missing = len(t) # まだ含まれていない文字数
best_start = 0
best_end = float('inf')
left = 0
for right, char in enumerate(s):
if need[char] > 0:
missing -= 1
need[char] -= 1
if missing == 0:
左から不要な文字を取り除く
while need[s[left]] < 0:
need[s[left]] += 1
left += 1
if right - left < best_end - best_start:
best_start = left
best_end = right
ウィンドウを縮小
need[s[left]] += 1
missing += 1
left += 1
if best_end == float('inf'):
return ""
return s[best_start:best_end + 1]
例
入力: s = "ADOBECODEBANC", t = "ABC"
出力: "BANC"
**時間計算量:** O(|s| + |t|)
**空間計算量:** O(|s| + |t|)
問題 7: スライディングウィンドウの最大値 (LeetCode 239)
サイズkのスライディングウィンドウの各位置での最大値を返せ。
from collections import deque
def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
dq = deque() # 値の降順でインデックスを保持
result = []
for i, num in enumerate(nums):
ウィンドウ外に出たインデックスを削除
if dq and dq[0] < i - k + 1:
dq.popleft()
現在の値より小さい要素は不要なので削除
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
ウィンドウが完成したら結果を追加
if i >= k - 1:
result.append(nums[dq[0]])
return result
例
入力: nums = [1,3,-1,-3,5,3,6,7], k = 3
出力: [3,3,5,5,6,7]
**時間計算量:** O(n) — 各要素はdequeへの追加・削除が最大1回
**空間計算量:** O(k)
問題 8: バスケットに入れるフルーツ (LeetCode 904)
最大2種類のフルーツしか入れられないバスケットで連続して収穫できる最大数を求めよ。
from collections import defaultdict
def totalFruit(fruits: list[int]) -> int:
basket = defaultdict(int)
left = 0
max_fruits = 0
for right, fruit in enumerate(fruits):
basket[fruit] += 1
3種類以上になったら左ポインタを移動
while len(basket) > 2:
basket[fruits[left]] -= 1
if basket[fruits[left]] == 0:
del basket[fruits[left]]
left += 1
max_fruits = max(max_fruits, right - left + 1)
return max_fruits
例
入力: fruits = [1,2,1,2,3]
出力: 4 ([1,2,1,2])
**時間計算量:** O(n)
**空間計算量:** O(1) — 最大3種類のフルーツのみ保存
3. Binary Search パターン
概念
ソートされた配列でO(log n)時間で要素を探索します。標準形だけでなく様々な変形がFAANG面接に登場します。
**標準 Binary Search テンプレート:**
def binarySearch(nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2 # オーバーフロー防止
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
問題 9: 回転ソート配列の検索 (LeetCode 33)
def search(nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
左半分がソートされている場合
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
右半分がソートされている場合
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
例
入力: nums = [4,5,6,7,0,1,2], target = 0
出力: 4
**時間計算量:** O(log n)
**空間計算量:** O(1)
問題 10: 回転ソート配列の最小値 (LeetCode 153)
def findMin(nums: list[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] > nums[right]:
left = mid + 1 # 最小値は右半分にある
else:
right = mid # midが最小値の可能性あり
return nums[left]
例
入力: nums = [3,4,5,1,2]
出力: 1
**時間計算量:** O(log n)
**空間計算量:** O(1)
問題 11: 2つのソート済み配列の中央値 (LeetCode 4) — 上級
def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
nums1が短い配列になるよう保証
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
half_len = (m + n + 1) // 2
left, right = 0, m
while left <= right:
i = (left + right) // 2 # nums1のパーティション
j = half_len - i # nums2のパーティション
if i < m and nums1[i] < nums2[j - 1]:
left = i + 1
elif i > 0 and nums1[i - 1] > nums2[j]:
right = i - 1
else:
if i == 0:
max_left = nums2[j - 1]
elif j == 0:
max_left = nums1[i - 1]
else:
max_left = max(nums1[i - 1], nums2[j - 1])
if (m + n) % 2 == 1:
return float(max_left)
if i == m:
min_right = nums2[j]
elif j == n:
min_right = nums1[i]
else:
min_right = min(nums1[i], nums2[j])
return (max_left + min_right) / 2.0
例
入力: nums1 = [1,3], nums2 = [2]
出力: 2.0
**時間計算量:** O(log(min(m, n)))
**空間計算量:** O(1)
問題 12: 2D行列の検索 (LeetCode 74)
def searchMatrix(matrix: list[list[int]], target: int) -> bool:
if not matrix or not matrix[0]:
return False
rows, cols = len(matrix), len(matrix[0])
left, right = 0, rows * cols - 1
while left <= right:
mid = left + (right - left) // 2
1Dインデックスを2D座標に変換
mid_val = matrix[mid // cols][mid % cols]
if mid_val == target:
return True
elif mid_val < target:
left = mid + 1
else:
right = mid - 1
return False
例
入力: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
出力: True
**時間計算量:** O(log(m\*n))
**空間計算量:** O(1)
4. Prefix Sum と HashMap パターン
概念
Prefix Sumは累積和を事前計算して区間和クエリをO(1)で処理します。HashMapと組み合わせると、特定条件を満たす区間を効率的に見つけられます。
問題 13: 合計がKの部分配列 (LeetCode 560)
合計がkの連続部分配列の数を求めよ。
from collections import defaultdict
def subarraySum(nums: list[int], k: int) -> int:
prefix_sum_count = defaultdict(int)
prefix_sum_count[0] = 1 # 空の配列のprefix sum = 0
current_sum = 0
count = 0
for num in nums:
current_sum += num
(current_sum - k)が以前に現れた回数を加算
count += prefix_sum_count[current_sum - k]
prefix_sum_count[current_sum] += 1
return count
例
入力: nums = [1,1,1], k = 2
出力: 2
**時間計算量:** O(n)
**空間計算量:** O(n)
問題 14: 最長連続数列 (LeetCode 128)
ソートされていない配列で最長の連続数列の長さをO(n)で求めよ。
def longestConsecutive(nums: list[int]) -> int:
num_set = set(nums)
max_length = 0
for num in num_set:
数列の開始点のみ処理（num-1が存在しない場合）
if num - 1 not in num_set:
current = num
length = 1
while current + 1 in num_set:
current += 1
length += 1
max_length = max(max_length, length)
return max_length
例
入力: nums = [100,4,200,1,3,2]
出力: 4 ([1,2,3,4])
**時間計算量:** O(n) — 各要素は最大2回アクセス
**空間計算量:** O(n)
問題 15: アナグラムのグループ化 (LeetCode 49)
文字列の配列をアナグラムごとにグループ化せよ。
from collections import defaultdict
def groupAnagrams(strs: list[str]) -> list[list[str]]:
anagram_map = defaultdict(list)
for s in strs:
key = tuple(sorted(s))
anagram_map[key].append(s)
return list(anagram_map.values())
文字カウントをキーとする最適化版
def groupAnagramsOptimized(strs: list[str]) -> list[list[str]]:
anagram_map = defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
anagram_map[tuple(count)].append(s)
return list(anagram_map.values())
例
入力: strs = ["eat","tea","tan","ate","nat","bat"]
出力: [["bat"],["nat","tan"],["ate","eat","tea"]]
**時間計算量:** O(n _ k) — nは文字列数、kは最大文字列長
**空間計算量:** O(n _ k)
問題 16: 頻度上位K要素 (LeetCode 347)
from collections import Counter
def topKFrequent(nums: list[int], k: int) -> list[int]:
方法1: ヒープ O(n log k)
count = Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)
def topKFrequentBucketSort(nums: list[int], k: int) -> list[int]:
方法2: バケットソート O(n)
count = Counter(nums)
bucket = [[] for _ in range(len(nums) + 1)]
for num, freq in count.items():
bucket[freq].append(num)
result = []
for freq in range(len(bucket) - 1, 0, -1):
for num in bucket[freq]:
result.append(num)
if len(result) == k:
return result
return result
例
入力: nums = [1,1,1,2,2,3], k = 2
出力: [1,2]
**時間計算量:** O(n) (バケットソート使用時)
**空間計算量:** O(n)
5. 企業別の出題傾向
Googleの面接は**配列と文字列操作**に重点を置いています。
- 頻出: Two Sumの変形、文字列パーシング、2D配列探索
- 重視スキル: エッジケース処理、コードの明確性
- 例題: K種類以下の文字を持つ最長部分文字列、バルーンを割る矢の最小数
Meta（Facebook）
Metaは**Sliding WindowとTwo Pointer**パターンを好みます。
- 頻出: 3Sum、Valid Palindrome II、Move Zeroes
- 重視スキル: 最適化理由の説明、コードの簡潔さ
- 例題: 積がK未満の部分配列、文字列の順列
Amazon
Amazonは**Hash TableとSorting**ベースの問題を好みます。
- 頻出: Two Sum、Group Anagrams、Top K Frequent
- 重視スキル: 実用的な解決策、リーダーシッププリンシパルとの関連付け
- 例題: K個の最近傍点、色の分類
Microsoft
Microsoftは**Binary Searchの変形**と配列操作問題を多く出題します。
- 頻出: Find Peak Element、Search a 2D Matrix
- 重視スキル: エッジケース、バグのないコード
- 例題: Spiral Matrix、Rotate Image
6. 面接実践テクニック
問題解決フレームワーク（45分基準）
**ステップ1 — 明確化（5分）**
面接官に必ず確認すること:
- 入力の範囲とタイプ（負数可能? 重複あり?）
- 出力フォーマット（インデックス? 値? カウント?）
- エッジケース（空配列、単一要素、全て同じ値）
- 最適化目標（時間 vs 空間）
**ステップ2 — ブルートフォース（5分）**
まずO(n^2)またはO(n^3)の単純な解法を説明します。これがベースラインになります。
**ステップ3 — 最適化（10分）**
パターン認識: Two Pointers? Sliding Window? Hash Map?
面接官とトレードオフを議論します。
**ステップ4 — コーディング（15分）**
クリーンにコーディングします。変数名は明確に、コメントは要点のみ:
def solve(nums, target):
Two Pointersの初期化
left, right = 0, len(nums) - 1
while left < right:
... ロジック
pass
**ステップ5 — テスト（10分）**
自分でテストケースを作り検証します:
- 通常ケース
- エッジケース（空配列、長さ1）
- 最悪ケース（全て重複、逆順ソート）
エッジケースチェックリスト
配列・文字列問題で必ず確認:
- 空の入力 (`[]`, `""`)
- 単一要素 (`[5]`, `"a"`)
- 全て同じ値 (`[3,3,3,3]`)
- 既にソート済みの場合
- 逆順ソートの場合
- 整数オーバーフローの可能性
- 負数の有無
時間配分テーブル
| フェーズ | 時間 | 重点ポイント |
| ---------------- | ---- | -------------------------- |
| 明確化 | 5分 | 要件確認、質問 |
| ブルートフォース | 5分 | ベースライン解法の提示 |
| 最適化 | 10分 | パターン特定、計算量改善 |
| コーディング | 15分 | クリーンでバグのない実装 |
| テスト | 10分 | トレース、エッジケース確認 |
7. 練習問題クイズ
ソート済み配列 `nums = [0,0,1,1,1,2,2,3,3,4]` からin-placeで重複を除去し、ユニークな要素数を返せ。追加スペースはO(1)のみ使用可。
**答え**: 5 (配列は [0,1,2,3,4,...] になる)
**解説**: Two Pointersを使います。遅いポインタ(slow)は次の書き込み位置を、速いポインタ(fast)は探索位置を指します。`nums[fast] != nums[slow]`の時、slowを増やして値をコピーします。
def removeDuplicates(nums):
if not nums:
return 0
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
二値配列 `nums = [1,1,0,0,1,1,1,0,1]` で最大k=1個の0を1に変えられるとき、最長の連続1の部分配列の長さを求めよ。
**答え**: 6
**解説**: Variable Sliding Windowを使います。ウィンドウ内の0の個数がkを超えたら左ポインタを移動します。
def longestOnes(nums, k):
left = 0
zeros = 0
max_len = 0
for right in range(len(nums)):
if nums[right] == 0:
zeros += 1
while zeros > k:
if nums[left] == 0:
zeros -= 1
left += 1
max_len = max(max_len, right - left + 1)
return max_len
ソート済み配列 `nums = [5,7,7,8,8,10]` でtarget=8の開始インデックスと終了インデックスを求めよ。
**答え**: [3, 4]
**解説**: Binary Searchを2回実行します。1回目は最も左のインデックス（leftmost）、2回目は最も右のインデックス（rightmost）を探します。
def searchRange(nums, target):
def findLeft(nums, target):
left, right, idx = 0, len(nums) - 1, -1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
idx = mid
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return idx
def findRight(nums, target):
left, right, idx = 0, len(nums) - 1, -1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
idx = mid
left = mid + 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return idx
return [findLeft(nums, target), findRight(nums, target)]
配列 `[1, -1, 1, -1, 1]` で合計が0の連続部分配列の数は?
**答え**: 4
**解説**: Prefix Sum + HashMapを使います。同じprefix sumが再度現れると、その間の区間の合計は0です。`count += prefix_sum_count[current_sum - k]`で計算します。
from collections import defaultdict
def subarraySum(nums, k=0):
prefix_sum_count = defaultdict(int)
prefix_sum_count[0] = 1
current_sum = 0
count = 0
for num in nums:
current_sum += num
count += prefix_sum_count[current_sum - k]
prefix_sum_count[current_sum] += 1
return count
結果: 4
配列 `nums = [1,2,3,4]` で各位置について自分以外の全要素の積を求めよ。除算禁止、O(n)時間、O(1)追加スペース。
**答え**: [24, 12, 8, 6]
**解説**: 左からの累積積（prefix product）と右からの累積積（suffix product）を利用します。出力配列自体を再利用してスペースを節約します。
def productExceptSelf(nums):
n = len(nums)
result = [1] * n
左からの累積積
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
右からの累積積を掛ける
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
まとめ
配列と文字列の問題はFAANG面接の根幹です。本記事で扱ったパターンを完全に習得すれば、ほとんどの問題をすばやく認識し、最適解法で取り組めるようになります。
**次の学習ステップ:**
1. LeetCodeで各パターンごとに20問ずつ解く
2. タイマーを使って45分以内に解く練習
3. コードレビュー: 他の人の解答と比較する
4. 面接官役になって問題を作ってみる
次の記事ではツリーとグラフのパターンを解説します。
현재 단락 (1/475)
FAANG（Facebook/Meta、Apple、Amazon、Netflix、Google）のコーディング面接では、配列と文字列の問題が全出題の40%以上を占めます。本記事では面接で頻出の6つの核...