Python: Collections and Recursion

Description

Almost every Python answer in a coding interview leans on the same few containers: a list to keep things in order, a dict to look things up, a set to remember what you've already seen, and a heap or a deque to decide what comes next. You've probably used them all. This lesson is about using them with confidence: picking the right one quickly, and knowing the handful of rules that quietly break code that looks perfectly fine.

Here's the kind of bug we mean. This loop removes the even numbers from a list:

nums = [2, 4, 6, 7]
for x in nums:
    if x % 2 == 0:
        nums.remove(x)
print(nums)          # [4, 7]

No error, and the answer is wrong: 4 is still there. Java would at least throw an exception; Python just keeps going. By the end of the lesson you'll know exactly why, and the safe way to write it.

We'll start simple and get more technical as we go:

1. Which container to pick, and what each one costs.
2. How dict and set find things, and what can be a key.
3. The collections helpers: defaultdict, Counter, deque, OrderedDict.
4. Heaps and sorted lists with heapq and bisect.
5. Sorting your own way.
6. Changing a collection while you loop over it - and how deep recursion can go.

Picking the right container

Two habits follow from this table. Never use x in some_list inside a loop to check whether you've seen something - that's a scan every time, and the loop becomes quadratic. Use a set. And never use list.pop(0) as a queue - it shifts every remaining item. Use a deque.

dict and set: how they find things

A dict (and a set) is a hash table. Python computes a number from the key - its hash - and uses it to jump straight to a slot, so lookups, inserts and deletes take about the same time however big the table is.

Two facts worth using in interviews:

• A dict remembers insertion order. Iterating a dict gives keys in the order they were first added - a language guarantee since Python 3.7. Updating an existing key keeps its place; deleting it and adding it again moves it to the end. A set has no defined order at all.
• Membership is O(1). x in some_dict and x in some_set jump straight to the slot.

What can be a key

seen = set()
seen.add((r, c))            # a tuple of ints: fine
seen.add([r, c])            # TypeError: cannot use 'list' as a set element (unhashable type: 'list')
groups[frozenset(tags)]     # a set as a key: freeze it first

Keys must be hashable: their hash must never change. That's why the built-in containers you can change - list, dict, set - can't be keys or set members. If a key could change after it was filed, the table would look for it in the wrong slot. Use a tuple instead of a list, and a frozenset instead of a set.

The collections helpers

from collections import Counter, OrderedDict, defaultdict, deque

counts = defaultdict(int)
counts["x"] += 1                    # no KeyError: a missing key starts at int() == 0

c = Counter("abcab")
c.most_common(2)                    # [('a', 2), ('b', 2)]
c["z"]                              # 0, and "z" is NOT added

window = deque(maxlen=3)
for x in range(5):
    window.append(x)                # deque([2, 3, 4], maxlen=3): the oldest fall off

Two details trip people up:

• Reading a defaultdict adds the key. if counts["y"] > 0: quietly inserts "y": 0, so len(counts) and "y" in counts change. To check without side effects, use "y" in counts or counts.get("y", 0). A Counter doesn't do this - reading a missing key just gives 0.
• most_common breaks ties by first appearance, not alphabetically. If a problem says "ties in alphabetical order", sort yourself: sorted(c.items(), key=lambda kv: (-kv[1], kv[0])).

OrderedDict adds move_to_end(key) and popitem(last=False) (remove the oldest), which is exactly an LRU cache: move a key to the end on every use, and evict from the front.

Heaps and sorted lists

heapq turns an ordinary list into a min-heap: the smallest item is always at index 0.

import heapq

h = [5, 1, 4, 2, 3]
heapq.heapify(h)                    # O(n): h is now [1, 2, 4, 5, 3]
heapq.heappop(h)                    # 1
heapq.heappush(h, 0)
heapq.nsmallest(2, [7, 3, 9, 1])    # [1, 3]

Only h[0] is guaranteed: the rest of the list is in "heap order", not sorted, so printing a heap shows something that looks almost sorted. For a max-heap, push negated values. To order by several things, push tuples - they compare field by field, so the second field breaks ties:

heapq.heappush(tasks, (-priority, name))   # highest priority first; ties by name, A to Z

There's no "decrease key" operation. If an item's priority changes, push a new entry and skip the stale one when it's popped.

bisect finds positions in a sorted list in O(log n):

import bisect

a = [1, 3, 3, 5, 8, 8, 10]
bisect.bisect_left(a, 3)            # 1: the first index where 3 could go
bisect.bisect_right(a, 3)           # 3: just after the last 3
bisect.bisect_right(a, 8) - bisect.bisect_left(a, 3)   # 5 values between 3 and 8

bisect.insort(a, x) keeps the list sorted, but inserting still shifts everything after the spot, so it's O(n) per insert.

Sorting your own way

nums.sort()                         # sorts in place and returns None
ordered = sorted(nums)              # returns a new list
people.sort(key=lambda p: (-p.score, p.name))   # score high to low, then name A to Z

The classic slip is nums = nums.sort(), which sets nums to None. Python's sort is stable: items that compare equal keep their original order - and that's still true with reverse=True, which keeps ties in their original order instead of reversing them.

When the rule compares pairs rather than single items - "Largest Number" puts a before b when a + b > b + a - a key can't express it. Wrap a comparison function with functools.cmp_to_key.

Changing a collection while looping over it

Back to the puzzle. A for loop over a list walks by position. Removing 2 shifts 4 into position 0, the loop moves on to position 1 - which now holds 6 - and 4 is never looked at.

Dicts and sets are stricter: changing their size during a loop raises an error.

d = {"a": 1, "b": 0, "c": 0}
for k in d:
    if d[k] == 0:
        del d[k]                    # RuntimeError: dictionary changed size during iteration

The fix is the same either way: build a new collection, or loop over a copy.

nums = [x for x in nums if x % 2]                # a new list
d = {k: v for k, v in d.items() if v != 0}      # a new dict
for k in list(d): ...                           # loop over a snapshot of the keys

How deep can recursion go?

Python stops recursion at about 1,000 nested calls by default and raises RecursionError. A recursive depth-first search on a path-shaped graph of 5,000 nodes fails, though the algorithm is fine.

You have three options:

• Raise the limit: sys.setrecursionlimit(10**6). Since Python 3.11 this is safe for plain Python functions - a depth of 500,000 runs fine.
• Rewrite with an explicit stack: a list you append to and pop from. This works on every Python version and in every interview.
• For memoized recursion, warm the cache from the bottom up. @cache doesn't help the first deep call: fib(5000) still recurses 5,000 levels before anything is cached.

Common mistakes

Check yourself

Try to answer before opening each one. Recalling beats re-reading.

1. Why does the loop at the top leave 4 in the list?

2. How do you pop the highest priority first, breaking ties by the alphabetically first name?

3. A Counter gives [('b', 2), ('a', 2)] from most_common(2), but the problem wants ties in alphabetical order. What's going on?

Key takeaways

• Pick by operation: set for "seen", dict for lookup, deque for queues, heapq for "smallest next", bisect for sorted search.
• Dicts keep insertion order; keys must be hashable - use tuples and frozensets.
• defaultdict reads add keys; Counter reads don't; most_common ties go by first appearance.
• A heap only promises h[0]; negate for max; tuples break ties.
• sort() returns None; sorting is stable, even with reverse=True.
• Never change a collection while looping over it - build a new one.
• Recursion stops near 1,000 by default: use an explicit stack or raise the limit.