Python Built-In Data Structures for Coding Interviews

Python is one of the best languages for coding interviews. The syntax is concise, the standard library is dense, and interviewers mostly don't care that it runs 30x slower than C++. But "Python is easy" is the trap. The data structures that bite people in interviews aren't exotic. They're the ones you use every day: list, dict, set, deque, and heapq. Each has an edge that will cost you an offer if you haven't seen it before.

And you will not see it until it's too late.

list: The Default Workhorse (with One Very Rude Surprise)

The Python list is a dynamic array. Most operations are exactly what you'd expect, except the ones that aren't.

nums = [1, 2, 3]
nums.append(4)         # O(1) amortized
nums.pop()             # O(1) - removes from end
nums.pop(0)            # O(n) - shifts every element left
nums.insert(0, 0)      # O(n) - same reason
nums[2]                # O(1) - index lookup
2 in nums              # O(n) - linear scan

The trap: pop(0) and insert(0, x) are O(n), not O(1). Every element shifts one spot. If you're draining a list from the front for BFS, you're paying O(n) per dequeue and getting O(n²) total. Your solution works on examples. It times out on test cases. The interviewer says nothing. You lose.

Use collections.deque instead. More on that in a minute.

Two more that cause silent bugs:

result = nums.sort()    # result is None, not a sorted list
result = sorted(nums)   # this is what you wanted

list.sort() sorts in-place and returns None. sorted(nums) returns a new list. Every candidate hits this at least once. Usually in a place they can't afford to.

The 2D grid trap is nastier because it looks completely fine until it's not:

# Wrong - one row, aliased three times
grid = [[0] * 3] * 3
grid[0][0] = 1   # sets grid[0][0], grid[1][0], grid[2][0] all to 1

# Right
grid = [[0] * 3 for _ in range(3)]

[[0] * cols] * rows creates one row and aliases it. Mutating any row mutates all of them. If you're debugging a grid problem where values keep mysteriously propagating across rows, this is it.

Michael Scott laughing at programming memes then crying while actually coding

*Reading that Python syntax is "clean and readable" vs finding out that [[0]*3]3 is one row wearing three hats.

For time complexity of every list operation, the Python wiki is the canonical reference.

dict: The Hash Map You Already Know (Sort Of)

dict is Python's hash map. O(1) average for get, set, and delete. Since Python 3.7, it preserves insertion order as a language guarantee, not an implementation detail. That part's fine.

d = {}
d["a"] = 1             # O(1)
d.get("b", 0)          # O(1), returns 0 if missing (no KeyError)
d.setdefault("c", [])  # O(1), inserts default only if key absent
"a" in d               # O(1) - use this, not a try/except
del d["a"]             # O(1)

The one operation most people get wrong: using d[key] when the key might be absent. d[key] raises KeyError. d.get(key, default) doesn't. Under interview pressure, this difference produces bugs that are hard to debug quickly. You stare at the traceback, wonder what went wrong, and eat two of your forty-five minutes.

Don't modify a dict while iterating over it. Wrap dict.keys() in list() first if you need to delete during traversal. Python will raise a RuntimeError at you and it will not be polite about it.

For more on why the O(1) guarantee holds and when it breaks, see the hash map time complexity deep dive.

set: O(1) Membership Checks (Unordered, No Exceptions)

set is an unordered collection of unique elements backed by a hash table. Add, remove, and membership checks are all O(1) average. This is what you want instead of x in list whenever you're checking membership more than once.

s = {1, 2, 3}
s.add(4)               # O(1)
s.discard(5)           # O(1), no error if missing
s.remove(5)            # O(1), raises KeyError if missing
3 in s                 # O(1)
s1 & s2                # intersection, O(min(len(s1), len(s2)))
s1 | s2                # union, O(len(s1) + len(s2))
s1 - s2                # difference, O(len(s1))

Sets are unordered. Never rely on iteration order. If you need ordered unique elements, sort the set explicitly or use a different structure.

frozenset is an immutable, hashable set. You can use it as a dict key or put it inside another set, which comes up when memoizing states in graph problems. Knowing it exists saves you from some very awkward workarounds.

collections.deque: The Real Queue

This is what you use for BFS. Not a list. A deque.

Use deque any time you need O(1) appends and pops from both ends. The canonical use case is BFS: dequeue from the left, enqueue on the right, run your solution in O(n) instead of O(n²).

from collections import deque

q = deque([1, 2, 3])
q.append(4)            # O(1), add to right
q.appendleft(0)        # O(1), add to left
q.pop()                # O(1), remove from right
q.popleft()            # O(1), remove from left
q[0]                   # O(1), peek front
q[-1]                  # O(1), peek back

deque with maxlen is a sliding window machine. When the deque is full, new appends automatically evict from the opposite end. No manual cleanup.

window = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
    window.append(x)
# window is now deque([3, 4, 5])

Random access is O(n). Deque is a doubly-linked list of fixed-size blocks, not a contiguous array. Great for queuing. Bad for indexing. Pick one. See BFS pattern recognition for how deque fits into the level-order traversal template.

heapq: The Min-Heap Module (That Is Always a Min-Heap)

Python has no Heap class. heapq is a module of functions that treat a regular list as a min-heap.

import heapq

nums = [3, 1, 4, 1, 5]
heapq.heapify(nums)            # O(n), rearranges in-place
heapq.heappush(nums, 2)        # O(log n)
smallest = heapq.heappop(nums) # O(log n)
peek = nums[0]                 # O(1), peek without removing

heapq is always a min-heap. To get a max-heap, negate your values on insert and negate again on pop. It feels cursed. It is cursed. It works.

max_heap = []
heapq.heappush(max_heap, -val)
max_val = -heapq.heappop(max_heap)

For top-K problems, push tuples where the first element is the priority:

heapq.heappush(heap, (priority, item))

Python compares tuples lexicographically, so the priority field controls ordering. If priorities can be equal and your items aren't comparable, add a counter as a tiebreaker: (priority, counter, item). Skip the counter and Python will try to compare the items when priorities tie. If those items don't support comparison operators, you get a TypeError mid-interview. Add the counter.

There is no decrease-key operation. For Dijkstra, the standard approach is lazy deletion: push updated entries, skip stale ones on pop. See Dijkstra's algorithm for the full template.

The Power-Ups: defaultdict, Counter, bisect

collections.defaultdict

defaultdict is a dict that calls a factory function to supply a default value when a key is missing. You never have to initialize before appending.

from collections import defaultdict

groups = defaultdict(list)
for val, key in pairs:
    groups[key].append(val)   # no KeyError, no if-key-not-in

counts = defaultdict(int)
for char in s:
    counts[char] += 1         # starts at 0 automatically

The trap: accessing a missing key with bracket notation creates that key with the default value. If you later iterate over the dict, you'll find phantom keys you never meant to insert. For checking existence, use key in d, not d[key]. One creates the key. The other checks for it.

collections.Counter

Counter is a defaultdict(int) with extra methods. It's the right tool any time you're counting frequencies.

from collections import Counter

c = Counter("abracadabra")
c.most_common(3)   # [('a', 5), ('b', 2), ('r', 2)], O(n log k)
c["z"]             # 0, no KeyError
c + Counter("aba") # combines counts
c - Counter("ab")  # subtracts, drops zero and negative counts

Counter subtraction drops elements with zero or negative counts, which is sometimes what you want and sometimes a complete surprise. most_common(k) uses a heap internally and runs in O(n log k).

bisect: Binary Search on Sorted Lists

bisect gives you O(log n) search on a sorted list, plus O(n) insertion that keeps it sorted. The search is fast. The insertion is not. If you need both, you have a problem bisect can't solve alone.

import bisect

a = [1, 3, 5, 7]
bisect.bisect_left(a, 5)    # 2, leftmost position for 5
bisect.bisect_right(a, 5)   # 3, rightmost position for 5
bisect.insort(a, 4)         # inserts 4, list is now [1, 3, 4, 5, 7]

bisect_left returns the index where you'd insert to keep sorted order, so a[bisect_left(a, x)] == x is true if x exists. See the official bisect docs for the full spec.

Python Data Structures Quick Reference

Structure	Key Operation	Complexity
`list`	`append` / `pop()`	O(1) amortized
`list`	`pop(0)` / `insert(0, x)`	O(n)
`list`	`x in list`	O(n)
`dict`	get / set / delete	O(1) avg
`set`	`add` / `discard` / `in`	O(1) avg
`deque`	`append` / `appendleft` / `popleft`	O(1)
`heapq`	`heappush` / `heappop`	O(log n)
`heapq`	`heapify`	O(n)
`Counter`	`most_common(k)`	O(n log k)
`bisect_left`	search in sorted list	O(log n)

What LeetCode Adds

LeetCode's Python 3 environment includes sortedcontainers, which is not part of the stdlib. SortedList gives you a sorted sequence with O(log n) add and O(log n) lookup, filling the gap Python has compared to Java's TreeMap or C++'s std::set.

from sortedcontainers import SortedList

sl = SortedList()
sl.add(3)
sl.add(1)
sl.add(2)
# sl is [1, 2, 3]
sl.bisect_left(2)   # 1

If your solution needs a sorted multiset, SortedList is the right tool. Don't count on it outside of LeetCode environments. If you reach for it in a phone screen on CoderPad, you're going to have a bad time.

Knowing the complexity of your operations cold is table stakes. The harder part in an actual interview is explaining your choices out loud while someone watches you think. Practicing with a voice-based mock interviewer at SpaceComplexity forces you to verbalize those decisions in real time, which is what the rubric actually scores.

For more on how Python compares to other interview languages, see Python for Coding Interviews and best language for coding interviews. If you're building out your full prep stack, Python Interview Cheat Sheet covers the broader set of built-ins, idioms, and patterns beyond data structures.