What’s one thing you learned? What’s still confusing?
Dynamic Programming, Part 2: The Classic Problems
Coin change, 0/1 knapsack, longest common subsequence and edit distance worked with the framework, space optimisation, plus two-pointer and sliding window.
Linked Lists, Part 1: Singly Linked & Basics
Node class, singly linked list operations (insert, delete, search, in-place reversal), and Floyd's two-pointer technique for cycle detection.
Linked Lists, Part 2: Doubly Linked, Merge & LRU Cache
Doubly linked lists with prev/next pointers, merging two sorted lists, recursive reversal, and a complete LRU cache implementation.
Interactive Labs for This Track
Loop Visualizer
You're a factory robot repeating the same task on an assembly line — watch how loops automate repetitive work
List Slicing
You have a playlist of 50 songs — grab just tracks 10 through 20 with a single slice expression
Sorting Algorithms
You're organizing a library of 10,000 books — which sorting method is fastest?
Ask questions, share insights
Step through a recursive function call-by-call. Each recursive invocation spawns a new branch. Watch the tree grow on the way down and collapse on the way back up, exactly what Python's call stack does.
import sys
# Python's default recursion limit
print(sys.getrecursionlimit()) # 1000
# Increase if needed (use sparingly -- prefer iterative for deep recursion)
sys.setrecursionlimit(10000)
# Call stack visualization for factorial(4):
#
# factorial(4) <-- frame 4: waiting for factorial(3)
# factorial(3) <-- frame 3: waiting for factorial(2)
# factorial(2) <-- frame 2: waiting for factorial(1)
# factorial(1) <-- frame 1: BASE CASE returns 1
# factorial(2) = 2 * 1 = 2 <-- frame 2 resumes, returns 2
# factorial(3) = 3 * 2 = 6 <-- frame 3 resumes, returns 6
# factorial(4) = 4 * 6 = 24 <-- frame 4 resumes, returns 24
def factorial(n: int) -> int:
"""Compute n! recursively.
Time: O(n) — n recursive calls
Space: O(n) — n frames on the call stack simultaneously
"""
if n <= 1: # BASE CASE: stop recursing
return 1
return n * factorial(n - 1) # RECURSIVE CASE: reduce to smaller problem
print(factorial(4)) # 24
print(factorial(10)) # 3628800HitRecursionError: maximum recursion depth exceeded? Either your base case never fires (infinite recursion — check the condition) or the problem genuinely needs more than 1000 frames (use iteration orsys.setrecursionlimit). See the error decoder for the diagnosis flow.
# --- 1. Factorial: O(n) time, O(n) space ---
def factorial(n: int) -> int:
return 1 if n <= 1 else n * factorial(n - 1)
# --- 2. Naive Fibonacci: O(2^n) time, O(n) space ---
# This is intentionally bad — we will fix it in Section 4.
def fib_naive(n: int) -> int:
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
# --- 3. Fast Power via squaring: O(log n) time ---
# Key insight: x^8 = (x^4)^2, so we halve the exponent each step.
def power(base: float, exp: int) -> float:
"""Compute base^exp in O(log exp) using recursive squaring."""
if exp == 0:
return 1
if exp % 2 == 0:
half = power(base, exp // 2)
return half * half # x^8 = (x^4)^2 — square the result
return base * power(base, exp - 1)
print(power(2, 10)) # 1024.0
print(power(3, 5)) # 243.0
# --- 4. Sum a list without built-ins: O(n) ---
def sum_list(lst: list[int]) -> int:
if not lst: # base case: empty list
return 0
return lst[0] + sum_list(lst[1:]) # head + sum(tail)
print(sum_list([1, 2, 3, 4, 5])) # 15
# --- 5. Flatten arbitrarily nested lists ---
def flatten(nested) -> list:
"""Recursively flatten a list of any nesting depth.
flatten([1, [2, [3, 4]], 5]) → [1, 2, 3, 4, 5]
"""
result = []
for item in nested:
if isinstance(item, list):
result.extend(flatten(item)) # recurse into sublist
else:
result.append(item)
return result
print(flatten([1, [2, [3, [4]], 5], 6])) # [1, 2, 3, 4, 5, 6]
# --- 6. Recursive binary search: O(log n) ---
def binary_search(arr: list[int], target: int,
lo: int = 0, hi: int | None = None) -> int:
"""Return the index of target or -1 if not found."""
if hi is None:
hi = len(arr) - 1
if lo > hi:
return -1 # base case: search space exhausted
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search(arr, target, mid + 1, hi) # right half
else:
return binary_search(arr, target, lo, mid - 1) # left half
print(binary_search([1, 3, 5, 7, 9, 11], 7)) # 3
print(binary_search([1, 3, 5, 7, 9, 11], 4)) # -1
# --- 7. Recursive merge sort: O(n log n) ---
def merge_sort(arr: list[int]) -> list[int]:
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return _merge(left, right)
def _merge(left: list[int], right: list[int]) -> list[int]:
result, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
return result + left[i:] + right[j:]
print(merge_sort([5, 2, 8, 1, 9, 3])) # [1, 2, 3, 5, 8, 9]
# --- 8. Generate all permutations: O(n * n!) ---
def permutations(lst: list) -> list[list]:
"""Generate all permutations of a list.
Strategy: for each element, make it the first element,
then recursively permute the rest.
"""
if len(lst) <= 1:
return [lst[:]] # base case: one permutation of 0 or 1 elements
result = []
for i in range(len(lst)):
lst[0], lst[i] = lst[i], lst[0] # choose element i as first
for perm in permutations(lst[1:]):
result.append([lst[0]] + perm) # prepend chosen element
lst[0], lst[i] = lst[i], lst[0] # restore (backtrack)
return result
perms = permutations([1, 2, 3])
print(f"{len(perms)} permutations:", perms)
# 6 permutations: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)fib(...) or factorial(...) call pushes a stack frame with its own local variables, and returns pop those frames one at a time. Step through the LIFO discipline below — including a recursion preset (factorial(4)) and an exception-unwinding preset that pops frames without their return values.factorial(n - 1) call, then unwind as each frame returns its product back up the chain.Edit the code, then click Trace it. Python actually runs in your browser — every line, every variable, every print.
Click Trace it to capture the execution trace. The scrubber below will let you step through every variable change line-by-line.
fib_naive(5): fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
fib(2) is called: 3 times. fib(3) is called 2 times. For fib(40), fib(2) is called hundreds of millions of times. We are recomputing the same values over and over.import time
def fib_naive(n: int) -> int:
"""Naive recursive fibonacci. Time: O(2^n), Space: O(n) stack depth."""
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
# Count actual calls to see the explosion
call_count = 0
def fib_counted(n: int) -> int:
global call_count
call_count += 1
if n <= 1:
return n
return fib_counted(n - 1) + fib_counted(n - 2)
for n in [10, 20, 30, 35]:
call_count = 0
result = fib_counted(n)
print(f"fib({n:>2}) = {result:>10,} | calls: {call_count:>12,}")
# fib(10) = 55 | calls: 177
# fib(20) = 6,765 | calls: 21,891
# fib(30) = 832,040 | calls: 2,692,537
# fib(35) = 9,227,465 | calls: 29,860,703
# At n=50, this would take minutes. At n=100, the universe ends first.
# The call count follows: calls(n) = fib(n+1) * 2 - 1 ≈ O(1.618^n)fib_naive(40) makes about how many function calls?
Watch how memoization and tabulation actually work — see every cache hit, miss, and table fill in real time:
import functools
import sys
# --- Naive baseline (needed for benchmark comparison below) ---
def fib_naive(n: int) -> int:
"""Naive recursive fibonacci. Time: O(2^n) — included here for benchmarking."""
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
# --- Method 1: @functools.lru_cache — the cleanest approach ---
@functools.lru_cache(maxsize=None) # None = unlimited cache size
def fib_memo(n: int) -> int:
"""Memoized fibonacci. Time: O(n), Space: O(n).
lru_cache intercepts each call. If fib_memo(k) was computed before,
it returns the cached value instantly. Each unique n is computed ONCE.
"""
if n <= 1:
return n
return fib_memo(n - 1) + fib_memo(n - 2)
# Reset counter
call_count = 0
# With memoization: fib(n) makes exactly 2n-1 unique calls (not 2^n)
print(fib_memo(50)) # 12586269025 (instant!)
print(fib_memo(100)) # 354224848179261915075 (still instant)
# Inspect the cache
print(fib_memo.cache_info())
# CacheInfo(hits=99, misses=101, maxsize=None, currsize=101)
# Only 101 unique calls made for fib(100)!
# --- Method 2: Manual memo dict ---
def fib_manual_memo(n: int, memo: dict | None = None) -> int:
"""Memoized fibonacci with explicit dictionary."""
if memo is None:
memo = {}
if n in memo:
return memo[n] # cache hit: return stored result
if n <= 1:
return n
memo[n] = fib_manual_memo(n - 1, memo) + fib_manual_memo(n - 2, memo)
return memo[n] # store before returning
print(fib_manual_memo(100)) # 354224848179261915075
# --- Method 3: functools.cache (Python 3.9+, shorthand for lru_cache(maxsize=None)) ---
@functools.cache
def fib_cache(n: int) -> int:
if n <= 1:
return n
return fib_cache(n - 1) + fib_cache(n - 2)
# Performance comparison
import time
def benchmark(label, fn, n):
start = time.perf_counter()
result = fn(n)
elapsed = time.perf_counter() - start
print(f"{label}: fib({n}) = {result} in {elapsed:.6f}s")
benchmark("Naive (n=35)", fib_naive, 35) # ~1-2 seconds
benchmark("Memo (n=35)", fib_memo, 35) # ~0.000001 seconds
benchmark("Memo (n=100)", fib_memo, 100) # ~0.000001 seconds# --- Fibonacci: bottom-up tabulation ---
def fib_table(n: int) -> int:
"""Fibonacci via tabulation. Time: O(n), Space: O(n)."""
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0 # base case
dp[1] = 1 # base case
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] # recurrence relation
return dp[n]
print(fib_table(10)) # 55
print(fib_table(50)) # 12586269025
# --- Space-optimized: O(1) space (rolling array) ---
# Key observation: dp[i] only depends on dp[i-1] and dp[i-2].
# We don't need the whole table — just the last two values.
def fib_optimized(n: int) -> int:
"""Fibonacci with O(1) space using rolling variables."""
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
curr = prev1 + prev2
prev2, prev1 = prev1, curr
return prev1
print(fib_optimized(100)) # 354224848179261915075
print(fib_optimized(1000)) # A very large number, computed in microseconds
# --- Show the table for small n ---
def fib_table_verbose(n: int) -> int:
"""Same as fib_table but prints the table."""
dp = [0] * (n + 1)
dp[1] = 1
print(f"Index: {list(range(n+1))}")
print(f"Init: {dp}")
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
print(f"Final: {dp}")
return dp[n]
fib_table_verbose(8)
# Index: [0, 1, 2, 3, 4, 5, 6, 7, 8]
# Init: [0, 1, 0, 0, 0, 0, 0, 0, 0]
# Final: [0, 1, 1, 2, 3, 5, 8, 13, 21]Before writing any DP solution, answer these five questions:
# THE 5-QUESTION DP FRAMEWORK
# ================================================
# 1. WHAT IS THE STATE?
# What information do I need to uniquely describe a subproblem?
# → dp[i] = ? (or dp[i][j] for 2D problems)
#
# 2. WHAT IS THE RECURRENCE?
# How does dp[i] relate to smaller subproblems dp[i-1], dp[i-2], etc.?
# → dp[i] = some function of dp[i-1], dp[i-2], ...
#
# 3. WHAT ARE THE BASE CASES?
# What are the smallest subproblems I can answer directly?
# → dp[0] = ?, dp[1] = ?
#
# 4. WHAT ORDER DO I FILL THE TABLE?
# Left to right? Right to left? Row by row?
# → dp[i] must be computed after all subproblems it depends on
#
# 5. WHAT IS THE FINAL ANSWER?
# Is it dp[n]? max(dp)? dp[-1][-1]?
# → depends on the problem
# ---- EXAMPLE: Climbing Stairs ----
# Problem: n steps. Each move: climb 1 or 2 steps. How many distinct ways?
#
# 1. STATE: dp[i] = number of distinct ways to reach step i
# 2. RECURRENCE: dp[i] = dp[i-1] + dp[i-2]
# (arrive from step i-1 by taking 1 step, or from step i-2 by taking 2 steps)
# 3. BASE CASES: dp[0] = 1 (one way to stay at ground), dp[1] = 1 (one way to reach step 1)
# 4. ORDER: left to right, i from 2 to n
# 5. ANSWER: dp[n]
def climb_stairs(n: int) -> int:
"""Count distinct ways to climb n stairs (1 or 2 steps at a time)."""
if n <= 2:
return n
dp = [0] * (n + 1)
dp[0] = 1 # base case: 1 way to be at the start
dp[1] = 1 # base case: 1 way to reach step 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
for stairs in range(1, 8):
print(f"climb_stairs({stairs}) = {climb_stairs(stairs)}")
# 1, 2, 3, 5, 8, 13, 21 -- the Fibonacci sequence!What does memoization actually do for a recursive function like fib(n)?
Watch recursion trees expand in real time. Toggle memoization on/off to see how it prunes redundant branches and compare naive vs DP performance:
n stairs taking 1 or 2 at a time — written naively, memoized, and tabulated, with a counter that shows exactly how much work each one does.fib(n) recomputes the same values exponentially. Adding @functools.cache transforms it to O(n) with one lineWhat is the time complexity of the naive recursive Fibonacci implementation fib(n) = fib(n-1) + fib(n-2)?