Python Coding Interview Questions and Answers
24 hand-picked Python Coding interview questions with
detailed answers. Open the interactive version above to search, filter
by difficulty, run code, bookmark questions and track your progress.
Reverse a string and check whether it is a palindrome.
Reversing: the Pythonic way is the slice s[::-1] — a negative step walks the sequence backwards. Interviewers often also want the manual two-pointer version to check you understand the mechanics.
Palindrome: compare characters from both ends moving inward. s == s[::-1] is the one-liner, but the two-pointer loop is O(1) space and can exit early on the first mismatch, while the slice builds a whole new string.
The usual follow-up is to ignore case, spaces, and punctuation — normalise first with a generator expression rather than a regex.
# reverse
s[::-1] # Pythonic
"".join(reversed(s)) # equivalent
# palindrome — one-liner
def is_palindrome(s: str) -> bool:
return s == s[::-1]
# palindrome — two pointers, O(1) space, early exit
def is_palindrome(s: str) -> bool:
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
# follow-up: ignore case / spaces / punctuation
def is_palindrome_clean(s: str) -> bool:
cleaned = [c.lower() for c in s if c.isalnum()]
return cleaned == cleaned[::-1]
is_palindrome_clean("A man, a plan, a canal: Panama") # True
Check whether two strings are anagrams.
Two strings are anagrams if they contain the same characters with the same counts.
Two approaches:
- Sort both and compare —
sorted(a) == sorted(b). One line, but O(n log n). - Count characters —
Counter(a) == Counter(b). O(n) and the better answer.
Always check lengths first — an early len(a) != len(b) return is free and rules out most non-anagrams immediately.
from collections import Counter
# ✅ O(n)
def is_anagram(a: str, b: str) -> bool:
return len(a) == len(b) and Counter(a) == Counter(b)
# O(n log n) — acceptable but weaker
def is_anagram_sorted(a: str, b: str) -> bool:
return sorted(a) == sorted(b)
# manual, no stdlib — increment then decrement
def is_anagram_manual(a: str, b: str) -> bool:
if len(a) != len(b):
return False
counts = {}
for ch in a:
counts[ch] = counts.get(ch, 0) + 1
for ch in b:
if ch not in counts:
return False
counts[ch] -= 1
if counts[ch] == 0:
del counts[ch]
return not counts
is_anagram("listen", "silent") # True
Count the frequency of characters (or words) in a string.
collections.Counter is purpose-built for this and gives you most_common(n) for free. It's the answer an experienced Python developer gives.
Interviewers often ask for the manual version too. Two idiomatic options without Counter:
dict.get(key, 0) + 1 — no import, works everywhere.defaultdict(int) — cleaner when you're building up counts across a loop.
For word frequency, normalise first: lowercase and strip punctuation, otherwise "The" and "the," count as different words.
from collections import Counter, defaultdict
# ✅ the Pythonic answer
Counter("mississippi") # {'i': 4, 's': 4, 'p': 2, 'm': 1}
Counter("mississippi").most_common(2) # [('i', 4), ('s', 4)]
# manual — dict.get
def char_count(s: str) -> dict:
counts = {}
for ch in s:
counts[ch] = counts.get(ch, 0) + 1
return counts
# manual — defaultdict
def char_count_dd(s: str) -> dict:
counts = defaultdict(int)
for ch in s:
counts[ch] += 1
return dict(counts)
# word frequency — normalise first!
import re
def word_count(text: str) -> Counter:
words = re.findall(r"[a-z']+", text.lower())
return Counter(words)
word_count("The cat. The CAT!").most_common() # [('the', 2), ('cat', 2)]
Find the first non-repeating character in a string.
The naive approach counts occurrences of each character by rescanning the string — O(n²).
The efficient solution is two passes, O(n):
- Build a frequency count of every character.
- Walk the original string again and return the first character whose count is 1.
The second pass must iterate the string, not the dict — you need the original order. (Dicts do preserve insertion order since 3.7, so iterating the Counter also works here, but iterating the string makes the intent explicit and is safer to reason about.)
from collections import Counter
def first_unique(s: str) -> str | None:
counts = Counter(s) # pass 1 — O(n)
for ch in s: # pass 2 — original ORDER matters
if counts[ch] == 1:
return ch
return None
first_unique("swiss") # 'w'
first_unique("aabbcc") # None
# variant: return the INDEX
def first_unique_index(s: str) -> int:
counts = Counter(s)
for i, ch in enumerate(s):
if counts[ch] == 1:
return i
return -1
# ❌ O(n²) — rescans the string for every character
def first_unique_slow(s):
for ch in s:
if s.count(ch) == 1: # count() is O(n) EACH time
return ch
Remove duplicates from a list while preserving order.
list(set(items)) removes duplicates but destroys the order — sets are unordered. That's the trap in this question.
Correct approaches:
dict.fromkeys(items) — the cleanest one-liner. Dicts preserve insertion order (3.7+) and keys are unique, so this dedupes and keeps order in O(n).- Seen-set loop — explicit and works when you need custom key logic (dedupe objects by
id, say) or the items aren't hashable as-is.
Note both require hashable elements. For unhashable items (dicts, lists), dedupe on a derived key such as a tuple of fields or a JSON string.
items = [3, 1, 3, 2, 1, 5]
# ❌ loses order
list(set(items)) # [1, 2, 3, 5] — arbitrary order
# ✅ one-liner, order preserved, O(n)
list(dict.fromkeys(items)) # [3, 1, 2, 5]
# ✅ explicit seen-set — needed for custom keys
def dedupe(items, key=lambda x: x):
seen = set()
out = []
for item in items:
k = key(item)
if k not in seen:
seen.add(k)
out.append(item)
return out
# dedupe objects by a field
dedupe(users, key=lambda u: u.email)
# unhashable items — dedupe on a derived key
rows = [{"id": 1}, {"id": 2}, {"id": 1}]
dedupe(rows, key=lambda r: r["id"]) # [{'id': 1}, {'id': 2}]
Group a list of words into anagram groups.
The core idea: find a canonical key that all anagrams share. Comparing every word against every other is O(n²·k); hashing by a shared key is O(n·k log k).
Two key choices:
- Sorted letters —
"".join(sorted(word)). "eat", "tea", "ate" all become "aet". Simple, O(k log k) per word. - Character count tuple — a 26-length tuple of counts. O(k) per word, so asymptotically better for long words, but more code.
Then defaultdict(list) collects words under their key — no if key not in groups boilerplate.
from collections import defaultdict
def group_anagrams(words: list[str]) -> list[list[str]]:
groups = defaultdict(list)
for word in words:
key = "".join(sorted(word)) # canonical form
groups[key].append(word)
return list(groups.values())
group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
# O(k) key instead of O(k log k) — count tuple
def group_anagrams_counts(words):
groups = defaultdict(list)
for word in words:
counts = [0] * 26
for ch in word:
counts[ord(ch) - ord("a")] += 1
groups[tuple(counts)].append(word) # tuple is hashable, list is not
return list(groups.values())
Find two numbers in a list that add up to a target.
The brute force is two nested loops — O(n²).
The hash-map solution is O(n) in a single pass. For each number, compute its complement (target - num) and check whether you've already seen it. Store each number's index as you go, so the lookup is O(1).
The elegance is that you check and insert in the same pass — you never need to look ahead, because any valid pair will be completed by the later of its two elements.
If the list is already sorted, a two-pointer approach solves it in O(n) time with O(1) space: move the left pointer right to increase the sum, the right pointer left to decrease it.
# ✅ O(n) time, O(n) space — one pass
def two_sum(nums: list[int], target: int) -> tuple[int, int] | None:
seen = {} # value -> index
for i, num in enumerate(nums):
complement = target - num
if complement in seen: # O(1) lookup
return (seen[complement], i)
seen[num] = i
return None
two_sum([2, 7, 11, 15], 9) # (0, 1)
# sorted input → two pointers, O(1) space
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
total = nums[left] + nums[right]
if total == target:
return (left, right)
if total < target:
left += 1 # need a bigger sum
else:
right -= 1 # need a smaller sum
return None
# ❌ O(n²)
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target: ...
Find the length of the longest substring without repeating characters.
This is the canonical sliding window problem. Maintain a window [left, right] that always contains only unique characters.
The algorithm:
- Expand the window by moving
right forward one character at a time. - If the new character is already in the window, jump
left to just past its previous occurrence — not one step at a time. - Record the maximum window size seen.
Storing each character's last index in a dict is what makes the jump O(1). The naive version moves left forward one position at a time, which is still correct but slower.
Critical detail: only move left forward — max(left, last[ch] + 1). A stale index from before the current window would otherwise drag left backwards and break the invariant.
def longest_unique(s: str) -> int:
last = {} # char -> last index seen
left = 0
best = 0
for right, ch in enumerate(s):
if ch in last and last[ch] >= left:
left = last[ch] + 1 # jump past the duplicate
last[ch] = right
best = max(best, right - left + 1)
return best
longest_unique("abcabcbb") # 3 ('abc')
longest_unique("bbbbb") # 1 ('b')
longest_unique("pwwkew") # 3 ('wke')
longest_unique("abba") # 2 ← the case that breaks a naive version
# return the substring itself
def longest_unique_str(s: str) -> str:
last, left, best, start = {}, 0, 0, 0
for right, ch in enumerate(s):
if ch in last and last[ch] >= left:
left = last[ch] + 1
last[ch] = right
if right - left + 1 > best:
best, start = right - left + 1, left
return s[start:start + best]
Flatten an arbitrarily nested list.
One level deep is easy — itertools.chain.from_iterable or a double comprehension.
Arbitrary depth needs recursion: walk each element; if it's itself iterable, recurse into it, otherwise yield it.
Write it as a generator — yield from makes the recursion read cleanly and keeps memory constant, since nothing intermediate is materialised.
Two details that matter:
- Strings are iterable, so a naive check recurses into
"abc" forever-ish, yielding individual characters. Explicitly exclude str and bytes. - Deep nesting can hit Python's recursion limit (~1000). An explicit stack version avoids it.
from typing import Iterable
# ✅ recursive generator — arbitrary depth, constant memory
def flatten(nested):
for item in nested:
if isinstance(item, Iterable) and not isinstance(item, (str, bytes)):
yield from flatten(item) # ← strings excluded!
else:
yield item
list(flatten([1, [2, [3, [4, 5]], 6], 7])) # [1, 2, 3, 4, 5, 6, 7]
list(flatten([1, ["ab", [2]]])) # [1, 'ab', 2] ← not 'a','b'
# one level only
from itertools import chain
list(chain.from_iterable([[1, 2], [3, 4]])) # [1, 2, 3, 4]
[x for sub in nested for x in sub] # same, comprehension
# iterative — avoids the recursion limit on very deep input
def flatten_iter(nested):
stack = [iter(nested)]
while stack:
try:
item = next(stack[-1])
except StopIteration:
stack.pop()
continue
if isinstance(item, (list, tuple)):
stack.append(iter(item))
else:
yield item
Split a list into chunks of size n (batching).
Very common in real work — batching database inserts, API calls, or file writes so you don't send 100,000 rows in one request.
For a list: a range-with-step slice is the clean solution — items[i:i+n] for i in range(0, len(items), n). Slicing past the end is safe in Python, so the final short chunk needs no special handling.
For an arbitrary iterable (a generator, a database cursor, a file) you can't slice or take len() — use itertools.islice in a loop, which pulls lazily and works on infinite sources.
Python 3.12 added itertools.batched, which does exactly this.
# list — slicing past the end is safe, so no special last-chunk case
def chunks(items: list, n: int):
for i in range(0, len(items), n):
yield items[i:i + n]
list(chunks([1, 2, 3, 4, 5], 2)) # [[1, 2], [3, 4], [5]]
# ✅ any iterable — generators, cursors, files (no len(), no slicing)
from itertools import islice
def batched(iterable, n):
it = iter(iterable)
while batch := list(islice(it, n)): # walrus: stops on empty
yield batch
for batch in batched(db_cursor, 500):
bulk_insert(batch) # 500 rows per round trip
# Python 3.12+ — in the stdlib
from itertools import batched
list(batched(range(7), 3)) # [(0,1,2), (3,4,5), (6,)]
Find the second largest number in a list without sorting.
Sorting is O(n log n) and does more work than needed. A single pass tracking two values is O(n) and O(1) space.
Track largest and second. For each number:
- If it beats
largest, the old largest becomes second, and it becomes the new largest. - Else if it's between
second and largest, it becomes second.
The edge cases are the real test: duplicates of the maximum ([5, 5, 3] — is the answer 5 or 3?), fewer than two elements, and all-equal lists. Clarify whether "second largest" means the second distinct value — usually it does.
def second_largest(nums: list[int]) -> int | None:
largest = second = float("-inf")
for n in nums:
if n > largest:
second, largest = largest, n # demote the old max
elif largest > n > second: # strict → skips duplicates
second = n
return second if second != float("-inf") else None
second_largest([3, 1, 4, 1, 5, 9, 2]) # 5
second_largest([5, 5, 3]) # 3 (second DISTINCT)
second_largest([7]) # None
second_largest([4, 4, 4]) # None
# if duplicates should count: use >= in the elif
# stdlib shortcuts (fine to mention)
sorted(set(nums))[-2] # O(n log n)
import heapq
heapq.nlargest(2, set(nums))[-1] # O(n log k) — better for top-k
Merge two sorted lists into one sorted list.
Concatenating and re-sorting is O((n+m) log(n+m)) — it throws away the fact that both inputs are already sorted.
The two-pointer merge is O(n+m): compare the current head of each list, append the smaller, advance that pointer. When one list is exhausted, extend with the remainder of the other. This is exactly the merge step of merge sort.
For k lists, a min-heap generalises it to O(N log k) — and heapq.merge already does this in the stdlib, returning a lazy iterator so it works on huge or streaming inputs.
# ✅ two pointers — O(n + m)
def merge(a: list[int], b: list[int]) -> list[int]:
out = []
i = j = 0
while i < len(a) and j < len(b):
if a[i] <= b[j]: # <= keeps it STABLE
out.append(a[i]); i += 1
else:
out.append(b[j]); j += 1
out.extend(a[i:]) # one of these is empty
out.extend(b[j:])
return out
merge([1, 3, 5], [2, 3, 6]) # [1, 2, 3, 3, 5, 6]
# ❌ discards the existing order — O((n+m) log(n+m))
sorted(a + b)
# k sorted iterables, lazily — the stdlib answer
import heapq
list(heapq.merge([1, 4], [2, 5], [3, 6])) # [1, 2, 3, 4, 5, 6]
# works on huge/streaming sources without loading them
with open("a.txt") as fa, open("b.txt") as fb:
for line in heapq.merge(fa, fb):
out.write(line)
Rotate a list by k positions.
Slicing is the Pythonic solution: rotating right by k means the last k elements move to the front — items[-k:] + items[:-k]. O(n) time and O(n) space.
Two details that catch people out:
k can exceed the list length, so always take k %= len(items) first. Rotating a 5-element list by 7 is the same as by 2.k = 0 breaks the slice — items[-0:] is items[0:], the whole list, so you get the list duplicated. Guard against it, which the modulo also handles if you check after.
collections.deque has a built-in rotate() that's O(k) and mutates in place — the right choice if you rotate repeatedly.
For an in-place O(1)-space rotation, use the three-reversal trick: reverse the whole list, then reverse each of the two parts.
def rotate_right(items: list, k: int) -> list:
if not items:
return items
k %= len(items) # handles k > len AND negative k
if k == 0:
return items[:] # ⚠️ items[-0:] would duplicate the list
return items[-k:] + items[:-k]
rotate_right([1, 2, 3, 4, 5], 2) # [4, 5, 1, 2, 3]
rotate_right([1, 2, 3, 4, 5], 7) # same as k=2
rotate_right([1, 2, 3, 4, 5], 0) # [1, 2, 3, 4, 5]
# rotate LEFT
items[k:] + items[:k]
# deque — O(k), in place, best for repeated rotation
from collections import deque
d = deque([1, 2, 3, 4, 5])
d.rotate(2) # deque([4, 5, 1, 2, 3])
# in-place, O(1) space — three reversals
def rotate_in_place(a, k):
n = len(a); k %= n
a.reverse()
a[:k] = reversed(a[:k])
a[k:] = reversed(a[k:])
Group a list of dictionaries by a key (a SQL-style GROUP BY).
This is everyday backend work — turning a flat list of rows into a grouped structure.
defaultdict(list) is the clean solution: it creates the empty list on first access, so there's no if key not in groups boilerplate. One pass, O(n).
itertools.groupby is the trap. Unlike SQL's GROUP BY, it only groups consecutive equal keys — so you must sort by the same key first, or one logical group comes back as several fragments. Forgetting this produces silently wrong results, not an error. Since sorting costs O(n log n), defaultdict is usually the better choice anyway.
For aggregation rather than collection, use defaultdict(int) or defaultdict(Decimal) and accumulate.
from collections import defaultdict
from operator import itemgetter
orders = [
{"id": 1, "customer": "ana", "total": 250},
{"id": 2, "customer": "bob", "total": 100},
{"id": 3, "customer": "ana", "total": 75},
]
# ✅ O(n), no sort needed
groups = defaultdict(list)
for o in orders:
groups[o["customer"]].append(o)
# {'ana': [{...}, {...}], 'bob': [{...}]}
# aggregate instead of collect
totals = defaultdict(int)
for o in orders:
totals[o["customer"]] += o["total"]
# {'ana': 325, 'bob': 100}
# ⚠️ groupby groups CONSECUTIVE keys only — MUST sort first
from itertools import groupby
orders.sort(key=itemgetter("customer")) # required!
for customer, group in groupby(orders, key=itemgetter("customer")):
print(customer, [o["id"] for o in group])
# generic helper
def group_by(rows, key):
out = defaultdict(list)
for r in rows:
out[key(r)].append(r)
return dict(out)
group_by(orders, key=lambda o: o["customer"])
Sort a list of dictionaries by multiple fields, in mixed directions.
Single field: sorted(rows, key=itemgetter("age")). operator.itemgetter is faster than an equivalent lambda because it's implemented in C.
Multiple fields, same direction: return a tuple from the key function — tuples compare element by element, so itemgetter("dept", "name") sorts by dept then name.
Mixed directions is the interesting case, and there are two techniques:
- Negate the numeric field —
key=lambda r: (-r["score"], r["name"]) gives score descending, name ascending. Only works for numbers. - Two stable passes — sort by the least significant field first, then the most significant. Python's sort is stable, so ties from the second sort retain the first sort's order. This works for any type, including strings you can't negate.
Handle missing keys with r.get("field", default) — itemgetter raises KeyError, and a None in the mix raises TypeError on comparison.
from operator import itemgetter
employees = [
{"name": "ana", "dept": "eng", "score": 90},
{"name": "bob", "dept": "eng", "score": 95},
{"name": "cat", "dept": "ops", "score": 90},
]
# single field
sorted(employees, key=itemgetter("score"), reverse=True)
# multiple fields, same direction — tuple key
sorted(employees, key=itemgetter("dept", "name"))
# mixed: score DESC, name ASC — negate the number
sorted(employees, key=lambda r: (-r["score"], r["name"]))
# mixed with a STRING descending — negation impossible, use two stable passes
rows = sorted(employees, key=itemgetter("score")) # least significant
rows = sorted(rows, key=itemgetter("dept"), reverse=True) # most significant
# missing keys / None values
sorted(rows, key=lambda r: r.get("score", 0)) # default
sorted(rows, key=lambda r: (r.get("score") is None, r.get("score", 0))) # Nones last
Merge two dictionaries, including a deep/recursive merge of nested dicts.
Shallow merge: a | b (3.9+) or {**a, **b}. Later values win. Perfect for flat config overrides.
The problem: a shallow merge replaces nested dicts entirely rather than merging into them. If a has {"db": {"host": "x", "port": 5432}} and b has {"db": {"port": 6000}}, a shallow merge loses host completely. This is the classic config-loading bug.
Deep merge recurses: when the same key holds a dict in both inputs, merge those dicts too; otherwise the override wins.
Important: return a new dict rather than mutating the input. Mutating a shared defaults dict means the second call sees the first call's overrides — a genuinely nasty bug to track down.
# shallow — later wins
merged = defaults | overrides # 3.9+
merged = {**defaults, **overrides} # any version
# ⚠️ shallow merge REPLACES nested dicts
a = {"db": {"host": "localhost", "port": 5432}, "debug": False}
b = {"db": {"port": 6000}}
a | b # {'db': {'port': 6000}, ...} ← host is GONE
# ✅ deep merge — returns a NEW dict, never mutates the inputs
def deep_merge(base: dict, override: dict) -> dict:
out = dict(base) # copy, don't mutate
for key, value in override.items():
if (key in out
and isinstance(out[key], dict)
and isinstance(value, dict)):
out[key] = deep_merge(out[key], value) # recurse
else:
out[key] = value
return out
deep_merge(a, b)
# {'db': {'host': 'localhost', 'port': 6000}, 'debug': False} ✅ host kept
# layered config without merging at all
from collections import ChainMap
config = ChainMap(env_vars, config_file, defaults) # first match wins
Find the top K most frequent elements in a list.
Two steps: count, then select the top K.
Counter(items).most_common(k) does both in one line and is the answer to give first.
The complexity discussion is the real question. Sorting all distinct elements to take K of them is O(n log n) — wasteful when K is small. A min-heap of size K gives O(n log k): push each element, and pop the smallest whenever the heap exceeds K, so it always holds the K largest seen so far.
heapq.nlargest(k, ...) implements exactly that and is the practical choice. (Internally most_common(k) also uses nlargest when k is given — worth knowing.)
For genuinely huge or streaming data where you can't hold all counts, this becomes the Count-Min Sketch problem — approximate counts in sub-linear space.
from collections import Counter
import heapq
words = ["a", "b", "a", "c", "b", "a"]
# ✅ the one-liner — uses nlargest internally when k is given
Counter(words).most_common(2) # [('a', 3), ('b', 2)]
# explicit heap — O(n log k)
counts = Counter(words)
heapq.nlargest(2, counts.items(), key=lambda kv: kv[1])
# top-k objects by a field
heapq.nlargest(10, employees, key=lambda e: e.salary)
# ⚠️ most_common() with NO k sorts EVERYTHING — O(n log n)
Counter(words).most_common() # full sort
# manual min-heap of size k — the underlying idea
def top_k(nums, k):
heap = []
for n in nums:
heapq.heappush(heap, n)
if len(heap) > k:
heapq.heappop(heap) # drop the smallest → keeps k largest
return sorted(heap, reverse=True)
top_k([5, 1, 9, 3, 7], 3) # [9, 7, 5]
Write a decorator that takes arguments (e.g. a retry decorator).
A plain decorator is a function taking a function. A decorator with arguments needs three levels, because @retry(times=3) is called first and must return a decorator:
- Outer — takes the decorator's arguments, returns the decorator.
- Middle — takes the function, returns the wrapper.
- Inner (wrapper) — takes
*args, **kwargs and does the work.
@functools.wraps is mandatory. Without it the wrapper replaces the original function's __name__, __doc__, and signature — which breaks introspection, debugging, and any framework that inspects handlers (Flask route names collide, pytest fixtures misbehave, Sphinx docs go blank).
For a retry specifically: use exponential backoff with jitter, catch only specific exceptions, and re-raise after the final attempt rather than swallowing the error.
import functools, time, random
def retry(times=3, delay=1.0, exceptions=(Exception,)):
def decorator(func): # ← takes the function
@functools.wraps(func) # ← MANDATORY
def wrapper(*args, **kwargs): # ← does the work
last = None
for attempt in range(times):
try:
return func(*args, **kwargs)
except exceptions as e:
last = e
if attempt == times - 1:
raise # don't swallow the final failure
backoff = delay * (2 ** attempt)
time.sleep(backoff + random.uniform(0, backoff * 0.1)) # jitter
raise last
return wrapper
return decorator
@retry(times=3, delay=0.5, exceptions=(ConnectionError, TimeoutError))
def fetch(url):
return requests.get(url, timeout=5)
# without @wraps:
# fetch.__name__ → 'wrapper' ❌ breaks frameworks and debugging
# with @wraps:
# fetch.__name__ → 'fetch' ✅
# simple timing decorator (no arguments — two levels only)
def timed(func):
@functools.wraps(func)
def wrapper(*args, **kwargs):
start = time.perf_counter()
try:
return func(*args, **kwargs)
finally:
print(f"{func.__name__} took {time.perf_counter() - start:.3f}s")
return wrapper
Write a memoization decorator from scratch.
Memoisation caches a function's return value per argument set, so repeated calls with the same inputs are O(1) lookups. The classic demonstration is naive recursive Fibonacci, which goes from O(2ⁿ) to O(n).
Building it: a dict keyed by the arguments, wrapped in a closure. The key must be hashable, so use a tuple of args plus a frozen form of kwargs — a plain dict can't be a key.
In production use functools.lru_cache (or functools.cache in 3.9+, which is unbounded). It's C-implemented, thread-safe, has a bounded size so it can't leak, and exposes cache_info().
Two real caveats: the cache holds strong references to arguments and results, so an unbounded cache on a long-lived object is a memory leak; and memoisation is only valid for pure functions — caching something that reads a database or the clock returns stale data forever.
import functools
# from scratch
def memoize(func):
cache = {} # closure state
@functools.wraps(func)
def wrapper(*args, **kwargs):
key = (args, tuple(sorted(kwargs.items()))) # must be HASHABLE
if key not in cache:
cache[key] = func(*args, **kwargs)
return cache[key]
wrapper.cache = cache # expose for tests/clearing
return wrapper
@memoize
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
fib(100) # instant — without memoisation this is O(2^n)
# ✅ production: C-implemented, thread-safe, BOUNDED
@functools.lru_cache(maxsize=1024)
def parse_rule(text: str) -> Rule: ...
parse_rule.cache_info() # CacheInfo(hits=42, misses=8, maxsize=1024, currsize=8)
parse_rule.cache_clear()
@functools.cache # 3.9+, unbounded — careful with memory
def fib2(n): ...
# ❌ never memoize impure functions
@functools.cache
def get_user(user_id):
return db.query(user_id) # returns stale data forever after the first call
Write a custom context manager (both the class and the decorator form).
Two ways to write one:
- Class-based — implement
__enter__ (returns the value bound by as) and __exit__(exc_type, exc_val, tb). Best when the manager holds state or is reused. @contextlib.contextmanager — write a generator: everything before yield is setup, everything after is teardown. Much less code for simple cases.
The critical detail: use try/finally in the generator form. If the body raises, the exception propagates out of the yield, and without finally your teardown never runs — which defeats the entire purpose.
__exit__'s return value matters: returning True suppresses the exception. Return None/False (the default) to let it propagate. Accidentally returning a truthy value silently swallows every error in the block.
from contextlib import contextmanager
import time
# ✅ generator form — try/finally is ESSENTIAL
@contextmanager
def timer(label: str):
start = time.perf_counter()
try:
yield # body runs here
finally:
print(f"{label}: {time.perf_counter() - start:.3f}s") # always runs
with timer("query"):
run_report() # timing printed even if this raises
# yield a value to bind with `as`
@contextmanager
def transaction(conn):
txn = conn.begin()
try:
yield conn # bound by `as`
except Exception:
txn.rollback()
raise # don't swallow it
else:
txn.commit()
with transaction(conn) as c:
c.execute(sql)
# class form — for reusable/stateful managers
class Timer:
def __enter__(self):
self.start = time.perf_counter()
return self # what `as` binds
def __exit__(self, exc_type, exc_val, tb):
self.elapsed = time.perf_counter() - self.start
return False # ⚠️ True would SUPPRESS the exception
with Timer() as t:
work()
print(t.elapsed)
Process a file too large to fit in memory using generators.
f.read() or f.readlines() loads the whole file — fine for 10 MB, fatal for 10 GB.
Iterating the file object yields one line at a time in constant memory, because file objects are already lazy iterators.
The powerful pattern is a generator pipeline: chain small generators together, each transforming the stream. Nothing is materialised — data flows through one item at a time, and memory stays flat regardless of file size. It reads like a Unix pipe, and each stage is independently testable.
For fixed-size binary reads, loop on f.read(chunk_size) with the walrus operator until it returns empty.
# ❌ loads everything
lines = open("huge.log").readlines()
# ✅ constant memory — file objects are lazy iterators
with open("huge.log", encoding="utf-8") as f:
for line in f:
process(line)
# ✅ generator pipeline — each stage lazy, memory flat
def read_lines(path):
with open(path, encoding="utf-8") as f:
for line in f:
yield line.rstrip("\n")
def parse(lines):
for line in lines:
parts = line.split("\t")
if len(parts) == 3:
yield {"ts": parts[0], "level": parts[1], "msg": parts[2]}
def only_errors(records):
for r in records:
if r["level"] == "ERROR":
yield r
# compose — nothing runs until iterated, nothing held in memory
pipeline = only_errors(parse(read_lines("huge.log")))
for record in pipeline:
alert(record)
# count without materialising
error_count = sum(1 for _ in only_errors(parse(read_lines(path))))
# fixed-size binary chunks
with open("video.mp4", "rb") as f:
while chunk := f.read(8192):
upload(chunk)
Implement an LRU cache with O(1) get and put.
The requirement is O(1) for both operations, which rules out scanning for the least-recently-used item.
The classic solution combines two structures:
- A hash map for O(1) lookup by key.
- A doubly linked list for O(1) reordering — most recent at one end, least recent at the other. Doubly linked (not singly) because you must unlink a node in O(1) given only that node, which needs the previous pointer.
In Python, OrderedDict already is that structure — it's a dict plus a doubly linked list internally. move_to_end() and popitem(last=False) are both O(1), which makes the implementation about ten lines.
Even a plain dict works since 3.7 (insertion order is guaranteed): delete and reinsert to mark as recently used, and next(iter(d)) gives the oldest key.
Interviewers often want the manual linked-list version — say the OrderedDict answer first, then offer to write it from scratch.
from collections import OrderedDict
# ✅ OrderedDict IS a dict + doubly linked list
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.data = OrderedDict()
def get(self, key):
if key not in self.data:
return -1
self.data.move_to_end(key) # O(1) → most recent
return self.data[key]
def put(self, key, value):
if key in self.data:
self.data.move_to_end(key)
self.data[key] = value
if len(self.data) > self.cap:
self.data.popitem(last=False) # O(1) → evict oldest
cache = LRUCache(2)
cache.put(1, "a"); cache.put(2, "b")
cache.get(1) # 'a' → 1 is now most recent
cache.put(3, "c") # evicts key 2, not key 1
cache.get(2) # -1
# plain dict also works (3.7+ preserves insertion order)
class LRUDict:
def __init__(self, cap): self.cap, self.d = cap, {}
def get(self, k):
if k not in self.d: return -1
v = self.d.pop(k); self.d[k] = v # delete + reinsert = most recent
return v
def put(self, k, v):
if k in self.d: del self.d[k]
elif len(self.d) >= self.cap:
del self.d[next(iter(self.d))] # oldest key
self.d[k] = v
Implement Fibonacci — recursive, memoised, iterative, and as a generator.
A staple because it exposes four different approaches and their complexities:
- Naive recursion — O(2ⁿ) time. It recomputes the same subproblems exponentially:
fib(30) makes over a million calls. Never ship this. - Memoised recursion — O(n) time, O(n) space. One
@cache line turns the exponential version linear, which is the cleanest demonstration of dynamic programming there is. - Iterative — O(n) time, O(1) space. Just two rolling variables. This is the best single answer.
- Generator — infinite lazy sequence, O(1) space, and you take as many terms as you want.
Note that recursion also risks RecursionError — Python's default limit is around 1000 frames, so fib(2000) fails even with memoisation.
import functools
# ❌ O(2^n) — recomputes everything
def fib_naive(n):
return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)
# ✅ memoised — O(n), one decorator turns exponential into linear
@functools.cache
def fib_memo(n):
return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)
# ✅ best: O(n) time, O(1) space
def fib(n: int) -> int:
a, b = 0, 1
for _ in range(n):
a, b = b, a + b # tuple swap — no temp variable
return a
# ✅ generator — infinite, lazy, O(1) space
def fib_gen():
a, b = 0, 1
while True:
yield a
a, b = b, a + b
from itertools import islice
list(islice(fib_gen(), 10)) # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
# ⚠️ recursion limit (~1000 frames) — this raises RecursionError
# fib_memo(2000)
fib(2000) # ✅ iterative handles it fine (Python ints are arbitrary precision)
Transpose a matrix and rotate it 90 degrees.
Transpose (swap rows and columns) is a one-liner with zip(*matrix). The * unpacks the rows as separate arguments, and zip then pairs the first element of each row, the second of each, and so on — which is exactly the transpose.
Rotate 90° clockwise = transpose, then reverse each row. Rotating counter-clockwise = transpose, then reverse the row order. Deriving rotation from transpose is the insight worth showing — it means you only have to remember one operation.
zip returns tuples, so wrap in list() if you need mutable rows.
For an in-place rotation on a square matrix (O(1) space), transpose by swapping across the diagonal, then reverse each row.
matrix = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
# transpose — * unpacks rows, zip pairs them column-wise
list(zip(*matrix)) # [(1,4,7), (2,5,8), (3,6,9)]
[list(row) for row in zip(*matrix)] # as lists
# rotate 90° CLOCKWISE = transpose + reverse each row
[list(row)[::-1] for row in zip(*matrix)]
# [[7,4,1], [8,5,2], [9,6,3]]
# equivalently: reverse rows first, then transpose
[list(row) for row in zip(*matrix[::-1])]
# rotate 90° COUNTER-CLOCKWISE = transpose + reverse row ORDER
[list(row) for row in zip(*matrix)][::-1]
# in-place, square matrix, O(1) space
def rotate_in_place(m):
n = len(m)
for i in range(n): # transpose across the diagonal
for j in range(i + 1, n):
m[i][j], m[j][i] = m[j][i], m[i][j]
for row in m: # reverse each row
row.reverse()
# flatten / build
[x for row in matrix for x in row] # [1,2,...,9]
[[0] * 3 for _ in range(3)] # ✅ 3 independent rows
# [[0] * 3] * 3 ❌ three references to the SAME row!
