DSA Interview

Study Guide
DS / AI & SWE Roles · FAANG-Level Interview Prep · 9 Tiers · Python Examples

Every topic: definition + commented Python code + complexity table. Hard topics (DP, Graphs,
Trees, Recursion) get deeper treatment with real-world analogies, two examples (simple +
interview-level), and common mistake callouts. Quick Revision boxes at every tier for rapid
self-testing.
 ■ TIER 1 — Arrays & Strings

## Arrays — The Foundation

A contiguous block of memory storing elements of the same type. Indexed from 0. Random access is O(1) because
address = base + index × size.

Operation Time Space

Access by index O(1) O(1)

Search (unsorted) O(n) O(1)

Insert/Delete at end O(1) amortized O(1)

Insert/Delete at middle O(n) O(1)

■ Interview Tip: Arrays are the #1 topic in interviews. Master TWO POINTERS and SLIDING WINDOW before
anything else — they solve ~40% of array problems.

Two Pointers Pattern

Use two indices that move toward each other or in the same direction. Eliminates the need for a nested loop, reducing
O(n²) → O(n).

# Pattern 1: Opposite ends — check if pair sums to target (sorted array)

def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target: return [left, right]
elif s < target: left += 1 # need bigger sum
else: right -= 1 # need smaller sum
return []

# Pattern 2: Same direction — remove duplicates from sorted array in-place

def remove_duplicates(nums):
if not nums: return 0
slow = 0
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]: # found a new unique value
slow += 1
nums[slow] = nums[fast]
return slow + 1 # length of unique portion

Sliding Window Pattern

Maintain a window [left, right] over the array. Expand right to grow, shrink left to satisfy a constraint. Converts O(n²)
brute force to O(n).
 # Longest substring without repeating characters — classic sliding window
def length_of_longest_substring(s: str) -> int:
char_index = {} # last seen index of each character
left = 0
max_len = 0
for right, char in enumerate(s):
# If char was seen and is inside the current window, shrink left
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1
char_index[char] = right
max_len = max(max_len, right - left + 1)
return max_len
# Time: O(n) Space: O(min(n, alphabet_size))

■ Interview Tip: Fixed-size window: move both left and right together. Variable-size window: expand right freely,
shrink left when a constraint is violated. Know which type the problem is asking for.

Prefix Sum Pattern

Precompute cumulative sums so any subarray sum is answerable in O(1). Sum of nums[i..j] = prefix[j+1] - prefix[i].

# Subarray sum equals k — use prefix sum + hash map

def subarray_sum(nums, k):
count = 0
prefix = 0
seen = {0: 1} # prefix sum -> frequency; base case: empty prefix
for n in nums:
prefix += n
# If (prefix - k) was seen before, a subarray summing to k exists
count += [Link](prefix - k, 0)
seen[prefix] = [Link](prefix, 0) + 1
return count
# Time: O(n) Space: O(n)

## Strings

Strings are immutable arrays of characters in Python. Most string problems reduce to array techniques — two pointers,
sliding window, or hash maps for frequency counting.
# Anagram check — frequency map approach
from collections import Counter
def is_anagram(s: str, t: str) -> bool:
return Counter(s) == Counter(t) # O(n) time, O(1) space (26 letters)

# Valid palindrome — two pointers

def is_palindrome(s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]: return False
left += 1; right -= 1
return True

# Longest palindromic substring — expand around center

def longest_palindrome(s):
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
return s[l+1:r] # last valid expansion
best = ''
for i in range(len(s)):
for p in [expand(i, i), expand(i, i+1)]: # odd and even length
if len(p) > len(best): best = p
return best
# Time: O(n²) Space: O(1) | Manacher's algo gives O(n) but rarely asked

■ Interview Tip: String interviews almost always involve: anagram/frequency counting (Counter), palindrome
(two pointers / expand from center), or substring search (sliding window). Know all three cold.

■ Quick Revision — Tier 1 — Arrays & Strings

✓ Two pointers: opposite ends for sorted-array pair problems; same direction for partition/deduplicate.
✓ Sliding window: fixed window = move together; variable window = expand right, shrink left on violation.
✓ Prefix sum + hash map = O(n) subarray sum queries. Base case: seen = {0: 1}.
✓ String problems map directly to array techniques — treat them the same way.
✓ When you see O(n²) brute force involving subarrays/substrings, think sliding window or prefix sum.
 ■ TIER 2 — Hash Maps, Stacks & Queues

## Hash Maps & Hash Sets

A hash map stores key-value pairs with O(1) average-case insert, delete, and lookup. A hash set stores unique keys
only. Both use hashing to map keys to array indices.

Operation Time Space

Insert / Delete / Lookup (avg) O(1) O(n)

Insert / Delete / Lookup (worst, collision) O(n) O(n)

Iteration O(n) O(1)

# Two Sum — classic hash map problem

def two_sum(nums, target):
seen = {} # value -> index
for i, n in enumerate(nums):
complement = target - n
if complement in seen:
return [seen[complement], i]
seen[n] = i
return []
# Time: O(n) Space: O(n) — one-pass, no sorting needed

# Group Anagrams — sorted string as canonical key

from collections import defaultdict
def group_anagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # 'eat','tea','ate' all -> ('a','e','t')
groups[key].append(s)
return list([Link]())

■ Interview Tip: When you see 'find pair', 'find duplicate', 'count frequency', or 'group by property' — reach for a
hash map. It's the single most-used data structure in coding interviews.

## Stack

LIFO (Last In, First Out). Think: stack of plates. Push to top, pop from top. Python's list works as a stack. Used for
matching brackets, monotonic problems, and DFS.

Operation Time Space

Push / Pop / Peek O(1) O(1)

Search O(n) O(1)

 # Valid Parentheses — canonical stack problem
def is_valid(s: str) -> bool:
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for ch in s:
if ch in '([{':
[Link](ch) # push opening bracket
else:
# must match the most recent opening bracket
if not stack or stack[-1] != pairs[ch]:
return False
[Link]()
return len(stack) == 0

# Monotonic Stack — Next Greater Element

def next_greater(nums):
result = [-1] * len(nums)
stack = [] # stores indices of elements waiting for their answer
for i, n in enumerate(nums):
while stack and nums[stack[-1]] < n:
idx = [Link]()
result[idx] = n # n is the next greater element for idx
[Link](i)
return result
# Time: O(n) — each element pushed/popped at most once

■ Interview Tip: Monotonic stack is high-frequency in DS interviews. Increasing stack → next smaller element.
Decreasing stack → next greater element. Largest rectangle in histogram is the canonical hard problem — know
it.

## Queue & Deque

Queue: FIFO (First In, First Out). Use [Link] in Python — O(1) append and popleft. Essential for BFS.
Deque supports O(1) operations on BOTH ends.
from collections import deque

# BFS template using queue

def bfs(graph, start):
visited = set([start])
queue = deque([start])
while queue:
node = [Link]() # O(1) — use deque, NOT [Link](0)
for neighbor in graph[node]:
if neighbor not in visited:
[Link](neighbor)
[Link](neighbor)

# Sliding Window Maximum — deque as monotonic queue

def max_sliding_window(nums, k):
dq = deque() # stores indices; front always has the max
result = []
for i, n in enumerate(nums):
while dq and nums[dq[-1]] < n: # remove smaller elements from back
[Link]()
[Link](i)
if dq[0] == i - k: # front is outside window
[Link]()
if i >= k - 1: # window is full
[Link](nums[dq[0]])
return result
# Time: O(n) Space: O(k)

■ Interview Tip: Never use [Link](0) for a queue — it's O(n). Always use [Link] with popleft() for
O(1). This mistake causes TLE on large inputs and signals inexperience to interviewers.

■ Quick Revision — Tier 2 — Hash Maps, Stacks & Queues

✓ Hash map lookup/insert is O(1) average. Know worst-case O(n) from collisions.
✓ Stack = LIFO. Monotonic stack solves next-greater/smaller in O(n) vs O(n²) brute force.
✓ Queue = FIFO. Always use [Link] — [Link](0) is O(n) and will cause TLE.
✓ Deque supports O(1) on both ends — use for sliding window maximum pattern.
✓ 'Find pair / count / group' → hash map. 'Matching brackets / span' → stack. 'Level order / shortest path' → queue.
 ■ TIER 3 — Linked Lists

## Singly Linked List

A sequence of nodes where each node holds a value and a pointer to the next node. No random access — you must
traverse from the head. Head pointer is your entry point; losing it means losing the list.

Operation Time Space

Access by index O(n) O(1)

Insert/Delete at head O(1) O(1)

Insert/Delete at tail (with tail ptr) O(1) O(1)

Search O(n) O(1)

class ListNode:
def __init__(self, val=0, next=None):
[Link] = val
[Link] = next

# Reverse a linked list — iterative (O(n) time, O(1) space)

def reverse_list(head):
prev, curr = None, head
while curr:
nxt = [Link] # save next before breaking the link
[Link] = prev # reverse the pointer
prev = curr # advance prev
curr = nxt # advance curr
return prev # prev is now the new head

■ Interview Tip: The dummy node trick: create a dummy = ListNode(0); [Link] = head. This eliminates
edge cases for empty lists or head deletions. Return [Link] at the end. Use this in almost every linked list
problem.

Fast & Slow Pointer (Floyd's Algorithm)

Two pointers moving at different speeds — slow moves 1 step, fast moves 2 steps. When fast reaches the end, slow is
at the middle. If there's a cycle, fast will eventually lap slow and they'll meet.
 # Detect cycle in linked list
def has_cycle(head):
slow = fast = head
while fast and [Link]:
slow = [Link]
fast = [Link]
if slow is fast: # they meet → cycle exists
return True
return False

# Find middle of linked list (slow is at middle when fast reaches end)
def find_middle(head):
slow = fast = head
while fast and [Link]:
slow = [Link]
fast = [Link]
return slow

# Find kth node from end — fast starts k steps ahead

def kth_from_end(head, k):
slow = fast = head
for _ in range(k): fast = [Link] # advance fast by k
while fast:
slow = [Link]
fast = [Link]
return slow

■ Analogy: Fast and slow pointers are like two runners on a circular track. The faster runner will always lap the slower
one if there's a loop. If the track is linear, the faster one just hits the wall first.

Merge Two Sorted Lists

# Interview staple — merge two sorted linked lists
def merge_two_lists(l1, l2):
dummy = ListNode(0) # dummy head simplifies edge cases
curr = dummy
while l1 and l2:
if [Link] <= [Link]:
[Link] = l1; l1 = [Link]
else:
[Link] = l2; l2 = [Link]
curr = [Link]
[Link] = l1 or l2 # attach remaining nodes
return [Link]

■ Interview Tip: Linked list interview checklist: (1) Use dummy node. (2) Draw the pointer changes before
coding. (3) Check for cycles if the problem mentions 'circular' or 'loop'. (4) Fast/slow pointer for middle or cycle
detection.

■ Quick Revision — Tier 3 — Linked Lists

✓ Always use a dummy node to handle empty list and head deletion edge cases.
✓ Fast/slow pointer: cycle detection, finding middle, kth from end — all O(n) time O(1) space.
✓ Reversing a linked list: prev=None, curr=head; save next, flip pointer, advance both.
✓ Linked lists have no random access — every operation requires traversal from head.
✓ Draw pointer diagrams before coding; pointer manipulation bugs are invisible without visualization.
 ■ TIER 4 — Recursion, Backtracking & Sorting

## Recursion

A function that calls itself with a smaller subproblem until a base case is reached. Every recursion has: (1) base case
— stops recursion, (2) recursive case — reduces the problem. The call stack depth equals the recursion depth, so
space complexity is at least O(depth).

■ Analogy: Recursion is like Russian nesting dolls (Matryoshka). Each doll contains a smaller version of itself. The
smallest doll is the base case — it doesn't open further.

# Fibonacci — naive O(2^n), memoized O(n)

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
if n <= 1: return n # base case
return fib(n-1) + fib(n-2) # recursive case

# Power of x^n — fast exponentiation O(log n)

def my_pow(x, n):
if n == 0: return 1
if n < 0: return 1 / my_pow(x, -n)
half = my_pow(x, n // 2) # compute half once (not twice!)
if n % 2 == 0: return half * half
else: return half * half * x

## Backtracking

Backtracking is recursion with the ability to UNDO a choice. Build a solution incrementally, and when a path leads to a
dead end, backtrack (undo the last step) and try the next option. Used for: permutations, combinations, subsets,
sudoku, N-Queens, word search.

■ Analogy: Backtracking is like navigating a maze. You walk forward until you hit a wall. Then you step back to the last
junction and try a different path. You never skip a junction — you always fully explore before backtracking.

# Template: Subsets (power set)

def subsets(nums):
result = []
def backtrack(start, current):
[Link](current[:]) # snapshot of current subset
for i in range(start, len(nums)):
[Link](nums[i]) # choose
backtrack(i + 1, current) # explore
[Link]() # un-choose (backtrack)
backtrack(0, [])
return result
 # Permutations (interview-level)
def permute(nums):
result = []
def backtrack(path, remaining):
if not remaining: # base case: used all numbers
[Link](path[:])
return
for i in range(len(remaining)):
[Link](remaining[i])
backtrack(path, remaining[:i] + remaining[i+1:])
[Link]()
backtrack([], nums)
return result
# Time: O(n * n!) Space: O(n) call stack + O(n * n!) for results

# Combination Sum — elements can be reused, find all combos summing to target
def combination_sum(candidates, target):
result = []
def backtrack(start, current, remaining):
if remaining == 0: # found valid combination
[Link](current[:])
return
if remaining < 0: return # pruning: exceeded target
for i in range(start, len(candidates)):
[Link](candidates[i])
backtrack(i, current, remaining - candidates[i]) # reuse allowed
[Link]()
backtrack(0, [], target)
return result

■ Interview Tip: The backtracking template is always: (1) base case check, (2) loop through choices, (3) choose,
(4) recurse, (5) un-choose. Pruning (early return) is what separates an accepted solution from TLE.

## Sorting Algorithms

Interviewers expect you to know sort complexities cold. In practice, use Python's built-in sort (Timsort, O(n log n)).
Know merge sort and quicksort well enough to implement from scratch.

Operation Time Space

Bubble / Selection / Insertion Sort O(n²) avg O(1)

Merge Sort O(n log n) all cases O(n)

O(n log n) avg / O(n²)

Quick Sort worst O(log n)

Heap Sort O(n log n) all cases O(1)

Counting Sort O(n + k) O(k)

Python built-in sort (Timsort) O(n log n) O(n)

 # Merge Sort — stable, guaranteed O(n log n), divide and conquer
def merge_sort(arr):
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)

def merge(left, right):

result, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: [Link](left[i]); i += 1
else: [Link](right[j]); j += 1
[Link](left[i:]); [Link](right[j:])
return result

# Quick Sort — in-place, avg O(n log n), Lomuto partition

def quick_sort(arr, lo, hi):
if lo < hi:
pivot_idx = partition(arr, lo, hi)
quick_sort(arr, lo, pivot_idx - 1)
quick_sort(arr, pivot_idx + 1, hi)

def partition(arr, lo, hi):

pivot = arr[hi] # choose last element as pivot
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1

■ Interview Tip: Quick sort worst case (O(n²)) happens when pivot is always min/max — already sorted input.
Fix: random pivot selection. Merge sort is stable; quick sort is not. Know this distinction.

Binary Search — Sorted Array / Search Space

Eliminates half the search space each iteration. Works on any monotonic condition, not just sorted arrays. Template:
find the leftmost position where condition(mid) is True.
# Classic binary search
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2 # avoid integer overflow
if nums[mid] == target: return mid
elif nums[mid] < target: left = mid + 1
else: right = mid - 1
return -1

# Binary search on answer — find minimum speed to eat all bananas

import math
def min_eating_speed(piles, h):
def can_finish(speed):
return sum([Link](p / speed) for p in piles) <= h
left, right = 1, max(piles)
while left < right:
mid = (left + right) // 2
if can_finish(mid): right = mid # try smaller speed
else: left = mid + 1
return left
# Time: O(n log m) where m = max pile size

■ Interview Tip: Binary search on answer space: whenever a problem asks for minimum/maximum that satisfies
a condition, binary search the answer. Ask: 'Is the solution space monotonic?' If yes, binary search applies.

■ Quick Revision — Tier 4 — Recursion, Backtracking & Sorting

✓ Backtracking template: choose → recurse → un-choose. Add pruning to avoid TLE.
✓ Merge sort: O(n log n) guaranteed, stable, O(n) space. Quick sort: avg O(n log n), O(1) extra space.
✓ Quick sort worst case on sorted input — random pivot selection fixes this.
✓ Binary search: mid = left + (right-left)//2 to avoid overflow. Use left <= right for exact match.
✓ Binary search on answer: if problem asks for min/max satisfying a condition, the answer space is often searchable.
✓ Subsets: 2^n results. Permutations: n! results. Combinations: C(n,k) results. Know the output size.
 ■ TIER 5 — Trees & Binary Search Trees

## Binary Tree Fundamentals

A tree where each node has at most 2 children (left, right). Height h: O(log n) for balanced, O(n) worst case (skewed).
Most tree problems are solved with DFS (recursion) or BFS (queue).

Operation Time Space

Balanced tree height O(log n) —

Skewed tree height O(n) —

DFS traversal O(n) O(h) stack

O(w) queue (w = max

BFS traversal O(n) width)

class TreeNode:
def __init__(self, val=0, left=None, right=None):
[Link] = val; [Link] = left; [Link] = right

# DFS Traversals — all O(n) time, O(h) space

def inorder(root): # left → root → right (gives SORTED output for BST)
if not root: return []
return inorder([Link]) + [[Link]] + inorder([Link])

def preorder(root): # root → left → right (useful for tree serialization)

if not root: return []
return [[Link]] + preorder([Link]) + preorder([Link])

def postorder(root): # left → right → root (useful for deletion / size calc)
if not root: return []
return postorder([Link]) + postorder([Link]) + [[Link]]

# BFS / Level Order — use a queue

from collections import deque
def level_order(root):
if not root: return []
result, queue = [], deque([root])
while queue:
level = []
for _ in range(len(queue)): # process all nodes at this level
node = [Link]()
[Link]([Link])
if [Link]: [Link]([Link])
if [Link]: [Link]([Link])
[Link](level)
return result

Key Recursive Patterns

 # Maximum depth of binary tree
def max_depth(root):
if not root: return 0
return 1 + max(max_depth([Link]), max_depth([Link]))

# Check if tree is balanced (height difference <= 1 at every node)

def is_balanced(root):
def height(node):
if not node: return 0
lh = height([Link])
if lh == -1: return -1 # early exit: already unbalanced
rh = height([Link])
if rh == -1: return -1
if abs(lh - rh) > 1: return -1 # unbalanced at this node
return 1 + max(lh, rh)
return height(root) != -1

# Lowest Common Ancestor (LCA)

def lca(root, p, q):
if not root or root == p or root == q: return root
left = lca([Link], p, q)
right = lca([Link], p, q)
if left and right: return root # p and q are in different subtrees
return left or right # both in same subtree

■ Analogy: Tree recursion has a beautiful structure: almost every problem says 'solve for [Link], solve for [Link],
combine the answers.' That combination step — and the base case — is usually all you need. Trust the recursion.

## Binary Search Tree (BST)

A BST maintains the invariant: left subtree values < root < right subtree values. Inorder traversal of a BST always gives
a sorted sequence. All operations are O(h) — O(log n) balanced, O(n) worst case.

# BST Search — O(h)

def search_bst(root, val):
if not root or [Link] == val: return root
if val < [Link]: return search_bst([Link], val)
else: return search_bst([Link], val)

# Validate BST — pass allowed range down the tree

def is_valid_bst(root, min_val=float('-inf'), max_val=float('inf')):
if not root: return True
if not (min_val < [Link] < max_val): return False
return (is_valid_bst([Link], min_val, [Link]) and
is_valid_bst([Link], [Link], max_val))

# Kth Smallest in BST — inorder traversal (iterative to avoid O(n) space)

def kth_smallest(root, k):
stack, curr = [], root
count = 0
while stack or curr:
while curr: # go as far left as possible
[Link](curr); curr = [Link]
curr = [Link]() # process node
count += 1
if count == k: return [Link]
curr = [Link]
 ■ Interview Tip: Validate BST mistake: checking only that [Link] < [Link] < [Link] at each node is WRONG.
You need to pass min/max bounds down the tree. The left subtree's entire range must be below [Link].

■ Quick Revision — Tier 5 — Trees

✓ Inorder (L→Root→R): sorted output for BST. Preorder: serialization. Postorder: bottom-up calculation.
✓ BFS = level order using a deque. Lock in the 'for _ in range(len(queue))' pattern for level separation.
✓ Tree recursion mantra: base case (None → return 0/True/None) + solve left + solve right + combine.
✓ BST validation: pass (min_val, max_val) bounds down — checking only adjacent nodes is a classic bug.
✓ LCA: if both p and q found in different subtrees, current node is the LCA.
✓ Balanced tree: height O(log n). Skewed tree: height O(n). All tree operations are O(h).
 ■ TIER 6 — Heaps, Tries & Advanced Trees

## Heap (Priority Queue)

A heap is a complete binary tree satisfying the heap property: min-heap: parent ≤ children (root is minimum). Python's
heapq is a min-heap. Simulate max-heap by negating values. Used for: top-K problems, scheduling, Dijkstra's
algorithm.

Operation Time Space

Insert (heappush) O(log n) O(1)

Get min/max (peek) O(1) O(1)

Remove min (heappop) O(log n) O(1)

Build heap from list O(n) O(1)

Heap sort O(n log n) O(1)

import heapq

# Top K frequent elements — heap of size k

from collections import Counter
def top_k_frequent(nums, k):
freq = Counter(nums)
# Use min-heap of size k: keep only the k largest frequencies
return [Link](k, [Link](), key=[Link])

# K closest points to origin — max-heap simulation (negate distance)

def k_closest(points, k):
heap = []
for x, y in points:
dist = -(x*x + y*y) # negate for max-heap behavior
[Link](heap, (dist, x, y))
if len(heap) > k: # maintain heap of size k
[Link](heap)
return [(x, y) for (_, x, y) in heap]

# Merge K sorted lists — use heap with (value, list_index, node)

def merge_k_lists(lists):
dummy = curr = ListNode(0)
heap = []
for i, node in enumerate(lists):
if node: [Link](heap, ([Link], i, node))
while heap:
val, i, node = [Link](heap)
[Link] = node; curr = [Link]
if [Link]: [Link](heap, ([Link], i, [Link]))
return [Link]
# Time: O(n log k) where n = total nodes, k = number of lists

■ Interview Tip: Top-K problems: if K is small relative to n, a heap of size K is more efficient than sorting (O(n
log k) vs O(n log n)). Always ask the interviewer: 'Can K be large? Is the data streaming?' — this changes the
approach.

Two Heaps Pattern — Median of Data Stream

 # Maintain median in a stream using two heaps
class MedianFinder:
def __init__(self):
[Link] = [] # max-heap (negated) — lower half
[Link] = [] # min-heap — upper half

def add_num(self, num):

[Link]([Link], -num) # push to max-heap
# Balance: ensure every element in small <= every element in large
if [Link] and [Link] and (-[Link][0] > [Link][0]):
[Link]([Link], -[Link]([Link]))
# Balance sizes: small can be at most 1 larger than large
if len([Link]) > len([Link]) + 1:
[Link]([Link], -[Link]([Link]))
if len([Link]) > len([Link]):
[Link]([Link], -[Link]([Link]))

def find_median(self):
if len([Link]) > len([Link]): return -[Link][0]
return (-[Link][0] + [Link][0]) / 2

■ Analogy: Two heaps for median: imagine two sorted groups — everyone shorter than the median in one room
(max-heap: tallest at the door), everyone taller in another room (min-heap: shortest at the door). The median is always at
one of the two doors.

## Trie (Prefix Tree)

A Trie is a tree where each path from root to a node represents a string prefix. Each node can have up to 26 children
(one per letter). Used for: autocomplete, spell check, word search, prefix matching. Insert and search are O(m) where
m = word length.
class TrieNode:
def __init__(self):
[Link] = {} # char -> TrieNode
self.is_end = False # marks end of a valid word

class Trie:
def __init__(self):
[Link] = TrieNode()

def insert(self, word):

node = [Link]
for ch in word:
if ch not in [Link]:
[Link][ch] = TrieNode()
node = [Link][ch]
node.is_end = True

def search(self, word):

node = [Link]
for ch in word:
if ch not in [Link]: return False
node = [Link][ch]
return node.is_end

def starts_with(self, prefix):

node = [Link]
for ch in prefix:
if ch not in [Link]: return False
node = [Link][ch]
return True # is_end doesn't matter for prefix check
# Insert/Search/Prefix: O(m) time, O(m) space per word

■ Interview Tip: Trie insert/search is O(m) per word regardless of how many words are stored — this beats O(m
* n) for n words if you search repeatedly. Tries also allow prefix queries that a hash set can't do efficiently.

■ Quick Revision — Tier 6 — Heaps & Tries

✓ Min-heap in Python via heapq. Max-heap: negate values. heappush = O(log n), heappop = O(log n), peek = O(1).
✓ Top-K with heap of size K = O(n log k) — better than sorting O(n log n) when K << n.
✓ Two heaps (max-heap + min-heap) = O(log n) median updates. Classic hard interview pattern.
✓ Trie insert/search = O(m) per word. Enables prefix queries that hash sets can't do.
✓ [Link](k, iterable) and [Link](k, iterable) are built-in conveniences.
 ■ TIER 7 — Graphs

A graph is a set of vertices (nodes) connected by edges. Directed or undirected, weighted or unweighted, cyclic or
acyclic. Most graph problems are solved with DFS or BFS — know BOTH templates cold.

## Graph Representations

# Adjacency List — most common, O(V+E) space

from collections import defaultdict
graph = defaultdict(list)
graph[0].append(1); graph[0].append(2) # edge 0->1, 0->2

# Build from edge list

def build_graph(n, edges):
g = defaultdict(list)
for u, v in edges:
g[u].append(v)
g[v].append(u) # remove for directed graph
return g

# Adjacency Matrix — O(V²) space, O(1) edge lookup, good for dense graphs
# matrix[i][j] = 1 if edge from i to j exists

## DFS & BFS Templates

# DFS — iterative (stack) or recursive

def dfs(graph, start):
visited = set()
def _dfs(node):
[Link](node)
for neighbor in graph[node]:
if neighbor not in visited:
_dfs(neighbor)
_dfs(start)
return visited

# BFS — always iterative with a queue, guarantees shortest path (unweighted)

def bfs(graph, start):
from collections import deque
visited = {start}
queue = deque([start])
dist = {start: 0}
while queue:
node = [Link]()
for neighbor in graph[node]:
if neighbor not in visited:
[Link](neighbor)
dist[neighbor] = dist[node] + 1
[Link](neighbor)
return dist

Number of Islands — Classic DFS on Grid

 def num_islands(grid):
if not grid: return 0
rows, cols = len(grid), len(grid[0])
count = 0

def dfs(r, c):

# Out of bounds, water, or already visited
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '#' # mark visited by mutating grid
dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)

for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
dfs(r, c) # flood fill from this island
count += 1
return count
# Time: O(m*n) Space: O(m*n) for call stack in worst case

## Topological Sort (DAG)

Orders vertices in a Directed Acyclic Graph (DAG) such that for every edge u→v, u comes before v. Used for: course
scheduling, build order, task dependencies. Two approaches: Kahn's algorithm (BFS/in-degree) or DFS post-order.

■ Analogy: Topological sort is like getting dressed in the morning. You must put on socks before shoes, underwear
before pants. The valid ordering is not unique, but every dependency must be respected.

# Kahn's Algorithm — BFS with in-degree tracking

from collections import deque
def topo_sort(n, prerequisites):
graph = defaultdict(list)
in_degree = [0] * n
for course, prereq in prerequisites:
graph[prereq].append(course)
in_degree[course] += 1

# Start with all nodes that have no prerequisites

queue = deque([i for i in range(n) if in_degree[i] == 0])
order = []
while queue:
node = [Link]()
[Link](node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0: # all prereqs met
[Link](neighbor)

return order if len(order) == n else [] # empty = cycle detected

# Time: O(V+E) Space: O(V+E)

■ Interview Tip: Cycle detection in topological sort: if the result doesn't include all n nodes, a cycle exists
(some nodes were never added to the queue because their in-degree never reached 0).

## Shortest Path Algorithms

Dijkstra's — Weighted Graphs (Non-Negative Weights)
import heapq
def dijkstra(graph, start, n):
# graph[u] = [(weight, v), ...]
dist = [float('inf')] * n
dist[start] = 0
heap = [(0, start)] # (distance, node)

while heap:
d, u = [Link](heap)
if d > dist[u]: continue # stale entry — skip
for w, v in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
[Link](heap, (dist[v], v))
return dist
# Time: O((V+E) log V) Space: O(V+E)

Union-Find (Disjoint Set Union — DSU)

Efficiently tracks connected components. Supports union and find in near O(1) with path compression and union by
rank. Used for: cycle detection, MST (Kruskal's), connected components.

■ Analogy: Union-Find is like managing friend groups. Each person has a 'group representative'. When two people
become friends, you merge their groups by pointing one representative to the other. Path compression ensures finding
your rep is nearly instant.

class UnionFind:
def __init__(self, n):
[Link] = list(range(n)) # each node is its own parent
[Link] = [0] * n

def find(self, x): # find root with path compression

if [Link][x] != x:
[Link][x] = [Link]([Link][x]) # compress path
return [Link][x]

def union(self, x, y): # merge by rank

rx, ry = [Link](x), [Link](y)
if rx == ry: return False # already connected — cycle detected!
if [Link][rx] < [Link][ry]: rx, ry = ry, rx
[Link][ry] = rx
if [Link][rx] == [Link][ry]: [Link][rx] += 1
return True

# Use: detect cycle in undirected graph

def has_cycle(n, edges):
uf = UnionFind(n)
for u, v in edges:
if not [Link](u, v): # already in same component
return True # adding this edge creates a cycle
return False
# find/union: O(α(n)) ≈ O(1) amortized with path compression + union by rank

■ Interview Tip: Union-Find vs DFS for cycle detection: UF is faster in practice for dynamic edge insertion
(online). DFS is fine for static graphs. Kruskal's MST algorithm relies on UF to greedily add edges without
creating cycles.
■ Quick Revision — Tier 7 — Graphs
✓ BFS = shortest path (unweighted). DFS = connectivity, cycle detection, topological sort.
✓ Always track visited set to avoid infinite loops in cyclic graphs.
✓ Topological sort: Kahn's (BFS + in-degree). If result length < n, cycle exists.
✓ Dijkstra: min-heap + dist array. Skip stale heap entries (d > dist[u]).
✓ Union-Find: path compression + union by rank gives near O(1) per operation.
✓ Grid problems (islands, walls): 4-directional DFS/BFS. Mark visited by mutating grid or using a set.
 ■ TIER 8 — Dynamic Programming

Dynamic Programming (DP) solves a problem by breaking it into overlapping subproblems, solving each subproblem
once, and storing the result (memoization or tabulation). The key insight: if the problem has optimal substructure +
overlapping subproblems, DP applies. Two implementation styles: top-down (recursion + memo) and bottom-up
(iterative table).

■ Analogy: DP is like building a staircase by remembering which steps you've already built. Without DP, you'd rebuild
every step from scratch each time. With DP, you store completed steps and compose them. Fibonacci without memo =
O(2^n). With memo = O(n). Same problem, radically different performance.

## The DP Framework — 5 Steps

• 1. Define the state: what does dp[i] (or dp[i][j]) represent?

• 2. Write the recurrence: how does dp[i] relate to smaller subproblems?
• 3. Identify the base case: smallest valid input.
• 4. Determine iteration order: which subproblems must be solved first?
• 5. Extract the answer: which entry (or combination) gives the final answer?

## 1D DP Patterns

Climbing Stairs / Fibonacci-type

# Climb stairs: 1 or 2 steps. How many ways to reach step n?
def climb_stairs(n):
if n <= 2: return n
dp = [0] * (n + 1)
dp[1] = 1; dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2] # recurrence: arrive from i-1 or i-2
return dp[n]
# Space optimized: only need last 2 values -> O(1) space

House Robber — Cannot Take Adjacent Elements

# Rob non-adjacent houses for maximum profit
def rob(nums):
# dp[i] = max money robbing houses 0..i
prev2, prev1 = 0, 0
for n in nums:
# Either skip this house (prev1) or rob it (prev2 + n)
prev2, prev1 = prev1, max(prev1, prev2 + n)
return prev1
# Time: O(n) Space: O(1) — classic space optimization

Longest Increasing Subsequence (LIS)

 # LIS: dp[i] = length of LIS ending at index i
def length_of_lis(nums):
n = len(nums)
dp = [1] * n # each element is a LIS of length 1 by itself
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]: # can extend the subsequence
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# Time: O(n²) Space: O(n)

# O(n log n) version using patience sorting (binary search on tails array)
import bisect
def lis_fast(nums):
tails = [] # tails[i] = smallest tail of increasing subseq of length i+1
for n in nums:
pos = bisect.bisect_left(tails, n)
if pos == len(tails): [Link](n)
else: tails[pos] = n
return len(tails)

## 2D DP Patterns

Unique Paths on a Grid

# Count unique paths from top-left to bottom-right (only right/down moves)
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)] # first row and col are all 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1] # from above + from left
return dp[m-1][n-1]
# Time: O(m*n) Space: O(m*n) -> optimizable to O(n)

0/1 Knapsack — Classic DP

Given items with weights and values, maximize value without exceeding a capacity W. Each item can be taken or left
(0/1).

def knapsack(weights, values, W):

n = len(weights)
# dp[i][w] = max value using first i items with capacity w
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(W + 1):
# Option 1: don't take item i
dp[i][w] = dp[i-1][w]
# Option 2: take item i (if it fits)
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1])
return dp[n][W]
# Time: O(n*W) Space: O(n*W) -> O(W) with 1D rolling array

Longest Common Subsequence (LCS)

 # LCS: longest subsequence present in both strings (not necessarily contiguous)
def lcs(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]: # characters match
dp[i][j] = dp[i-1][j-1] + 1
else: # take best of skip either char
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
# Time: O(m*n) Space: O(m*n)

Coin Change — Unbounded Knapsack Variant

# Minimum coins to make amount — coins can be reused
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # base case: 0 coins to make amount 0
for amt in range(1, amount + 1):
for coin in coins:
if coin <= amt:
dp[amt] = min(dp[amt], dp[amt - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# Time: O(amount * len(coins)) Space: O(amount)

■ Interview Tip: DP state definition is the hardest part. Write it as a sentence: 'dp[i] is the minimum number of
coins needed to make amount i.' Once you have this, the recurrence usually follows naturally.

Edit Distance — Classic String DP

# Minimum operations (insert, delete, replace) to convert word1 to word2
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i # delete all chars in word1
for j in range(n+1): dp[0][j] = j # insert all chars of word2
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] # chars match, no op
else:
dp[i][j] = 1 + min(
dp[i-1][j], # delete from word1
dp[i][j-1], # insert into word1
dp[i-1][j-1] # replace
)
return dp[m][n]

■ Quick Revision — Tier 8 — Dynamic Programming

✓ DP applies when: optimal substructure + overlapping subproblems. Otherwise, try greedy.
✓ State definition is everything. Write it as a sentence before coding.
✓ 1D DP: Fibonacci-type, House Robber, LIS. 2D DP: Knapsack, LCS, Edit Distance, Unique Paths.
✓ Space optimization: 2D DP often reducible to 1D rolling array (saves O(n) space).
✓ Memoization (top-down) = recursion + cache. Tabulation (bottom-up) = iterative. Both are O(same).
✓ Coin change = unbounded knapsack (items reusable). 0/1 Knapsack = each item used at most once.
 ■ TIER 9 — Advanced Topics & Interview Meta

## Greedy Algorithms

Make the locally optimal choice at each step with the hope of finding a global optimum. Greedy works when a locally
optimal choice leads to a globally optimal solution (provable via exchange argument). Greedy doesn't work for 0/1
Knapsack but DOES work for Fractional Knapsack, interval scheduling, and Huffman coding.

# Meeting Rooms II — minimum rooms needed for all meetings

import heapq
def min_meeting_rooms(intervals):
[Link](key=lambda x: x[0]) # sort by start time
rooms = [] # min-heap of end times
for start, end in intervals:
if rooms and rooms[0] <= start: # a room is free
[Link](rooms, end)
else: # need a new room
[Link](rooms, end)
return len(rooms)

# Jump Game — can you reach the last index?

def can_jump(nums):
max_reach = 0
for i, jump in enumerate(nums):
if i > max_reach: return False # current position unreachable
max_reach = max(max_reach, i + jump)
return True
# Greedy: always track the furthest reachable index

■ Interview Tip: How to tell if greedy works: try to construct a counterexample. If you can't, it's likely correct.
Use an exchange argument: 'suppose a different choice is optimal — swapping to the greedy choice cannot
make it worse.'

## Bit Manipulation

Operations directly on binary representation. Extremely fast (single CPU instruction). Common in low-level coding,
competitive programming, and some FAANG interviews.
 # Key bit operations:
n & 1 # check if n is odd (last bit is 1)
n >> 1 # divide by 2 (right shift)
n << 1 # multiply by 2 (left shift)
n & (n-1) # clear the lowest set bit (Brian Kernighan's trick)
n ^ n == 0 # XOR of a number with itself is 0
a ^ b ^ a == b # XOR is its own inverse

# Count set bits (number of 1s)

def count_bits(n):
count = 0
while n:
n &= (n - 1) # removes lowest set bit each iteration
count += 1
return count

# Single Number — find the one element appearing once (all others appear twice)
def single_number(nums):
result = 0
for n in nums:
result ^= n # XOR cancels out pairs; only unique element remains
return result
# Time: O(n) Space: O(1) — no hash map needed

# Power of two check

def is_power_of_two(n):
return n > 0 and (n & (n-1)) == 0 # power of 2 has exactly one set bit

■ Interview Tip: XOR is the most powerful bit trick: a^a=0, a^0=a, XOR is commutative and associative. The
'find single number in array of pairs' is solved in O(n) time and O(1) space using XOR — impossible with any
other clean approach.

## Complexity Analysis — The Cheat Sheet

Your ability to state complexity immediately and confidently separates you from other candidates.

# Time Complexity Quick Reference:

O(1) — hash map lookup, array access, stack push/pop
O(log n) — binary search, heap operations, BST operations (balanced)
O(n) — single loop, sliding window, BFS/DFS, two pointers
O(n log n) — sorting, merge sort, heap sort, many divide-and-conquer
O(n²) — nested loops, bubble/insertion/selection sort, naive LIS
O(2^n) — subsets, backtracking (exponential choices per step)
O(n!) — permutations

# Space Complexity Quick Reference:

O(1) — in-place algorithms (two pointers, bit manipulation)
O(log n) — recursion depth of balanced BST, binary search
O(n) — hash maps, stacks, queues, storing n elements
O(n²) — 2D DP tables, adjacency matrix
O(h) — tree recursion stack (h = height; O(log n) balanced, O(n) skewed)

## Problem-Solving Framework (The Interview Meta)

What you say and how you approach the problem matters as much as the code itself.
• 1. Clarify: ask about input size, edge cases (empty input, single element, negatives), expected output, duplicates.
 • 2. Examples: trace through 2-3 small examples manually before coding.
• 3. Brute force first: state the naive O(n²) or O(2^n) solution. This shows you understand the problem.
• 4. Optimize: identify the bottleneck. 'The inner loop is redundant because...' Then propose the better approach.
• 5. Code: write clean, readable code. Use meaningful variable names. Explain as you go.
• 6. Verify: trace through your own test case after coding. Check edge cases explicitly.
• 7. Complexity: state time AND space complexity and justify it.

## Pattern Recognition Cheat Sheet

If the problem involves... Think...

Sorted array, find pair/target Two Pointers

Contiguous subarray with condition Sliding Window

Subarray sum / range query Prefix Sum + Hash Map

Matching brackets / spans Stack

Shortest path (unweighted) BFS

All paths / connectivity / cycle DFS

Shortest path (weighted) Dijkstra (min-heap)

Connected components, dynamic edges Union-Find (DSU)

Scheduling / ordering with dependencies Topological Sort

Top-K / K-th largest Heap (size K)

Prefix / autocomplete / word search Trie

Overlapping subproblems Dynamic Programming

Maximize/minimize with local choices Greedy

All combinations / subsets / permutations Backtracking

Hierarchy / parent-child Tree + Recursion / BFS

XOR / unique element Bit Manipulation

'Minimum rooms / intervals' Sort + Greedy + Heap

■ Quick Revision — Tier 9 — Advanced Topics & Meta

✓ Greedy: prove correctness via exchange argument. Works for interval scheduling, not 0/1 Knapsack.
✓ XOR tricks: a^a=0, a^0=a. Single unique number in paired array solved in O(n)/O(1).
✓ n&(n-1) clears the lowest set bit — use to count set bits in O(number of set bits).
✓ Always state brute force first, then optimize. Never jump to optimal without explaining the thought process.
✓ Time complexity must roll off the tongue: log n = halving, n log n = sort, 2^n = subsets, n! = perms.
✓ Pattern recognition is the real skill — most interview problems are variants of 15 core patterns.
 ■ Master Reference — Data Structure Complexities

Every row here is fair game in an interview. Know these by heart.

Data Structure Access Search Insert Delete Space

Array O(1) O(n) O(n) O(n) O(n)

Dynamic Array O(1) O(n) O(1) am O(n) O(n)

Singly Linked List O(n) O(n) O(1) O(1)* O(n)

Hash Map — O(1) O(1) O(1) O(n)

Hash Set — O(1) O(1) O(1) O(n)

Stack (list) O(n) O(n) O(1) O(1) O(n)

Queue (deque) O(n) O(n) O(1) O(1) O(n)

Min/Max Heap O(1)* O(n) O(log n) O(log n) O(n)

BST (balanced) O(log n) O(log n) O(log n) O(log n) O(n)

BST (skewed) O(n) O(n) O(n) O(n) O(n)

Trie O(m) O(m) O(m) O(m) O(ALPHABET*n)

Graph (adj list) — O(V+E) O(1) O(V+E) O(V+E)

* O(1) heap access = peek only (root). O(1) linked list delete = with a pointer to the node. 'am' = amortized. m = string
length. V/E = vertices/edges.