Python Hacks for Coding Interviews

In an interview, every minute spent hand-writing a frequency loop or debugging an aliased grid is a minute not spent on the actual problem. This cheat sheet collects the Python idioms and standard-library tools that save that time, and ties each one back to the internals that make it correct and fast.

Integers and bits#

Python ints never overflow, so you can compute 2**100 directly and skip max-int overflow checks.

x = 5
print(bin(x))            # '0b101'
print((x >> 2) & 1)      # 1: is bit 2 set?
print(x & (x - 1))       # 4: clears the lowest set bit
print(x ^ x, x ^ 0)      # 0 5: a^a = 0 and a^0 = a ("Single Number")
print(int("101", 2))     # 5: parse binary without a loop

mask = 0
mask |= 1 << 3           # bitmask as a compact visited-set
print(mask >> 3 & 1)     # 1

Strings#

Strings are immutable, so += in a loop copies everything each time ($O(n^2)$ total). Collect pieces in a list and join once.

s = "hello"
parts = []
for ch in s:
    parts.append(ch.upper())   # amortised O(1)
print("".join(parts))          # 'HELLO'

print(s[::-1])                 # 'olleh': reversed copy
print(ord("b") - ord("a"))     # 1: char -> 0..25 index
print(chr(97))                 # 'a'

Counting and grouping#

Counter and defaultdict replace most hand-written counting and grouping loops.

from collections import Counter, defaultdict

counts = Counter("banana")
print(counts)                  # Counter({'a': 3, 'n': 2, 'b': 1})
print(counts.most_common(2))   # [('a', 3), ('n', 2)]
print(Counter("abc") == Counter("cab"))   # True: anagram check

groups = defaultdict(list)     # missing keys start as []
for word in ["eat", "tea", "tan"]:
    groups["".join(sorted(word))].append(word)
print(dict(groups))
# {'aet': ['eat', 'tea'], 'ant': ['tan']}

Sorting with tuple keys#

Python's sort is stable and compares tuples element by element, so one key= handles multi-criteria ordering.

data = [("Alice", 25), ("Bob", 20), ("Charlie", 25)]
data.sort(key=lambda x: (-x[1], x[0]))   # score desc, then name asc
print(data)   # [('Alice', 25), ('Charlie', 25), ('Bob', 20)]

(-25, "Alice") and (-25, "Charlie") tie on the first element, so the name breaks the tie.

Comprehensions and grids#

Comprehensions are shorter and usually faster than an equivalent for loop with append.

nums = [1, 2, 3, 4, 5, 6]
evens = [x for x in nums if x % 2 == 0]

rows, cols = 3, 4
grid = [[0] * cols for _ in range(rows)]   # independent rows
# NOT [[0] * cols] * rows: that repeats ONE row object

matrix = [[1, 2], [3, 4]]
flat = [v for row in matrix for v in row]        # [1, 2, 3, 4]
transposed = [list(r) for r in zip(*matrix)]     # [[1, 3], [2, 4]]
# rotate 90° clockwise: reverse the rows, then transpose
rotated = [list(r) for r in zip(*matrix[::-1])]  # [[3, 1], [4, 2]]
print(flat, transposed, rotated)

Heaps, deques and ordered dicts#

These three containers cover priority queues, BFS queues and LRU caches.

import heapq
from collections import deque, OrderedDict

nums = [5, 1, 8, 3]
heapq.heapify(nums)                 # O(n), min-heap in place
heapq.heappush(nums, 2)             # O(log n)
print(heapq.heappop(nums))          # 1: smallest first

# only a min-heap exists: negate for max
max_heap = [-x for x in [5, 1, 8]]
heapq.heapify(max_heap)
print(-max_heap[0])                 # 8

print(heapq.nlargest(2, [5, 1, 8, 3]))   # [8, 5]

q = deque([1, 2, 3])                # takes an iterable
q.append(4); print(q.popleft())     # 1: O(1) at both ends (BFS queue)

lru = OrderedDict(a=1, b=2, c=3)
lru.move_to_end("a")                # mark as most recently used
print(lru.popitem(last=False))      # ('b', 2): evict the oldest

Binary search with bisect#

bisect gives you a correct binary search on a sorted list without writing the loop yourself.

import bisect

a = [1, 3, 3, 5]
print(bisect.bisect_left(a, 3))   # 1: first index where 3 could go
print(bisect.bisect_right(a, 3))  # 3: index after the last 3
bisect.insort(a, 4)               # insert keeping order (O(n) shift)
print(a)                          # [1, 3, 3, 4, 5]

Memoisation#

lru_cache turns a plain recursive function into top-down DP with one line.

from functools import lru_cache
import sys

# the default (~1000) is low for deep DFS/DP
sys.setrecursionlimit(10_000)

@lru_cache(maxsize=None)           # or functools.cache (3.9+)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(80))                     # 23416728348467685

Arguments must be hashable, so pass tuples, not lists.

Quickselect for "k smallest / largest / closest"#

When you only need the top k (unordered), partition instead of sorting. Quicksort's partition step puts the pivot at its final index with smaller items on the left, so you recurse into one side only: $O(n)$ on average versus $O(n \log n)$ for a full sort.

import random

def k_smallest(nums, k):
    nums = nums[:]
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        r = random.randint(lo, hi)
        nums[r], nums[hi] = nums[hi], nums[r]
        pivot, i = nums[hi], lo
        for j in range(lo, hi):           # Lomuto partition
            if nums[j] < pivot:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
        nums[i], nums[hi] = nums[hi], nums[i]
        if i == k - 1:
            break
        if i < k - 1:
            lo = i + 1        # answer boundary is to the right
        else:
            hi = i - 1        # ... or to the left
    return nums[:k]

print(sorted(k_smallest([7, 2, 9, 4, 1, 8], 3)))   # [1, 2, 4]

Use it for Kth Largest Element, K Closest Points to Origin and Top K Frequent Elements (partition on frequency).

Small snippets worth memorising#

These short helpers come up often enough that it pays to know them by heart.

# Union-Find with path compression
parent = list(range(5))

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry:
        return False  # already connected: this edge makes a cycle
    parent[rx] = ry
    return True

print(union(0, 1), union(1, 0))   # True False

# Sudoku: which 3x3 box is (row, col) in?
row, col = 4, 7
print((row // 3) * 3 + col // 3)  # 5

Quick reference#

A summary of the idioms above, with the slower or buggier habit each one replaces.

Key takeaways#

• Lean on the standard library: Counter, defaultdict, deque, heapq, bisect, lru_cache.
• Join strings once; never += in a loop.
• Build grids with a comprehension so rows are independent.
• heapq is a min-heap; negate values for a max-heap.
• For "top k" questions, quickselect gives $O(n)$ average without a full sort.