14. Interview Patterns Cheat Sheet

Signal → Pattern Mapping

You hear / see...	Pattern to use	Key data structure
Sorted array + pair sum	Two pointers	—
Subarray/substring + constraint	Sliding window	defaultdict(int)
Range sum on static array	Prefix sums	List
Max subarray sum	Kadane's	Two variables
Sorted + find position	Binary search	bisect
"Minimum X such that feasible(X)"	Binary search on answer	Feasibility function
Count/find with complement	Hash map lookup	dict
Frequency / group / top-K	Counter / heap	Counter, heapq
Matching brackets / undo	Stack	list
Next greater/smaller element	Monotonic stack	list
Level-by-level / minimum depth	BFS	deque
Any path / all paths / DFS	DFS / backtracking	Recursion + stack
Connected components	DFS / Union-Find	UnionFind
Shortest path (unweighted)	BFS	deque
Shortest path (weighted)	Dijkstra	heapq
Dependency order / cycle?	Topological sort	deque + in-degree
Optimal substructure + overlapping	Dynamic programming	1D/2D array + @cache
Prefix matching / autocomplete	Trie	TrieNode

---

Common Mistakes to Avoid

# ❌ Off-by-one in binary search
while l < r:
    mid = (l + r) // 2
    r = mid      # correct for lower-bound
    # r = mid - 1  ← wrong, skips mid when it could be the answer

# ❌ Forgetting to snapshot in backtracking
result.append(path)    # WRONG — path is mutable, will be empty at end
result.append(path[:]) # CORRECT — snapshot at this moment

# ❌ Mutating a list while iterating it
for x in arr:
    if condition: arr.remove(x)   # WRONG — skips elements

# ❌ Wrong recursion base case
def dfs(node):
    # missing: if not node: return
    for nb in graph[node]:        # crashes on None
        dfs(nb)

# ❌ Using list.pop(0) for a queue — O(n)
queue = []
queue.pop(0)           # WRONG — use deque.popleft()

from collections import deque
q = deque()
q.popleft()            # CORRECT — O(1)

---

Space/Time Complexity for Every Structure

Structure	Access	Search	Insert	Delete	Space
list (array)	$O(1)$	$O(n)$	$O(1)$†	$O(n)$	$O(n)$
dict / set	$O(1)$	$O(1)$	$O(1)$†	$O(1)$	$O(n)$
Sorted list	$O(1)$	$O(\log n)$	$O(n)$	$O(n)$	$O(n)$
Stack (list)	$O(1)$ top	—	$O(1)$†	$O(1)$	$O(n)$
Queue (deque)	$O(1)$ ends	—	$O(1)$	$O(1)$	$O(n)$
Heap (heapq)	$O(1)$ min	—	$O(\log n)$	$O(\log n)$	$O(n)$
BST (balanced)	—	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$
Trie	—	$O(L)$	$O(L)$	$O(L)$	$O(n \cdot L)$
Graph (adj list)	—	$O(V+E)$	$O(1)$	$O(V)$	$O(V+E)$

† Amortised

---

FAANG Difficulty Tiers

Tier	What it tests	Typical companies
Easy	Pattern recognition: two-sum, valid parens, reverse linked list	All FAANG (warm-up)
Medium	Combine patterns: sliding window + hash, BFS + visited, DP 1D	Google, Meta, Amazon
Hard	Advanced DP (2D, bitmask), graph algorithms, monotonic structures	Google, Jane Street

In FAANG interviews, the goal is usually one medium solved cleanly and explained well. A perfect medium beats a scrambled hard.

---

Last-Minute Checklist (Before Every Interview)

□ Ask clarifying questions before writing any code
□ State the brute force approach and its complexity first
□ Explain your optimised approach before coding
□ Name variables descriptively (not 'a', 'b', 'x')
□ Write the base case of recursion first
□ Walk through your code with the given example
□ Test edge cases: empty input, single element, all same, negative numbers
□ State time AND space complexity for your final solution
□ Ask: "Does this solution meet your expectations?"

---

End of Python DSA — FAANG Interview Prep — August 2026