Practice Problems

Four original problems, each with an approach and a Python solution. Try each one before reading the solution: first decide how to split the input and what information has to cross the split.

Problem 1: Disagreeing judges

Two judges each rank the same n contestants from best to worst. Count the pairs of contestants that the two judges put in opposite order. n can be 200,000, so checking all pairs is too slow.

Approach: number the contestants by judge A's order, then rewrite judge B's list in those numbers. A pair is ordered differently exactly when it is an inversion in the rewritten list, so the answer is an inversion count in O(n log n).

def disagreements(judge_a, judge_b):
    rank = {name: i for i, name in enumerate(judge_a)}
    seq = [rank[name] for name in judge_b]

    def sort_count(xs):
        if len(xs) <= 1:
            return xs, 0
        mid = len(xs) // 2
        left, x = sort_count(xs[:mid])
        right, y = sort_count(xs[mid:])
        merged, i, j, cross = [], 0, 0, 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                j += 1
                cross += len(left) - i
        merged.extend(left[i:])
        merged.extend(right[j:])
        return merged, x + y + cross

    return sort_count(seq)[1]

print(disagreements(["ann", "bo", "cy", "di"], ["bo", "ann", "di", "cy"]))  # 2

Problem 2: Climbing a huge staircase

You climb a staircase of n steps, taking 1 or 2 steps at a time. How many different ways are there to reach the top, modulo 1_000_000_007? n can be as large as 10^18.

Approach: ways(n) = ways(n - 1) + ways(n - 2) with ways(0) = ways(1) = 1, so ways(n) is the Fibonacci number F(n + 1). A loop of 10^18 steps is impossible, but the step is a matrix: [[1, 1], [1, 0]]^n = [[F(n+1), F(n)], [F(n), F(n-1)]]. Raise the matrix to the n-th power with fast exponentiation in O(log n) matrix products.

MOD = 1_000_000_007

def mat_mult(x, y):
    return [[(x[i][0] * y[0][j] + x[i][1] * y[1][j]) % MOD for j in range(2)]
            for i in range(2)]

def mat_pow(m, e):
    if e == 0:
        return [[1, 0], [0, 1]]
    half = mat_pow(m, e // 2)
    result = mat_mult(half, half)
    return mat_mult(result, m) if e % 2 else result

def stairs(n):
    return mat_pow([[1, 1], [1, 0]], n)[0][0]

print([stairs(n) for n in range(6)])  # [1, 1, 2, 3, 5, 8]
print(stairs(10**18))

Problem 3: The k-th slowest request

A log holds the response times of n requests (many values repeat). Report the k-th largest response time (k = 1 is the slowest) without sorting the whole log.

Approach: quickselect on the position n - k in ascending order. Because values repeat, use a three-way split into less, equal and greater; otherwise a log full of equal values would make every step remove just one element.

import random

def kth_largest(values, k):
    target = len(values) - k            # 0-based position in ascending order
    items = list(values)
    while True:
        pivot = random.choice(items)
        less = [v for v in items if v < pivot]
        equal = [v for v in items if v == pivot]
        greater = [v for v in items if v > pivot]
        if target < len(less):
            items = less
        elif target < len(less) + len(equal):
            return pivot
        else:
            target -= len(less) + len(equal)
            items = greater

times = [120, 85, 300, 85, 95, 300, 40]
print(kth_largest(times, 1), kth_largest(times, 3))  # 300 120

The expected total work is O(n), because on average each round keeps a constant fraction of the items.

Problem 4: The best stretch of trading days

Given daily profits (some negative), find the largest total of a non-empty run of consecutive days.

Approach: the best run lies entirely in the left half, entirely in the right half, or crosses the middle. The crossing case is the best suffix of the left half plus the best prefix of the right half, found by scanning outward from the middle in O(n). That gives T(n) = 2T(n/2) + O(n) = O(n log n). (Kadane's algorithm solves this in O(n), but the divide-and-conquer version is the pattern behind segment trees.)

def max_run(a):
    def solve(lo, hi):                  # inclusive range, non-empty
        if lo == hi:
            return a[lo]
        mid = (lo + hi) // 2
        best_side = max(solve(lo, mid), solve(mid + 1, hi))
        total, best_left = 0, float("-inf")
        for i in range(mid, lo - 1, -1):
            total += a[i]
            best_left = max(best_left, total)
        total, best_right = 0, float("-inf")
        for i in range(mid + 1, hi + 1):
            total += a[i]
            best_right = max(best_right, total)
        return max(best_side, best_left + best_right)
    return solve(0, len(a) - 1)

print(max_run([3, -4, 5, -1, 2, -6, 4]))  # 6  (5 - 1 + 2)
print(max_run([-3, -1, -2]))              # -1

Summary

• Problem 1 reduces a comparison of two rankings to an inversion count.
• Problem 2 applies fast exponentiation to matrices instead of numbers.
• Problem 3 needs a three-way partition so repeated values cannot slow quickselect down.
• Problem 4 shows the crossing-middle case that many divide-and-conquer solutions share.