Interview-Ready Reference — Arrays · Dicts · Sets · Strings · Collections · Builtins
# Creation a = [] # empty list a = [1, 2, 3] a = [0] * 5 # [0, 0, 0, 0, 0] a = list(range(5)) # [0, 1, 2, 3, 4] a = [x**2 for x in range(5)] # comprehension # ── Core mutations ───────────────────────────── a.append(x) # O(1) add to right a.pop() # O(1) remove+return from right a.pop(0) # O(n) remove from left — use deque! a.insert(2, x) # O(n) insert at index a.remove(x) # O(n) removes FIRST occurrence a.extend([4,5]) # += in place; faster than + (no copy) a.clear() # empties list, keeps object # ── Access & search ──────────────────────────── a[0], a[-1] # first, last — O(1) a[1:4] # slice [1,4) — returns new list a[::-1] # reversed copy a.index(x) # first index of x — raises if missing a.count(x) # how many times x appears — O(n) x in a # membership — O(n)! use set for O(1) # ── Sorting ───────────────────────────────────── a.sort() # in-place, stable, O(n log n) a.sort(reverse=True) a.sort(key=lambda x: x[1]) # sort by field a.sort(key=lambda x: (x[1], -x[0])) # multi-key sorted(a) # returns NEW list, original unchanged a.reverse() # in-place reverse — O(n) # ── Copy & misc ───────────────────────────────── b = a.copy() # shallow copy (same as a[:]) b = a[:] # also shallow copy — idiomatic len(a) # O(1) — stored as attribute a + [4,5] # concatenate — creates new list O(n) # ── 2D / Matrix ──────────────────────────────── matrix = [[0]*3 for _ in range(3)] # CORRECT bad = [[0]*3] * 3 # WRONG — same row object 3 times! transposed = list(zip(*matrix)) # elegant transpose flat = [x for row in matrix for x in row] # flatten
# Creation d = {} d = {'a': 1, 'b': 2} d = dict(a=1, b=2) d = dict(zip(keys, values)) # zip two lists → dict d = {k: v for k, v in pairs} # dict comprehension # ── Read ──────────────────────────────────────── d['a'] # KeyError if missing d.get('a') # None if missing — SAFE d.get('a', 0) # default value — very common 'a' in d # O(1) key membership # ── Write ─────────────────────────────────────── d['c'] = 3 # insert or overwrite d.setdefault('c', []).append(x) # init+append in one line d.update({'d': 4}) # merge another dict in d |= {'e': 5} # Python 3.9+ merge operator d.pop('a') # remove + return; KeyError if missing d.pop('a', None) # safe pop with default d.popitem() # remove+return last inserted (LIFO) # ── Iterate ───────────────────────────────────── d.keys() # view of keys d.values() # view of values d.items() # view of (k, v) tuples — use this most for k, v in d.items(): # idiomatic dict iteration pass # ── Group-by pattern (most powerful dict pattern) ─ from collections import defaultdict groups = defaultdict(list) for item in data: groups[key(item)].append(item) # no KeyError, no setdefault count = defaultdict(int) count[word] += 1 # starts at 0 automatically # ── Sorting a dict ────────────────────────────── sorted(d.items(), key=lambda x: x[1]) # sort by value sorted(d.items(), key=lambda x: -x[1]) # sort by value desc # Python 3.7+: dict preserves insertion order
# Creation s = set() # NOT {} — that's an empty dict! s = {1, 2, 3} s = set([1, 2, 2, 3]) # deduplication — {1, 2, 3} s = {x for x in arr if x > 0} # set comprehension # ── Mutation ──────────────────────────────────── s.add(x) # O(1) — no-op if already present s.remove(x) # O(1) — KeyError if missing s.discard(x) # O(1) — SAFE, no error if missing ✓ s.pop() # remove+return arbitrary element s.clear() # empty the set # ── Lookup ────────────────────────────────────── x in s # O(1) — the whole reason to use a set len(s) # O(1) # ── Set algebra — operator syntax ─────────────── a & b # intersection: elements in BOTH a | b # union: elements in EITHER a - b # difference: in a but NOT b a ^ b # symmetric diff: in one but NOT both a <= b # is a a subset of b? a >= b # is a a superset of b? # ── Set algebra — method syntax (accepts any iterable) ─ a.intersection(b) a.union(b) a.difference(b) a.isdisjoint(b) # True if no elements in common a.issubset(b) a.issuperset(b) # ── Frozenset (hashable, can be dict key) ─────── fs = frozenset([1,2,3]) d[fs] = "value" # regular set can't be a key! # ── Common patterns ───────────────────────────── seen = set() if x not in seen: seen.add(x) # visit-once pattern (DFS, dedup) dupes = [x for x in arr if arr.count(x) > 1] # slow dupes = list(set(x for x in arr if arr.count(x)>1)) # better
# Strings are immutable — every method returns a NEW string # ── Case & cleaning ───────────────────────────── s.upper() # "HELLO" s.lower() # "hello" s.title() # "Hello World" s.strip() # remove leading+trailing whitespace s.lstrip() / s.rstrip() s.strip('*') # strip specific characters # ── Search & check ────────────────────────────── s.find('x') # index or -1 (safe) s.index('x') # index or ValueError (raises) s.count('l') # occurrences of substring s.startswith('he') s.endswith('ld') 'sub' in s # substring check — O(n) but fast # ── Type checks (returns bool) ────────────────── s.isalpha() # all letters s.isdigit() # all digits s.isalnum() # letters or digits (no spaces/punct) s.isspace() # all whitespace s.isupper() / s.islower() # ── Split & join ──────────────────────────────── s.split() # split on whitespace, strips empties s.split(',') # split on delimiter s.split(',', maxsplit=2) # limit splits s.splitlines() # split on \n ','.join(['a','b','c']) # 'a,b,c' — O(n), use this not += ''.join(['h','i']) # 'hi' — build string from chars # ── Replace & format ──────────────────────────── s.replace('old', 'new') s.replace('o', '0', 2) # limit replacements f"Hello {name}, you are {age}" # f-string (preferred) f"{value:.2f}" # format float to 2 decimal places f"{n:04d}" # zero-pad integer # ── Slicing & reversing ───────────────────────── s[1:4] # substring s[::-1] # reverse — 'hello' → 'olleh' s[::2] # every other char # ── Character ↔ integer ───────────────────────── ord('a') # 97 chr(97) # 'a' ord(c) - ord('a') # 0-25 index for lowercase letter # ── Building strings efficiently ──────────────── parts = [] for c in iterable: parts.append(c) result = ''.join(parts) # O(n) total — not O(n²) like +=
from collections import deque, Counter, defaultdict, namedtuple, OrderedDict # ── deque — double-ended queue ─────────────────── # O(1) on BOTH ends. list.pop(0) is O(n) — always prefer deque for queues d = deque() d = deque([1,2,3]) d = deque(maxlen=3) # circular buffer — auto-evicts oldest d.append(x) # push right — O(1) d.appendleft(x) # push left — O(1) d.pop() # pop right — O(1) d.popleft() # pop left — O(1) ← use for BFS! d.extend([4,5]) # extend right d.extendleft([0,-1]) # extend left (note: reverses order) d.rotate(1) # rotate right by 1 (last→first) d.rotate(-1) # rotate left by 1 d[0], d[-1] # peek without removing — O(1) len(d) # O(1) # Use as STACK: append + pop # Use as QUEUE: append + popleft # ── Counter ───────────────────────────────────── c = Counter("aabbccc") # Counter({'c':3,'a':2,'b':2}) c = Counter([1,1,2,3]) c = Counter({'a':3, 'b':1}) c['x'] # 0 (not KeyError!) for missing keys c.most_common(2) # [('c',3),('a',2)] — top 2 c.most_common()[:-3:-1] # least common 2 list(c.elements()) # reconstruct with repetitions c.total() # sum of all counts (Python 3.10+) # Counter arithmetic (very useful!): Counter("aab") + Counter("abb") # add counts Counter("aab") - Counter("ab") # subtract, floor 0 Counter("aab") & Counter("abb") # min of each count Counter("aab") | Counter("abb") # max of each count # ── defaultdict ───────────────────────────────── dd = defaultdict(list) # missing key → [] dd = defaultdict(int) # missing key → 0 dd = defaultdict(set) # missing key → set() dd = defaultdict(lambda: [0]*26) # missing key → custom # ── namedtuple ────────────────────────────────── Point = namedtuple('Point', ['x', 'y']) p = Point(3, 4) p.x, p.y # named access AND index access p[0], p[1] # still a tuple underneath
import heapq # Python ONLY has min-heap. Negate values for max-heap. # Heap = list; heapq mutates it in place. # ── Build ──────────────────────────────────────── h = [] heapq.heappush(h, 3) # O(log n) heapq.heapify(lst) # convert list in-place — O(n)! # ── Access ─────────────────────────────────────── h[0] # peek minimum — O(1) heapq.heappop(h) # pop minimum — O(log n) heapq.heapreplace(h, val) # pop min + push val — 1 op, faster heapq.heappushpop(h, val) # push val then pop min — 1 op # ── Convenience ───────────────────────────────── heapq.nlargest(3, lst) # O(n log k) — better than sort for small k heapq.nsmallest(3, lst) # O(n log k) heapq.nlargest(3, lst, key=lambda x: x[1]) # with key function # ── Max-heap trick ─────────────────────────────── heapq.heappush(h, -val) # negate on push -heapq.heappop(h) # negate on pop # ── Tuple heaps (priority queues) ─────────────── # Tuples compared element-by-element; first element = priority heapq.heappush(h, (priority, value)) heapq.heappush(h, (0, 'urgent')) heapq.heappush(h, (5, 'low')) heapq.heappop(h) # (0, 'urgent') — lowest priority first # Tie-breaking: add a counter to avoid comparing values import itertools counter = itertools.count() heapq.heappush(h, (priority, next(counter), value)) # ── K-th largest (keep a min-heap of size k) ──── def kth_largest(nums, k): h = nums[:k] heapq.heapify(h) # O(k) for n in nums[k:]: if n > h[0]: heapq.heapreplace(h, n) # evict smallest, add n return h[0] # smallest of the k largest
# ── enumerate — index + value together ────────── for i, val in enumerate(arr): # 0-indexed pass for i, val in enumerate(arr, 1): # 1-indexed pass d = dict(enumerate(arr)) # {0:a, 1:b, 2:c, ...} # ── zip — pair up iterables ───────────────────── for a, b in zip(list1, list2): # stops at shortest pass for a, b in zip(s, s[1:]): # sliding window pairs pass list(zip(*matrix)) # transpose 2D matrix dict(zip(keys, values)) # build dict from two lists # zip_longest fills shorter with a fill value from itertools import zip_longest for a, b in zip_longest(l1, l2, fillvalue=0): pass # ── map and filter ─────────────────────────────── list(map(int, ['1','2','3'])) # convert types list(map(lambda x: x*2, arr)) # apply fn to each list(filter(lambda x: x>0, arr)) # keep truthy results # Prefer list comprehensions — more readable: [x*2 for x in arr] # equivalent to map [x for x in arr if x > 0] # equivalent to filter # ── any / all — short-circuit evaluation ──────── any(x > 0 for x in arr) # True if ANY element > 0 all(x > 0 for x in arr) # True if ALL elements > 0 any(c.isdigit() for c in s) # string contains a digit? # ── Numeric builtins ───────────────────────────── abs(-5) # 5 pow(2, 10) # 1024 pow(2, 10, 1000) # 2^10 mod 1000 — O(log n)! divmod(17, 5) # (3, 2) — quotient and remainder round(3.14159, 2) # 3.14 # ── min / max with key ─────────────────────────── min(arr) max(arr) min(arr, key=lambda x: x[1]) # min by second element max(d, key=d.get) # key with highest dict value min(3, 7, 2) # works on multiple args too # ── Infinity as sentinel ───────────────────────── float('inf') # larger than any number float('-inf') # smaller than any number # ── Type conversion ────────────────────────────── int('42'), str(42), float('3.14') bin(10), hex(255), oct(8) # '0b1010', '0xff', '0o10' int('1010', 2) # binary string → int: 10
from itertools import ( product, permutations, combinations, combinations_with_replacement, accumulate, groupby, chain, cycle, islice, repeat ) # ── Combinatorics ──────────────────────────────── list(permutations([1,2,3])) # all 6 orderings (tuples) list(permutations('ABC', 2)) # 2-length permutations list(combinations([1,2,3], 2)) # [(1,2),(1,3),(2,3)] no repeats list(combinations_with_replacement('AB', 2)) # [AA, AB, BB] list(product([0,1], repeat=3)) # all 3-bit strings (8 tuples) list(product('AB', 'xy')) # cartesian product: Ax Ay Bx By # ── accumulate — running computation ──────────── list(accumulate([1,2,3,4])) # [1,3,6,10] prefix sums list(accumulate([1,2,3], max)) # [1,2,3] running max list(accumulate([1,2,3], lambda a,b: a*b)) # [1,2,6] running product # ── chain — flatten one level ──────────────────── list(chain([1,2], [3,4], [5])) # [1,2,3,4,5] list(chain.from_iterable([[1,2],[3,4]])) # flatten nested # ── cycle & repeat ────────────────────────────── list(islice(cycle([1,2,3]), 7)) # [1,2,3,1,2,3,1] list(repeat(0, 5)) # [0,0,0,0,0] — lazy [0]*5 # ── Sorting patterns ───────────────────────────── # Multi-key sort arr.sort(key=lambda x: (x[1], -x[0])) # by [1] asc, [0] desc sorted(words, key=lambda w: (w.lower(), w)) # case-insensitive sorted(words, key=len) # by length sorted(words, key=lambda s: s[::-1]) # by reversed string # bisect — binary search on sorted list import bisect bisect.bisect_left(nums, x) # leftmost position x could insert bisect.bisect_right(nums, x) # rightmost position x could insert bisect.insort(nums, x) # insert x maintaining sort order # bisect_left = first index where nums[i] >= x (lower bound) # bisect_right = first index where nums[i] > x (upper bound) # functools.reduce from functools import reduce reduce(lambda a,b: a*b, [1,2,3,4]) # 24 — running accumulation # functools.lru_cache — memoization decorator from functools import lru_cache @lru_cache(maxsize=None) def fib(n): if n <= 1: return n return fib(n-1) + fib(n-2) # now O(n), was O(2^n)
# ── Tuple ──────────────────────────────────────── # Immutable, hashable, can be dict key/set member t = (1, 2, 3) t = 1, 2, 3 # parentheses optional t = (1,) # singleton — trailing comma required! t.count(x), t.index(x) # only two methods — immutable! # ── Unpacking ──────────────────────────────────── a, b = b, a # swap — no temp variable needed a, b, c = [1, 2, 3] first, *rest = [1,2,3,4] # first=1, rest=[2,3,4] *init, last = [1,2,3,4] # init=[1,2,3], last=4 a, *_, z = [1,2,3,4,5] # a=1, z=5, middle discarded (a, b), c = (1, 2), 3 # nested unpacking # ── Walrus operator := (Python 3.8+) ──────────── # Assign AND use in same expression while chunk := f.read(8192): # read until empty process(chunk) if (n := len(a)) > 10: # avoid computing len twice print(f"list is {n} items") # ── Conditional expression (ternary) ──────────── val = x if condition else y result = a or b # b if a is falsy — common default pattern result = a and b # b if a is truthy # ── Falsy values to memorize ───────────────────── # False, None, 0, 0.0, '', [], {}, set(), () if not arr: pass # empty list check — Pythonic # ── is vs == ───────────────────────────────────── a == b # value equality a is b # identity (same object in memory) x is None # ALWAYS use 'is' for None, True, False slow.next is fast.next # linked list cycle check — must use 'is' # ── range tricks ───────────────────────────────── range(5) # 0,1,2,3,4 range(1, 6) # 1,2,3,4,5 range(10, 0, -1) # 10,9,...,1 range(0, 10, 2) # 0,2,4,6,8 list(reversed(range(5))) # [4,3,2,1,0] # ── Comprehension patterns ─────────────────────── {k: len(v) for k, v in d.items()} # transform dict {v: k for k, v in d.items()} # invert dict (assumes unique vals) [x for row in grid for x in row] # flatten 2D [[row[i] for row in grid] for i in range(len(grid[0]))] # transpose
# ── LIST ───────────────────────────────────────── # append/pop right: O(1) amortized # insert/pop left: O(n) — use deque! # index access: O(1) # search (in): O(n) # sort: O(n log n) # slice: O(k) where k = slice length # ── DICT / SET ─────────────────────────────────── # get/set/delete: O(1) average # membership (in): O(1) average ← this is why you use them # iteration: O(n) # set operations &|−: O(min(a,b)) or O(len(a)+len(b)) # ── STRING ─────────────────────────────────────── # index/slice: O(k) # concatenation s+t: O(n+m) — creates new string # join: O(n) total — always prefer join # find/count/in: O(n) substring search # split: O(n) # ── DEQUE ──────────────────────────────────────── # append/pop both ends: O(1) # index access [i]: O(n) — not like list! # ── HEAP ───────────────────────────────────────── # heappush/heappop: O(log n) # heapify: O(n) ← not O(n log n)! # peek (h[0]): O(1) # nlargest/nsmallest: O(n log k) # ── DECISION GUIDE ─────────────────────────────── # Need O(1) membership? → set # Need O(1) key→value lookup? → dict # Need O(1) on both ends? → deque # Need min/max efficiently? → heap # Need sorted order? → sort + bisect # Need to count frequencies? → Counter # Need graph adjacency? → defaultdict(list) # Need hashable collection? → tuple or frozenset # ── n² → n transformations ─────────────────────── # Two nested loops checking pairs → hash the complement # Sorted array + two conditions → two pointers # "Next greater element" → monotonic stack # Subarray sum = k → prefix sum + hash # "Is X reachable?" → BFS / DFS + visited set # Repeated subproblem computation → memoize with @lru_cache