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 requests (many values repeat). Report the k-th largest response time (k = 1 is the slowest) without sorting the whole log.