The complexities, templates and tricks that make Python the fastest language to write correct interview solutions in.

Complexity cheat sheet

Operation	list	dict / set	deque	heapq
Access by index / key	O(1)	O(1) avg	O(n) in the middle	—
Search `x in …`	O(n)	O(1) avg	O(n)	O(n)
Append / add at end	O(1)*	O(1) avg	O(1)	push O(log n)
Remove at front	O(n)	—	O(1)	pop min O(log n)
Insert / delete in middle	O(n)	O(1) avg (by key)	O(n)	—
Min / max	O(n)	O(n)	O(n)	O(1) peek
Sort	O(n log n)	—	—	—

* amortised. Strings are immutable: slicing and + copy — O(k).

Templates

Python — BFS

from collections import deque

def bfs(graph, start):
    """Shortest path (edges) from start in an unweighted graph."""
    dist = {start: 0}
    q = deque([start])
    while q:
        node = q.popleft()
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                q.append(nxt)
    return dist

graph = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}
print(bfs(graph, "a"))          # {'a': 0, 'b': 1, 'c': 1, 'd': 2}

Python — binary search

def lower_bound(nums, target):
    """First index with nums[i] >= target (len(nums) if none)."""
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

print(lower_bound([1, 3, 5, 7], 5), lower_bound([1, 3], 9))   # 2 2

Python — sliding window

def longest_unique_substring(s):
    seen, left, best = {}, 0, 0
    for right, ch in enumerate(s):
        if seen.get(ch, -1) >= left:
            left = seen[ch] + 1          # shrink past the duplicate
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

print(longest_unique_substring("abcabcbb"))   # 3

Python — Dijkstra

import heapq

def dijkstra(adj, src):
    dist = {src: 0}
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float("inf")):
            continue                      # stale entry
        for v, w in adj.get(u, []):
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

adj = {"a": [("b", 4), ("c", 1)], "c": [("b", 2)]}
print(dijkstra(adj, "a"))                 # {'a': 0, 'b': 3, 'c': 1}

Tricks that save time

Python

from functools import cache

@cache
def climb(n):                 # ways to climb n stairs taking 1 or 2 steps
    return 1 if n <= 1 else climb(n - 1) + climb(n - 2)

print(climb(50))              # 20365011074