Practice Problems

The heart of every search problem is spotting what is monotone. The five problems below practice boundary finding, "latest value before" lookups, searching on the answer, and building a monotone predicate out of an array's shape. Try each one yourself before reading the approach and solution.

Problem 1. Students in a score band

You are given exam scores sorted in ascending order and a list of queries. For each query (L, R), report how many students scored at least L and at most R. There are up to 100,000 students and 100,000 queries.

Approach: scanning everything per query could take ten billion comparisons. The number of scores at most R is upper_bound(R), and the number below L is lower_bound(L), so their difference is the answer at O(log n) per query.

from bisect import bisect_left, bisect_right


def count_in_range(scores, queries):
    return [bisect_right(scores, r) - bisect_left(scores, l) for l, r in queries]


print(count_in_range([40, 55, 55, 70, 85, 90], [(50, 80), (55, 55), (91, 100)]))
# [3, 2, 0]

Problem 2. Sensor value at a given time

A sensor log is a list of (timestamp, value) pairs in ascending time order. For each query time t, return the most recent value recorded at or before t, or None if no such reading exists.

Approach: upper_bound(t) is the position of the first reading after t, so the reading just before it is the answer. If that position is 0, nothing was recorded yet. Build the list of timestamps once and each query becomes a single binary search.

from bisect import bisect_right


def value_at(log, t):
    times = [time for time, _ in log]
    i = bisect_right(times, t) - 1
    return log[i][1] if i >= 0 else None


log = [(100, 21.5), (160, 22.0), (220, 21.8)]
print(value_at(log, 99), value_at(log, 160), value_at(log, 500))
# None 22.0 21.8

With many queries, build times once outside the function and reuse it.

Problem 3. Binding chapters into k volumes

A list pages holds the page count of each chapter. You must bind the chapters, in order, into at most k volumes of consecutive chapters. Minimize the page count of the thickest volume and return it.

Approach: the question "can the thickest volume stay at or below cap pages?" flips from false to true exactly once as cap grows. Feasibility is a greedy O(n) scan that fills each volume until the next chapter would overflow it. The answer lies between the longest single chapter and the total page count, for O(n log(total)) overall.

def min_thickest(pages, k):
    def fits(cap):
        volumes, current = 1, 0
        for p in pages:
            if current + p > cap:
                volumes += 1
                current = 0
            current += p
        return volumes <= k

    lo, hi = max(pages), sum(pages)
    while lo < hi:
        mid = (lo + hi) // 2
        if fits(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


print(min_thickest([30, 10, 40, 20, 50], 2))   # 80
print(min_thickest([30, 10, 40, 20, 50], 3))   # 60