Study Guide [DS/A]

Core Data Structures

# Lists
arr = [1, 2, 3]
arr.append(4)
last = arr.pop()          # removes and returns last
arr[0]                    # first element
arr[-1]                   # last element
arr[1:3]                  # slice: index 1 inclusive to 3 exclusive
arr[::-1]                 # reversed copy
len(arr)

# Sets — O(1) average membership
s = {1, 2, 3}
empty_set = set()
s.add(4)
s.discard(2)              # no error if missing; .remove() raises KeyError
if 3 in s: ...
unique_vals = set(arr)

# Dicts
mp = {'a': 1, 'b': 2}
mp['c'] = 3
val = mp.get('d', 0)      # 0 if 'd' not in mp — no KeyError
if 'a' in mp: ...
del mp['a']

# Tuples — immutable; hashable (can be dict keys or set members)
t = (1, 2, 3)
t[0]
list(t)                   # convert to list
tuple([1, 2, 3])          # convert from list

Iteration Patterns

# Arrays — prefer enumerate over range(len(...))
for x in arr: ...
for i in range(len(arr)): ...
for i, x in enumerate(arr): ...      # index + value together
for x in reversed(arr): ...

# range(start, stop, step) — stop is exclusive
range(5, 10)                          # 5, 6, 7, 8, 9
range(0, 10, 2)                       # 0, 2, 4, 6, 8
range(10, 0, -1)                      # 10, 9, ..., 1 — count down

# Dicts
for k in mp: ...                      # keys
for v in mp.values(): ...
for k, v in mp.items(): ...           # key + value (most common)

# Sets — order not guaranteed
for x in s: ...
for x in sorted(s): ...              # if you need a stable order

2D Grids

# Initialize — m rows of n columns
rows, cols = 3, 4
grid = [[0] * cols for _ in range(rows)]   # CORRECT — independent rows
# bad_grid = [[0] * cols] * rows           # WRONG — all rows are the same object

# Iterate by index
for r in range(rows):
    for c in range(cols):
        val = grid[r][c]

# Iterate with enumerate (index + value)
for r, row in enumerate(grid):
    for c, val in enumerate(row):
        print(r, c, val)

# 4-direction deltas (up, down, left, right)
dirs_4 = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# 8-direction deltas (including diagonals)
dirs_8 = [(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)]

# Bounds check helper
rows, cols = len(grid), len(grid[0])
in_bounds = lambda r, c: 0 <= r < rows and 0 <= c < cols

for dr, dc in dirs_4:
    nr, nc = r + dr, c + dc
    if in_bounds(nr, nc):
        ...   # safe to access grid[nr][nc]

# Helper — all valid neighbor indices for (i, j), bounds-checked
def get_neighbors(i, j, rows, cols):
    neighbors = []
    for dr, dc in dirs_4:
        ni, nj = i + dr, j + dc
        if 0 <= ni < rows and 0 <= nj < cols:
            neighbors.append((ni, nj))
    return neighbors

Algorithm Templates

# Two pointers
l, r = 0, len(arr) - 1

# Sliding window
from collections import defaultdict
window = defaultdict(int)
l = 0
for r in range(len(s)):
    window[s[r]] += 1
    while invalid(window):
        window[s[l]] -= 1
        l += 1

# BFS — graph
from collections import deque
q = deque([start])
visited = {start}
while q:
    node = q.popleft()
    for nei in graph[node]:
        if nei not in visited:
            visited.add(nei)
            q.append(nei)

# BFS — 2D grid
from collections import deque
def bfs_grid(grid, start_r, start_c):
    rows, cols = len(grid), len(grid[0])
    dirs = [(-1,0),(1,0),(0,-1),(0,1)]
    in_bounds = lambda r, c: 0 <= r < rows and 0 <= c < cols
    q = deque([(start_r, start_c)])
    visited = {(start_r, start_c)}
    while q:
        r, c = q.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if in_bounds(nr, nc) and (nr, nc) not in visited:
                visited.add((nr, nc))
                q.append((nr, nc))

# DFS — iterative
stack = [start]
visited = {start}
while stack:
    node = stack.pop()
    for nei in graph[node]:
        if nei not in visited:
            visited.add(nei)
            stack.append(nei)

# Binary search — lo/hi loop
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Common Gotchas

# 1. Mutable default arguments — shared across all calls
def f_bad(x, arr=[]):      # BAD
    arr.append(x); return arr
def f_good(x, arr=None):   # GOOD
    if arr is None: arr = []
    arr.append(x); return arr

# 2. is vs == 
a, b = [1, 2], [1, 2]
a == b   # True  — same value
a is b   # False — different objects; use `is` only for None checks
if x is None: ...

# 3. Integer vs float division
5 / 2    # 2.5  (float)
5 // 2   # 2    (floor); use for index math: mid = (lo + hi) // 2

# 4. sort() vs sorted() — sort() mutates and returns None
arr.sort()              # in-place, returns None
new_arr = sorted(arr)   # returns new list
arr = arr.sort()        # BUG — arr is now None

# 5. Modifying a list while iterating over it
for x in arr:
    if condition(x): arr.remove(x)        # BAD — skips elements
new_arr = [x for x in arr if not condition(x)]  # GOOD

# 6. range() is end-exclusive
range(n)              # 0 .. n-1
range(start, end)     # start .. end-1
for i in range(1, n + 1): ...   # inclusive 1..n

# 7. any() / all()
if any(x > 0 for x in arr): ...   # at least one satisfies
if all(x >= 0 for x in arr): ...  # every element satisfies

# In the wild — array-based trie node, "does this child have anything left?"
# no dict-style falsy check available on a fixed-size list, so scan it
if all(c is None for c in child.children): ...   # child is a dead branch, safe to prune

collections.defaultdict

# Never KeyError — missing keys auto-initialize
graph = defaultdict(list)
graph['a'].append('b')        # no need to check if 'a' exists first

freq = defaultdict(int)
for c in "banana":
    freq[c] += 1              # starts at 0 automatically

# Value is your own class — pass the class itself, no lambda needed,
# as long as __init__ takes no required args (same idea as list/int above)
class Node:
    def __init__(self):
        self.children = defaultdict(Node)   # char -> Node, self-referential
        self.is_end = False

# Nested defaultdict — DOES need a lambda. defaultdict(list) evaluates
# immediately to one instance; that instance isn't callable, so the outer
# defaultdict needs a zero-arg factory that builds a fresh one each time.
groups = defaultdict(lambda: defaultdict(list))
groups['a']['b'].append(1)    # defaultdict(defaultdict(list)) would TypeError here

collections.Counter

from collections import Counter

c = Counter("banana")         # Counter({'a': 3, 'n': 2, 'b': 1})
c.most_common(2)              # [('a', 3), ('n', 2)]
c['z']                        # 0 — no KeyError

# Subtract two counters
c1 = Counter("abc")
c2 = Counter("ab")
c1 - c2                       # Counter({'c': 1})

collections.deque

from collections import deque

dq = deque([1, 2, 3])
dq.appendleft(0)    # O(1) — unlike list.insert(0, x)
dq.popleft()        # O(1) — unlike list.pop(0)

# BFS template
queue = deque([start])
while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        queue.append(neighbor)

heapq

import heapq

h = []
heapq.heappush(h, 3)
heapq.heappop(h)          # returns smallest

# Max heap — negate values
heapq.heappush(h, -5)
-heapq.heappop(h)         # returns 5

heapq.heapify(nums)       # in-place, O(n)
heapq.nlargest(3, nums)   # [5, 4, 3]

List Comprehensions · enumerate · zip

# List comprehension
squares = [x**2 for x in range(10) if x % 2 == 0]

# Grid init — DO NOT do [[0]*n]*m (aliasing bug!)
grid = [[0] * n for _ in range(m)]

# enumerate — index + value together
for i, val in enumerate(nums):
    print(i, val)

# zip — pair two lists, or transpose a matrix
for a, b in zip(list1, list2): ...
transposed = list(zip(*matrix))   # [(1,4),(2,5),(3,6)]

sorted() with key=

# Sort by second element
sorted(pairs, key=lambda x: x[1])

# Multi-key sort
sorted(words, key=lambda w: (len(w), w))

# Descending
sorted(nums, reverse=True)

# In-place
intervals.sort(key=lambda x: x[0])  # sort by start

dict.get(key, default)

d = {"a": 1}
d.get("b", 0)              # 0, no KeyError

# One-liner frequency count
freq = {}
freq[c] = freq.get(c, 0) + 1

String Methods

s = "  hello world  "
s.strip()               # "hello world"
s.split()               # ["hello", "world"]
" ".join(["a","b","c"]) # "a b c"
s[::-1]                 # reverse

"abc".isalpha()         # True
"123".isdigit()         # True
"abc123".isalnum()      # True

set Operations

a = {1, 2, 3}
b = {2, 3, 4}

a | b    # union       {1,2,3,4}
a & b    # intersect   {2,3}
a - b    # difference  {1}

# O(1) lookup — prefer over list for membership checks
seen = set()
if x not in seen:
    seen.add(x)

bisect

import bisect

nums = [1, 3, 4, 7, 9]

bisect.bisect_left(nums, 4)    # 2 — first index >= 4
bisect.bisect_right(nums, 4)   # 3 — first index > 4

bisect.insort(nums, 5)         # insert, keeping sorted — O(n)

# Check membership in O(log n)
idx = bisect.bisect_left(nums, x)
found = idx < len(nums) and nums[idx] == x

• Filter by "Google" tag, sort by frequency — do the top 20
• Complete Blind 75
• Complete NeetCode 150 (good explanations, more complete)
• Attempt at least one LeetCode weekly contest