Recursion Fundamentals
Every recursive solution has: a base case (stops the recursion), a recursive case (reduces the problem), and a trust-and-use pattern (trust that the recursive call returns the correct answer for the subproblem, then use it). The call stack depth = recursion depth. For O(n) depth: risk of stack overflow on large inputs — consider iteration with an explicit stack. Tail recursion: the recursive call is the last operation — some compilers optimize this to iteration (Python does NOT). Master theorem for divide-and-conquer: T(n) = aT(n/b) + f(n). Common cases: T(n) = 2T(n/2) + O(n) → O(n log n) (merge sort). T(n) = T(n/2) + O(1) → O(log n) (binary search). T(n) = 2T(n/2) + O(1) → O(n) (tree traversal).
Merge Sort — O(n log n) Stable Sort
def merge_sort(nums: list[int]) -> list[int]:
if len(nums) list[int]:
result = []
i = j = 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
result.extend(left[i:])
result.extend(right[j:])
return result
# Count inversions using merge sort (number of pairs i nums[j])
def count_inversions(nums: list[int]) -> tuple[list[int], int]:
if len(nums) <= 1:
return nums, 0
mid = len(nums) // 2
left, left_inv = count_inversions(nums[:mid])
right, right_inv = count_inversions(nums[mid:])
merged, split_inv = merge_count(left, right)
return merged, left_inv + right_inv + split_inv
def merge_count(left, right):
result, inv = [], 0
i = j = 0
while i < len(left) and j < len(right):
if left[i] right[j]
j += 1
result.extend(left[i:]); result.extend(right[j:])
return result, invQuick Select — O(n) Average k-th Smallest
import random
def find_kth_smallest(nums: list[int], k: int) -> int:
def partition(lo, hi) -> int:
pivot_idx = random.randint(lo, hi)
nums[pivot_idx], nums[hi] = nums[hi], nums[pivot_idx]
pivot = nums[hi]
store = lo
for i in range(lo, hi):
if nums[i] <= pivot:
nums[store], nums[i] = nums[i], nums[store]
store += 1
nums[store], nums[hi] = nums[hi], nums[store]
return store
lo, hi = 0, len(nums) - 1
while lo <= hi:
pivot = partition(lo, hi)
if pivot == k - 1:
return nums[pivot]
elif pivot < k - 1:
lo = pivot + 1
else:
hi = pivot - 1
return -1Fast Power (Exponentiation by Squaring)
def my_pow(x: float, n: int) -> float:
if n < 0:
x, n = 1 / x, -n
result = 1.0
while n:
if n % 2 == 1:
result *= x
x *= x
n //= 2
return result
# O(log n): square x on each iteration, halve nSubsets, Permutations, and Combinations
# Subsets (LC 78): generate all 2^n subsets
def subsets(nums: list[int]) -> list[list[int]]:
result = [[]]
for n in nums:
result += [subset + [n] for subset in result]
return result
# Permutations (LC 46)
def permutations(nums: list[int]) -> list[list[int]]:
if not nums: return [[]]
result = []
for i, n in enumerate(nums):
rest = nums[:i] + nums[i+1:]
for perm in permutations(rest):
result.append([n] + perm)
return result
# Combinations (LC 77): choose k from n
def combine(n: int, k: int) -> list[list[int]]:
result = []
def backtrack(start, current):
if len(current) == k:
result.append(current[:])
return
for i in range(start, n + 1):
# Pruning: not enough elements remaining
if n - i + 1 < k - len(current):
break
current.append(i)
backtrack(i + 1, current)
current.pop()
backtrack(1, [])
return result
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the Master Theorem and how do you apply it to divide-and-conquer algorithms?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Master Theorem: T(n) = aT(n/b) + f(n). a = number of subproblems, b = factor by which n is divided, f(n) = work done at the current level. Three cases: (1) f(n) = O(n^log_b(a) – epsilon): T(n) = O(n^log_b(a)) — subproblem work dominates. (2) f(n) = O(n^log_b(a)): T(n) = O(n^log_b(a) * log n) — work is equal at all levels. (3) f(n) = O(n^log_b(a) + epsilon): T(n) = O(f(n)) — top-level work dominates. Examples: Merge sort: T(n) = 2T(n/2) + O(n). a=2, b=2, n^log_2(2)=n^1=n. f(n)=O(n). Case 2: T(n)=O(n log n). Binary search: T(n)=T(n/2)+O(1). a=1, b=2, n^log_2(1)=n^0=1. f(n)=O(1). Case 2: T(n)=O(log n).”}},{“@type”:”Question”,”name”:”How does Quick Select achieve O(n) average time for k-th smallest element?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Quick Select uses the partitioning step from Quick Sort. A pivot is chosen and all elements <= pivot go left, all > pivot go right. After partitioning, the pivot is at its final sorted position k_pivot. If k_pivot == k-1: found. If k_pivot < k-1: recurse only on the right subarray. If k_pivot > k-1: recurse only on the left. Unlike Quick Sort, Quick Select recurses into only one side. Average case: T(n) = T(n/2) + O(n) = O(n) (geometric series). Worst case: O(n^2) with bad pivot (always picks smallest/largest). Randomized pivot selection makes worst case extremely unlikely. Median-of-medians deterministic pivot gives guaranteed O(n) worst case but higher constants — rarely needed in practice.”}},{“@type”:”Question”,”name”:”Why is exponentiation by squaring O(log n) and how does it handle negative exponents?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Naive power(x, n) multiplies x n times: O(n). Exponentiation by squaring: x^n = (x^2)^(n/2) if n is even, x * (x^2)^((n-1)/2) if n is odd. Each step halves n, so depth = O(log n). The iterative version: while n > 0: if n is odd, multiply result by x. Square x. Halve n. Total multiplications: O(log n). Negative exponents: x^(-n) = (1/x)^n. Convert at the start: if n < 0, replace x with 1/x and n with -n. Edge case: x=0 with n<0 is undefined (division by zero) — clarify with interviewer. Integer arithmetic: for x^n mod m, use (result * x) % m and (x * x) % m at each step to prevent integer overflow.”}},{“@type”:”Question”,”name”:”How does merge sort count inversions in O(n log n)?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”An inversion is a pair (i, j) where i < j but nums[i] > nums[j]. Counting all inversions naively is O(n^2). Merge sort insight: during the merge step, when we pick from the right subarray (right[j]) before the left subarray (left[i..end]), all remaining elements in the left subarray (left[i], left[i+1], …, left[end]) are greater than right[j] — each forms an inversion with right[j]. Count = len(left) – i (elements remaining in left). This counting happens at the merge step, and the merge step itself runs O(n) per level, O(n log n) total. The sort reorders the array while the inversion count accumulates — after all merges, the total inversion count is correct. This is because each inversion is counted exactly once: when the smaller element (from the right half) is placed before the larger element (from the left half) during a merge.”}},{“@type”:”Question”,”name”:”What is the difference between recursion with memoization and dynamic programming?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Top-down DP (memoization): write the recursive solution naturally, add a cache (dict or array) to store computed results. On each call: check cache first, compute if missing, store and return. Execution order: determined by recursion — only subproblems actually needed are computed (lazy evaluation). Bottom-up DP (tabulation): fill a DP table iteratively from smallest subproblems to largest. Execution order: all subproblems are computed regardless of whether they are needed (eager evaluation). Same asymptotic complexity, different constants: top-down has function call overhead; bottom-up avoids call stack and is often faster in practice. Top-down is easier to implement (natural from the problem definition). Bottom-up can be more memory-efficient (sliding window optimization: only keep the last row(s) of a 2D table). In interviews: start with top-down memoization, then mention that bottom-up is possible with the same recurrence.”}}]}
See also: Meta Interview Prep
See also: Atlassian Interview Prep
See also: Coinbase Interview Prep