Interview prep
A coding interview gives you a problem, a short time to solve it, and someone who wants to hear how you think. This page brings together what Python Arena has for it: the modules on data structures and algorithms, interview questions to drill, which technique fits which problem, what Python's operations cost, a plan for working through a problem, and the standard library tools that save you code. With weeks to go, work through the modules in order. With days, drill the questions and study the two tables.
Data structures and algorithms
Python Arena's own modules, for after the course: Big-O and the classic speed-ups, sorting, hash tables, trees and heaps, graphs, backtracking and dynamic programming. Many challenges have a big hidden test that a slow solution can't finish in time, the way an interviewer asks "can you make it faster?" Start with the first module: the others build on its Big-O.
Interview questions in Deathmatch
Quick questions like the ones interviewers ask, about Python itself and about algorithms and their costs: predict the output, fill in a blank, spot the bug, say whether it runs, pick the right answer. While the Boss reps setting in Deathmatch is on, every 8th question is a small program to write. It's on unless you turn it off or your browser can't run Python. Interview prep in Deathmatch is open to everyone, with no lessons needed first, and gives you three lives.
- Python's surprises: defaults, copies, floats, slices and scope 25 questions
- Data structures and algorithms: costs, searching, sorting, hashing, heaps, graphs and dynamic programming 27 questions
- Classes, objects, generators and recursion 20 questions
- Python itself: closures, decorators, iterators, context managers and the GIL 26 questions
Which technique fits?
What a problem asks often points to the technique that solves it. Find the row that sounds like your problem: it names a technique, what it costs, and the step that teaches it. n is the number of items, h a tree's height, and V and E a graph's vertices and edges.
| The problem asks | A technique that fits | Where to learn it |
|---|---|---|
| Is there a duplicate? Are there two values that add up to a target? | A set of the values seen so far, or a dict from each value to its index (two sum): O(n) on average | Sets and dicts for speed (module 59) |
| How often does each value appear? Which one is the most common? | A dict of counts, or collections.Counter, whose most_common(k) gives the top k: O(n) on average to count | Sets and dicts for speed (module 59) |
| Put the items into groups, such as the words that are anagrams of each other | A dict of lists, keyed by what the items share: tuple(sorted(word)) for anagrams. O(n·m log m) on average for n words of up to m letters | Hashing your own keys (module 61) |
Design a hash set or a hash map without set or dict | A list of buckets, each a chain of keys, and hash(key) % len(buckets) to pick one: O(1) on average while there are about as many buckets as keys | Buckets and chaining (module 61) |
| Design a cache that drops the least recently used item when it's full | An OrderedDict, a dict plus a doubly linked list: move_to_end on each use, popitem(last=False) when full. O(1) per call on average | Challenge: an LRU cache (module 61) |
| The largest, the smallest or the best so far, such as the best profit from buying low and selling later | One pass that remembers the best so far (the lowest price): O(n) time, O(1) memory | Big-O in practice (module 59) |
| Find a value in a sorted list, where it would go, or how many lie in a range. Or the smallest value that passes a check | Binary search, or bisect_left and bisect_right: O(log n) each, once the list is sorted. On the answer, O(log S) calls of the check for answers up to S | Binary search (module 59) |
| A pair with a given sum in a sorted list, or two sorted lists to merge | Two pointers, each moving only one way: O(n), with no set or dict | Two pointers (module 59) |
| The sum of a range, asked many times, or how many stretches add up to exactly k, with negative values too | Prefix sums, built once in O(n): each range sum is then O(1). For exactly k, a dict counting the earlier prefix sums, O(n) | Prefix sums (module 59) |
| The biggest sum of a stretch of any length, with negative values too | Kadane's algorithm: the best sum of a stretch that ends at each value, max(value, ending + value). O(n) time, O(1) memory | Prefix sums (module 59) |
| The best stretch of values in a row: k in a row with the biggest sum, the longest with no repeat | A sliding window: add what enters on the right, take out what leaves on the left. O(n) | Challenge: sliding windows (module 59) |
| The two closest values, a repeat, or items in order by a property | Sort first, with a key if needed (a tuple breaks ties): O(n log n). Then each item needs only its neighbor | Python's sort: keys and stability (module 60) |
| Meetings that overlap: is there a clash? Merge them, or fit the most into one room | Sorted by start, merge in one pass by stretching the last end. Sorted by end, take each meeting that starts once the last one taken has ended, a greedy choice that is provably right. O(n log n) | Python's sort: keys and stability (module 60) |
| How far from sorted is a list? Count its inversions, the pairs in the wrong order | Merge sort that counts while it merges: O(n log n) | Merge sort (module 60) |
| Sort a list of only a few different values, such as 0s, 1s and 2s, in one pass | A three-way partition with three indexes: O(n) time, no extra list | Quicksort and partitioning (module 60) |
| Sort many small whole numbers, such as a million scores from 0 to 100 | Counting sort: count each value, then write them out in order. O(n + k) for values from 0 to k | Counting sort (module 60) |
| The k smallest or largest, the k-th smallest, or the median | heapq.nsmallest or nlargest, O(n log k). Quickselect for one value, O(n) on average | The k smallest and the median (module 60) |
| Always take the smallest or most urgent next while new items arrive, the k-th largest so far, or merge k sorted lists | A heap with heapq: push and pop in O(log n), the smallest is h[0]. For the k-th largest, keep only the k largest. To merge k sorted lists, keep the next item of each in the heap: O(N log k) for N items | Heaps and heapq (module 62) |
| Data nested to any depth, such as lists inside lists | Recursion: a loop goes across one level, and a call goes down into each list inside it. O(n) for n items in all | When loops get clumsy (module 48) |
| A question about a whole tree: its size or height, is it balanced, are two trees the same? | Recursion: handle the root and let the calls handle its subtrees, with the empty tree (None) as the base case. O(n) | Binary trees and recursion (module 62) |
| Reverse a linked list, find its middle, or does it loop? | A loop that follows the links: prev, node and nxt to reverse it, a slow and a fast pointer for the middle or a loop. O(n) time, O(1) memory | Binary trees and recursion (module 62) |
| Keep values in order while you add them and look them up | A binary search tree, O(h) per step, O(log n) when balanced. In Python, a sorted list with bisect: O(log n) to look up, O(n) to add | Binary search trees (module 62) |
| Is this a valid binary search tree? What's its k-th smallest value? | An in-order walk, which visits a search tree's values in sorted order, or bounds passed down. O(n) | Traversals and validation (module 62) |
| Brackets that must match, or the next bigger value to the right of each item, such as the days until a warmer day | A stack, a list with append and pop: push each opening bracket and pop at each closing one. For the next bigger value, a stack of the items still waiting, kept in order. O(n) | Traversals and validation (module 62) |
| A tree level by level: the widest level, the view from the right side | A deque as the queue, taking len(queue) nodes each round: O(n) time | Level order with a deque (module 62) |
| All the words that start with a prefix, as someone types | A trie: O(m) to add a word or to find a prefix of m letters | Challenge: tries (module 62) |
| The fewest steps through a maze or a network | Breadth-first search: a deque as the queue, each vertex marked when it joins. O(V + E) | Breadth-first search (module 63) |
| Count the islands, fill a region, or can I get from here to there? | Depth-first search with a stack of your own and one shared visited set: O(V + E) | Depth-first search and flood fill (module 63) |
| An order for tasks that wait for others, such as courses with prerequisites, or is there a cycle? | Topological sort with Kahn's algorithm, in-degrees and a queue: O(V + E) | Topological sort (module 63) |
| The cheapest route when each road has its own cost | Dijkstra's algorithm with a heap, for costs that aren't negative: O((V + E) log V) | Dijkstra's shortest paths (module 63) |
| Groups that keep merging: are these two connected yet? Which link is redundant? | Union-find with union by size and path compression: almost O(1) per operation | Challenge: union-find (module 63) |
| List every subset of the items | Backtracking that takes or leaves each item: choose, explore, un-choose. O(n·2ⁿ) | Subsets: take it or leave it (module 64) |
| List every ordering of the items, or of the letters of a word with repeats | Backtracking that puts an unused item in each place: O(n·n!) for n different items. When letters repeat, choose among the letters left, with a count for each | Permutations (module 64) |
| Every combination of numbers that adds up to a target | Backtracking on the sorted numbers, with break once one is too big: still exponential at worst, but whole branches are cut | Combinations and pruning (module 64) |
| Place things so that none clash, such as queens on a board | Backtracking that checks each choice before making it, in O(1) with sets. Exponential at worst, so prune early | The N queens (module 64) |
| Fill in a sudoku, or any grid where each empty cell allows only a few values | Backtracking that fills first the cell with the fewest allowed values and backs up as soon as a cell has none. Exponential at worst | A sudoku solver (module 64) |
| Is a word hidden in a grid of letters? Every path through a maze? | Depth-first search that marks a cell on the way in and unmarks it on the way out. Exponential at worst | Paths and words in a grid (module 64) |
| A recursive answer that asks the same smaller question again and again | Memoization with a dict or @cache: the number of different questions times the work for each | Memoization (module 65) |
| In how many ways can you climb n stairs? The most you can earn, never working two days in a row? | A table filled from the smallest case up: O(n) time, and O(1) memory when only the last two values are kept. When the problem asks for the count modulo a big prime such as 1,000,000,007, take it after every addition | Bottom-up tables (module 65) |
| The fewest coins that make an amount, or the number of ways to make it | A table over the amounts from 0 up (greedy can fail): O(amount × coins) | Coin change (module 65) |
| Count the paths through a grid that move right and down, or find the cheapest one | A table where each cell builds on the cell above it and the one to its left: O(rows × cols) | Paths through a grid (module 65) |
| Compare two strings: their longest common subsequence, or the fewest edits from one to the other | A table over the prefixes of both strings: O(n × m) for lengths n and m | Longest common subsequence and edit distance (module 65) |
| Pick items under a weight limit for the most value, or numbers that add up to exactly t | The 0/1 knapsack: a table, or one row looped downward. O(n × capacity) | Challenge: the 0/1 knapsack (module 65) |
What Python's operations cost
How the time of Python's common operations grows with the data, in Big-O: O(1) takes the same time whatever the size, O(log n) grows very slowly, and O(n) grows with n, the number of items. These are CPython's costs, the Python that this site runs. Watch for the O(n) ones inside a loop over the data: that's a loop inside a loop, O(n²). Big-O in practice explains the notation.
| Operation | Time | Notes |
|---|---|---|
a[i], a[i] = x, len(a) (list) | O(1) | A list knows where each item is, and keeps its length. |
a.append(x), a.pop() (list) | O(1) | At the end of the list. For append this is amortized: now and then the list grows its room and copies its items, but over many appends each one costs O(1). |
a.insert(i, x), a.pop(i), del a[i] (list) | O(n - i) | The items from place i to the end shift by one: O(n) at the front, O(1) at the end. To add and remove at the front, use a deque. |
x in a, a.index(x), a.count(x), a.remove(x) (list) | O(n) | Looks at the items one by one. Inside a loop over the list, that's O(n²): put the items in a set first, or in a dict of their positions or counts. |
a[i:j], a.copy() (list) | O(k) | Copies the k items it takes into a new list: all n for a.copy() or a[:]. a + b copies both lists too. |
min(a), max(a), sum(a) | O(n) | Each one goes through every item. Inside a loop, keep the best so far in a variable instead. |
d[k], d[k] = v, k in d, del d[k] (dict) | O(1) on average, O(n) at worst | The key's hash finds its place in the table at once. Adding a new key is amortized, like append: now and then the table grows and every key moves to the new one. The O(n) worst case comes when many keys collide. Load factor and rehashing shows how. |
x in s, s.add(x), s.discard(x) (set) | O(1) on average, O(n) at worst | A table of hashed values, like a dict's keys, with the same costs: add is amortized, as the table grows now and then, and the O(n) worst case comes when many values collide. |
set(a), dict(pairs), Counter(a) | O(n) on average, O(n²) at worst | Adds the n items one at a time, each at a dict's or a set's cost. |
c.most_common(k) (Counter) | O(m log k) | m is the number of different items. It keeps the k biggest counts in a heap, as heapq.nlargest does. Without k it sorts all m, O(m log m). |
od.move_to_end(k), od.popitem(last=False) (OrderedDict) | O(1) on average, O(n) at worst | move_to_end finds the key by its hash, like a dict, then moves it to the end of a chain of keys kept in order. popitem(last=False) takes the first key in that chain, the oldest, and deletes it from the table like del d[k]. These are the two moves of an LRU cache. |
q.append(x), q.appendleft(x), q.pop(), q.popleft() (deque) | O(1) | A collections.deque adds and removes at both ends quickly. q[0] and q[-1] are O(1) too, but q[i] in the middle is O(n). |
heapq.heappush(h, x), heapq.heappop(h) | O(log n) | The smallest item is always h[0], which costs O(1) to read. heapq.heapreplace pops and pushes in one O(log n) step. |
heapq.heapify(a) | O(n) | Turns a list into a heap in place, faster than n pushes, which cost O(n log n). |
heapq.nsmallest(k, a), heapq.nlargest(k, a) | O(n log k) | Keeps the k best seen so far in a heap. Cheaper than sorting everything when k is small. |
bisect.bisect_left(a, x), bisect.bisect_right(a, x) (sorted list) | O(log n) | Binary search. bisect.insort(a, x) finds the place as fast, but inserting there is O(n). |
a.sort(), sorted(a) | O(n log n) | Also at worst. Sorting is stable: equal items keep their order. A list that is already sorted takes only O(n). A key function is called once per item. |
s[i], len(s) (str) | O(1) | Strings can't be changed, so every change makes a new string. |
s + t (str) | O(len(s) + len(t)) | Copies both into a new string. |
''.join(parts) | O(n) | n is the length of the result. The way to build a long string from many pieces: adding pieces with += in a loop can copy the string so far each time, O(n²) in all. |
Average assumes keys that hash well, as numbers, strings and tuples of them do. len is O(1) for lists, strings, tuples, dicts, sets and deques. Python's wiki has a longer table of costs.
Working through a problem
Interviewers want to see how you think as much as the answer. A plan for working through a problem out loud:
- Say the problem back in your own words. Ask about the input: how big can it be, can it be empty, can values repeat or be negative?
- Let the size guide you. Plain Python does roughly ten to fifty million simple steps a second, so for 100,000 items O(n²) is far too slow, while O(n log n) is fine.
- Work through a small example by hand, then the tricky ones: empty, one item, all the same, already sorted.
- Say a simple way first, even a slow one, and what it costs. It's a start, and something to test a faster way against.
- Look for a faster way. Which row of the techniques table sounds like the problem? Is there a hidden loop, such as
inon a list or a slice inside a loop? What would a set, a dict, sorting or two pointers give you? - Agree on the plan before you code. Then write it, saying what each part does. If recursion could go deeper than about 1,000 calls, Python's limit, use a loop with a stack, a queue or a table instead.
- Test it out loud on your examples, line by line, edge cases too.
- Say what it costs in time and in memory, and what you would improve with more time.
Python's tools for interview problems
Python's standard library has a tool for many interview problems. Most interviewers let you use them, as long as you can say what each one costs and could write the idea yourself. Each module's name links to its documentation.
collectionsCounterdoes the counting of Counting and grouping in one line, andmost_common(k)gives the k most common, as in Sets and dicts for speed.defaultdict(list)gives a missing key an empty list, handy for grouping and for adjacency lists.dequeadds and removes at both ends in O(1): the queue of level order and breadth-first search.OrderedDictmoves a key to the end and drops the oldest, both O(1) on average: the heart of an LRU cache.heapqA heap in a plain list, as in Heaps and heapq:
heappushadds an item andheappoptakes out the smallest, each in O(log n), andheapifyturns a list into a heap in O(n).nsmallestandnlargestgive the k smallest or largest in O(n log k), as in The k smallest and the median. For the largest first, push the values negated.mergegoes through k sorted lists as one sorted sequence, keeping the next item of each in a heap: O(N log k) for N items in all.bisectBinary search on a sorted list, as in Binary search:
bisect_leftfinds where a value goes in O(log n), andbisect_right(a, high) - bisect_left(a, low)counts the values from low to high.insortputs a value in its place, but inserting it there is O(n).functoolscacheremembers what a function returned for each argument, so a recursive solution works out each smaller question only once: memoization, for dynamic programming.lru_cache(maxsize=...)keeps only the most recently used answers, as in an LRU cache. The arguments must be hashable: pass a tuple, not a list.itertoolspermutations,combinationsandproductgo through every ordering or choice, handy for a brute-force answer to test a faster one against (Permutations, Combinations and pruning).accumulategives running totals:list(accumulate(values, initial=0))is the list of prefix sums.mathinfis bigger than any other number: the start of a running minimum, or the mark for an amount that can't be made in Coin change.comb(n, k)counts the ways to choose k of n items without making them, andgcdgives the greatest common divisor.
Places to practice
Other sites with many more problems. When a row of the techniques table feels easy, solve a few problems of that kind there, out loud and against the clock.
- LeetCode: A large collection of interview problems by topic and difficulty, which you can solve in Python.
- NeetCode: A short list of key interview problems grouped by technique, with video explanations.
- HackerRank: Practice tracks on data structures and algorithms. Many companies use it for their coding tests.
- Exercism: Free Python exercises, with mentors who can review your code.
- Codewars: Small puzzles ranked by difficulty. After you solve one, you can read other people's solutions.
- Project Euler: Math puzzles where a slow way can take hours and a clever one a second.
- Advent of Code: Two-part puzzles released each December, with every past year's puzzles still online.