Divide and Conquer Interview Patterns
Divide and conquer splits a problem into independent subproblems, solves each recursively, and merges the results. It is the foundation of merge sort, quick sort, binary search, Strassen’s matrix multiplication, and many tree-based problems. The Master Theorem gives the time complexity of most D&C recurrences.
Master Theorem
For T(n) = a*T(n/b) + f(n):
- If f(n) = O(n^c) where c < log_b(a): T(n) = O(n^log_b(a)) — subproblems dominate
- If f(n) = O(n^c) where c = log_b(a): T(n) = O(n^c * log n) — equal work at each level
- If f(n) = O(n^c) where c > log_b(a): T(n) = O(f(n)) — merge step dominates
Examples: Merge sort T(n) = 2T(n/2) + O(n) → O(n log n) (case 2). Binary search T(n) = T(n/2) + O(1) → O(log n) (case 2, c=0).
Pattern 1: Merge Sort
def merge_sort(arr: list[int]) -> list[int]:
if len(arr) list[int]:
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] O(n log n)
Pattern 2: Count Inversions (Merge Sort Variant)
def count_inversions(arr: list[int]) -> tuple[list[int], int]:
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, left_inv = count_inversions(arr[:mid])
right, right_inv = count_inversions(arr[mid:])
merged, split_inv = merge_count(left, right)
return merged, left_inv + right_inv + split_inv
def merge_count(left, right):
result, inversions = [], 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, inversions
Pattern 3: Quick Sort and Quick Select
def quicksort(arr: list[int], lo: int = 0, hi: int = None) -> None:
if hi is None: hi = len(arr) - 1
if lo >= hi: return
pivot_idx = partition(arr, lo, hi)
quicksort(arr, lo, pivot_idx - 1)
quicksort(arr, pivot_idx + 1, hi)
def partition(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] int:
"""Find k-th smallest element in O(n) average time."""
lo, hi = 0, len(arr) - 1
while lo < hi:
p = partition(arr, lo, hi)
if p == k:
return arr[k]
elif p < k:
lo = p + 1
else:
hi = p - 1
return arr[lo]
Pattern 4: Binary Search Variants
def binary_search(arr: list[int], target: int) -> int:
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target: return mid
elif arr[mid] int:
"""First index where arr[i] >= target."""
lo, hi = 0, len(arr)
while lo < hi:
mid = (lo + hi) // 2
if arr[mid] int:
"""First index where arr[i] > target."""
lo, hi = 0, len(arr)
while lo < hi:
mid = (lo + hi) // 2
if arr[mid] <= target: lo = mid + 1
else: hi = mid
return lo
Pattern 5: Closest Pair of Points (D&C Classic)
import math
def closest_pair_distance(points: list[tuple[float,float]]) -> float:
def dist(p1, p2):
return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)
def closest(pts):
n = len(pts)
if n <= 3:
return min(dist(pts[i], pts[j])
for i in range(n) for j in range(i+1, n))
mid = n // 2
mx = pts[mid][0]
dl = closest(pts[:mid])
dr = closest(pts[mid:])
d = min(dl, dr)
strip = [p for p in pts if abs(p[0] - mx) < d]
strip.sort(key=lambda p: p[1])
for i in range(len(strip)):
j = i + 1
while j < len(strip) and strip[j][1] - strip[i][1] O(n log^2 n); optimised to O(n log n)
Pattern 6: Majority Element (Boyer-Moore Voting)
def majority_element(nums: list[int]) -> int:
"""Element appearing more than n/2 times."""
candidate = count = 0
for n in nums:
if count == 0:
candidate = n
count += 1 if n == candidate else -1
return candidate
# Linear scan; can be viewed as D&C: majority must be majority in at least one half
Pattern 7: Maximum Subarray (Divide and Conquer)
def max_subarray_dc(nums: list[int], lo: int = 0, hi: int = None) -> int:
if hi is None: hi = len(nums) - 1
if lo == hi: return nums[lo]
mid = (lo + hi) // 2
left_max = max_subarray_dc(nums, lo, mid)
right_max = max_subarray_dc(nums, mid+1, hi)
# Max crossing subarray
left_sum = curr = 0
for i in range(mid, lo-1, -1):
curr += nums[i]
left_sum = max(left_sum, curr)
right_sum = curr = 0
for i in range(mid+1, hi+1):
curr += nums[i]
right_sum = max(right_sum, curr)
return max(left_max, right_max, left_sum + right_sum)
# T(n) = 2T(n/2) + O(n) -> O(n log n)
# Note: Kadane's O(n) is simpler -- D&C version is asked to illustrate the technique
Complexity Quick Reference
| Algorithm | Recurrence | Time |
|---|---|---|
| Binary search | T(n) = T(n/2) + O(1) | O(log n) |
| Merge sort | T(n) = 2T(n/2) + O(n) | O(n log n) |
| Quick sort (avg) | T(n) = 2T(n/2) + O(n) | O(n log n) |
| Quick select (avg) | T(n) = T(n/2) + O(n) | O(n) |
| Closest pair | T(n) = 2T(n/2) + O(n log n) | O(n log² n) |
| Strassen matrix mult. | T(n) = 7T(n/2) + O(n²) | O(n^2.81) |
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the Master Theorem and when can you apply it?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “The Master Theorem solves recurrences of the form T(n) = au00b7T(n/b) + f(n) where au22651, b>1: Case 1: if f(n) = O(n^(log_b(a)-u03b5)), then T(n) = u0398(n^log_b(a)). Case 2: if f(n) = u0398(n^log_b(a)), then T(n) = u0398(n^log_b(a) u00b7 log n). Case 3: if f(n) = u03a9(n^(log_b(a)+u03b5)) and au00b7f(n/b) u2264 cu00b7f(n), then T(n) = u0398(f(n)). Merge sort: T(n)=2T(n/2)+O(n) u2192 Case 2 u2192 O(n log n). Binary search: T(n)=T(n/2)+O(1) u2192 Case 2 u2192 O(log n).”
}
},
{
“@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 iarr[j]. During merge sort’s merge step, when you pick an element from the right half at position j (right_start + r), all remaining left-half elements (left_remaining) are inversions with it. Add left_remaining to count whenever you take from the right. Total inversions = sum of these counts across all merge levels. Time O(n log n), Space O(n).”
}
},
{
“@type”: “Question”,
“name”: “What is Quickselect and what is its average time complexity?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Quickselect finds the kth smallest element without full sorting. Pick a pivot, partition the array so all smaller elements are left and larger are right. If pivot lands at index k, return it. If k < pivot_index, recurse left; otherwise recurse right. Average O(n) because each partition reduces expected size by half. Worst case O(nu00b2) with bad pivots u2014 mitigated by random pivot selection. Used in "kth largest element in an array" and "top k frequent elements"."
}
},
{
"@type": "Question",
"name": "How do you find the closest pair of points in O(n log n)?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Sort points by x. Divide into left/right halves, recurse, get d=min(left_min, right_min). Then check the strip of width 2d around the midline u2014 for each point in the strip, only compare against the next 7 points sorted by y (geometric proof). The combine step is O(n) making the recurrence T(n)=2T(n/2)+O(n) u2192 O(n log n). This beats the O(nu00b2) brute force for large n."
}
},
{
"@type": "Question",
"name": "What distinguishes divide and conquer from dynamic programming?",
"acceptedAnswer": {
"@type": "Answer",
"text": "Divide and conquer splits the problem into independent subproblems with no overlap u2014 merge sort's left and right halves share no elements, so results cannot be reused. Dynamic programming handles overlapping subproblems u2014 Fibonacci(n) needs Fibonacci(n-1) and Fibonacci(n-2), which themselves overlap heavily. DP uses memoization or tabulation to avoid recomputation. If subproblems are independent, D&C is appropriate. If they overlap, use DP."
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Databricks Interview Guide
Asked at: Coinbase Interview Guide
Asked at: LinkedIn Interview Guide