An event log is kept on a slow disk as a sorted sequence of timestamps. Reading one timestamp is expensive, while asking for the length is free. Analysts ask many questions of the form "how many events happened between lo and hi, inclusive?".
Write count_between(shelf, queries). shelf is a Shelf: len(shelf) gives the number of timestamps and shelf[i] reads the one at position i (slices are refused, and looping over the shelf reads every item). queries is a list of pairs (lo, hi). Return a list with, for each query, the number of timestamps t with lo <= t <= hi (0 when lo > hi).
Every read is counted. The tests call your function through on_shelf(count_between, values, queries), which allows about 2 * (log2(n) + 2) reads per query on a shelf of n timestamps and raises TooManyReads beyond that. Other helpers you can use with Run: Shelf(values) (its reads attribute is the count so far; it has no budget), event_times(n, seed) and windows(q, top, seed).
Examples
Input: on_shelf(count_between, [2, 3, 3, 7, 10, 10, 10, 15], [(3, 10), (4, 6), (0, 100), (10, 10), (9, 2)])
Output: ([6, 0, 8, 3, 0], True)
Input: on_shelf(count_between, [], [(1, 5)])
Output: ([0], True)
Constraints
0 <= n <= 200000timestamps, integers in non-decreasing order; at most2000queries.- The limit counts reads, not time.
Goals
- See why a scan of the data per question is the cost to remove, not the Python around it
- Use `bisect` on any object that supports `len()` and indexing
- Count the items in a closed range with two searches instead of a loop