4 drills · 4 pattern exercises · 6 micro drills
Patterns used in this topic, with difficulty breakdown.
Compute the nth Fibonacci number without redundantly recalculating the same sub-values.
All 4 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Compute the nth Fibonacci number without redundantly recalculating the same sub-values.
Naive recursion recomputes fib(k) exponentially many times — memoization stores each result once, collapsing O(2^n) to O(n).
Prompt
Compute the nth Fibonacci number efficiently.
Solution
# Recursive + memo
def fib(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fib(n - 1) + fib(n - 2) # store to avoid recomputation
return memo[n]
# Iterative (O(1) space)
def fib_iter(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
# Test: fib(10) == 55In plain English: Compute n factorial (n x (n-1) x ... x 1) using recursion.
The simplest recursion: reduce by one, multiply on the way back up. Base case 0! = 1 stops the chain.
Prompt
Compute n! recursively.
Solution
def factorial(n):
if n <= 1:
return 1 # base case: 0! = 1! = 1
return n * factorial(n - 1) # multiply on unwind
# Iterative:
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i # accumulate product bottom-up
return result
# Test: factorial(5) == 120In plain English: Compute x raised to the power n efficiently by squaring halves instead of multiplying one at a time.
Squaring the half-result means each call halves n — log(n) multiplications instead of n.
Prompt
Compute x^n in O(log n) time.
Solution
def power(x, n):
if n == 0:
return 1
if n < 0:
return 1 / power(x, -n)
half = power(x, n // 2) # halve exponent, square result
if n % 2 == 0:
return half * half
else:
return half * half * x
# Test: power(2, 10) == 1024
# Test: power(2, -2) == 0.25In plain English: Generate every possible subset of a list of elements (the power set).
Each element has exactly two choices: include or exclude — this binary decision tree has 2^n leaves, one per subset.
Prompt
Generate all subsets (power set) of a list of numbers.
Solution
# Recursive
def subsets(nums):
if not nums:
return [[]]
rest = subsets(nums[1:])
return rest + [[nums[0]] + s for s in rest] # include/exclude first element
# Iterative
def subsets_iter(nums):
result = [[]]
for x in nums:
result += [s + [x] for s in result]
return result
# Test: subsets([1,2,3]) => 8 subsets4 exercises: spot the signals, pick the method, avoid the trap.
Compute the nth Fibonacci number efficiently.
Signals
Memoize or tabulate. dp[i] = dp[i-1] + dp[i-2]. O(n) time, O(n) or O(1) space.
Naive recursion is O(2^n) — exponential. Adding @lru_cache makes it O(n).
Trap
The naive recursive tree is the textbook example of why memoization matters.
Compute n! recursively.
Signals
Multiply n * factorial(n-1). Base case: return 1. O(n) time, O(n) stack space.
Trap
Iterative loop is simpler and uses O(1) space. But this drill practices recursion.
Compute x^n in O(log n) time.
Signals
If n even: (x^(n/2))². If n odd: x * x^(n-1). Halves n each step → O(log n) multiplications.
Trap
Naive loop of n multiplications is O(n). The 'square the half' insight is key to O(log n).
Generate all subsets (power set) of a list of numbers.
Signals
For each element, branch: include it or exclude it. Collect results at leaf nodes. O(2^n).
Iterate from 0 to 2^n-1. Each bitmask represents a subset. Same O(2^n).
Trap
Both approaches are O(2^n) — that's unavoidable since there are 2^n subsets.
6 quick recall drills to reinforce this topic.
Iterative Fibonacci is O(n) time, O(1) space. Classic DP introduction pattern.
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
# a is fib(n)Iterative factorial avoids recursion overhead. Used in combinatorics and permutation counting.
res = 1
for i in range(2, n + 1):
res *= iIterative binary exponentiation handles negative exponents. Same as pow(x, n).
def power(x, n):
res = 1
if n < 0: x, n = 1/x, -n
while n:
if n & 1: res *= x
x *= x
n >>= 1
return resBinary exponentiation computes x^n in O(log n). Essential for modular arithmetic problems.
res = 1
while exp:
if exp & 1:
res *= base
base *= base
exp >>= 1At each index, branch into include or exclude. Generates all 2^n subsets. Alternative: iterative bit-mask approach.
def subsets(nums):
res = []
def bt(i, path):
if i == len(nums):
res.append(path[:])
return
bt(i+1, path) # exclude
path.append(nums[i])
bt(i+1, path) # include
path.pop()
bt(0, [])
return resTry placing each number into k buckets. Prune: skip if bucket overflows, skip symmetric bucket states.
def canPartitionKSubsets(nums, k):
total = sum(nums)
if total % k: return False
target = total // k
nums.sort(reverse=True)
buckets = [0] * k
def backtrack(i):
if i == len(nums): return all(b == target for b in buckets)
seen = set()
for j in range(k):
if buckets[j] + nums[i] > target: continue
if buckets[j] in seen: continue # prune symmetric
seen.add(buckets[j])
buckets[j] += nums[i]
if backtrack(i + 1): return True
buckets[j] -= nums[i]
return False
return backtrack(0)