Quick Reference
OOP — Class + Inheritance + Polymorphism
1class Parent:
2 def __init__(self, name):
3 self.name = name
4 def method(self): return "base"
5 def __str__(self): return f"Parent({self.name})"
6 def __repr__(self): return f"Parent('{self.name}')"
7
8class Child(Parent):
9 def __init__(self, name, extra):
10 super().__init__(name)
11 self.extra = extra
12 def method(self): return "override" # polymorphism
13 def __str__(self): return f"Child({self.name})"
OOP — @property (Read-Only / Write-Only)
1class X:
2 def __init__(self):
3 self._val = 0
4
5 @property # READ-ONLY
6 def val(self): return self._val
7
8 @property # WRITE-ONLY (getter raises)
9 def deposit(self): raise AttributeError
10 @deposit.setter
11 def deposit(self, amt): self._val += amt
filter / reduce
filter: keep items where fn returns True. reduce: fold list into one value.
1from functools import reduce
2
3valid = list(filter(lambda x: x[1] != "NA", data))
4
5total = reduce(lambda acc, x: acc + x, [1,2,3], 0) # 6
Build dict with reduce (mutable acc — faster):
1def collect(acc, item):
2 acc.setdefault(item[0], []).append(item[1])
3 return acc # ← MUST return acc!
4result = reduce(collect, data, {})
Immutable style (slower, but works in lambda):
1reduce(lambda acc, x: {**acc, x[0]: acc.get(x[0], 0) + x[1]}, data, {})
Sorting
1sorted(data, key=lambda x: (-x[1], x[0])) # desc by [1], asc by [0]
2# ⚠️ negative trick only works on numbers, not strings
3# sorted() → NEW list .sort() → in-place, returns None
@lru_cache (Memoization)
Turn exponential recursion into O(n). Args must be hashable (no lists — use tuples).
1from functools import lru_cache
2@lru_cache(maxsize=None)
3def fn(n): ...
defaultdict / Counter
1from collections import defaultdict, Counter
2
3groups = defaultdict(list) # auto [] on missing key
4counts = defaultdict(int) # auto 0 on missing key
5
6c = Counter([1,2,2,3,3,3]) # {3:3, 2:2, 1:1}
7c.most_common(2) # [(3,3), (2,2)]
String Methods
1" hello ".strip() # 'hello' both ends
2" hello ".lstrip() # 'hello ' left only
3" hello ".rstrip() # ' hello' right only
4"hello world".split() # ['hello', 'world'] by whitespace
5"a,b,c".split(",") # ['a', 'b', 'c'] by delimiter
6"a b c".split(" ") # ['a', 'b', '', 'c'] exact space (keeps empty!)
7# ⚠️ "".split() → [] but "".split(" ") → [""]
8", ".join(["a", "b", "c"]) # 'a, b, c' list → str
9"hello".replace("ll", "r") # 'hero'
10"hello".find("ll") # 2 (-1 if not found)
11"abcabc".count("a") # 2
12"hello".startswith("he") # True
13"file.py".endswith(".py") # True
14"hello".upper() # 'HELLO'
15"HELLO".lower() # 'hello'
16"hello world".title() # 'Hello World'
17"123".isdigit() # True
18"abc".isalpha() # True
19"abc123".isalnum() # True
1# ord / chr — character ↔ number
2ord('A') # 65 ord('a') # 97 ord('0') # 48
3chr(65) # 'A' chr(97) # 'a'
4ord('c') - ord('a') # 2 (letter → index)
5chr(ord('a') + 3) # 'd' (index → letter)
6chr((ord(c) - ord('a') + shift) % 26 + ord('a')) # Caesar cipher
List / Set / Dict Methods
1# LIST
2lst.append(x) # add to end (in-place)
3lst.insert(i, x) # insert at index (in-place)
4lst.pop() # remove + return last
5lst.pop(0) # remove + return first
6lst.remove(x) # remove first x (ValueError if missing)
7lst.index(x) # index of first x (ValueError if missing)
8lst.reverse() # in-place, returns None!
9lst.extend([1,2]) # add each item vs lst.append([1,2]) → nested
10
11# SET
12s.add(x) # add one
13s.discard(x) # remove (no error if missing)
14s.remove(x) # remove (KeyError if missing)
15a & b # intersection
16a | b # union
17a - b # difference
18a ^ b # symmetric difference
19
20# COMPREHENSIONS
21[x**2 for x in lst if x > 0] # list
22{k: v for k, v in pairs} # dict
23{x for x in lst} # set
24[x for row in matrix for x in row] # flatten 2D
Dict Tricks
1d.get(key, default) # no KeyError
2d.setdefault(key, []).append(item) # group without defaultdict
3counts[x] = counts.get(x, 0) + 1 # count without Counter
try / except
1try:
2 risky_thing()
3except ValueError: # catch specific
4 print("bad value")
5except (TypeError, KeyError): # catch multiple
6 print("wrong type or key")
7
8raise ValueError("insufficient balance") # throw your own
9raise AttributeError("write-only")
for-else
else runs only if loop finishes WITHOUT break. Useful for “search and fail” patterns.
1for item in lst:
2 if item == target:
3 print("found")
4 break
5else:
6 print("not found") # only runs if no break
enumerate
1for i, val in enumerate(lst): # i=0,1,2...
2for i, val in enumerate(lst, start=1): # i=1,2,3...
Formatting & Type Checks
1import math # for ceil, gcd, sqrt, inf
2f"${balance:.2f}" # 2 decimal places
3isinstance(x, (int, float)) # True for subclasses too
4type(x) == int # exact match only
Algorithms
Greedy vs Backtracking
“Can my local choice block someone downstream?” No → Greedy (O(N)). Yes → Backtracking (O(P^N)).
Backtracking — Wishful Thinking
Template: choose → recurse → undo. Assume the rest works (wishful thinking). If it didn’t, undo and try next.
1def backtrack(remaining, state):
2 if not remaining:
3 return state
4
5 curr = remaining[0]
6 for option in get_options(curr):
7 if not is_valid(option, state): continue
8 apply(option, state) # CHOOSE
9 result = backtrack(remaining[1:], state)
10 if result is not None: # wish granted
11 return result
12 undo(option, state) # UNDO
13 return None # all failed
Concrete example — student scheduling:
1def assign(students, classes):
2 def bt(rem, cls, res):
3 if not rem: return res
4 curr = rem[0]
5 for pref in curr["preferences"]:
6 if cls[pref] == 0: continue
7 res.setdefault(pref, []).append(curr["name"])
8 cls[pref] -= 1
9 ans = bt(rem[1:], cls, res)
10 if ans is not None: return ans
11 cls[pref] += 1; res[pref].pop()
12 return None
13 return bt(students, classes.copy(), {})
LCS (Longest Common Subsequence)
Find longest sequence present in both strings in same order. Exponential without memo.
1def lcs(t1, t2, acc=""):
2 if not t1 or not t2: return acc
3 if t1[0] == t2[0]:
4 return lcs(t1[1:], t2[1:], acc + t1[0])
5 p1 = lcs(t1, t2[1:], acc)
6 p2 = lcs(t1[1:], t2, acc)
7 return p1 if len(p1) > len(p2) else p2
Edit Distance (Levenshtein)
Min operations (insert/delete/replace) to turn s1 into s2. Use @lru_cache.
1from functools import lru_cache
2
3def edit_distance(s1, s2):
4 @lru_cache(maxsize=None)
5 def dp(i, j):
6 if i == 0: return j
7 if j == 0: return i
8 if s1[i-1] == s2[j-1]: return dp(i-1, j-1)
9 return 1 + min(dp(i-1, j), dp(i, j-1), dp(i-1, j-1))
10 return dp(len(s1), len(s2))
Wildcard Match
? = one char, * = any sequence (including empty).
1def match(pat, text):
2 if not pat and not text: return True
3 if not pat: return False
4 if pat[0] == '*':
5 return match(pat[1:], text) or (bool(text) and match(pat, text[1:]))
6 if not text: return False
7 if pat[0] == '?' or pat[0] == text[0]:
8 return match(pat[1:], text[1:])
9 return False
RLE (Run-Length Encoding)
Group consecutive identical elements into (key, count) pairs. Only the bucket function changes per problem.
1# Iterative
2def rle(seq, bucket=lambda x: x):
3 out = []
4 for x in seq:
5 key = bucket(x)
6 if out and out[-1][0] == key:
7 out[-1] = (key, out[-1][1] + 1) # tuple immutable → replace
8 else:
9 out.append((key, 1))
10 return out
11
12# Recursive
13def rle_rec(seq):
14 if not seq: return ()
15 rest = rle_rec(seq[1:])
16 if rest and rest[0][0] == seq[0]:
17 return ((seq[0], rest[0][1] + 1),) + rest[1:]
18 return ((seq[0], 1),) + rest
Two-Pointer Merge
Merge two sorted lists in O(M+N) without re-sorting.
1def merge(l1, l2, comp=lambda x, y: x - y):
2 p1 = p2 = 0; out = []
3 while p1 < len(l1) and p2 < len(l2):
4 if comp(l1[p1], l2[p2]) <= 0:
5 out.append(l1[p1]); p1 += 1
6 else:
7 out.append(l2[p2]); p2 += 1
8 out.extend(l1[p1:]); out.extend(l2[p2:])
9 return out
Dense Ranking (1-2-2-3)
Same score = same rank. Next different score = rank + 1 (no skip).
1def dense_rank(rows, key=lambda x: (-x[1], -x[2], -x[3], x[0])):
2 s = sorted(rows, key=key)
3 rank = 1; out = [(rank, *s[0])]
4 for i in range(1, len(s)):
5 if s[i][1:] != s[i-1][1:]: rank += 1
6 out.append((rank, *s[i]))
7 return out
Sliding Window (Moving Average)
O(n) with running sum: add new element, subtract oldest.
1def sma(prices, w):
2 out = [None] * (w - 1)
3 s = sum(prices[:w])
4 out.append(s / w)
5 for i in range(w, len(prices)):
6 s += prices[i] - prices[i - w]
7 out.append(s / w)
8 return out
2D Grid
Setup: find smallest N where N*N >= len(s), create grid.
1N = 1
2while N * N < len(s): N += 1
3grid = [[" "] * N for _ in range(N)]
Zigzag (odd rows reversed):
1row, col = i // N, i % N
2if row % 2 == 1: col = N - col - 1
Column fill right-to-left:
1for col_offset in range(N):
2 for row in range(N):
3 grid[row][N - col_offset - 1] = s[p]; p += 1
4 if p >= len(s): break
Formulas
Weighted average: sum(value x weight) / sum(weights). E.g. GPA.
1sum(v * w for v, w in data) / sum(w for _, w in data)
Trimmed mean: drop outliers then average. E.g. drop highest + lowest judge score.
1(sum(scores) - max(scores) - min(scores)) / (len(scores) - 2)
Euclidean distance: straight-line between two points.
1math.sqrt(sum((a - b) ** 2 for a, b in zip(p1, p2)))
Manhattan distance: grid-walking distance (no diagonals).
1sum(abs(a - b) for a, b in zip(p1, p2))
Prime check: trial division up to sqrt(n).
1def is_prime(n):
2 if n < 2: return False
3 for i in range(2, int(n**0.5) + 1):
4 if n % i == 0: return False
5 return True
GCD: built-in.
1math.gcd(a, b)
Newton’s method (sqrt): stop when guess stops changing.
1x_next = (x_prev + n / x_prev) / 2
2# converge when: abs(x_next - x_prev) < tol
“Top X% rounded up”: ceil, never round.
1top_k = math.ceil(total * percentage / 100)
Circular indexing: wraparound.
1day = i % 7
Diagonal detection: same diagonal = same sum or same difference.
1same_pos_diag = (r1 + c1) == (r2 + c2)
2same_neg_diag = (r1 - c1) == (r2 - c2)
90° rotation: given vector (dx, dy), the perpendicular is (-dy, dx) or (dy, -dx). Use to find square corners from one edge.
1dx, dy = x2 - x1, y2 - y1
2c1, d1 = (x2 - dy, y2 + dx), (x1 - dy, y1 + dx) # counterclockwise
3c2, d2 = (x2 + dy, y2 - dx), (x1 + dy, y1 - dx) # clockwise
Distance between two points:
1dist = ((x1 - x2)**2 + (y1 - y2)**2) ** 0.5
2# compare with tolerance: abs(dist - target) < 1e-9
Common Pitfalls
Banker’s rounding: round(2.5) = 2, not 3. Use math.ceil() for “round up”.
split gotcha: "".split(" ") = [""]. "".split() = [].
Shared reference: [[0]] * 3 — all rows are same list. Fix: [[0] for _ in range(3)].
Mutation during iteration: for n in nums: nums.remove(n) skips elements. Fix: list comp.
One-shot iterators: list(map(...)) second time = []. Wrap in list() immediately.
sorted vs sort: sorted(lst) = new list. lst.sort() = None (in-place).
Mutable default: def f(x, target=[]) — shared across calls. Fix: target=None.
+= on alias: y = x; y += [6] mutates x too. y = y + [6] is safe.
Shallow copy: a[:] — outer new, inner shared. Fix: [row[:] for row in a].
Single-element tuple: (1,) is tuple. (1) is just int.
str(n) for digits: left-to-right, handles 0. n%10 loop reverses + misses 0. Also: ch is string — int(ch) before math.
Tuple immutable: out[-1][1] += 1 crashes. Fix: out[-1] = (key, count+1).
Pre-Submit
1□ Edge: [], "", 0, None, single, all-same, negative, boundaries
2□ Return type matches spec (list? tuple? int? float?)
3□ return X, not print(X)
4□ Off-by-one: range(n) vs range(n+1), < vs <=
5□ Remove debug prints
6□ Didn't shadow: list, dict, sum, max, min, type
7□ Imports at top
8□ Fn signature matches spec
Regex
1import re
findall: all matches as list of strings. With groups (), returns only group content.
1re.findall(r'\d+', "age 25, score 99") # ['25', '99']
2re.findall(r'(\d+)-(\d+)', "12-34 56-78") # [('12','34'), ('56','78')]
search: first match anywhere. Returns match object or None — always check before .group().
1m = re.search(r'(\d+)-(\d+)', "call 123-456")
2if m:
3 m.group(0) # '123-456' (full match)
4 m.group(1) # '123' (first group)
sub / split:
1re.sub(r'\d+', 'X', "abc123def456") # 'abcXdefX'
2re.split(r'[,;\s]+', "a, b;c d") # ['a','b','c','d']
Greedy vs non-greedy:
1re.findall(r'<.+>', '<a><b>') # ['<a><b>'] greedy
2re.findall(r'<.+?>', '<a><b>') # ['<a>','<b>'] non-greedy
Pattern cheat:
| Pattern | Meaning |
|---|---|
\d / \D | digit / non-digit |
\w / \W | word char [a-zA-Z0-9_] / non-word |
\s / \S | whitespace / non-whitespace |
\b | word boundary |
. | any char except \n |
+ / * / ? | 1+ / 0+ / 0 or 1 |
{n} / {n,m} | exactly n / n to m |
^ / $ | start / end of string |
(...) | capture group |
(?=...) | lookahead (match without consuming) |
Mock Test Solutions
MT1 — Char Type Map (Recursive)
1def f(s):
2 if not s: return ""
3 c = s[0]
4 if c.lower() in "aeiou": pre = "V"
5 elif c.isalpha(): pre = "C"
6 else: pre = "-"
7 return pre + f(s[1:])
MT2 — DNA Grouping (Recursive RLE)
1def group_bases(dna):
2 if not dna: return ()
3 rest = group_bases(dna[1:])
4 if rest and rest[0][0] == dna[0]:
5 return ((dna[0], rest[0][1] + 1),) + rest[1:]
6 return ((dna[0], 1),) + rest
MT3 — Zigzag Grid
1def zigzag_fill(s):
2 if not s: return [[]]
3 N = 1
4 while N * N < len(s): N += 1
5 grid = [[" "] * N for _ in range(N)]
6 for i in range(len(s)):
7 row, col = i // N, i % N
8 if row % 2 == 1: col = N - col - 1
9 grid[row][col] = s[i]
10 return grid
MT4 — Avg Rating (Functional)
1from functools import reduce
2def avg_rating(votes):
3 valid = list(filter(lambda x: x[1] != "NA", votes))
4 def collect(acc, item):
5 acc.setdefault(item[0], {"t": 0, "c": 0})
6 acc[item[0]]["t"] += item[1]; acc[item[0]]["c"] += 1
7 return acc
8 temp = reduce(collect, valid, {})
9 return {k: v["t"]/v["c"] for k, v in temp.items()}
MT5 — Library Fines (OOP + Polymorphism)
1class MemberCard:
2 def __init__(self, mid):
3 self.member_id = mid; self.balance = 0.0
4 def top_up(self, amt): self.balance += amt; return self.balance
5 def fine_for(self, loan): return loan.days_overdue * 0.5
6 def pay_fine(self, loan):
7 fine = self.fine_for(loan)
8 if self.balance >= fine: self.balance -= fine
9 else: raise ValueError("insufficient")
10 return fine
11 def __str__(self): return f"MemberCard({self.member_id}): balance=${self.balance:.2f}"
12
13class StudentMemberCard(MemberCard):
14 def fine_for(self, loan): return super().fine_for(loan) * 0.5
15 def __str__(self): return f"StudentMemberCard({self.member_id}): balance=${self.balance:.2f}"
MT6 — BankAccount (@property)
1class BankAccount:
2 def __init__(self, owner):
3 self._owner = owner; self._balance = 0.0; self._pin = "0000"
4 @property
5 def owner(self): return self._owner
6 @property
7 def balance(self): return self._balance
8 @property
9 def deposit(self): raise AttributeError
10 @deposit.setter
11 def deposit(self, q): self._balance += q
12 @property
13 def pin(self): raise AttributeError
14 @pin.setter
15 def pin(self, q): self._pin = q
MT7 — Column Grid R→L
1def col_fill_rtl(s):
2 if not s: return [[]]
3 N = 1
4 while N * N < len(s): N += 1
5 grid = [["?"] * N for _ in range(N)]
6 p = 0
7 for i in range(N):
8 for j in range(N):
9 grid[j][N - i - 1] = s[p]; p += 1
10 if p >= len(s): return grid
11 return grid
MT8 — High/Low Rating (Functional)
Approach 1: named function (clean, O(n), recommended)
1from functools import reduce
2def high_low(records):
3 valid = list(filter(lambda x: type(x[1]) == int, records))
4 def collect(acc, item):
5 k = item[0]
6 prev = acc.get(k, (float("inf"), float("-inf")))
7 acc[k] = (min(prev[0], item[1]), max(prev[1], item[1]))
8 return acc
9 return reduce(collect, valid, {})
Approach 2: pure lambda (one-liner flex, O(n²) — new dict each step)
1from functools import reduce
2def high_low(records):
3 valid = list(filter(lambda x: type(x[1]) == int, records))
4 return reduce(lambda acc, item: {**acc, item[0]: (
5 min(acc.get(item[0], (float("inf"), float("-inf")))[0], item[1]),
6 max(acc.get(item[0], (float("inf"), float("-inf")))[1], item[1]),
7 )}, valid, {})
MT9 — Digit Parity RLE
1# Iterative
2def encode_parity(n):
3 out = []
4 for ch in str(n):
5 t = "E" if int(ch) % 2 == 0 else "O"
6 if out and t == out[-1][0]:
7 out[-1] = (t, out[-1][1] + 1)
8 else:
9 out.append((t, 1))
10 return out
11
12# Recursive
13def encode_parity_rec(n):
14 char = "E" if (n % 10) % 2 == 0 else "O"
15 if n < 10: return [(char, 1)]
16 rest = encode_parity_rec(n // 10)
17 if rest[-1][0] == char:
18 return rest[:-1] + [(char, rest[-1][1] + 1)]
19 return rest + [(char, 1)]