Algorithms
You do not pass the algorithms round of a Python interview by reciting a textbook — you pass it with two numbers, the time and the space of whatever you just wrote. "It runs in O(n)" without the second number counts as half an answer, and "it runs fast" counts as none. On top of the classic theory Python adds a layer of its own: every standard-library operation has a concrete price, and that price often contradicts how the code looks. x in some_list looks exactly like x in some_set but costs O(n) against O(1); list.pop(0) looks like dequeuing but shifts the entire tail.
The second layer is what Python already implements, so you never rewrite it by hand. list.sort() and sorted() are Timsort — a stable hybrid sort with a hard O(n log n) worst-case guarantee and linear behaviour on partially ordered input. Binary search lives in the bisect module. The heap is heapq, the queue is collections.deque. You write your own quicksort for exactly one purpose — to show in an interview that you understand partitioning, pivot choice and the worst case; in production code it loses to sorted() on every axis at once. Work through each mechanism in the layers below, and always say both bounds out loud, time and space.
Topic map
- Big-O and asymptotics — an upper bound on the growth of time and space, dropping constants, and why the smaller asymptotic loses on small inputs.
- The real cost of Python operations — the complexity of
list,dictandsetoperations in CPython, amortization, and turningO(n·m)intoO(n)with a singleset. - Linear search —
O(n)with no ordering requirement, when it honestly beats binary search, and how a hash table replaces a nested scan. - Binary search and bisect — halving sorted data in
O(log n), the boundary invariant, and the ready-madebisect_left/bisect_right. - Rotated sorted array — the binary-search variant where each step decides which half is still sorted.
- Quicksort and Timsort — partitioning around a pivot,
O(n log n)average againstO(n²)on an edge pivot, the missing stability, and why production takessorted(). - Counting sort —
O(n + k)without a single comparison when the value range is bounded, and thekat which it loses. - External sorting — data that does not fit in RAM — slicing into sorted runs and
k-way merging viaheapq.merge. - Two pointers — opposing and same-direction pointers that buy
O(n)time atO(1)extra space. - Deduplication —
dict.fromkeyskeeps first-seen order,setdoes not, and unhashable elements need a key. - Matrix traversal — main and anti-diagonal indices, the
[[0]*n]*ntrap, and transposition viazip(*m). - Breadth-first search — level-by-level traversal on
collections.dequeinO(V + E), and shortest paths only in an unweighted graph. - Dijkstra's algorithm — shortest paths by weight via
heapq, lazy deletion instead ofdecrease-key, and the ban on negative edges. - Dynamic programming — optimal substructure and overlapping subproblems, top-down memoization against bottom-up tabulation.
- Greedy algorithms — the locally optimal choice, the conditions under which it is provably optimal, and its role as an approximation for NP-complete problems.
- k-nearest neighbours — a lazy classifier with no training, mandatory feature scaling, and the curse of dimensionality.
Common mistakes and traps
| Mistake | Consequence |
|---|---|
| Reading Big-O as seconds rather than a growth rate | Constants are dropped — an O(n log n) with a heavy constant genuinely loses to O(n²) on a hundred elements |
Leaving an in test against a list inside a loop | Each test costs O(m), so the whole pass becomes O(n·m) instead of O(n) with a set |
| Applying binary search to unsorted data | The discarded half may hold the target — the answer is wrong, and nothing raises |
| Writing your own quicksort with a first or last pivot | On already-sorted input the partition is maximally unbalanced — O(n²) and RecursionError at n = 2000; it is also unstable, unlike the Timsort behind sorted() |
Building a BFS queue on a list and popping with pop(0) | Every pop shifts the whole tail in O(n) — the traversal turns quadratic instead of O(V + E) |
| Running Dijkstra on a graph with negative weights | A finalized vertex is never revisited and the answer silently comes out too high — you need Bellman-Ford |
Dropping duplicates with set() and expecting order to survive | Set order follows hashes; on integers it accidentally looks sorted, on strings it falls apart |
| Assuming a greedy choice is always optimal | On coins [1, 3, 4] and amount 6 greedy takes three coins instead of two — optimality must be proven, not assumed |
What interviews check
The algorithms round works as a funnel. It opens with definitions — what O(n) means, how linear search differs from binary, how quicksort works. Precision of phrasing is enough here, but exactly one detail separates a junior from a middle — whether both bounds were named. "Binary search is O(log n)" is half of it; "O(log n) time, O(1) space in the iterative form and O(log n) in the recursive one, and the input must be sorted" is the full answer, after which half the follow-ups disappear.
Then come the questions about the worst case and Python specifics, and that is where candidates fall. "When does quicksort become O(n²)?" expects the pairing "an edge pivot plus already-sorted input", not a vague "on bad data". "Why does BFS not find the shortest path in a weighted graph?" expects you to name Dijkstra and explain that the queue counts edges, not weights. "How do you drop duplicates while keeping order?" expects dict.fromkeys, not set. The practical part almost always asks you to beat brute force — collapsing O(n²) to O(n) with a dict in two-sum, O(n·m) to O(n) with a set, O(n·m) to O((n + m) log n) with bisect. The typical mistake is always the same — the solution works and prints the right answer, but the candidate never states its complexity, and complexity is exactly what is being graded.