Python toolkit for coding rounds

Python suits coding rounds because the structures most problems need are one import away: Counter counts, deque queues, heapq keeps the smallest item at hand, bisect searches sorted lists and functools.cache remembers results. A few everyday habits work against you, though. Grid rows that share one list, division that rounds the other way and recursion that stops at a thousand calls all pass the sample tests and fail hidden ones. This lesson goes through the parts of the standard library that interview problems use, reproduces each trap with its fix on Python 3.14.8, and ends with the versions that introduced each feature, so you know what an older judge accepts.

Count and group with Counter and defaultdict

Most “how many”, “which is most frequent” and “group these” problems start with a dictionary. Counter builds one from any iterable in a single pass, and defaultdict removes the “is the key there yet?” check when you collect values under a key.

from collections import Counter, defaultdict
import heapq

words = "pear fig pear apple fig kiwi apple pear".split()

# Counter counts in one pass; most_common breaks ties by first appearance.
counts = Counter(words)
print(counts.most_common(3))


def top_k(words, k):
    """The k most frequent words; equal counts in alphabetical order."""
    counts = Counter(words)
    return heapq.nsmallest(k, counts, key=lambda w: (-counts[w], w))


print(top_k(words, 3))

# defaultdict(list) collects the positions of each word without checking for a missing key.
positions = defaultdict(list)
for i, w in enumerate(words):
    positions[w].append(i)
print(dict(positions))

[('pear', 3), ('fig', 2), ('apple', 2)]
['pear', 'apple', 'fig']
{'pear': [0, 2, 7], 'fig': [1, 4], 'apple': [3, 6], 'kiwi': [5]}

The first line is most_common(3). Its documentation says that elements with equal counts keep the order in which they were first encountered, so fig comes before apple because it appeared first. Problems usually ask for a different tie rule, such as “equal counts in alphabetical order”, and most_common cannot give that. The top_k function makes the rule part of the key: (-counts[w], w) sorts by count from high to low, then by the word from A to Z, and heapq.nsmallest(k, …) picks the first k under that key. The documentation of nsmallest states that it is equivalent to sorting with the same key and keeping the first k, and that it is fastest when k is small compared with the input; for k close to n, sorted(...)[:k] is quicker.

defaultdict(list) calls list() the first time a key is read, so positions[w].append(i) works for a new word without any setup. The last line shows that the dictionary keeps its keys in the order they were first added, which makes output repeatable. For what each structure costs, operation by operation, see the DSA toolkit lesson, which maps them across five languages.

Queues and heaps: deque and heapq

A breadth-first search takes nodes from the front of a queue and adds them at the back. A Python list is the wrong tool for that: the collections documentation notes that lists “incur O(n) memory movement costs for pop(0) and insert(0, v)”, because every remaining element shifts by one place. deque adds and removes at both ends in O(1).

import heapq
from collections import deque
from itertools import count

# Breadth-first search with a deque: popleft() is O(1), list.pop(0) is O(n).
roads = {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": ["F"], "E": ["F"], "F": []}


def fewest_hops(start, goal):
    hops = {start: 0}
    queue = deque([start])
    while queue:
        town = queue.popleft()
        if town == goal:
            return hops[town]
        for nxt in roads[town]:
            if nxt not in hops:
                hops[nxt] = hops[town] + 1
                queue.append(nxt)
    return -1


print("fewest hops from A to F:", fewest_hops("A", "F"))

# Equal priorities make heapq compare the next field of the tuple: here two dicts.
jobs = [(2, {"name": "backup"}), (2, {"name": "report"}), (1, {"name": "email"})]
heap = []
try:
    for job in jobs:
        heapq.heappush(heap, job)
except TypeError as error:
    print("TypeError:", error)

# A running count as the second field decides ties, in the order the jobs arrived.
order = count()
heap = []
for priority, job in jobs:
    heapq.heappush(heap, (priority, next(order), job))
print([heapq.heappop(heap)[2]["name"] for _ in range(len(jobs))])

# Largest first: the max-heap functions of Python 3.14, then the negation that works everywhere.
scores = [40, 75, 62, 90]
heap = scores[:]
heapq.heapify_max(heap)
print("heappop_max:", heapq.heappop_max(heap), heapq.heappop_max(heap))
negated = [-s for s in scores]
heapq.heapify(negated)
print("negated keys:", -heapq.heappop(negated), -heapq.heappop(negated))

fewest hops from A to F: 3
TypeError: '<' not supported between instances of 'dict' and 'dict'
['email', 'backup', 'report']
heappop_max: 90 75
negated keys: 90 75

The cost difference is not small. On a star graph of 200,000 nodes, where the queue holds 199,999 nodes after the first step, a search that used list.pop(0) took 16.6 seconds on an Apple M5 Pro running Python 3.14.8, and the same search with deque.popleft() took 0.03 seconds. A list with a separate index of its front, never popped, took 0.04 seconds and is a good choice when you also need the visiting order afterwards.

heapq keeps a min-heap inside an ordinary list: heap[0] is always the smallest item. Pushing tuples orders items by their first field, and when two first fields are equal, Python compares the second fields. That is where the TypeError in the output comes from: two jobs with priority 2 made heapq compare two dictionaries, and dictionaries have no order. The documentation of heapq gives the fix used next: put a running count between the priority and the item. No two counts are equal, so the comparison never reaches the item, and equal priorities come out in the order they went in.

For the largest item first, Python 3.14 added heapify_max, heappush_max, heappop_max, heapreplace_max and heappushpop_max. On an older Python, store negated keys in an ordinary min-heap and negate them again on the way out, as the last line does; the negation works for numbers only, so for strings use a key you can negate, such as a count.

Sorted data: bisect and sort keys

When the data is sorted, a binary search answers “how many lie in this range”, “what is the first value at or after x” and “where would x go” in O(log n). bisect_left returns the first position where a value could be inserted keeping the order, bisect_right the position after any equal values, and the difference of the two counts a range.

from bisect import bisect_left, bisect_right, insort

times = [3, 8, 8, 12, 15, 21]

# How many times fall between 8 and 15, both included?
print(bisect_right(times, 15) - bisect_left(times, 8))

# The first time at or after 13 (None when there is none).
i = bisect_left(times, 13)
print(times[i] if i < len(times) else None)

# key= (Python 3.10 and later) searches records sorted by one field.
bookings = [("asha", 9), ("ravi", 11), ("meena", 14)]
print(bisect_left(bookings, 12, key=lambda b: b[1]))

# insort keeps the list sorted, but each insertion moves the later items: O(n).
insort(times, 10)
print(times)

# Several sort keys at once: age from oldest, then name from A to Z.
people = [("ravi", 31), ("asha", 25), ("meena", 31), ("dev", 25)]
print(sorted(people, key=lambda p: (-p[1], p[0])))

4
15
2
[3, 8, 8, 10, 12, 15, 21]
[('meena', 31), ('ravi', 31), ('asha', 25), ('dev', 25)]

Four values lie between 8 and 15, the first time at or after 13 is 15, and the booking search shows key=, which Python 3.10 added: it searches a list of records by one field without building a separate list of that field. Keep in mind what insort costs. Its search is O(log n), but the documentation points out that the insertion that follows is O(n), so a loop of n insertions is O(n²); when values arrive one by one and you need the smallest or largest each time, a heap is the better structure, and when the whole input is known, sort it once.

Python’s sort is stable, so you can sort by several keys in one call by returning a tuple, as the last line does: (-age, name) puts the oldest first and breaks ties by name. Negating works for numbers; to sort strings in reverse inside a tuple, sort twice instead, by the minor key first and then by the major key with reverse=True, relying on stability.

itertools for pairs, prefix sums and runs

Many array problems compare neighbours, add up ranges or look at runs of equal values. itertools has a ready function for each, which saves index arithmetic and the off-by-one mistakes that come with it.

from itertools import accumulate, batched, combinations, groupby, pairwise, product

temps = [31, 33, 30, 35, 35, 36]

# Neighbouring pairs (3.10): the change from one day to the next.
print([b - a for a, b in pairwise(temps)])

# Prefix sums with a leading 0, so the sum of temps[i:j] is prefix[j] - prefix[i].
prefix = list(accumulate(temps, initial=0))
print(prefix, prefix[4] - prefix[1])

# Runs of equal neighbours: groupby only groups items that are next to each other.
print([(ch, len(list(run))) for ch, run in groupby("aaabccdd")])

# Every pair, and every pair of digits 0-2 (with repetition): no nested loops to write.
print(list(combinations("abc", 2)))
print(len(list(product(range(3), repeat=2))))

# Fixed-size chunks (3.12); the last one may be shorter.
print(list(batched(range(7), 3)))

[2, -3, 5, 0, 1]
[0, 31, 64, 94, 129, 164, 200] 98
[('a', 3), ('b', 1), ('c', 2), ('d', 2)]
[('a', 'b'), ('a', 'c'), ('b', 'c')]
9
[(0, 1, 2), (3, 4, 5), (6,)]

• pairwise (Python 3.10) yields each element with its neighbour, here the change from one day to the next.
• accumulate(temps, initial=0) gives prefix sums with a leading zero, so the sum of temps[i:j] is prefix[j] - prefix[i]: 98 for the three values from index 1 to 3.
• groupby groups equal neighbours only, which is exactly what run-length counting needs; to group equal values that are not adjacent, sort first or use a dictionary.
• combinations and product replace nested loops when a problem says “every pair” or “every choice”.
• batched (Python 3.12) cuts an iterable into chunks of a given size; the last chunk may be shorter.

Deep recursion and functools.cache

Recursive solutions, such as a depth-first search or a top-down dynamic programme, meet the recursion limit first. sys.getrecursionlimit() is 1,000 by default, so a chain of 5,000 calls raises RecursionError. Raising the limit with sys.setrecursionlimit works for plain Python functions: since Python 3.11, most calls from Python code to Python code use no C stack space, so the recorded run reaches a depth of 200,000 once the limit is a million.

import sys
from functools import cache

print("default limit:", sys.getrecursionlimit())


def depth(n):
    return 0 if n == 0 else 1 + depth(n - 1)


def attempt(label, f, n):
    try:
        print(f"{label}, depth {n}: {f(n)}")
    except RecursionError as error:
        # The message names the guard that stopped the call (the text after " (" varies by machine).
        print(f"{label}, depth {n}: RecursionError: {str(error).split(' (')[0]}")


attempt("plain", depth, 5_000)
sys.setrecursionlimit(1_000_000)
attempt("plain, limit raised", depth, 200_000)


@cache
def cached_depth(n):
    return 0 if n == 0 else 1 + cached_depth(n - 1)


# Each cached call also runs the cache's C code, which uses the C stack.
attempt("cached, limit raised", cached_depth, 5_000)
cached_depth.cache_clear()
attempt("cached, limit raised", cached_depth, 20_000)

# Two ways that reach 200,000: your own dict as the memo, or no recursion at all.
memo = {0: 0}


def memo_depth(n):
    if n not in memo:
        memo[n] = 1 + memo_depth(n - 1)
    return memo[n]


attempt("own dict, limit raised", memo_depth, 200_000)


def loop_depth(n):
    value = 0
    for _ in range(n):
        value += 1
    return value


attempt("loop", loop_depth, 200_000)

default limit: 1000
plain, depth 5000: RecursionError: maximum recursion depth exceeded
plain, limit raised, depth 200000: 200000
cached, limit raised, depth 5000: 5000
cached, limit raised, depth 20000: RecursionError: Stack overflow
own dict, limit raised, depth 200000: 200000
loop, depth 200000: 200000

The cached function is different. With the same raised limit it passes at depth 5,000 and fails at 20,000, and the message is not the recursion limit’s “maximum recursion depth exceeded” but “Stack overflow”. The wrapper that @cache puts around the function is implemented in C in CPython, so every level of the recursion also runs C code on the thread’s fixed-size stack, and Python 3.12 guards such code with a separate mechanism that stops it before the stack runs out. How deep it gets depends on the platform’s stack size; here, with the 16 MB main-thread stack of the macOS build, the cached function failed somewhere between those two depths.

Three fixes work, in the order to try them:

1. Iterate. Fill the table bottom-up in a loop, or keep an explicit stack for a depth-first search. There is no depth limit at all, and it is usually faster.
2. Memoise with your own dictionary and raise the recursion limit. The calls are plain Python calls again, so only the recursion limit applies, as the own dict line shows.
3. Run the recursion in a thread with a larger stack, using threading.stack_size() before starting the thread. It works natively, but each thread reserves that much memory, and the Python that runs in a browser cannot start threads at all.

This example shows recorded output only, without a Run button: the Python that runs in your browser has a much smaller stack, and deep recursion stops it.

Five traps that pass the sample tests

Each of these behaves correctly on small, friendly inputs, which is why they survive the sample tests:

import sys

# 1. [[0] * 3] * 2 repeats one row object, so both "rows" change together.
grid = [[0] * 3] * 2
grid[0][0] = 1
print("aliased:", grid)
grid = [[0] * 3 for _ in range(2)]
grid[0][0] = 1
print("separate:", grid)

# 2. // and % round the quotient down (towards minus infinity), not towards zero.
print("-7 // 2 =", -7 // 2, " -7 % 2 =", -7 % 2, " int(-7 / 2) =", int(-7 / 2))

# 3. round() sends an exact half to the even neighbour.
print("round:", round(0.5), round(1.5), round(2.5), round(3.5))


# 4. A default list is made once, when the function is defined, and shared by every call.
def add_tag(tag, tags=[]):
    tags.append(tag)
    return tags


print("shared default:", add_tag("a"), add_tag("b"))

# 5. str() of an int with more than 4,300 digits raises ValueError (a guard since Python 3.11).
n = 7**6000
try:
    print(len(str(n)))
except ValueError as error:
    print("ValueError:", str(error).split(";")[0])
sys.set_int_max_str_digits(0)  # 0 switches the guard off for this program
print("digits:", len(str(n)))

aliased: [[1, 0, 0], [1, 0, 0]]
separate: [[1, 0, 0], [0, 0, 0]]
-7 // 2 = -4  -7 % 2 = 1  int(-7 / 2) = -3
round: 0 2 2 4
shared default: ['a', 'b'] ['a', 'b']
ValueError: Exceeds the limit (4300 digits) for integer string conversion
digits: 5071

1. Aliased rows. [[0] * 3] * 2 repeats a reference to one inner list, so a change to one row appears in both. The programming FAQ of the documentation gives the fix: build each row in a comprehension, [[0] * cols for _ in range(rows)]. Repeating a list of numbers with * is safe; repeating a list of lists is not.
2. Floor division. // rounds the quotient towards minus infinity and % takes the sign of the divisor, so -7 // 2 is -4 and -7 % 2 is 1. Java, C++, Go and JavaScript truncate towards zero and give -3 and -1. Python’s rule is convenient for x % m, which is never negative for a positive m, but code ported from another language, or a problem that says “drop the fraction”, needs int(a / b) for small values or a sign adjustment for large ones.
3. round() sends halves to the even neighbour. The documentation of round says that when two multiples are equally close, rounding goes to the even one, so 0.5, 1.5, 2.5 and 3.5 become 0, 2, 2 and 4. A problem that says “round halves up” needs the decimal module with ROUND_HALF_UP, or integer arithmetic on scaled values.
4. A shared default list. A default value is evaluated once, when the function is defined, so tags=[] gives every call the same list: the two calls printed ['a', 'b'] twice. Use None as the default and create the list inside. The same applies to a seen=set() or memo={} default in a recursive helper, which then leaks results from one test case into the next.
5. Printing a very long integer. Since Python 3.11, converting an integer of more than 4,300 decimal digits to text raises ValueError, a guard against slow conversions. Problems that print an exact large result, such as a big factorial, need sys.set_int_max_str_digits(0) (or a large enough value) before printing. Binary, octal and hexadecimal conversions are not limited.

Which Python version has what

Most judges run a recent Python. HackerRank’s execution environment page, for example, lists Python 3.14.2 for its coding questions. A company’s own platform or an older judge may not, and a feature that is missing there fails at the first call or does not even parse. These are the versions that introduced the features of this lesson and a few neighbours that interview code uses:

If you cannot check the version first, the safe forms are short: negated keys instead of the max-heap functions, functools.lru_cache(maxsize=None) instead of cache, zip(a, a[1:]) instead of pairwise, and slicing instead of batched. The lesson on choosing your interview language shows how to compare a platform’s listed version with the features you use.

Practise: fix the traps

The exercise below hides one trap from this lesson in each of five short functions. Every function returns the right answer on its first test and a wrong one on another. Fix each one, run the tests, and check your fixes against the recorded output of traps.py.

def blank_grid(rows, cols):
    """A rows x cols grid of zeros; changing one cell changes only that cell."""
    return [[0] * cols] * rows


def average_toward_zero(values):
    """The integer average of a non-empty list, with the fraction dropped towards zero (7.5 -> 7, -7.5 -> -7)."""
    return sum(values) // len(values)


def round_half_up(amount):
    """A non-negative amount (at most two decimals) rounded to a whole number, halves going up (2.5 -> 3)."""
    return round(amount)


def add_tag(tag, tags=[]):
    """Appends tag to tags and returns the list; without a list, a new one is started on every call."""
    tags.append(tag)
    return tags


def digit_sum(n):
    """The sum of the decimal digits of a non-negative integer of any size."""
    return sum(int(d) for d in str(n))

from traps import add_tag, average_toward_zero, blank_grid, digit_sum, round_half_up


def test_grid_rows_are_separate():
    """changing one cell of blank_grid(3, 2) leaves the other rows alone"""
    grid = blank_grid(3, 2)
    grid[0][1] = 7
    assert grid == [[0, 7], [0, 0], [0, 0]]


def test_grid_shape():
    """blank_grid(2, 3) has two rows of three zeros; zero rows give an empty list"""
    assert blank_grid(2, 3) == [[0, 0, 0], [0, 0, 0]]
    assert blank_grid(0, 4) == []


def test_average_positive():
    """the average of [7, 8] is 7.5, which becomes 7"""
    assert average_toward_zero([7, 8]) == 7


def test_average_negative():
    """the average of [-7, -8] is -7.5, which becomes -7, not -8"""
    assert average_toward_zero([-7, -8]) == -7


def test_average_mixed_signs():
    """the average of [-7, 0] is -3.5, which becomes -3"""
    assert average_toward_zero([-7, 0]) == -3


def test_average_exact():
    """an exact average is returned as it is"""
    assert average_toward_zero([-4, -2, 0]) == -2


def test_round_halves_go_up():
    """0.5, 1.5, 2.5 and 3.5 round to 1, 2, 3 and 4"""
    assert [round_half_up(x) for x in (0.5, 1.5, 2.5, 3.5)] == [1, 2, 3, 4]


def test_round_other_amounts():
    """amounts that are not halves round to the nearer whole number"""
    assert [round_half_up(x) for x in (2.49, 2.51, 7.0, 0.0, 99.99)] == [2, 3, 7, 0, 100]


def test_round_returns_an_int():
    """the result is an int"""
    assert type(round_half_up(2.5)) is int


def test_add_tag_starts_a_new_list_each_time():
    """two calls without a list each return a list with only their own tag"""
    assert add_tag("urgent") == ["urgent"]
    assert add_tag("later") == ["later"]


def test_add_tag_appends_to_a_given_list():
    """a list that is passed in is extended and returned"""
    tags = ["home"]
    assert add_tag("work", tags) is tags
    assert tags == ["home", "work"]


def test_digit_sum_small():
    """digit_sum(0) is 0 and digit_sum(9045) is 18"""
    assert digit_sum(0) == 0
    assert digit_sum(9045) == 18


def test_digit_sum_just_under_the_limit():
    """3 ** 9000 has 4,295 digits, whose sum is 19494"""
    assert digit_sum(3**9000) == 19494


def test_digit_sum_over_the_limit():
    """2 ** 20000 has 6,021 digits, whose sum is 26995"""
    assert digit_sum(2**20000) == 26995

Interview questions

Fresher · What do -7 // 2 and -7 % 2 give in Python, and why does Java give different answers?

Python’s // rounds the quotient down, towards minus infinity, so -7 // 2 is -4, and % takes the sign of the divisor so that (a // b) * b + a % b == a always holds, which makes -7 % 2 equal to 1. Java, C++, Go and JavaScript truncate the quotient towards zero instead: there -7 / 2 is -3 and -7 % 2 is -1. The difference matters in two places. Reducing a negative number modulo m is already correct in Python, while Java needs Math.floorMod(x, m) or ((x % m) + m) % m. And a solution ported from Java to Python, or a problem that says “drop the fraction”, needs truncation, written int(a / b) for small values or as an adjustment of the floor result when the signs differ.

Key takeaways

• Counter, defaultdict, deque, heapq and bisect cover counting, grouping, queues, priorities and sorted lookups; put the tie rule of a “top k” problem into the key.
• Never use list.pop(0) as a queue: on 200,000 nodes it cost 16.6 seconds against 0.03 for deque.
• Give heap entries a running count after the priority, so ties never compare the items.
• @cache recursion fails on the C stack long before a raised recursion limit; iterate, or memoise with your own dictionary.
• Build grids with a comprehension, remember that // and % round towards minus infinity, that round sends halves to even, that default lists are shared, and that str() refuses integers over 4,300 digits.
• Check the platform’s Python version before using 3.10, 3.12 or 3.14 features.