Data Structures
A Python interview probes data structures through the standard library, not through an algorithms textbook. The question sounds like "what is a queue", but the interviewer is waiting for the second half — what will you build it on, and what does that cost. In CPython every abstraction has a concrete carrier, and the carrier fixes the complexity: a stack lives on list, a queue on collections.deque, a heap on a flat list through the heapq module, a graph on a dict of adjacency. A balanced search tree, however, is not in the standard library at all — and you have to say that out loud, together with what replaces it.
Three traps follow, and they turn up more often than any others. list.pop(0) looks like dequeuing, but it costs O(n) — every remaining pointer shifts left in a single memmove, and a graph traversal quietly becomes quadratic. heapq implements a min-heap only, so a maximum is obtained by negating the key, and a (priority, item) tuple blows up with TypeError exactly when two priorities tie and the payloads are not comparable. An adjacency matrix in pure Python is not V² bits but V² eight-byte pointers. Each layer below takes one carrier and its real price.
Topic map
- Stack and queue — LIFO versus FIFO, why
listis perfect for a stack and hopeless for a queue, and whatcollections.dequegives you. - Trees — a connected acyclic graph of
nnodes andn-1edges, depth-first and breadth-first traversal, and CPython's recursion limit. - Binary search tree — the ordering invariant over whole subtrees, degeneration into a chain on sorted input, and what replaces the balanced BST the stdlib does not ship.
- Heap and heapq — a partial order over a flat list,
heapifyinO(n), the negation trick for a max-heap, and tuple priorities with a counter. - Graphs — direction, weights, cycles, the mandatory
visitedset, and traversals inO(V+E). - Graph representation in memory — adjacency list versus matrix,
O(V+E)versusO(V²), and when a matrix does win.
Common mistakes and traps
| Mistake | Consequence |
|---|---|
Building a queue on list and dequeuing with pop(0) | Every removal shifts the whole tail — O(n) instead of O(1), and a graph traversal turns quadratic |
Thinking heapq can do a max-heap | The module implements a min-heap only; a maximum comes from negating the key or wrapping it with an inverted __lt__ |
Pushing (priority, item) with non-comparable payloads | On tied priorities the comparison falls through to the second tuple element and raises TypeError |
| Checking the BST invariant on direct children only | The validator accepts a tree where a grandchild violates its grandparent's bound; the check must carry a (low, high) corridor |
Claiming a BST search is always O(log n) | Without rebalancing, sorted input degenerates the tree into a chain and yields O(n) |
| Looking for a ready balanced BST in the standard library | There is none — use dict, bisect over a sorted list, or third-party sortedcontainers |
Traversing a graph without a visited set | The first cycle makes the traversal infinite, and a diamond-shaped DAG produces exponentially many re-entries |
| Choosing an adjacency matrix for a sparse graph | O(V²) references instead of O(V+E) — hundreds of megabytes where units would do |
| Confusing a heap with a search tree | A heap is ordered vertically only, parent ≤ children; printing its list does not yield a sorted sequence |
What interviews check
The questions are deceptively simple — "how does a stack differ from a queue", "what is a tree", "what is a graph". Everyone knows the first half of the answer and the interviewer is not interested in it; the whole assessment happens in the second half, where you name the carrier and the complexity. "A queue is FIFO" closes the question at junior level; "a queue is FIFO, and in Python you build it on collections.deque, because removing from the head of a list costs O(n)" closes it at middle. The same holds for heaps: "a complete binary tree" is half of it, and the other half is "the heapq module over an ordinary list, min-heap only, heappush/heappop in O(log n), heapify in O(n)".
Then come two follow-ups that sink most candidates. The first is the worst case: "what if the keys are inserted in ascending order?" A correct answer separates a balanced tree from an unbalanced one and says O(n) without flinching. The second is the choice of representation: "ten thousand vertices, twenty thousand edges — what do you use?" What is wanted here is arithmetic, not a name: a list is on the order of V+E cells, a matrix is V², a difference of thousands of times. The typical mistake is identical on both questions — the candidate confidently recites a textbook definition and never once pronounces the letter O. When the topic goes deeper, expect a queue built from two stacks, why heapify is linear rather than O(n log n), and what you would use in place of the TreeMap the standard library does not have.