Free Handbook · Runs in your browser

Data Structures & Algorithms

Arrays, hash maps, stacks, queues, linked lists, trees, heaps and graphs — each built by hand and then as the Python built-in — plus searching, sorting, recursion and dynamic programming, traced step by step so they are easy, not scary.

0 / 108 lessons🔥 0 day streak

ShareX LinkedIn

Module 13 · what you'll be able to do

Explain what a data structure is and pick the right one by its cost table
Build a stack, a queue, a linked list and a binary search tree from scratch
Use dict, set, deque, heapq and sorted the way a working engineer does
Trace binary search, BFS and merge sort by hand
Turn a slow recursive solution into a fast one with memoisation
Recognise the structure an interview problem is secretly about

What a data structure is (and why you already use them)

A data structure is just a way of arranging data so that some operation is fast. A list is fast to index and slow to search; a dictionary is fast to search and cannot be indexed by position. An algorithm is a recipe that uses those operations. You have used both since Module 03 — this module makes the trade-offs explicit, because choosing the structure is most of solving the problem.

pythonEdit it. ⌘/Ctrl + Enter runs.

import time

names = [f"user{i}" for i in range(200_000)]
lookup = set(names)                 # same data, different structure

def timed(fn):
    t = time.perf_counter()
    fn()
    return (time.perf_counter() - t) * 1000

# Is "user199999" in the data?  A list checks every item; a set jumps straight there.
list_ms = timed(lambda: [("user199999" in names) for _ in range(200)])
set_ms = timed(lambda: [("user199999" in lookup) for _ in range(200)])
print("list search:", "much slower than the set" if list_ms > set_ms * 5 else "about the same (try a bigger list)")
print("set search:", "instant" if set_ms < 50 else "slow?")

You should see

list search: much slower than the set
set search: instant

Your turn

Change "user199999" to "user0" (the first item). Why is the list suddenly fast too? That is why we talk about the worst case.

The whole module on one card. O(1) means "the same speed no matter how big the data"; O(n) means "grows with the data". Module 12 has the plain-English version of Big-O.
Structure	Python	Index by position	Search by value	Add / remove at end	Add / remove at front	Ordered?
Array / dynamic array	`list`	O(1)	O(n)	O(1)	O(n)	yes, by insertion
Hash map	`dict`	—	O(1) by key	O(1)	—	insertion order kept
Hash set	`set`	—	O(1)	O(1)	—	no
Stack	`list` (append/pop)	—	O(n)	O(1)	—	LIFO
Queue	`collections.deque`	O(n)	O(n)	O(1)	O(1)	FIFO
Linked list	build it	O(n)	O(n)	O(1) with tail	O(1)	yes
Binary search tree	build it	—	O(log n) if balanced	O(log n)	—	sorted
Heap	`heapq`	—	O(n)	O(log n)	min in O(1)	partial
Graph	`dict` of lists	—	BFS / DFS O(V+E)	O(1)	—	no

How to use this module

Each lesson builds the structure by hand in ten to twenty lines, runs it, then shows the built-in you would use at work. Do not memorise the code. Memorise the cost table and the one sentence under each heading that says what the structure is for.

Arrays: what a list really is

A Python list is a dynamic array: one block of memory with slots side by side, so items[i] is a single jump. Adding at the end is cheap because Python keeps spare slots ready; inserting at the front is expensive because every other item has to shuffle right. That single fact explains most list performance.

pythonEdit it. ⌘/Ctrl + Enter runs.

import time

def timed(fn):
    t = time.perf_counter(); fn()
    return (time.perf_counter() - t) * 1000

n = 30_000
def append_end():
    a = []
    for i in range(n):
        a.append(i)
def insert_front():
    a = []
    for i in range(n):
        a.insert(0, i)        # shuffles everything right, every time
append_ms, insert_ms = timed(append_end), timed(insert_front)
print("append 30k at the END:", "fast" if append_ms < insert_ms else "?")
print("insert 30k at the FRONT:", "much slower — every item shuffles right" if insert_ms > append_ms * 3 else "similar?")

# The three list skills that matter most: index, slice, and knowing what mutates
nums = [10, 20, 30, 40, 50]
print(nums[0], nums[-1], nums[1:3], nums[::-1])
nums.append(60); nums.pop(); nums[2] = 99
print(nums)

# Two-dimensional "array": a list of lists (a grid)
grid = [[0] * 3 for _ in range(2)]     # 2 rows × 3 columns
grid[0][1] = 7
print(grid)

You should see

append 30k at the END: fast
insert 30k at the FRONT: much slower — every item shuffles right
10 50 [20, 30] [50, 40, 30, 20, 10]
[10, 20, 99, 40, 50]
[[0, 7, 0], [0, 0, 0]]

Your turn

Write rotate_left(items, k) that returns the list rotated left by k places using one slice expression. rotate_left([1,2,3,4,5], 2) → [3,4,5,1,2].

Error you will hit

The grid bug: [[0] * 3] * 2 makes two names for ONE row

python

grid = [[0] * 3] * 2
grid[0][1] = 7
print(grid)

[[0, 7, 0], [0, 7, 0]]

Why the interpreter said that

No exception — worse, a silent wrong answer. * 2 repeats the reference to the same inner list, so both rows are the same object. Changing "row 0" changes "row 1" too.

The fix

Build each row separately with a comprehension: [[0] * 3 for _ in range(2)]. The inner [0] * 3 is fine because ints are immutable.

python

grid = [[0] * 3 for _ in range(2)]
grid[0][1] = 7
print(grid)   # [[0, 7, 0], [0, 0, 0]]

Quick check

Which list operation is O(n) — grows with the size of the list?

Hash maps and sets: O(1) lookup

A hash map (Python dict) turns a key into a number with a hash function, and uses that number as the slot to store the value. Looking something up is therefore one calculation and one jump — no scanning. A set is a hash map that stores only keys. This is why "put it in a dict" fixes most slow code, and why keys must be immutable: a key whose hash could change would be lost in the wrong slot.

pythonEdit it. ⌘/Ctrl + Enter runs.

# A toy hash map in 15 lines — so it stops being magic
class TinyMap:
    def __init__(self, slots=8):
        self.buckets = [[] for _ in range(slots)]     # each slot holds (key, value) pairs
    def _slot(self, key):
        return hash(key) % len(self.buckets)          # key → slot number
    def put(self, key, value):
        bucket = self.buckets[self._slot(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value); return      # overwrite
        bucket.append((key, value))
    def get(self, key, default=None):
        for k, v in self.buckets[self._slot(key)]:  # only ONE bucket is searched
            if k == key:
                return v
        return default

m = TinyMap()
m.put("ada", 36); m.put("bob", 28); m.put("ada", 37)
print(m.get("ada"), m.get("bob"), m.get("zed", "?"))

# The real thing — and the four idioms you use every day
ages = {"ada": 36, "bob": 28}
print(ages.get("cy", 0))                     # missing key → default, no KeyError
counts = {}
for word in "a b a c b a".split():
    counts[word] = counts.get(word, 0) + 1   # counting idiom
print(counts)
from collections import Counter, defaultdict
print(Counter("a b a c b a".split()).most_common(1))
groups = defaultdict(list)
for name, team in [("ada", "data"), ("bob", "infra"), ("cy", "data")]:
    groups[team].append(name)                # missing key → new list
print(dict(groups))

# Sets: membership, and the three algebra operations
seen = {"ada", "bob"}
print("ada" in seen, "zed" in seen)
print(sorted({1, 2, 3} & {2, 3, 4}), sorted({1, 2} | {9}), sorted({1, 2, 3} - {2}))

# A toy hash map in 15 lines — so it stops being magic
class TinyMap:
    def __init__(self, slots=8):
        self.buckets = [[] for _ in range(slots)]     # each slot holds (key, value) pairs
    def _slot(self, key):
        return hash(key) % len(self.buckets)          # key → slot number
    def put(self, key, value):
        bucket = self.buckets[self._slot(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value); return      # overwrite
        bucket.append((key, value))
    def get(self, key, default=None):
        for k, v in self.buckets[self._slot(key)]:  # only ONE bucket is searched
            if k == key:
                return v
        return default

m = TinyMap()
m.put("ada", 36); m.put("bob", 28); m.put("ada", 37)
print(m.get("ada"), m.get("bob"), m.get("zed", "?"))

# The real thing — and the four idioms you use every day
ages = {"ada": 36, "bob": 28}
print(ages.get("cy", 0))                     # missing key → default, no KeyError
counts = {}
for word in "a b a c b a".split():
    counts[word] = counts.get(word, 0) + 1   # counting idiom
print(counts)
from collections import Counter, defaultdict
print(Counter("a b a c b a".split()).most_common(1))
groups = defaultdict(list)
for name, team in [("ada", "data"), ("bob", "infra"), ("cy", "data")]:
    groups[team].append(name)                # missing key → new list
print(dict(groups))

# Sets: membership, and the three algebra operations
seen = {"ada", "bob"}
print("ada" in seen, "zed" in seen)
print(sorted({1, 2, 3} & {2, 3, 4}), sorted({1, 2} | {9}), sorted({1, 2, 3} - {2}))

You should see

37 28 ?
0
{'a': 3, 'b': 2, 'c': 1}
[('a', 3)]
{'data': ['ada', 'cy'], 'infra': ['bob']}
True False
[2, 3] [1, 2, 9] [1, 3]

Your turn

Using a dict, write first_repeat(items) that returns the first value that appears twice, or None. One pass, O(n).

Error you will hit

TypeError: unhashable type: 'list'

python

visited = set()
visited.add([0, 1])

Traceback (most recent call last):
  File "your code", line 2, in <module>
    visited.add([0, 1])
TypeError: unhashable type: 'list'

Why the interpreter said that

A set (and a dict key) needs a hash, and a list refuses to have one because its contents can change. If the list changed after being stored, its hash would change and it could never be found again.

The fix

Use a tuple for a fixed record such as a coordinate. This comes up constantly in grid problems: visited.add((row, col)).

python

visited = set()
visited.add((0, 1))
print((0, 1) in visited)   # True

Hash function: Turns a key into an integer, fast and deterministically. Equal keys always hash equal. hash("ada") in Python.
Collision: Two keys landing in the same slot. Handled by chaining (a small list per slot, as above) or probing. Rare enough that lookups stay O(1) on average.
Hashable: Has a stable hash: str, int, float, bool, tuple (of hashables), frozenset. Not: list, dict, set.

Stacks: last in, first out

A stack is a pile of plates: you add to the top and take from the top. That is it. Python needs no special type — a list with append and pop is a perfect stack. Stacks are how the interpreter tracks function calls (the call stack in every traceback), how undo works, how brackets are matched, and how you turn recursion into a loop.

pythonEdit it. ⌘/Ctrl + Enter runs.

class Stack:
    def __init__(self):
        self._items = []
    def push(self, x):   self._items.append(x)
    def pop(self):       return self._items.pop()      # IndexError if empty — see below
    def peek(self):      return self._items[-1]
    def is_empty(self):  return not self._items
    def __len__(self):   return len(self._items)

s = Stack()
for x in [1, 2, 3]:
    s.push(x)
print(s.pop(), s.pop(), len(s), s.peek())

# Use 1: reverse anything
def reverse(text):
    stack = list(text)          # push every char
    out = ""
    while stack:
        out += stack.pop()      # pop gives them back reversed
    return out
print(reverse("stack"))

# Use 2: match brackets — the interview classic
def balanced(expr):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in expr:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack
print(balanced("{[()]}"), balanced("([)]"), balanced("(("))

# Use 3: evaluate postfix ("3 4 + 2 *" means (3 + 4) * 2)
def eval_postfix(tokens):
    stack = []
    for t in tokens.split():
        if t.isdigit():
            stack.append(int(t))
        else:
            b, a = stack.pop(), stack.pop()
            stack.append({"+": a + b, "-": a - b, "*": a * b}[t])
    return stack[0]
print(eval_postfix("3 4 + 2 *"))

class Stack:
    def __init__(self):
        self._items = []
    def push(self, x):   self._items.append(x)
    def pop(self):       return self._items.pop()      # IndexError if empty — see below
    def peek(self):      return self._items[-1]
    def is_empty(self):  return not self._items
    def __len__(self):   return len(self._items)

s = Stack()
for x in [1, 2, 3]:
    s.push(x)
print(s.pop(), s.pop(), len(s), s.peek())

# Use 1: reverse anything
def reverse(text):
    stack = list(text)          # push every char
    out = ""
    while stack:
        out += stack.pop()      # pop gives them back reversed
    return out
print(reverse("stack"))

# Use 2: match brackets — the interview classic
def balanced(expr):
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in expr:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack
print(balanced("{[()]}"), balanced("([)]"), balanced("(("))

# Use 3: evaluate postfix ("3 4 + 2 *" means (3 + 4) * 2)
def eval_postfix(tokens):
    stack = []
    for t in tokens.split():
        if t.isdigit():
            stack.append(int(t))
        else:
            b, a = stack.pop(), stack.pop()
            stack.append({"+": a + b, "-": a - b, "*": a * b}[t])
    return stack[0]
print(eval_postfix("3 4 + 2 *"))

You should see

3 2 1 1
kcats
True False False
14

Your turn

Write min_stack: a stack that also returns the current minimum in O(1). Hint: keep a second stack of "minimum so far".

VisualizeMatching brackets with a stackStep 1 / 7

1stack = []
2for ch in "([)]":
3    if ch in "([{":
4        stack.append(ch)
5    elif stack.pop() != {")": "(", "]": "["}[ch]:
6        print("unbalanced"); break

Line 2

First character (.

Variables now

`ch`	`'('`
`stack`	`[]`

All 7 steps as a table

Step	Line	What happened	Variables now
1	2	First character `(`.	`ch = '('` `stack = []`
2	4	It is an opener — push it.	`stack = ['(']`
3	2	Next `[`.	`ch = '['`
4	4	Opener — push.	`stack = ['(', '[']`
5	2	Next `)`.	`ch = ')'`
6	5	A closer. Pop the top: `[`. The matching opener for `)` is `(`. `[` ≠ `(`.	`stack = ['(']`
7	6	Mismatch — the brackets interleave, which is not allowed. Print and stop.

Error you will hit

IndexError: pop from empty list

python

stack = []
stack.pop()

Traceback (most recent call last):
  File "your code", line 2, in <module>
    stack.pop()
IndexError: pop from empty list

Why the interpreter said that

You popped more than you pushed. In bracket matching this is the ")(" case — a closer arrives before any opener. It is a real input, not a bug in pop.

The fix

Guard the pop: if not stack: return False. Every stack algorithm has this line.

Queues and deques: first in, first out

A queue is a line at a shop: join at the back, served from the front. Queues drive breadth-first search, task schedulers, print spoolers and message systems like Kafka. ⛔ A plain list is the wrong queue: pop(0) shuffles every element, O(n). Python's collections.deque ("deck", double-ended queue) does both ends in O(1).

pythonEdit it. ⌘/Ctrl + Enter runs.

from collections import deque
import time

q = deque()
q.append("ada"); q.append("bob"); q.append("cy")   # join the back
print(q.popleft(), q.popleft(), list(q))           # served from the front

# Both ends: deque is also a great stack, and a sliding window
d = deque([1, 2, 3])
d.appendleft(0); d.append(4)
print(d, d[0], d[-1])

window = deque(maxlen=3)                            # keeps only the last 3
for x in range(6):
    window.append(x)
print(list(window))

# Why not a list?
def timed(fn):
    t = time.perf_counter(); fn()
    return (time.perf_counter() - t) * 1000
n = 40_000
def list_queue():
    a = list(range(n))
    while a: a.pop(0)
def deque_queue():
    a = deque(range(n))
    while a: a.popleft()
list_ms, deque_ms = timed(list_queue), timed(deque_queue)
print("list.pop(0) × 40k:", "much slower — every pop moves the whole list" if list_ms > deque_ms * 3 else "similar?")
print("deque.popleft() × 40k:", "fast" if deque_ms < list_ms else "?")

# A queue-based simulation: hot potato / round-robin scheduler
def round_robin(tasks, quantum):
    q = deque(tasks)          # (name, remaining_time)
    order = []
    while q:
        name, left = q.popleft()
        left -= quantum
        if left > 0:
            q.append((name, left))   # back of the line
        else:
            order.append(name)       # finished
    return order
print(round_robin([("A", 5), ("B", 2), ("C", 4)], quantum=2))

from collections import deque
import time

q = deque()
q.append("ada"); q.append("bob"); q.append("cy")   # join the back
print(q.popleft(), q.popleft(), list(q))           # served from the front

# Both ends: deque is also a great stack, and a sliding window
d = deque([1, 2, 3])
d.appendleft(0); d.append(4)
print(d, d[0], d[-1])

window = deque(maxlen=3)                            # keeps only the last 3
for x in range(6):
    window.append(x)
print(list(window))

# Why not a list?
def timed(fn):
    t = time.perf_counter(); fn()
    return (time.perf_counter() - t) * 1000
n = 40_000
def list_queue():
    a = list(range(n))
    while a: a.pop(0)
def deque_queue():
    a = deque(range(n))
    while a: a.popleft()
list_ms, deque_ms = timed(list_queue), timed(deque_queue)
print("list.pop(0) × 40k:", "much slower — every pop moves the whole list" if list_ms > deque_ms * 3 else "similar?")
print("deque.popleft() × 40k:", "fast" if deque_ms < list_ms else "?")

# A queue-based simulation: hot potato / round-robin scheduler
def round_robin(tasks, quantum):
    q = deque(tasks)          # (name, remaining_time)
    order = []
    while q:
        name, left = q.popleft()
        left -= quantum
        if left > 0:
            q.append((name, left))   # back of the line
        else:
            order.append(name)       # finished
    return order
print(round_robin([("A", 5), ("B", 2), ("C", 4)], quantum=2))

You should see

ada bob ['cy']
deque([0, 1, 2, 3, 4]) 0 4
[3, 4, 5]
list.pop(0) × 40k: much slower — every pop moves the whole list
deque.popleft() × 40k: fast
['B', 'C', 'A']

Your turn

Implement a queue using two stacks (lists): push onto stack A; to pop, if stack B is empty pour A into B first. Amortised O(1) — a favourite interview question.

The one rule

Front removal → deque.popleft(), never list.pop(0). Every BFS you write from now on starts with from collections import deque.

Linked lists: nodes and pointers

A linked list is a chain of nodes, each holding a value and a reference to the next node. Nothing is side by side in memory, so there is no indexing — to reach item 5 you walk five links. What you gain: inserting or removing at a known node is O(1), with no shuffling. You will rarely build one at work (deque is a linked structure underneath), but you will be asked to in interviews, and it is the simplest way to learn to think in references.

pythonEdit it. ⌘/Ctrl + Enter runs.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next          # a reference to another Node, or None at the end

class LinkedList:
    def __init__(self):
        self.head = None
    def push_front(self, value):            # O(1)
        self.head = Node(value, self.head)
    def append(self, value):                # O(n) without a tail pointer
        node = Node(value)
        if self.head is None:
            self.head = node; return
        cur = self.head
        while cur.next:                     # walk to the last node
            cur = cur.next
        cur.next = node
    def remove(self, value):                # unlink the first match
        prev, cur = None, self.head
        while cur and cur.value != value:
            prev, cur = cur, cur.next
        if cur is None:
            return False
        if prev is None:
            self.head = cur.next            # removing the head
        else:
            prev.next = cur.next            # skip over cur
        return True
    def __iter__(self):
        cur = self.head
        while cur:
            yield cur.value
            cur = cur.next
    def __repr__(self):
        return " -> ".join(str(v) for v in self) + " -> None"

ll = LinkedList()
for v in [3, 2, 1]:
    ll.push_front(v)
ll.append(4)
print(ll)
print(ll.remove(2), ll.remove(99), ll)

# The interview classic: reverse in place, three pointers
def reverse(ll):
    prev, cur = None, ll.head
    while cur:
        nxt = cur.next        # remember where we were going
        cur.next = prev       # flip the arrow
        prev, cur = cur, nxt  # step forward
    ll.head = prev
reverse(ll)
print(ll)

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next          # a reference to another Node, or None at the end

class LinkedList:
    def __init__(self):
        self.head = None
    def push_front(self, value):            # O(1)
        self.head = Node(value, self.head)
    def append(self, value):                # O(n) without a tail pointer
        node = Node(value)
        if self.head is None:
            self.head = node; return
        cur = self.head
        while cur.next:                     # walk to the last node
            cur = cur.next
        cur.next = node
    def remove(self, value):                # unlink the first match
        prev, cur = None, self.head
        while cur and cur.value != value:
            prev, cur = cur, cur.next
        if cur is None:
            return False
        if prev is None:
            self.head = cur.next            # removing the head
        else:
            prev.next = cur.next            # skip over cur
        return True
    def __iter__(self):
        cur = self.head
        while cur:
            yield cur.value
            cur = cur.next
    def __repr__(self):
        return " -> ".join(str(v) for v in self) + " -> None"

ll = LinkedList()
for v in [3, 2, 1]:
    ll.push_front(v)
ll.append(4)
print(ll)
print(ll.remove(2), ll.remove(99), ll)

# The interview classic: reverse in place, three pointers
def reverse(ll):
    prev, cur = None, ll.head
    while cur:
        nxt = cur.next        # remember where we were going
        cur.next = prev       # flip the arrow
        prev, cur = cur, nxt  # step forward
    ll.head = prev
reverse(ll)
print(ll)

You should see

1 -> 2 -> 3 -> 4 -> None
True False 1 -> 3 -> 4 -> None
4 -> 3 -> 1 -> None

Your turn

Add find_middle() using two pointers — slow moves one node per step, fast moves two. When fast reaches the end, slow is in the middle. No length count needed.

VisualizeReversing 1 → 2 → 3 with three pointersStep 1 / 11

1prev, cur = None, head          # head is node 1
2while cur:
3    nxt = cur.next
4    cur.next = prev
5    prev, cur = cur, nxt
6head = prev

Line 1

Start: nothing reversed yet; cur is node 1.

Variables now

`prev`	`None`
`cur`	`1`
`list`	`1→2→3`

All 11 steps as a table

Step	Line	What happened	Variables now
1	1	Start: nothing reversed yet; `cur` is node 1.	`prev = None` `cur = 1` `list = 1→2→3`
2	3	Remember node 2 before we break the link.	`nxt = 2`
3	4	Point node 1 backwards (at None). Node 1 is now the tail of the reversed part.	`list = 1→None, 2→3`
4	5	Advance: the reversed part ends at 1; continue from 2.	`prev = 1` `cur = 2`
5	3	Remember node 3.	`nxt = 3`
6	4	Node 2 now points back at node 1.	`list = 2→1→None, 3`
7	5	Advance.	`prev = 2` `cur = 3`
8	3	Remember None — nothing after 3.	`nxt = None`
9	4	Node 3 points back at node 2.	`list = 3→2→1→None`
10	5	Advance: cur becomes None, so the loop ends.	`prev = 3` `cur = None`
11	6	The new head is the last node we processed.	`head = 3`

Error you will hit

AttributeError: 'NoneType' object has no attribute 'next'

python

cur = head
while cur.next.value != 99:     # walks off the end
    cur = cur.next

Traceback (most recent call last):
  File "your code", line 2, in <module>
    while cur.next.value != 99:
AttributeError: 'NoneType' object has no attribute 'next'

Why the interpreter said that

Every linked-list bug is this one: a pointer reached None (the end) and you asked it for .next or .value. Here 99 was not in the list, so the walk ran off the end.

The fix

Loop while cur (or while cur and cur.next) and check the value inside the body. Draw the boxes and arrows on paper before you code — everyone does.

Recursion, revisited: the call stack you can see

Module 04 introduced recursion. Trees, graphs and divide-and-conquer sorting all lean on it, so here is the mental model that makes it easy: a recursive function is a base case (the answer for the smallest input, no recursion) plus a step that shrinks the problem and trusts the function to solve the smaller one. Each call is a frame on the call stack; the answers assemble on the way back up.

pythonEdit it. ⌘/Ctrl + Enter runs.

def factorial(n):
    if n <= 1:                    # base case
        return 1
    return n * factorial(n - 1)   # step: trust the smaller call
print(factorial(5))

# Make the stack visible
def factorial_loud(n, depth=0):
    print("  " * depth + f"factorial({n})")
    if n <= 1:
        print("  " * depth + "→ 1"); return 1
    result = n * factorial_loud(n - 1, depth + 1)
    print("  " * depth + f"→ {result}")
    return result
factorial_loud(4)

# Recursion on a structure: sum a nested list of any depth
def deep_sum(x):
    if isinstance(x, list):
        return sum(deep_sum(item) for item in x)
    return x
print(deep_sum([1, [2, [3, 4]], 5]))

# Every recursion is also a loop with an explicit stack
def deep_sum_iter(x):
    total, stack = 0, [x]
    while stack:
        item = stack.pop()
        if isinstance(item, list):
            stack.extend(item)
        else:
            total += item
    return total
print(deep_sum_iter([1, [2, [3, 4]], 5]))

# Recursion limit is real
import sys
print(sys.getrecursionlimit())

def factorial(n):
    if n <= 1:                    # base case
        return 1
    return n * factorial(n - 1)   # step: trust the smaller call
print(factorial(5))

# Make the stack visible
def factorial_loud(n, depth=0):
    print("  " * depth + f"factorial({n})")
    if n <= 1:
        print("  " * depth + "→ 1"); return 1
    result = n * factorial_loud(n - 1, depth + 1)
    print("  " * depth + f"→ {result}")
    return result
factorial_loud(4)

# Recursion on a structure: sum a nested list of any depth
def deep_sum(x):
    if isinstance(x, list):
        return sum(deep_sum(item) for item in x)
    return x
print(deep_sum([1, [2, [3, 4]], 5]))

# Every recursion is also a loop with an explicit stack
def deep_sum_iter(x):
    total, stack = 0, [x]
    while stack:
        item = stack.pop()
        if isinstance(item, list):
            stack.extend(item)
        else:
            total += item
    return total
print(deep_sum_iter([1, [2, [3, 4]], 5]))

# Recursion limit is real
import sys
print(sys.getrecursionlimit())

You should see

120
factorial(4)
  factorial(3)
    factorial(2)
      factorial(1)
      → 1
    → 2
  → 6
→ 24
15
15
1000

Your turn

Write power(base, exp) recursively in O(log exp): if exp is even, power(base, exp // 2) ** 2; if odd, multiply by base once more.

Visualizefactorial(3): down the stack, then back upStep 1 / 10

1def factorial(n):
2    if n <= 1:
3        return 1
4    return n * factorial(n - 1)
5print(factorial(3))

Line 5

Call factorial(3). A frame is pushed.

Variables now

stack f(3)

All 10 steps as a table

Step	Line	What happened	Variables now
1	5	Call `factorial(3)`. A frame is pushed.	`stack = f(3)`
2	2	3 ≤ 1? No.	`n = 3`
3	4	Needs `factorial(2)` first — push another frame and wait.	`stack = f(3) f(2)`
4	2	2 ≤ 1? No.	`n = 2`
5	4	Needs `factorial(1)` — push.	`stack = f(3) f(2) f(1)`
6	2	1 ≤ 1? Yes — base case.	`n = 1`
7	3	Return 1. Frame popped.	`stack = f(3) f(2)`
8	4	f(2) resumes: 2 × 1 = 2. Return. Frame popped.	`stack = f(3)`
9	4	f(3) resumes: 3 × 2 = 6. Return.	`stack = (empty)`
10	5	Print the result.

Error you will hit

RecursionError: maximum recursion depth exceeded

python

def count_down(n):
    print(n)
    count_down(n - 1)      # no base case
count_down(3)

3
2
1
0
-1
...
RecursionError: maximum recursion depth exceeded

Why the interpreter said that

Nothing ever stops the calls, so frames pile up until Python refuses (default limit 1000). The same error appears when the base case exists but the step does not move toward it, e.g. count_down(n) instead of n - 1.

The fix

Every recursive function needs (1) a base case that returns without recursing and (2) a step that makes the input strictly smaller. Write the base case first.

python

def count_down(n):
    if n < 0:
        return
    print(n)
    count_down(n - 1)
count_down(3)

Trees and binary search trees

A tree is nodes with children instead of a single next: folders on a disk, HTML elements, a company org chart, the JSON you parsed in Module 06. A binary search tree (BST) is a tree with a rule — everything left is smaller, everything right is bigger — which turns searching into "go left or go right" and halves the work at every step: O(log n) when the tree is balanced.

pythonEdit it. ⌘/Ctrl + Enter runs.

class TreeNode:
    def __init__(self, value):
        self.value, self.left, self.right = value, None, None

def insert(root, value):
    if root is None:
        return TreeNode(value)                     # found the empty spot
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

def contains(root, value):
    while root:
        if value == root.value:
            return True
        root = root.left if value < root.value else root.right   # halve the search
    return False

root = None
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, v)
print(contains(root, 7), contains(root, 5))

# The three traversals — in-order gives you the values SORTED
def inorder(n):    return inorder(n.left) + [n.value] + inorder(n.right) if n else []
def preorder(n):   return [n.value] + preorder(n.left) + preorder(n.right) if n else []
def postorder(n):  return postorder(n.left) + postorder(n.right) + [n.value] if n else []
print(inorder(root))
print(preorder(root))
print(postorder(root))

def height(n):
    return 0 if n is None else 1 + max(height(n.left), height(n.right))
print(height(root))

# Level-order (BFS) — needs a queue, prints the tree row by row
from collections import deque
def level_order(root):
    rows, q = [], deque([root])
    while q:
        rows.append([n.value for n in q])
        q = deque(c for n in q for c in (n.left, n.right) if c)
    return rows
print(level_order(root))

class TreeNode:
    def __init__(self, value):
        self.value, self.left, self.right = value, None, None

def insert(root, value):
    if root is None:
        return TreeNode(value)                     # found the empty spot
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

def contains(root, value):
    while root:
        if value == root.value:
            return True
        root = root.left if value < root.value else root.right   # halve the search
    return False

root = None
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, v)
print(contains(root, 7), contains(root, 5))

# The three traversals — in-order gives you the values SORTED
def inorder(n):    return inorder(n.left) + [n.value] + inorder(n.right) if n else []
def preorder(n):   return [n.value] + preorder(n.left) + preorder(n.right) if n else []
def postorder(n):  return postorder(n.left) + postorder(n.right) + [n.value] if n else []
print(inorder(root))
print(preorder(root))
print(postorder(root))

def height(n):
    return 0 if n is None else 1 + max(height(n.left), height(n.right))
print(height(root))

# Level-order (BFS) — needs a queue, prints the tree row by row
from collections import deque
def level_order(root):
    rows, q = [], deque([root])
    while q:
        rows.append([n.value for n in q])
        q = deque(c for n in q for c in (n.left, n.right) if c)
    return rows
print(level_order(root))

You should see

True False
[1, 3, 4, 6, 7, 8, 10, 13, 14]
[8, 3, 1, 6, 4, 7, 10, 14, 13]
[1, 4, 7, 6, 3, 13, 14, 10, 8]
4
[[8], [3, 10], [1, 6, 14], [4, 7, 13]]

Your turn

Write min_value(root) (keep going left) and max_value(root). Then is_bst(root): check that the in-order traversal is strictly increasing.

A BST is only fast if it is balanced

Insert 1, 2, 3, 4, 5 in that order and every node goes right: you have built a linked list with extra steps, and search is O(n) again. Real systems use self-balancing trees (AVL, red-black — what a database index is). You will not implement one; you should know why they exist.

Quick check

Which traversal of a binary search tree visits the values in sorted order?

Heaps: always know the smallest

A heap is a tree stored in a flat list with one promise: the smallest item is always at index 0. Adding or removing the smallest costs O(log n) — far better than re-sorting a list. That makes it a priority queue: "give me the most urgent thing next". Python ships it as heapq, which works on a plain list. Use it for top-k, merging sorted streams, scheduling, and Dijkstra.

pythonEdit it. ⌘/Ctrl + Enter runs.

import heapq

h = []
for x in [5, 1, 8, 3, 2]:
    heapq.heappush(h, x)
print(h[0], h)                  # smallest at h[0]; the rest is heap order, NOT sorted
print([heapq.heappop(h) for _ in range(len(h))])   # popping repeatedly IS sorted

# Top-k without sorting everything: O(n log k)
scores = [72, 95, 88, 61, 99, 84, 90]
print(heapq.nlargest(3, scores), heapq.nsmallest(2, scores))

# Priority queue of tasks: (priority, task) tuples compare by priority first
tasks = [(3, "write tests"), (1, "fix prod"), (2, "review PR")]
heapq.heapify(tasks)              # turn a list into a heap in place, O(n)
while tasks:
    print(heapq.heappop(tasks))

# Max-heap: negate the values
nums = [4, 9, 2]
mx = [-n for n in nums]
heapq.heapify(mx)
print(-heapq.heappop(mx))

# Merge k sorted lists — the classic
print(list(heapq.merge([1, 4, 9], [2, 3], [5, 6, 7])))

You should see

1 [1, 2, 8, 5, 3]
[1, 2, 3, 5, 8]
[99, 95, 90] [61, 72]
(1, 'fix prod')
(2, 'review PR')
(3, 'write tests')
9
[1, 2, 3, 4, 5, 6, 7, 9]

Your turn

Given a stream of numbers, print the running median after each one using two heaps (a max-heap of the lower half, a min-heap of the upper half).

Error you will hit

The heap is not a sorted list

python

import heapq
h = [5, 1, 8, 3, 2]
heapq.heapify(h)
print(h[1])       # "second smallest"?

Why the interpreter said that

No exception — a wrong answer. Only h[0] is guaranteed to be the minimum. The heap keeps a looser order (each parent ≤ its children) precisely so that pushes and pops stay O(log n).

The fix

Pop to get items in order, or use heapq.nsmallest(2, h).

python

import heapq
h = [5, 1, 8, 3, 2]
heapq.heapify(h)
print(heapq.nsmallest(2, h)[1])   # 2

Graphs: BFS and DFS

A graph is nodes (vertices) joined by edges: cities and roads, users and follows, tasks and their dependencies, files and imports. A tree is just a graph with no cycles. The universal representation is an adjacency list — a dict from each node to the list of its neighbours. Two algorithms cover most graph questions: BFS (a queue, explores by distance — shortest path in unweighted graphs) and DFS (a stack or recursion, explores by depth — cycles, components, ordering).

pythonEdit it. ⌘/Ctrl + Enter runs.

from collections import deque

# Undirected graph as an adjacency list
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
    "F": [],            # isolated
}

def bfs(graph, start):
    """Visit by distance. The queue holds the frontier; visited stops cycles."""
    order, visited, q = [], {start}, deque([start])
    while q:
        node = q.popleft()
        order.append(node)
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                q.append(nb)
    return order
print("bfs ", bfs(graph, "A"))

def dfs(graph, start):
    """Same code with a stack instead of a queue — goes deep first."""
    order, visited, stack = [], set(), [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        stack.extend(reversed(graph[node]))
    return order
print("dfs ", dfs(graph, "A"))

def shortest_path(graph, start, goal):
    """BFS, remembering how we reached each node."""
    parent, q = {start: None}, deque([start])
    while q:
        node = q.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node); node = parent[node]
            return path[::-1]
        for nb in graph[node]:
            if nb not in parent:
                parent[nb] = node
                q.append(nb)
    return None
print(shortest_path(graph, "A", "E"), shortest_path(graph, "A", "F"))

def components(graph):
    seen, groups = set(), []
    for node in graph:
        if node not in seen:
            group = bfs(graph, node)
            seen.update(group)
            groups.append(sorted(group))
    return groups
print(components(graph))

# Directed graph + DFS = topological order (do tasks in dependency order)
deps = {"build": ["test"], "lint": ["test"], "test": ["deploy"], "deploy": []}
def topo(g):
    seen, out = set(), []
    def visit(n):
        if n in seen: return
        seen.add(n)
        for m in g[n]: visit(m)
        out.append(n)            # added AFTER everything it points to
    for n in g: visit(n)
    return out[::-1]
print(topo(deps))

from collections import deque

# Undirected graph as an adjacency list
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
    "F": [],            # isolated
}

def bfs(graph, start):
    """Visit by distance. The queue holds the frontier; visited stops cycles."""
    order, visited, q = [], {start}, deque([start])
    while q:
        node = q.popleft()
        order.append(node)
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                q.append(nb)
    return order
print("bfs ", bfs(graph, "A"))

def dfs(graph, start):
    """Same code with a stack instead of a queue — goes deep first."""
    order, visited, stack = [], set(), [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        stack.extend(reversed(graph[node]))
    return order
print("dfs ", dfs(graph, "A"))

def shortest_path(graph, start, goal):
    """BFS, remembering how we reached each node."""
    parent, q = {start: None}, deque([start])
    while q:
        node = q.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node); node = parent[node]
            return path[::-1]
        for nb in graph[node]:
            if nb not in parent:
                parent[nb] = node
                q.append(nb)
    return None
print(shortest_path(graph, "A", "E"), shortest_path(graph, "A", "F"))

def components(graph):
    seen, groups = set(), []
    for node in graph:
        if node not in seen:
            group = bfs(graph, node)
            seen.update(group)
            groups.append(sorted(group))
    return groups
print(components(graph))

# Directed graph + DFS = topological order (do tasks in dependency order)
deps = {"build": ["test"], "lint": ["test"], "test": ["deploy"], "deploy": []}
def topo(g):
    seen, out = set(), []
    def visit(n):
        if n in seen: return
        seen.add(n)
        for m in g[n]: visit(m)
        out.append(n)            # added AFTER everything it points to
    for n in g: visit(n)
    return out[::-1]
print(topo(deps))

You should see

bfs  ['A', 'B', 'C', 'D', 'E']
dfs  ['A', 'B', 'D', 'C', 'E']
['A', 'B', 'D', 'E'] None
[['A', 'B', 'C', 'D', 'E'], ['F']]
['lint', 'build', 'test', 'deploy']

Your turn

Add a has_cycle(graph) for the directed deps graph: DFS with three colours (unvisited / in progress / done) — reaching an "in progress" node means a cycle.

VisualizeBFS from A: the queue is the frontierStep 1 / 9

1visited, q = {"A"}, deque(["A"])
2while q:
3    node = q.popleft()
4    order.append(node)
5    for nb in graph[node]:
6        if nb not in visited:
7            visited.add(nb); q.append(nb)

Line 1

Start with A marked and queued.

Variables now

`q`	`[A]`
`visited`	`{A}`
`order`	`[]`

All 9 steps as a table

Step	Line	What happened	Variables now
1	1	Start with A marked and queued.	`q = [A]` `visited = {A}` `order = []`
2	3	Take A from the front.	`node = A` `q = []`
3	4	Record it.	`order = [A]`
4	7	A's neighbours B and C are new — mark and queue both.	`q = [B, C]` `visited = {A, B, C}`
5	3	Take B.	`node = B` `q = [C]`
6	7	B's neighbours: A (seen), D (new).	`q = [C, D]` `visited = {A, B, C, D}` `order = [A, B]`
7	3	Take C. Its neighbours A and D are already seen — nothing queued.	`node = C` `q = [D]` `order = [A, B, C]`
8	3	Take D. New neighbour: E.	`node = D` `q = [E]` `order = [A, B, C, D]` `visited = {A, B, C, D, E}`
9	3	Take E. No new neighbours. Queue empty — done. F was never reachable.	`q = []` `order = [A, B, C, D, E]`

Which one?

Shortest path / fewest steps / nearest → BFS. Does a path exist / count components / detect a cycle / order dependencies → DFS. Weighted shortest path → Dijkstra, which is BFS with a heap instead of a queue. Grid problems ("number of islands") are graphs where each cell's neighbours are up/down/left/right — Module 12 has one.

Searching: linear vs binary

Linear search checks every item — O(n), and the only option for unsorted data. Binary search works on sorted data: look at the middle, and the half the target cannot be in is thrown away. A million items take at most 20 steps. The idea generalises far beyond lists — "find the smallest X that satisfies a condition" is binary search on the answer.

pythonEdit it. ⌘/Ctrl + Enter runs.

def linear_search(items, target):
    for i, x in enumerate(items):
        if x == target:
            return i
    return -1

def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    steps = 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid, steps
        if items[mid] < target:
            lo = mid + 1            # target is in the right half
        else:
            hi = mid - 1            # target is in the left half
    return -1, steps

data = list(range(0, 2_000_000, 2))         # a million even numbers, sorted
print(linear_search(data, 1_999_998))         # checks a million items
print(binary_search(data, 1_999_998))         # 20 steps
print(binary_search(data, 7))                 # not there (odd)

# The standard library version
import bisect
print(bisect.bisect_left([1, 3, 5, 7], 5), bisect.bisect_left([1, 3, 5, 7], 4))

# Binary search on the ANSWER: smallest capacity that ships all packages in D days
def days_needed(weights, cap):
    days, load = 1, 0
    for w in weights:
        if load + w > cap:
            days += 1; load = 0
        load += w
    return days
def min_capacity(weights, D):
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(weights, mid) <= D:
            hi = mid                # feasible — try smaller
        else:
            lo = mid + 1
    return lo
print(min_capacity([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))

def linear_search(items, target):
    for i, x in enumerate(items):
        if x == target:
            return i
    return -1

def binary_search(items, target):
    lo, hi = 0, len(items) - 1
    steps = 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid, steps
        if items[mid] < target:
            lo = mid + 1            # target is in the right half
        else:
            hi = mid - 1            # target is in the left half
    return -1, steps

data = list(range(0, 2_000_000, 2))         # a million even numbers, sorted
print(linear_search(data, 1_999_998))         # checks a million items
print(binary_search(data, 1_999_998))         # 20 steps
print(binary_search(data, 7))                 # not there (odd)

# The standard library version
import bisect
print(bisect.bisect_left([1, 3, 5, 7], 5), bisect.bisect_left([1, 3, 5, 7], 4))

# Binary search on the ANSWER: smallest capacity that ships all packages in D days
def days_needed(weights, cap):
    days, load = 1, 0
    for w in weights:
        if load + w > cap:
            days += 1; load = 0
        load += w
    return days
def min_capacity(weights, D):
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(weights, mid) <= D:
            hi = mid                # feasible — try smaller
        else:
            lo = mid + 1
    return lo
print(min_capacity([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))

You should see

999999
(999999, 20)
(-1, 20)
2 2
15

Your turn

Write first_true(lo, hi, pred): given that pred is False then True across the range, return the first index where it is True. Then use it to find the square root of 1,000,000 to the nearest integer.

VisualizeBinary search for 7 in [1, 3, 5, 7, 9, 11]Step 1 / 7

1lo, hi = 0, 5
2while lo <= hi:
3    mid = (lo + hi) // 2
4    if items[mid] == 7: break
5    if items[mid] < 7: lo = mid + 1
6    else: hi = mid - 1

Line 1

Search the whole list.

Variables now

`lo`	`0`
`hi`	`5`

All 7 steps as a table

Step	Line	What happened	Variables now
1	1	Search the whole list.	`lo = 0` `hi = 5`
2	3	Middle index (0 + 5) // 2 = 2 → items[2] is 5.	`mid = 2`
3	5	5 < 7, so 7 must be to the right. Discard indexes 0–2.	`lo = 3`
4	3	Middle of 3..5 is 4 → items[4] is 9.	`mid = 4`
5	6	9 > 7, so look left. Discard 4–5.	`hi = 3`
6	3	lo == hi == 3 → items[3] is 7.	`mid = 3`
7	4	Found in 3 steps. Linear search would have taken 4 — and for a million items, 20 versus a million.

Error you will hit

Binary search on unsorted data returns nonsense

python

items = [9, 1, 7, 3]
print(binary_search(items, 7))   # from the example above

(-1, 2)

Why the interpreter said that

No exception, wrong answer: 7 is in the list. Binary search assumes sorted order; the first comparison threw away the half that contained the target. The other classic bug is while lo < hi with hi = len(items) mixed with hi = mid - 1 — off-by-one that skips the last item.

The fix

Sort first (O(n log n), worth it if you will search many times), or use linear search once. Pick one convention for hi — inclusive with lo <= hi, or exclusive with lo < hi — and never mix them.

Sorting: from bubble sort to sorted()

You will call sorted() a thousand times before you write a sort, so the point of this lesson is not to reimplement it — it is to understand why the built-in is O(n log n), what "stable" means, and to recognise merge sort's divide-and-conquer shape, which reappears everywhere. Bubble sort is here only because seeing an O(n²) algorithm is the fastest way to appreciate the difference.

pythonEdit it. ⌘/Ctrl + Enter runs.

def bubble_sort(a):
    """O(n²): keep swapping neighbours until a full pass makes no swap."""
    a = a[:]
    for end in range(len(a) - 1, 0, -1):
        swapped = False
        for i in range(end):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:
            break
    return a
print(bubble_sort([5, 2, 9, 1, 5, 6]))

def merge_sort(a):
    """O(n log n): split in half, sort each half, merge two sorted lists."""
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:           # <= keeps it stable
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    return merged + left[i:] + right[j:]
print(merge_sort([5, 2, 9, 1, 5, 6]))

# Timing: n = 2000
import random, time
data = [random.randint(0, 10**6) for _ in range(2000)]
def timed(fn):
    t = time.perf_counter(); fn(data)
    return (time.perf_counter() - t) * 1000
bubble_ms, merge_ms, builtin_ms = timed(bubble_sort), timed(merge_sort), timed(sorted)
print("bubble_sort:", "much slower than merge_sort" if bubble_ms > merge_ms * 3 else "similar? (try n = 5000)")
print("merge_sort vs sorted:", "the built-in wins — it is C code" if builtin_ms <= merge_ms else "close")

# What you actually write at work: sorted + key, and stability
people = [("ada", 36), ("bob", 28), ("cy", 36), ("dee", 28)]
print(sorted(people, key=lambda p: p[1]))                  # stable: ada before cy, bob before dee
print(sorted(people, key=lambda p: (-p[1], p[0])))         # age desc, then name asc
words = ["banana", "Apple", "cherry"]
print(sorted(words), sorted(words, key=str.lower))

def bubble_sort(a):
    """O(n²): keep swapping neighbours until a full pass makes no swap."""
    a = a[:]
    for end in range(len(a) - 1, 0, -1):
        swapped = False
        for i in range(end):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swapped = True
        if not swapped:
            break
    return a
print(bubble_sort([5, 2, 9, 1, 5, 6]))

def merge_sort(a):
    """O(n log n): split in half, sort each half, merge two sorted lists."""
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:           # <= keeps it stable
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    return merged + left[i:] + right[j:]
print(merge_sort([5, 2, 9, 1, 5, 6]))

# Timing: n = 2000
import random, time
data = [random.randint(0, 10**6) for _ in range(2000)]
def timed(fn):
    t = time.perf_counter(); fn(data)
    return (time.perf_counter() - t) * 1000
bubble_ms, merge_ms, builtin_ms = timed(bubble_sort), timed(merge_sort), timed(sorted)
print("bubble_sort:", "much slower than merge_sort" if bubble_ms > merge_ms * 3 else "similar? (try n = 5000)")
print("merge_sort vs sorted:", "the built-in wins — it is C code" if builtin_ms <= merge_ms else "close")

# What you actually write at work: sorted + key, and stability
people = [("ada", 36), ("bob", 28), ("cy", 36), ("dee", 28)]
print(sorted(people, key=lambda p: p[1]))                  # stable: ada before cy, bob before dee
print(sorted(people, key=lambda p: (-p[1], p[0])))         # age desc, then name asc
words = ["banana", "Apple", "cherry"]
print(sorted(words), sorted(words, key=str.lower))

You should see

[1, 2, 5, 5, 6, 9]
[1, 2, 5, 5, 6, 9]
bubble_sort: much slower than merge_sort
merge_sort vs sorted: the built-in wins — it is C code
[('bob', 28), ('dee', 28), ('ada', 36), ('cy', 36)]
[('ada', 36), ('cy', 36), ('bob', 28), ('dee', 28)]
['Apple', 'banana', 'cherry'] ['Apple', 'banana', 'cherry']

Your turn

Implement quick_sort(a): pick a pivot, build less, equal, greater lists with comprehensions, recurse on the outer two. Three lines of real work.

Know the row for Timsort by heart; know the others exist and why.
Algorithm	Time	Space	Stable	When you meet it
Bubble / insertion	O(n²)	O(1)	yes	Tiny inputs; insertion sort is what Timsort uses on small runs
Merge sort	O(n log n)	O(n)	yes	External sorting (data bigger than memory), linked lists
Quick sort	O(n log n) avg, O(n²) worst	O(log n)	no	C's qsort; in-memory arrays
Heap sort	O(n log n)	O(1)	no	Guaranteed bound, no extra memory
Timsort (`sorted`)	O(n log n), O(n) if nearly sorted	O(n)	yes	Python, Java, every day
Counting / radix	O(n + k)	O(k)	yes	Integers in a small range — beats n log n

Quick check

What does it mean that a sort is stable?

Dynamic programming, gently

Dynamic programming (DP) has a scary name for a simple idea: if you will need the answer to a sub-problem more than once, save it. Start with the recursive solution that is obviously correct, notice it recomputes the same calls, add a cache (memoisation), and — if you like — flip it into a table filled bottom-up. Fibonacci is the "hello world"; the shape is the same for coin change, edit distance and knapsack.

pythonEdit it. ⌘/Ctrl + Enter runs.

import time
from functools import lru_cache

calls = 0
def fib_naive(n):
    global calls
    calls += 1
    return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)
print(fib_naive(20), "took", calls, "calls")      # exponential — fib(20) alone is 21,891 calls

# Step 1: memoise — same code, one decorator
@lru_cache(maxsize=None)
def fib_memo(n):
    return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)
print(fib_memo(90))

# Step 2: bottom-up table — no recursion, O(n) time, O(1) space
def fib_table(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a
print(fib_table(90))

# The same three steps on a real problem: climbing stairs, 1 or 2 steps at a time
@lru_cache(maxsize=None)
def ways(n):
    return 1 if n <= 1 else ways(n - 1) + ways(n - 2)
print(ways(10), ways(40))

# Coin change (fewest coins) — a 1-D table where table[a] = best for amount a
def min_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                best[a] = min(best[a], best[a - c] + 1)
    return best[amount] if best[amount] != INF else -1
print(min_coins([1, 5, 10, 25], 63), min_coins([2], 3))

# Longest common subsequence — the 2-D table shape (diff tools, DNA alignment)
def lcs(a, b):
    t = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            t[i][j] = t[i-1][j-1] + 1 if a[i-1] == b[j-1] else max(t[i-1][j], t[i][j-1])
    return t[len(a)][len(b)]
print(lcs("ABCBDAB", "BDCABA"))

import time
from functools import lru_cache

calls = 0
def fib_naive(n):
    global calls
    calls += 1
    return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)
print(fib_naive(20), "took", calls, "calls")      # exponential — fib(20) alone is 21,891 calls

# Step 1: memoise — same code, one decorator
@lru_cache(maxsize=None)
def fib_memo(n):
    return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)
print(fib_memo(90))

# Step 2: bottom-up table — no recursion, O(n) time, O(1) space
def fib_table(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a
print(fib_table(90))

# The same three steps on a real problem: climbing stairs, 1 or 2 steps at a time
@lru_cache(maxsize=None)
def ways(n):
    return 1 if n <= 1 else ways(n - 1) + ways(n - 2)
print(ways(10), ways(40))

# Coin change (fewest coins) — a 1-D table where table[a] = best for amount a
def min_coins(coins, amount):
    INF = float("inf")
    best = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                best[a] = min(best[a], best[a - c] + 1)
    return best[amount] if best[amount] != INF else -1
print(min_coins([1, 5, 10, 25], 63), min_coins([2], 3))

# Longest common subsequence — the 2-D table shape (diff tools, DNA alignment)
def lcs(a, b):
    t = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            t[i][j] = t[i-1][j-1] + 1 if a[i-1] == b[j-1] else max(t[i-1][j], t[i][j-1])
    return t[len(a)][len(b)]
print(lcs("ABCBDAB", "BDCABA"))

You should see

6765 took 21891 calls
2880067194370816120
2880067194370816120
89 165580141
6 -1
4

Your turn

Write max_subarray(nums) (Kadane): walk once, keeping best_ending_here = max(x, best_ending_here + x). It is DP with a one-cell table.

1
Write the brute-force recursion
Define the answer for size n in terms of smaller sizes. Do not optimise. Test it on tiny inputs.
2
Spot the repeated sub-problems
Print the arguments; if the same (n) or (i, j) appears many times, memoisation will help. If every call is unique, DP is not the tool.
3
Add <code>@lru_cache</code>
Arguments must be hashable (ints, strings, tuples — not lists). This alone turns exponential into polynomial.
4
Optionally, go bottom-up
Replace recursion with a table filled from the base case upwards. Same answers, no recursion limit, often less memory (keep only the last row).

How to recognise a DP problem

The words minimum / maximum / how many ways / longest / is it possible, an input that shrinks by one step each time, and a choice at each step (take it or not, one step or two). If the greedy "take the best now" answer can be wrong, it is probably DP.

Cheat sheet and what to practise

If the problem says…	Reach for	Because
"count", "group", "have we seen", "pairs that sum to"	`dict` / `set` / `Counter`	O(1) lookup turns n² into n
"nested", "matching", "undo", "most recent", "next greater"	stack (`list`)	LIFO mirrors the structure
"shortest path", "fewest steps", "level by level", "nearest"	BFS with `deque`	explores by distance
"connected", "reachable", "cycle", "dependency order"	DFS (recursion or stack)	explores exhaustively
"top k", "k smallest", "merge sorted", "schedule by priority"	`heapq`	min in O(1), push/pop in O(log n)
"sorted array", "find the smallest X such that"	binary search / `bisect`	halves the space each step
"subarray", "substring", "window of size k"	sliding window (two pointers)	each element enters and leaves once
"how many ways", "minimum cost", "longest …", "can we make"	DP (memoise, then table)	overlapping sub-problems
"tree", "hierarchy", "folder", "org chart"	recursion on nodes	a tree is defined recursively

The problems below are the graded ones from /practice/python that lean on this module — real data-engineering shapes rather than puzzles. Then Module 15 has the interview questions, where the senior tier asks you to explain these choices out loud.

Practice this — graded problems in your browser

Top 3 from a stream (heap / Counter)Solve it →De-duplicate with a setSolve it →Sort by two keysSolve it →Batch a stream (queue)Solve it →

JuniorWhen would you use a set instead of a list?

When I need to check membership or remove duplicates and do not care about order or position. x in a_set is O(1); x in a_list scans. The trade-off is that set items must be hashable and the set is unordered.

What they are really testing: Whether you know the cost table, not the syntax.

Mid-levelExplain BFS vs DFS and give a case where the choice matters.

Both visit every reachable node; BFS uses a queue and visits by distance, DFS uses a stack (or recursion) and goes deep first. It matters for shortest path in an unweighted graph — BFS finds it, DFS does not. DFS is the natural fit for cycle detection and topological sort, and uses less memory on wide graphs.

What they are really testing: That you can reason about the data structure behind the algorithm, not recite it.

SeniorA Python dict lookup is O(1) — when is that not true, and what would you do about it?

Average O(1) relies on a good hash spreading keys across buckets. With many collisions (adversarial keys, or a custom __hash__ that returns a constant) it degrades toward O(n). Python randomises string hashing per process to blunt hash-flooding attacks. If keys are user-controlled and the map is a hot path, I would cap the map size, use a keyed hash, or move the lookup into a database index that handles it.

What they are really testing: Depth — whether "O(1)" is a fact you memorised or a mechanism you understand.

← Module 12Problem Solving Module 14 →Python + Tools

Frequently asked questions

Do I need to learn data structures and algorithms to get a Python job?

For most application and data roles you need the cost table (which structure is fast for what), fluency with dict, set, deque, heapq and sorted, and the ability to reason about Big-O out loud. Implementing a red-black tree is not required; recognising that a problem is "really a BFS" is.

Is this enough for coding interviews?

It is the foundation every interview assumes: arrays, hash maps, stacks, queues, linked lists, trees, heaps, graphs, binary search, sorting, recursion and dynamic programming, each with the canonical example. Pair it with Module 12 (patterns) and Module 15 (questions), then practise timed problems.

Finish the Python handbook, then get hired

Sit the exam for your certificate, run your resume through the ATS checker, and see the jobs that ask for exactly this.

Check my resume

Found this course useful? Share it.

ShareX LinkedIn

Comments

Join the conversation. Sign in to leave a comment — we'd love to hear your thoughts.