Split View: FAANG 코딩 인터뷰 완전 정복: 배열과 문자열 핵심 패턴
FAANG 코딩 인터뷰 완전 정복: 배열과 문자열 핵심 패턴
FAANG 코딩 인터뷰 완전 정복: 배열과 문자열 핵심 패턴
FAANG(Facebook/Meta, Apple, Amazon, Netflix, Google) 코딩 인터뷰에서 배열과 문자열 문제는 전체 출제 비중의 40% 이상을 차지합니다. 이 글에서는 실제 인터뷰에서 자주 등장하는 6가지 핵심 패턴을 실전 코드와 함께 완전히 정복합니다.
1. Two Pointers 패턴
개념 및 언제 사용하는가
Two Pointers 패턴은 정렬된 배열이나 연결 리스트에서 두 개의 포인터를 사용해 선형 시간에 문제를 해결하는 기법입니다.
사용 조건:
- 정렬된 배열에서 두 원소의 합/차를 구하는 경우
- 배열의 양 끝에서 조건을 만족하는 쌍을 찾는 경우
- 중복 제거나 파티셔닝이 필요한 경우
핵심 아이디어: O(n^2) 브루트 포스를 O(n)으로 줄일 수 있습니다.
문제 1: Two Sum II (LeetCode 167)
정렬된 배열에서 두 수의 합이 target이 되는 인덱스를 찾아라.
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 [] # 문제 조건상 항상 해가 존재
# 예시
# Input: numbers = [2,7,11,15], target = 9
# Output: [1,2]
시간 복잡도: O(n) - 각 포인터가 최대 n번 이동 공간 복잡도: O(1) - 추가 공간 불필요
FAANG 팁: 정렬되지 않은 배열이라면 HashMap을 사용한 O(n) 풀이를 먼저 제시하고, 정렬된 경우 Two Pointers가 더 공간 효율적임을 설명하세요.
문제 2: 3Sum (LeetCode 15)
배열에서 합이 0인 세 원소를 모두 찾아라 (중복 없이).
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
# 예시
# Input: nums = [-1, 0, 1, 2, -1, -4]
# Output: [[-1, -1, 2], [-1, 0, 1]]
시간 복잡도: O(n^2) - 정렬 O(n log n) + 이중 루프 O(n^2) 공간 복잡도: O(1) ~ O(n) (정렬 알고리즘에 따라)
FAANG 팁: 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
# 예시
# Input: height = [1,8,6,2,5,4,8,3,7]
# Output: 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
# 예시
# Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
# Output: 6
시간 복잡도: O(n) 공간 복잡도: O(1) - prefix max 배열 없이 투 포인터로 해결
FAANG 팁: Google, Amazon 인터뷰 단골 문제입니다. DP 방식(O(n) space)도 알아두고, 투 포인터가 왜 더 효율적인지 설명할 수 있어야 합니다.
2. Sliding Window 패턴
개념
연속된 부분 배열/문자열에서 최적해를 찾는 패턴입니다. 윈도우를 슬라이딩하며 전체를 한 번만 순회합니다.
Fixed Window: 윈도우 크기가 고정된 경우 Variable Window: 조건에 따라 윈도우 크기가 변하는 경우
문제 5: Longest Substring Without Repeating Characters (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
# 예시
# Input: "abcabcbb"
# Output: 3 ("abc")
시간 복잡도: O(n) 공간 복잡도: O(min(n, charset_size))
문제 6: Minimum Window Substring (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) # 아직 포함하지 못한 문자 수
start = 0
best_start = 0
best_end = float('inf')
left = 0
for right, char in enumerate(s):
# 필요한 문자라면 missing 감소
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]
# 예시
# Input: s = "ADOBECODEBANC", t = "ABC"
# Output: "BANC"
시간 복잡도: O(|s| + |t|) 공간 복잡도: O(|s| + |t|)
문제 7: Sliding Window Maximum (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
# 예시
# Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
# Output: [3,3,5,5,6,7]
시간 복잡도: O(n) - 각 원소가 deque에 한 번씩 추가/삭제 공간 복잡도: O(k)
문제 8: Fruit Into Baskets (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
# 예시
# Input: fruits = [1,2,1,2,3]
# Output: 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: Search in Rotated Sorted Array (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
# 예시
# Input: nums = [4,5,6,7,0,1,2], target = 0
# Output: 4
시간 복잡도: O(log n) 공간 복잡도: O(1)
문제 10: Find Minimum in Rotated Sorted Array (LeetCode 153)
def findMin(nums: list[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
# mid가 right보다 크면 최소값은 오른쪽 절반에 있음
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]
# 예시
# Input: nums = [3,4,5,1,2]
# Output: 1
시간 복잡도: O(log n) 공간 복잡도: O(1)
문제 11: Median of Two Sorted Arrays (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의 파티션
# i가 너무 작으면 오른쪽으로
if i < m and nums1[i] < nums2[j - 1]:
left = i + 1
# i가 너무 크면 왼쪽으로
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
# 예시
# Input: nums1 = [1,3], nums2 = [2]
# Output: 2.0
시간 복잡도: O(log(min(m, n))) 공간 복잡도: O(1)
문제 12: Search a 2D Matrix (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
# 예시
# Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
# Output: True
시간 복잡도: O(log(m*n)) 공간 복잡도: O(1)
4. Prefix Sum & Hash Map 패턴
개념
Prefix Sum은 누적합을 미리 계산해 구간 합 쿼리를 O(1)에 처리합니다. Hash Map과 결합하면 특정 조건을 만족하는 구간을 효율적으로 찾을 수 있습니다.
문제 13: Subarray Sum Equals K (LeetCode 560)
합이 k인 연속 부분 배열의 개수를 구하라.
from collections import defaultdict
def subarraySum(nums: list[int], k: int) -> int:
# prefix_sum_count[s] = prefix sum이 s인 경우의 수
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가 이전에 나온 prefix sum이면 해당 구간의 합 = k
count += prefix_sum_count[current_sum - k]
prefix_sum_count[current_sum] += 1
return count
# 예시
# Input: nums = [1,1,1], k = 2
# Output: 2
시간 복잡도: O(n) 공간 복잡도: O(n)
문제 14: Longest Consecutive Sequence (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
# 예시
# Input: nums = [100,4,200,1,3,2]
# Output: 4 ([1,2,3,4])
시간 복잡도: O(n) - 각 원소는 최대 두 번 방문 공간 복잡도: O(n)
문제 15: Group Anagrams (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:
# 26개 알파벳 카운트를 키로 사용
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
anagram_map[tuple(count)].append(s)
return list(anagram_map.values())
# 예시
# Input: strs = ["eat","tea","tan","ate","nat","bat"]
# Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
시간 복잡도: O(n _ k) - n은 문자열 수, k는 최대 문자열 길이 공간 복잡도: O(n _ k)
문제 16: Top K Frequent Elements (LeetCode 347)
from collections import Counter
import heapq
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
# 예시
# Input: nums = [1,1,1,2,2,3], k = 2
# Output: [1,2]
시간 복잡도: O(n) with Bucket Sort 공간 복잡도: O(n)
5. FAANG 기업별 배열/문자열 출제 경향
Google 인터뷰는 Arrays와 String Manipulation에 집중합니다.
- 자주 출제: Two Sum 변형, 문자열 파싱, 2D 배열 탐색
- 핵심 스킬: 엣지 케이스 처리, 코드 명확성
- 예시 문제: Longest Substring with At Most K Distinct Characters, Minimum Number of Arrows to Burst Balloons
Meta (Facebook)
Meta는 Sliding Window와 Two Pointer 패턴을 선호합니다.
- 자주 출제: 3Sum, Valid Palindrome II, Move Zeroes
- 핵심 스킬: 최적화 이유 설명, 코드 간결성
- 예시 문제: Subarray Product Less Than K, Permutation in String
Amazon
Amazon은 Hash Table과 Sorting 기반 문제를 선호합니다.
- 자주 출제: Two Sum, Group Anagrams, Top K Frequent
- 핵심 스킬: 실용적인 해결책, LP(리더십 원칙) 연결
- 예시 문제: K Closest Points to Origin, Sort Colors
Microsoft
Microsoft는 Binary Search 변형과 배열 조작 문제를 자주 냅니다.
- 자주 출제: Find Peak Element, Search a 2D Matrix
- 핵심 스킬: 엣지 케이스, 버그 없는 코드
- 예시 문제: Spiral Matrix, Rotate Image
6. 인터뷰 실전 팁
문제 접근 프레임워크 (45분 기준)
1단계 - Clarify (5분)
면접관에게 반드시 확인할 사항들:
- 입력 범위와 타입 (음수 가능? 중복 있음?)
- 출력 형식 (인덱스? 값? 개수?)
- 엣지 케이스 (빈 배열, 단일 원소, 모두 같은 값)
- 최적화 목표 (시간 vs 공간)
2단계 - Brute Force (5분)
먼저 O(n^2) 또는 O(n^3) 브루트 포스를 설명합니다. 이것이 베이스라인이 됩니다.
3단계 - Optimize (10분)
패턴 인식: Two Pointers? Sliding Window? Hash Map? 면접관과 트레이드오프를 논의합니다.
4단계 - Code (15분)
깔끔하게 코딩합니다. 변수명은 명확하게, 주석은 핵심만:
def solve(nums, target):
# 투 포인터 초기화
left, right = 0, len(nums) - 1
while left < right:
# ... 로직
pass
5단계 - Test (10분)
직접 테스트 케이스를 만들어 검증합니다:
- 정상 케이스
- 엣지 케이스 (빈 배열, 길이 1)
- 최악의 경우
엣지 케이스 체크리스트
배열/문자열 문제에서 반드시 확인:
- 빈 입력 (
[],"") - 단일 원소 (
[5],"a") - 모든 원소가 같은 값 (
[3,3,3,3]) - 이미 정렬된 경우
- 역순 정렬된 경우
- 오버플로우 가능성 (int 범위 초과)
- 음수 포함 여부
시간 분배 전략
| 단계 | 시간 | 핵심 포인트 |
|---|---|---|
| Clarify | 5분 | 면접관에게 질문하며 요구사항 확인 |
| Brute Force | 5분 | 단순한 해법 먼저 제시 |
| Optimize | 10분 | 패턴 파악, 복잡도 개선 |
| Coding | 15분 | 깔끔하고 버그 없이 |
| Testing | 10분 | 직접 트레이스, 엣지 케이스 |
7. 연습 문제 퀴즈
퀴즈 1: Two Pointers로 정렬된 배열에서 중복 제거하기
정렬된 배열 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
퀴즈 2: Sliding Window로 최대 연속 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
퀴즈 3: Binary Search 응용 - 경계값 찾기
정렬된 배열 nums = [5,7,7,8,8,10]에서 target=8의 시작 인덱스와 끝 인덱스를 구하라.
정답: [3, 4]
설명: Binary Search를 두 번 실행합니다. 첫 번째는 가장 왼쪽 인덱스(leftmost), 두 번째는 가장 오른쪽 인덱스(rightmost)를 찾습니다.
def searchRange(nums, target):
def findLeft(nums, target):
left, right = 0, len(nums) - 1
idx = -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 = 0, len(nums) - 1
idx = -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)]
퀴즈 4: Prefix Sum으로 짝수 길이 구간의 합이 같은 경우 세기
배열 [1, -1, 1, -1, 1]에서 합이 0인 연속 부분 배열의 개수는?
정답: 4
설명: Prefix Sum + HashMap을 사용합니다. prefix sum이 같은 경우가 m번 나타나면 C(m,2)개의 구간이 합이 0입니다. prefix_sum_count를 이용해 count += prefix_sum_count[current_sum]으로 계산합니다.
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
퀴즈 5: 종합 문제 - Product of Array Except Self
배열 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 인터뷰의 핵심입니다. 이 글에서 다룬 패턴들을 완전히 내재화하면 대부분의 문제를 빠르게 인식하고 최적 해법으로 접근할 수 있습니다.
다음 학습 단계:
- LeetCode에서 각 패턴별 문제 20개씩 풀기
- 시간을 재며 45분 안에 해결하는 연습
- 코드 리뷰: 다른 사람의 풀이와 비교
- 면접관 역할로 직접 문제 출제해보기
다음 편에서는 트리와 그래프 패턴을 다룹니다.
FAANG Coding Interview Mastery: Arrays & Strings Core Patterns
FAANG Coding Interview Mastery: Arrays & Strings Core Patterns
Arrays and strings account for over 40% of FAANG (Facebook/Meta, Apple, Amazon, Netflix, Google) coding interview questions. This guide covers 6 essential patterns you must master, complete with working Python code and in-depth analysis.
1. Two Pointers Pattern
Concept and When to Use It
The Two Pointers pattern uses two indices to traverse a sorted array or string in linear time, eliminating the need for nested loops.
Use when:
- Finding pairs in a sorted array that satisfy a condition
- Comparing elements from both ends of an array
- Removing duplicates or partitioning in-place
Core insight: Reduces O(n^2) brute force to O(n).
Problem 1: Two Sum II (LeetCode 167)
Given a sorted array, find two numbers that add up to the target.
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 []
# Example
# Input: numbers = [2,7,11,15], target = 9
# Output: [1,2]
Time Complexity: O(n) — each pointer moves at most n steps total Space Complexity: O(1) — no extra space needed
FAANG Tip: For unsorted arrays, present a HashMap O(n) solution first, then explain why Two Pointers is more space-efficient on sorted input.
Problem 2: 3Sum (LeetCode 15)
Find all unique triplets in the array that sum to zero.
def threeSum(nums: list[int]) -> list[list[int]]:
nums.sort()
result = []
for i in range(len(nums) - 2):
# Skip duplicates for the first element
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]])
# Skip duplicates
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
# Example
# Input: nums = [-1, 0, 1, 2, -1, -4]
# Output: [[-1, -1, 2], [-1, 0, 1]]
Time Complexity: O(n^2) — sort O(n log n) plus double loop O(n^2) Space Complexity: O(1) to O(n) depending on sort algorithm
FAANG Tip: A frequent Meta interview question. Don't miss the duplicate-skipping logic — interviewers often probe for it.
Problem 3: Container With Most Water (LeetCode 11)
Given a height array, find the maximum area of water that can be contained.
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)
# Move the pointer at the shorter wall (seeking a taller one)
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_water
# Example
# Input: height = [1,8,6,2,5,4,8,3,7]
# Output: 49
Time Complexity: O(n) Space Complexity: O(1)
Why is this optimal? Moving the taller wall would only decrease the width while never increasing the limiting height — so it can never yield a larger area.
Problem 4: Trapping Rain Water (LeetCode 42)
Compute how much rainwater can be trapped between the bars.
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
# Example
# Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
# Output: 6
Time Complexity: O(n) Space Complexity: O(1) — no prefix max arrays needed
FAANG Tip: A staple at Google and Amazon. Know both the DP approach (O(n) space) and this Two Pointers approach, and be ready to explain why they are equivalent.
2. Sliding Window Pattern
Concept
The Sliding Window pattern finds optimal subarrays or substrings by maintaining a window that expands and contracts as it slides through the input.
Fixed Window: Window size is constant Variable Window: Window size adjusts based on a constraint
Problem 5: Longest Substring Without Repeating Characters (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
# Optimized version using a 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
# Example
# Input: "abcabcbb"
# Output: 3 ("abc")
Time Complexity: O(n) Space Complexity: O(min(n, charset_size))
Problem 6: Minimum Window Substring (LeetCode 76)
Find the smallest window in s that contains all characters of 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) # Characters still needed
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:
# Shrink from the left
while need[s[left]] < 0:
need[s[left]] += 1
left += 1
if right - left < best_end - best_start:
best_start = left
best_end = right
# Slide the window forward
need[s[left]] += 1
missing += 1
left += 1
if best_end == float('inf'):
return ""
return s[best_start:best_end + 1]
# Example
# Input: s = "ADOBECODEBANC", t = "ABC"
# Output: "BANC"
Time Complexity: O(|s| + |t|) Space Complexity: O(|s| + |t|)
Problem 7: Sliding Window Maximum (LeetCode 239)
Return the maximum of each sliding window of size k.
from collections import deque
def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
dq = deque() # Stores indices in decreasing order of values
result = []
for i, num in enumerate(nums):
# Remove indices outside the window
if dq and dq[0] < i - k + 1:
dq.popleft()
# Remove indices with smaller values (they can never be the max)
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
# Start recording once the first window is full
if i >= k - 1:
result.append(nums[dq[0]])
return result
# Example
# Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
# Output: [3,3,5,5,6,7]
Time Complexity: O(n) — each element is added/removed from deque at most once Space Complexity: O(k)
Problem 8: Fruit Into Baskets (LeetCode 904)
Find the maximum number of fruits you can collect if you can only carry at most 2 types.
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
# Shrink window when we have more than 2 fruit types
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
# Example
# Input: fruits = [1,2,1,2,3]
# Output: 4 ([1,2,1,2])
Time Complexity: O(n) Space Complexity: O(1) — at most 3 fruit types stored at once
3. Binary Search Pattern
Concept
Binary Search finds elements in a sorted array in O(log n) time. FAANG interviews frequently test non-standard variants.
Standard Binary Search Template:
def binarySearch(nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2 # Avoids integer overflow
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Problem 9: Search in Rotated Sorted Array (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
# Left half is sorted
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# Right half is sorted
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
# Example
# Input: nums = [4,5,6,7,0,1,2], target = 0
# Output: 4
Time Complexity: O(log n) Space Complexity: O(1)
Problem 10: Find Minimum in Rotated Sorted Array (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 # Min is in the right half
else:
right = mid # Mid could be the minimum
return nums[left]
# Example
# Input: nums = [3,4,5,1,2]
# Output: 1
Time Complexity: O(log n) Space Complexity: O(1)
Problem 11: Median of Two Sorted Arrays (LeetCode 4) — Hard
def findMedianSortedArrays(nums1: list[int], nums2: list[int]) -> float:
# Ensure nums1 is the smaller array
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 # Partition index in nums1
j = half_len - i # Partition index in 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:
# Correct partition found
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
# Example
# Input: nums1 = [1,3], nums2 = [2]
# Output: 2.0
Time Complexity: O(log(min(m, n))) Space Complexity: O(1)
Problem 12: Search a 2D Matrix (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
# Map 1D index to 2D coordinates
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
# Example
# Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
# Output: True
Time Complexity: O(log(m*n)) Space Complexity: O(1)
4. Prefix Sum & Hash Map Pattern
Concept
Prefix Sum precomputes cumulative sums so that range sum queries run in O(1). Combined with a HashMap, it finds subarrays satisfying specific conditions efficiently.
Problem 13: Subarray Sum Equals K (LeetCode 560)
Count the number of contiguous subarrays whose sum equals k.
from collections import defaultdict
def subarraySum(nums: list[int], k: int) -> int:
prefix_sum_count = defaultdict(int)
prefix_sum_count[0] = 1 # Empty prefix has sum 0
current_sum = 0
count = 0
for num in nums:
current_sum += num
# If (current_sum - k) was seen before, those subarrays sum to k
count += prefix_sum_count[current_sum - k]
prefix_sum_count[current_sum] += 1
return count
# Example
# Input: nums = [1,1,1], k = 2
# Output: 2
Time Complexity: O(n) Space Complexity: O(n)
Problem 14: Longest Consecutive Sequence (LeetCode 128)
Find the length of the longest consecutive sequence in O(n) time.
def longestConsecutive(nums: list[int]) -> int:
num_set = set(nums)
max_length = 0
for num in num_set:
# Only start a sequence from its lowest element
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
# Example
# Input: nums = [100,4,200,1,3,2]
# Output: 4 ([1,2,3,4])
Time Complexity: O(n) — each number is visited at most twice Space Complexity: O(n)
Problem 15: Group Anagrams (LeetCode 49)
Group strings that are anagrams of each other.
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())
# Optimized version using character count as key
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())
# Example
# Input: strs = ["eat","tea","tan","ate","nat","bat"]
# Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Time Complexity: O(n _ k) — n strings, k is max string length Space Complexity: O(n _ k)
Problem 16: Top K Frequent Elements (LeetCode 347)
from collections import Counter
import heapq
def topKFrequent(nums: list[int], k: int) -> list[int]:
# Approach 1: Heap — 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]:
# Approach 2: Bucket Sort — O(n)
count = Counter(nums)
# Index = frequency, value = list of numbers with that frequency
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
# Example
# Input: nums = [1,1,1,2,2,3], k = 2
# Output: [1,2]
Time Complexity: O(n) with Bucket Sort Space Complexity: O(n)
5. FAANG Company-Specific Trends
Google interviews are Array and String manipulation heavy.
- Frequent: Two Sum variants, string parsing, 2D array traversal
- Key skills: Edge case handling, code clarity and readability
- Example problems: Longest Substring with At Most K Distinct Characters, Minimum Number of Arrows to Burst Balloons
Meta (Facebook)
Meta favors Sliding Window and Two Pointer patterns.
- Frequent: 3Sum, Valid Palindrome II, Move Zeroes
- Key skills: Explaining optimization rationale, concise code
- Example problems: Subarray Product Less Than K, Permutation in String
Amazon
Amazon leans toward Hash Table and Sorting based problems.
- Frequent: Two Sum, Group Anagrams, Top K Frequent
- Key skills: Practical solutions, tying to Leadership Principles
- Example problems: K Closest Points to Origin, Sort Colors
Microsoft
Microsoft asks Binary Search variants and array manipulation.
- Frequent: Find Peak Element, Search a 2D Matrix
- Key skills: Rigorous edge case coverage, bug-free code
- Example problems: Spiral Matrix, Rotate Image
6. Interview Strategy
Problem-Solving Framework (45 Minutes)
Step 1 — Clarify (5 minutes)
Always ask the interviewer:
- Input range and types (can values be negative? duplicates allowed?)
- Output format (indices? values? count?)
- Edge cases (empty array, single element, all same value)
- Optimization target (time vs. space)
Step 2 — Brute Force (5 minutes)
State a naive O(n^2) or O(n^3) solution. This establishes a baseline.
Step 3 — Optimize (10 minutes)
Identify the pattern: Two Pointers? Sliding Window? Hash Map? Discuss trade-offs with the interviewer before coding.
Step 4 — Code (15 minutes)
Write clean code with meaningful variable names:
def solve(nums, target):
# Initialize two pointers
left, right = 0, len(nums) - 1
while left < right:
# ... logic
pass
Step 5 — Test (10 minutes)
Walk through your own test cases:
- Normal case
- Edge cases (empty array, length 1)
- Worst case (all duplicates, reverse sorted)
Edge Case Checklist
Always verify these for array/string problems:
- Empty input (
[],"") - Single element (
[5],"a") - All identical values (
[3,3,3,3]) - Already sorted input
- Reverse sorted input
- Integer overflow potential
- Negative numbers
Time Allocation Table
| Phase | Time | Key Focus |
|---|---|---|
| Clarify | 5 min | Ask questions, nail requirements |
| Brute Force | 5 min | Establish baseline solution |
| Optimize | 10 min | Identify pattern, improve complexity |
| Coding | 15 min | Clean, bug-free implementation |
| Testing | 10 min | Trace through, catch edge cases |
7. Practice Quiz
Quiz 1: Remove Duplicates from Sorted Array with Two Pointers
Given sorted array nums = [0,0,1,1,1,2,2,3,3,4], remove duplicates in-place using O(1) extra space and return the count of unique elements.
Answer: 5 (array becomes [0,1,2,3,4,...])
Explanation: Use slow and fast pointers. The slow pointer tracks the next write position. When nums[fast] != nums[slow], increment slow and overwrite.
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
Quiz 2: Max Consecutive Ones with One Flip
Binary array nums = [1,1,0,0,1,1,1,0,1]. You may flip at most k=1 zeros to ones. Find the maximum length of a contiguous subarray of ones.
Answer: 6
Explanation: Variable Sliding Window. Track the count of zeros in the window; shrink from the left when zeros exceed 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
Quiz 3: Binary Search for First and Last Position
Sorted array nums = [5,7,7,8,8,10], target = 8. Find the first and last index.
Answer: [3, 4]
Explanation: Run Binary Search twice — once biased left (continue searching left after finding target), once biased right.
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)]
Quiz 4: Count Subarrays with Zero Sum using Prefix Sum
Array [1, -1, 1, -1, 1] — how many contiguous subarrays have sum equal to 0?
Answer: 4
Explanation: Use Prefix Sum + HashMap. Every time the same prefix sum appears again, all subarrays between those two positions have sum 0. Count with 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
# Result: 4
Quiz 5: Product of Array Except Self
Array nums = [1,2,3,4]. Return an array where each element is the product of all other elements. No division allowed. O(n) time, O(1) extra space.
Answer: [24, 12, 8, 6]
Explanation: Two passes — first accumulate left products into the result array, then multiply by right products in a second pass from the right.
def productExceptSelf(nums):
n = len(nums)
result = [1] * n
# Pass 1: left products
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
# Pass 2: multiply by right products
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
Conclusion
Arrays and strings are the bedrock of FAANG coding interviews. Mastering these 6 patterns lets you recognize most problems instantly and approach them with an optimal strategy.
Next steps:
- Solve 20 problems per pattern on LeetCode
- Practice under a 45-minute timer
- Code review: compare your solution with top-voted answers
- Flip the script: try creating your own problem variants
The next guide in this series covers Trees and Graphs patterns.