Learnings

Python in practice, part 6 of 9

Python Data Structures and Algorithms

A data structure is a way of arranging values so that some operations on them are cheap. An algorithm is a list of steps that solves a problem. This page covers the structures Python gives you, a few you can build yourself, and the algorithms that come up most often in interviews and in everyday code. The running example is a small bank. Every example runs on the standard library alone, so nothing needs pip install.

Measuring

Part 1 of 6 · how to say that code is fast or slow

Before comparing structures you need a way to compare them. Seconds are a poor measure, because they change with the machine. Programmers count steps and ask how the count grows when the input grows.

Big-O in plain words

Big-O notation describes how the amount of work grows as the input grows. The input size is called n: the number of accounts, transactions or customers. O(n) means "double the input and the work doubles". O(1) means "the work stays the same however large the input is".

Big-O drops small details. A loop that does 3 steps per item and a loop that does 5 steps per item are both O(n). What matters is the shape of the growth.

Big-ONameSteps at n = 1,000Steps at n = 1,000,000What it feels like
O(1)constant11Instant at any size. Looking up a dict key.
O(log n)logarithmicabout 10about 20Instant. Each step halves what is left. Binary search.
O(n)linear1,0001,000,000Fine. One pass over the data. Summing a list.
O(n log n)linearithmicabout 10,000about 20,000,000Still fine. Sorting.
O(n2)quadratic1,000,0001,000,000,000,000Fine for small input, hopeless for large input. A loop inside a loop over the same data.

Rule of thumb: plain Python gets through very roughly ten million simple steps in a second. A million steps is not noticeable. A million million steps would take more than a day.

Counting steps

You can see the growth rates without a clock. Each function below does a different kind of work and returns how many steps it took.

The input grew 100 times, from 10 to 1,000. The halving loop went from 3 steps to 9. The single pass grew 100 times. The loop inside a loop grew 10,000 times.

Habit: to find the Big-O of your own code, look for loops. One loop over the data is O(n). A loop inside a loop is usually O(n2). A loop that halves the data is O(log n). Also count hidden loops: x in some_list, sum(), max() and slicing all walk the list.

Built-in structures and their costs

Part 2 of 6 · list, dict, set and tuple

Python's four built-in containers cover most needs. They look similar in code, but the same operation can cost one step on one of them and a million steps on another.

Lists

A list keeps its items side by side in one block of memory, in order. Reading items[i] is O(1) because Python can jump straight to position i. Adding at the end with append is also O(1).

Adding at the front is different. insert(0, x) must first move every existing item one place to the right, so it is O(n). Doing it n times is O(n2).

The example prints a comparison and not the times themselves, because times differ on every machine and every run. The gap here is large enough that the answer is always True.

Searching a list with in, index() or count() is O(n). Python has no shortcut: it compares your value with each item from the left until it finds a match or runs out.

Dicts and sets

A dict and a set find things without searching. They use hashing. Python runs the key through the built-in hash() function, which turns it into a number. That number decides which slot of an internal table the key goes into. To look the key up later, Python computes the same number and goes straight to that slot.

So lookups, inserts and deletes are O(1) on average, whether the dict holds five accounts or five million.

A dict remembers the order in which keys were inserted. A set has no order you can rely on.

What can be a key

A key must be hashable: its hash must never change while it is in the dict. Immutable values such as numbers, strings and tuples of immutable values are hashable. Lists, dicts and sets can change, so they are not.

Detail: the actual number returned by hash() for a string changes each time Python starts. That is deliberate, for security. Never save hash values or depend on them.

Tuples

A tuple is a fixed sequence. It cannot grow, shrink or have an item replaced. Reading by position is O(1) and searching is O(n), the same as a list.

Use a tuple for a small group of values that belong together, such as one transaction. Use a list for a collection of similar things that changes over time, such as all transactions.

What each operation costs

These are the costs for CPython, the standard Python. "Average" means the usual case. n is the number of items in the container.

Operationlistdictsettuple
Read by position, x[i]O(1)not availablenot availableO(1)
Read by key, d[key]not availableO(1) averagenot availablenot available
Membership, x in cO(n)O(1) averageO(1) averageO(n)
Add at the endO(1), appendO(1) average, d[k] = vO(1) average, addcannot change
Add at the front or middleO(n), inserthas no positionshas no positionscannot change
Remove the last itemO(1), pop()O(1), popitem()not availablecannot change
Remove the first itemO(n), pop(0)not availablenot availablecannot change
Remove a given value or keyO(n), remove(x)O(1) average, del d[k]O(1) average, discard(x)cannot change
Length, len(c)O(1)O(1)O(1)O(1)
Loop over everythingO(n)O(n)O(n)O(n)
Copy or sliceO(size of the copy)O(n)O(n)O(size of the copy)
SortO(n log n)use sorted(d)use sorted(s)use sorted(t)

Trade-off: dicts and sets buy their speed with memory. They keep spare empty slots, so they take more room than a list holding the same items.

Choosing the right one

The most common mistake is to test membership on a list inside a loop. The example counts how many comparisons Python makes when it looks for one account among 1,000, first in a list and then in a set.

The list needed 1,000 comparisons. The set used the hash to go to the right slot and needed one comparison to confirm the match.

You need toReach for
Keep items in order and read them by positionlist
Ask "have I seen this before?" many timesset
Find a record by its id or namedict
Remove duplicatesset, or dict.fromkeys(items) to keep the order
Hold a small fixed record, or build a dict key from several valuestuple
Add and remove at both endscollections.deque, covered next

Structures from the library

Part 3 of 6 · ready-made tools in the standard library

The standard library adds structures for jobs the four built-ins do badly. Knowing they exist saves you from writing them by hand, and in an interview it shows that you know the language.

A queue with deque

A queue serves items in the order they arrived: first in, first out. Customers waiting at a bank counter form a queue.

A list is a poor queue. list.pop(0) removes the first item and then shifts every other item one place to the left, which is O(n). collections.deque (say "deck", short for double-ended queue) adds and removes at both ends in O(1).

Limit: a deque is fast at its two ends only. Reading or inserting in the middle is O(n). If you need items[i] often, stay with a list.

A stack with a list

A stack serves the newest item first: last in, first out. Think of a pile of plates. A plain list is a good stack, because append and pop() both work at the end and are O(1).

An undo history is a stack. The last change made is the first one undone.

A priority queue with heapq

A priority queue hands out the most important item first, whatever order the items arrived in. The heapq module keeps a plain list arranged as a heap, in which the smallest item is always at position 0. Adding an item and removing the smallest are both O(log n).

Here VIP customers have priority 1 and everyone else priority 2. A lower number is served first. The arrival number in the middle breaks ties, so two customers with the same priority are served in arrival order.

A heap is also the quick way to get the top few items of a large collection without sorting all of it.

Detail: heapq only makes a min-heap, with the smallest first. To serve the largest first, push the negative of the number, or use nlargest.

Searching a sorted list with bisect

If a list is sorted, you can find a position in it in O(log n) by repeatedly halving the range. The bisect module does this. bisect_right(limits, x) returns how many limits are less than or equal to x, which is exactly the question "which tier is this value in?".

The bank pays a higher interest rate on larger balances.

Detail: insort finds the position in O(log n), but the insert itself still shifts items, so the whole call is O(n).

Grouping and counting

Two jobs come up constantly: put items into groups, and count how often each thing appears. defaultdict creates a missing value for you the first time a key is used. Counter is a dict made for counting.

Both do the work in one pass, so they are O(n).

Records

A record is a group of named fields, such as one account. A plain tuple works, but account[2] says nothing about what position 2 holds. namedtuple gives the positions names and stays immutable. A dataclass is a normal class with the boring methods written for you, and its fields can change.

Choosing: use a namedtuple for small values that never change and may be used as dict keys. Use a dataclass when fields change or the record needs methods. Add @dataclass(frozen=True) to make a dataclass immutable and hashable.

Build your own

Part 4 of 6 · four classic structures written by hand

In real code you will rarely write these, because the built-ins and the library are faster and already tested. Interviewers still ask for them, and writing each one once is the best way to understand what the library does for you.

A linked list

A linked list is a chain of nodes. Each node holds one value and a reference to the next node. The list itself only remembers the first node, called the head.

Adding at the front is O(1): make a node and point it at the old head. Nothing has to shift. The price is that there is no items[i]. To reach an item you must walk the chain from the head, which is O(n).

Concept: because the class defines __iter__, a for loop, list() and in all work on it. collections.deque is built on a similar idea, with links in both directions.

Stack and queue classes

Wrapping a list or a deque in a small class gives the structure a clear name and hides the operations that would break it. Nobody can insert into the middle of a Stack by mistake.

A binary search tree

A binary search tree (BST) keeps values sorted in a branching shape. Each node has up to two children. Everything in the left branch is smaller than the node, and everything in the right branch is larger.

To search, start at the top and go left or right at each node. Each step throws away one branch. If the tree is balanced, meaning its branches have similar depth, a search takes O(log n) steps.

The in-order traversal visits the keys in sorted order. Seven accounts were searched in three steps.

Weakness: insert keys that are already sorted (1001, 1002, 1003, ...) and every node goes to the right. The tree becomes a linked list and searching falls to O(n). Self-balancing trees fix this, but Python has none built in. For sorted data in Python, use a sorted list with bisect, or a dict when you only need lookups.

A graph

A graph is a set of things, called nodes, and the connections between them, called edges. Road maps, social networks and file dependencies are graphs.

The simplest way to store one in Python is a dict. Each key is a node and its value is the list of nodes it connects to. Here the nodes are bank branches and an edge means that money can be transferred directly between the two.

Every route is stored twice, once from each end, because transfers work in both directions. The chapter on breadth-first and depth-first search uses this graph to find a route between two branches.

Algorithms

Part 5 of 6 · searching, sorting and the patterns behind interview questions

A small number of ideas solve a large share of problems. Each chapter here shows one idea in its smallest form.

Linear and binary search

Linear search checks each item in turn. It works on any list and is O(n). Binary search needs a sorted list. It looks at the middle item, then throws away the half that cannot contain the target, and repeats. It is O(log n).

Both found position 900. Linear search took 901 steps and binary search took 10. In real code, do not write binary search yourself. Use bisect, which is tested and runs at C speed.

Interview tip: the usual bugs in a hand-written binary search are low < high where low <= high is needed, and forgetting the + 1 or - 1, which makes the loop run forever. Test it with an empty list, one item, and targets at both ends.

Sorting with sorted

sorted(items) returns a new sorted list. items.sort() sorts a list in place and returns None. Both use an algorithm called Timsort. It is O(n log n) in the worst case and faster on data that is already partly in order, which real data often is. It is also stable: items that compare as equal keep the order they had before the sort.

The key argument is a function that is called once on each item. Python sorts by what the function returns. operator.itemgetter builds such a function for a position or dict key, and operator.attrgetter builds one for an attribute.

Sandhya and Subhash have the same balance. In both balance sorts Sandhya stays ahead of Subhash, because she came first in the original list. That is stability, and reverse=True keeps it.

Several keys in different directions

To sort by balance from high to low and then by name from A to Z, return a tuple from the key and negate the number. When a field cannot be negated, such as a string, sort twice: first by the least important key, then by the most important. Stability keeps the first order inside each group.

Detail: min() and max() take a key too, and they are O(n). Do not sort a whole list just to get its largest item.

Merge sort by hand

You should always use sorted() in real code. Writing one sort yourself shows where O(n log n) comes from. Merge sort follows a plan called divide and conquer: split the list in half, sort each half, then merge the two sorted halves into one.

Merging two sorted lists is easy. Look at the front of each, take the smaller, and repeat.

A list of n items can be halved about log n times before the pieces have one item each. At every level of halving, the merges together handle all n items. That gives n times log n.

Recursion and iteration

A recursive function calls itself on a smaller version of the problem. It needs a base case, an input small enough to answer directly, or it never stops. Iteration means solving the same problem with a loop.

Each call that has not finished yet takes up memory. Python stops a chain of calls that grows too deep and raises RecursionError. The default limit is 1000. So use recursion when the depth stays small, as it does in a balanced tree or in merge sort, and use a loop when the depth grows with the size of the input.

Memoisation

Fibonacci numbers show a second problem. Each number is the sum of the two before it, so the obvious recursive function calls itself twice, and those calls repeat the same work again and again. Memoisation means remembering the answer for each input the first time it is computed. functools.lru_cache adds that to any function.

The slow version made 21,891 calls to find the 20th number. With the cache the function body ran 21 times, once for each value from 0 to 20.

Detail: lru_cache only works when the arguments are hashable, because it stores them as dict keys. Python 3.9 and later also offer functools.cache, which is the same as lru_cache(maxsize=None).

Two pointers

A "pointer" here is just an index into a list. The two-pointer pattern keeps two of them and moves them towards each other. On a sorted list it replaces a loop inside a loop, turning O(n2) into O(n).

The problem: find two transactions that add up to exactly 10,000. Start with one pointer at the smallest amount and one at the largest. If the sum is too small, move the left pointer up. If it is too large, move the right pointer down.

Alternative: if the list is not sorted and you may not sort it, walk it once and keep the amounts seen so far in a set. For each amount, check whether target - amount is in the set. That is also O(n).

Sliding window

A window is a run of neighbouring items. Many problems ask for the best window: the largest total over any 3 days, the longest run without a repeat. The slow way adds up every window from scratch. The sliding-window pattern moves the window one step at a time and only adjusts for the item that entered and the item that left.

The best three days in a row start at position 4 and total 9,900. The loop does two small steps per day whatever the window size, so it is O(n).

Breadth-first and depth-first search

There are two standard ways to explore a graph. Breadth-first search (BFS) visits everything one step away, then everything two steps away, and so on. It uses a queue. Depth-first search (DFS) follows one path as far as it goes, then backs up and tries the next. It uses a stack, or recursion.

Both keep a set of nodes already seen, so they never visit a node twice or go round in circles.

The shortest route between two branches

Because BFS reaches nodes in order of distance, the first time it reaches the goal it has found a route with the fewest hops. Remember which branch each branch was reached from, then walk those links backwards from the goal.

Cost: BFS and DFS both visit each node once and look at each edge a fixed number of times, so they are O(nodes + edges). BFS finds the fewest hops only when every edge counts the same. If routes had different fees, you would need Dijkstra's algorithm, which is BFS with a heapq priority queue in place of the deque.

Dynamic programming

Dynamic programming (DP) is for problems whose answer is built from answers to smaller versions of the same problem, where those smaller versions repeat. You solve each small problem once and store the result. Memoised Fibonacci was already an example.

The problem: an ATM must pay out an amount using the fewest notes. The obvious plan is greedy: always take the largest note that fits. With real note values that works. Imagine a machine loaded with notes of 100, 300 and 400, and it fails.

The idea in one line: the fewest notes for an amount is one note plus the fewest notes for what remains, trying each note and keeping the best. Without the cache the same remaining amounts would be solved again and again.

Counting the ways

The same idea can be written as a loop that fills a table from the smallest problem upwards. This version counts in how many different ways an amount can be paid with 100, 200 and 500 notes. ways[a] holds the number of ways to pay a.

The four ways to pay 500 are one 500 note, 200+200+100, 200+100+100+100 and five 100 notes. The table makes the work O(amount × number of notes), where trying every combination would grow far faster.

How to spot DP: the question asks for the fewest, the most, or the number of ways, and a choice made now changes what is left to solve. Write the plain recursive version first, then add lru_cache.

Interview habits

Part 6 of 6 · how to work through a problem out loud

Knowing the structures is half of an interview. The other half is showing how you think. These two chapters are short on purpose.

A checklist for any problem

  1. Clarify. Repeat the problem in your own words. Ask how large the input can be, whether it is sorted, whether it can be empty, and whether values can repeat or be negative. Work one small example by hand.
  2. Brute force first. Say the simplest correct solution out loud, even if it is slow. A working O(n2) answer is worth more than a clever answer you cannot finish.
  3. State the complexity. Give the Big-O for time and for extra memory. Then ask what is repeated or wasted. That is usually where a dict, a set, sorting or a second pointer removes a loop.
  4. Test edge cases. Walk through your code with an empty input, one item, all items equal, and the largest and smallest values. Fix what breaks before you say you are done.

The example follows the steps for one question: "does this list of transaction ids contain a duplicate?"

Habit: keep the brute-force version. Comparing it with the fast version on small inputs, as the assert does here, is the cheapest test you can write.

Which structure to reach for

The problem saysReach forTypical cost
"Have I seen this before?", duplicates, membershipsetO(1) per check
Look up by id or name, count or group thingsdict, Counter, defaultdictO(1) per lookup
Process in arrival order, level by levelcollections.deque as a queueO(1) per add or remove
Undo, matching brackets, "most recent first"list as a stackO(1) per push or pop
Top k, smallest or largest so far, next most urgentheapqO(log n) per push or pop
Find a value or a range in sorted databinary search with bisectO(log n)
A pair or triple with a given sum in sorted datatwo pointersO(n)
Best run of neighbouring itemssliding windowO(n)
Fewest steps, shortest route with equal stepsbreadth-first searchO(nodes + edges)
Explore everything, find any path, detect a cycledepth-first searchO(nodes + edges)
Fewest, most or number of ways, with repeating sub-problemsdynamic programming, lru_cachenumber of distinct sub-problems × work for each
The order of the items does not matter to the answersort first, then one passO(n log n)

Big-O tells you how code grows, not how long it takes on your machine today. Measuring that, and understanding where time and memory go, is the subject of the next page: Python Performance and Memory.