← Back to Post
Split View: FAANG 코딩 인터뷰 완전 정복: 백트래킹, 힙, 고급 패턴
|
FAANG 코딩 인터뷰 완전 정복: 백트래킹, 힙, 고급 패턴
FAANG 코딩 인터뷰 완전 정복: 백트래킹, 힙, 고급 패턴
이 글에서는 FAANG 인터뷰에서 자주 출제되는 백트래킹, 힙/우선순위 큐, 단조 스택, 트라이, 비트 조작 패턴을 다룹니다.
1. Backtracking 패턴
백트래킹 핵심 템플릿
백트래킹은 결정 트리를 탐색하여 조건을 만족하는 모든 해를 찾는 기법입니다.
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]) # Choose
backtrack(i + 1, current) # Explore
current.pop() # Unchoose
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]) # Choose
backtrack(current, remaining[:i] + remaining[i+1:]) # Explore
current.pop() # Unchoose
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. Heap / Priority Queue 패턴
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)
두 힙(최대 힙 + 최소 힙)을 사용하는 핵심 패턴입니다.
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. Monotonic Stack 패턴
단조 스택 개념
단조 스택은 스택 내 원소들이 단조증가 또는 단조감소를 유지하는 스택입니다.
- 단조 증가 스택: 이전보다 작거나 같은 원소가 오면 pop (다음 작은 원소 문제)
- 단조 감소 스택: 이전보다 크거나 같은 원소가 오면 pop (다음 큰 원소 문제)
Daily Temperatures (LeetCode 739)
def dailyTemperatures(temperatures: list) -> list:
n = len(temperatures)
result = [0] * n
stack = [] # (온도, 인덱스) 또는 인덱스만 저장
for i, temp in enumerate(temperatures):
# 스택 top보다 현재 온도가 높으면 pop (더 따뜻한 날 발견)
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] # 마지막에 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 - Stack 방식 (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. Trie (Prefix Tree) 패턴
Trie 구현
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:
# Trie 구성
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. Bit Manipulation 패턴
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) - Hamming Weight
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" 조건이 필요한 이유는?
정답: 같은 레벨(depth)에서만 중복을 건너뛰어야 하기 때문입니다.
설명: "i > 0" 조건이면 이전 재귀 호출에서 이미 사용된 원소를 자식 노드에서도 건너뛰어버려 유효한 조합이 누락됩니다. "i > start" 조건은 현재 재귀 호출의 시작 인덱스 이후에만 중복을 건너뛰므로, 같은 레벨에서 같은 값이 두 번 선택되는 경우만 제거합니다.
퀴즈 2: Find Median from Data Stream에서 두 힙을 사용하는 이유는?
정답: 중앙값을 O(1)에 조회하고 삽입을 O(log n)에 처리하기 위해서입니다.
설명: 정렬된 배열을 유지하면 삽입이 O(n), 정렬만 하면 조회가 O(n)입니다. 두 힙(하위 절반의 최대 힙 + 상위 절반의 최소 힙)을 균형 있게 유지하면 중앙값은 두 힙의 top을 보면 되므로 O(1), 삽입은 힙 연산이므로 O(log n)이 됩니다.
퀴즈 3: Largest Rectangle in Histogram에서 heights 배열 끝에 0을 추가하는 이유는?
정답: 루프 종료 후 스택에 남은 원소들을 모두 처리하기 위해서입니다.
설명: 마지막에 0을 추가하면 모든 이전 높이보다 작으므로 스택의 모든 원소가 pop됩니다. 이를 통해 루프 후 별도의 처리 없이 스택을 비울 수 있습니다. 같은 효과를 위해 별도의 후처리 루프를 사용해도 됩니다.
퀴즈 4: Single Number에서 XOR을 사용하는 수학적 원리는?
정답: XOR의 두 가지 핵심 성질: a XOR a = 0 (같은 수 두 번 XOR = 0), a XOR 0 = a (0과 XOR = 자기 자신)
설명: 배열에서 두 번씩 나타나는 숫자들을 모두 XOR하면 0이 됩니다. 한 번만 나타나는 숫자를 XOR하면 그 숫자가 남습니다. XOR은 교환법칙과 결합법칙이 성립하므로, 순서에 관계없이 동일한 결과가 나옵니다.
퀴즈 5: Word Search II에서 Trie를 사용하는 이유는?
정답: 여러 단어를 동시에 탐색하고 공통 접두사를 공유함으로써 효율을 높이기 위해서입니다.
설명: 각 단어를 개별적으로 DFS로 탐색하면 O(words _ board_cells _ 4^word_length)의 복잡도가 됩니다. Trie를 사용하면 공통 접두사를 가진 단어들의 탐색을 공유할 수 있으며, 현재 경로가 어떤 단어의 접두사도 되지 않을 때 즉시 가지치기가 가능합니다.
마무리
복잡도 요약:
| 패턴 | 시간 | 공간 |
|---|---|---|
| Backtracking Subsets | O(n * 2^n) | O(n) |
| Backtracking Permutations | O(n * n!) | O(n) |
| Heap - K번째 원소 | O(n log k) | O(k) |
| Merge K Lists | O(N log k) | O(k) |
| Monotonic Stack | O(n) | O(n) |
| Trie Insert/Search | O(L) | O(ALPHABET _ N _ L) |
| Bit XOR trick | O(n) | O(1) |
인터뷰 준비 로드맵:
- Backtracking: Subsets → Permutations → Combination Sum → N-Queens
- Heap: Kth Largest → Top K → Merge K Lists → Median Finder
- Monotonic Stack: Daily Temperatures → Largest Rectangle
- Trie: Implement → Word Search II
- Bit: Single Number → Counting Bits → Power of Two
FAANG Coding Interview Mastery: Backtracking, Heap, and Advanced Patterns
FAANG Coding Interview Mastery: Backtracking, Heap, and Advanced Patterns
This guide covers backtracking, heap/priority queue, monotonic stack, Trie, and bit manipulation patterns that appear frequently in FAANG interviews.
1. Backtracking Patterns
The Backtracking Template
Backtracking explores a decision tree to find all solutions satisfying a constraint.
def backtrack(state, choices):
# Base case: found a valid solution
if is_solution(state):
result.append(state[:]) # Save a copy, not a reference
return
for choice in choices:
# Choose
make_choice(state, choice)
# Explore (recurse)
backtrack(state, remaining_choices)
# Unchoose (undo — this is the key!)
undo_choice(state, choice)
Core Principles:
- Always save a copy of state to results (not a reference)
- State must be identical before and after each recursive call
- Use pruning to eliminate unnecessary branches early
Subsets (LeetCode 78)
def subsets(nums: list) -> list:
result = []
def backtrack(start, current):
result.append(current[:]) # Save current subset
for i in range(start, len(nums)):
current.append(nums[i]) # Choose
backtrack(i + 1, current) # Explore
current.pop() # Unchoose
backtrack(0, [])
return result
- Time: O(n * 2^n)
- Space: O(n) (call stack)
Subsets II — Handling Duplicates (LeetCode 90)
def subsetsWithDup(nums: list) -> list:
nums.sort() # Sort for duplicate detection
result = []
def backtrack(start, current):
result.append(current[:])
for i in range(start, len(nums)):
# Skip duplicates at the same recursion level
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
# Visited array approach (more efficient)
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 — Handling Duplicates (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
# Skip if same value and previous element not yet visited
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]) # Can reuse same element
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 (top-right to bottom-left)
diag2 = set() # row + col (top-left to bottom-right)
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] = '#' # Mark as visited
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 # Restore
return found
for r in range(rows):
for c in range(cols):
if backtrack(r, c, 0):
return True
return False
2. Heap / Priority Queue Patterns
Python heapq Complete Guide
import heapq
# Min-heap (default)
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 2)
print(heapq.heappop(min_heap)) # 1 (minimum)
# Max-heap (negate values)
max_heap = []
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -2)
print(-heapq.heappop(max_heap)) # 3 (maximum)
# Build heap from list
nums = [3, 1, 4, 1, 5, 9]
heapq.heapify(nums) # O(n)
# n largest / n smallest
heapq.nlargest(3, nums) # Top 3 largest
heapq.nsmallest(3, nums) # Top 3 smallest
# Tuple heap: (priority, value)
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:
# Maintain a min-heap of size 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] # kth largest
# QuickSelect O(n) average
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)
# Maintain a min-heap of size k using (freq, num) pairs
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]
# Bucket sort 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 = []
# Push the first node from each list
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
- Time: O(N log k), where N = total nodes, k = number of lists
Find Median from Data Stream (LeetCode 295)
The two-heap pattern is a key interview technique.
class MedianFinder:
def __init__(self):
self.small = [] # Max-heap (lower half, stored as negatives)
self.large = [] # Min-heap (upper half)
def addNum(self, num: int) -> None:
# Add to small heap, then rebalance
heapq.heappush(self.small, -num)
# If max of small > min of large, move element
if self.small and self.large and (-self.small[0] > self.large[0]):
heapq.heappush(self.large, -heapq.heappop(self.small))
# Balance sizes
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. Monotonic Stack Patterns
The Monotonic Stack Concept
A monotonic stack maintains elements in monotonically increasing or decreasing order.
- Monotonically increasing stack: pop when a smaller or equal element arrives (finds next smaller element)
- Monotonically decreasing stack: pop when a larger or equal element arrives (finds next greater element)
Daily Temperatures (LeetCode 739)
def dailyTemperatures(temperatures: list) -> list:
n = len(temperatures)
result = [0] * n
stack = [] # stores indices
for i, temp in enumerate(temperatures):
# Pop while current temperature is warmer
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)
# Elements remaining in stack have no next greater element
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 = [] # Monotonically increasing stack (indices)
max_area = 0
heights = heights + [0] # Sentinel to flush the stack at the end
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 — Stack Approach (LeetCode 42)
def trap(height: list) -> int:
stack = [] # Monotonically decreasing 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. Trie (Prefix Tree) Patterns
Trie Implementation
class TrieNode:
def __init__(self):
self.children = {} # or [None] * 26 for lowercase letters
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 == '.':
# Wildcard: explore all children
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:
# Build Trie from word 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)
# Continue searching for longer words
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] = '#' # Mark visited
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 # Restore
for r in range(rows):
for c in range(cols):
dfs(r, c, root, '')
return list(result)
5. Bit Manipulation Patterns
XOR Tricks and Bit Operation Fundamentals
# Basic bit operations
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 (two's complement)
print(a << 1) # Left shift: 0b10100 = 20
print(a >> 1) # Right shift: 0b0101 = 5
# Useful bit tricks
n = 12
print(n & (n-1)) # Remove lowest set bit: 8
print(n & (-n)) # Isolate lowest set bit: 4
print(n ^ n) # XOR with itself = 0
print(0 ^ n) # XOR with 0 = n
Single Number (LeetCode 136)
def singleNumber(nums: list) -> int:
# XOR all numbers: pairs cancel out to 0
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):
# Number of 1s in i = number of 1s in (i >> 1) + lowest bit
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 — Hamming Weight (LeetCode 191)
def hammingWeight(n: int) -> int:
count = 0
while n:
n &= (n - 1) # Remove the lowest set bit
count += 1
return count
# Python built-in
def hammingWeight_v2(n: int) -> int:
return bin(n).count('1')
6. Real Interview Strategies
How to Ask for Hints When Stuck
Staying silent when stuck is the worst thing you can do. Try phrases like these:
"I'm running into [specific issue] with my current approach.
Am I missing something obvious here?"
"I'm thinking of using [specific data structure / algorithm].
Does that seem like a reasonable direction?"
Hidden Rule: Even when a hint is given, how you incorporate it matters just as much as the answer.
How to Discuss Code Optimization
When asked to optimize:
"My current solution runs in O(n^2) time and O(n) space.
I think using [specific data structure / algorithm]
could bring this down to O(n log n). Should I implement that?"
How to Explain Time and Space Complexity
Always state the reasoning, not just the answer:
"The time complexity is O(n log n).
The outer loop runs n times, and each iteration performs
a heap operation costing O(log n).
The space complexity is O(k) because
we maintain a heap of at most k elements."
The Interview Execution Framework
1. Understand the Problem (5 min)
- Create your own examples
- Ask about edge cases
2. Explain Your Approach (5 min)
- Brute force first
- Then discuss optimizations
3. Code (15-20 min)
- Talk through your logic as you code
- Use meaningful variable names
4. Test (5 min)
- Trace through your own example
- Verify edge cases
7. Practice Quiz
Quiz 1: Why does Subsets II need the condition "i > start" instead of "i > 0"?
Answer: To skip duplicates only at the same level of recursion, not across different levels.
Explanation: Using "i > 0" would skip elements that were already used in a parent call, causing valid combinations to be missed. "i > start" only skips when the same value appears twice at the current recursion depth, which is exactly the condition that produces duplicate subsets.
Quiz 2: Why do we use two heaps in Find Median from Data Stream?
Answer: To achieve O(1) median retrieval and O(log n) insertion.
Explanation: Maintaining a sorted array gives O(n) insertion. Using only one heap gives O(n) retrieval. Two balanced heaps (a max-heap for the lower half and a min-heap for the upper half) let us read the median from the tops of the heaps in O(1), while heap push and pop are O(log n).
Quiz 3: Why do we append 0 to heights in Largest Rectangle in Histogram?
Answer: To force all remaining elements to be popped from the stack after the loop ends.
Explanation: The sentinel value 0 is smaller than any valid height, so it triggers the while-loop to pop every remaining index from the stack. This eliminates the need for a separate post-loop cleanup step. You could also handle the remaining elements manually after the loop — both approaches are correct.
Quiz 4: What mathematical property of XOR makes Single Number work?
Answer: Two key XOR properties: a XOR a = 0 (any number XORed with itself is 0), and a XOR 0 = a (any number XORed with 0 is itself).
Explanation: All numbers appearing twice cancel out to 0 when XORed together. The number appearing once is XORed with 0, leaving itself. XOR is commutative and associative, so the order does not matter.
Quiz 5: Why do we use a Trie instead of checking each word individually in Word Search II?
Answer: To share common prefix traversal across multiple words and prune branches that cannot lead to any word.
Explanation: Searching for each word individually costs O(words _ cells _ 4^L) where L is word length. A Trie allows multiple words sharing a common prefix to share the same DFS path. When the current board path is not a prefix of any word in the Trie, we can prune immediately, dramatically reducing the total number of DFS calls.
Summary
Complexity Reference:
| Pattern | Time | Space |
|---|---|---|
| Backtracking Subsets | O(n * 2^n) | O(n) |
| Backtracking Permutations | O(n * n!) | O(n) |
| Heap — Kth element | O(n log k) | O(k) |
| Merge K Lists | O(N log k) | O(k) |
| Monotonic Stack | O(n) | O(n) |
| Trie Insert/Search | O(L) | O(ALPHABET _ N _ L) |
| Bit XOR trick | O(n) | O(1) |
Interview Preparation Roadmap:
- Backtracking: Subsets → Permutations → Combination Sum → N-Queens
- Heap: Kth Largest → Top K → Merge K Lists → Median Finder
- Monotonic Stack: Daily Temperatures → Largest Rectangle
- Trie: Implement Trie → Word Search II
- Bit Manipulation: Single Number → Counting Bits → Power of Two