Sorted Timestamps + Binary Search

When a design stores events with timestamps and later asks "which ones fall between start and end?", keep the timestamps in a sorted list. Two binary searches then find both ends of the range in $O(\log n)$ , and the answer is the slice between them. The same idea handles "value as of time t" and "counts per minute / hour / day" queries.

The idea#

In a sorted list, bisect_left(a, x) is the first index whose item is >= x, and bisect_right(a, x) is the first index whose item is > x. So the items in the closed range [lo, hi] are exactly a[bisect_left(a, lo) : bisect_right(a, hi)].

Two tricks make this fit design problems:

Tuples as keys. Store (timestamp, id). To bracket every id at a timestamp, search for (lo, -1) on the left and (hi, inf) on the right.
Fixed-width strings sort like times. In "YYYY:MM:DD:HH:MM:SS" every field has a fixed width, so string order equals chronological order. You can compare and bisect the strings directly.

This works because in a sorted list, everything in a range sits in one contiguous block. Binary search finds the two edges of that block without looking at anything outside it.

How to spot it#

These cues point to a sorted list plus binary search.

"retrieve all ids between start and end", optionally "at granularity Year / Day / Hour"
"get the value of key at timestamp" (latest value at or before t)
"number of events per minute / hour / day between start and end"
the time range changes per query, so a fixed ring buffer does not fit

Template#

The template covers both halves of the pattern: a range query over (timestamp, id) pairs, and per-bucket counts.

init():
    events = empty list                 # sorted (timestamp, id)
put(id, ts):
    if ts arrives in order: append (ts, id)
    else: insert (ts, id) at its sorted spot   # O(n) shift in a list
range(lo, hi):
    i = bisect_left(events, (lo, sentinel below every id))
    j = bisect_right(events, (hi, sentinel above every id))
    return the ids in events[i:j]       # O(log n + m)
bucket_counts(times, start, end, delta):
    counts = ((end - start) // delta + 1) zeros
    i = bisect_left(times, start)       # skip everything before start
    while i < length and times[i] <= end:
        counts[(times[i] - start) // delta] += 1
        i += 1
    return counts

Granularity becomes a prefix length#

Log queries often come with a granularity, and this is where the fixed-width string trick pays off. With granularity "Day", only YYYY:MM:DD matters, which is the first 10 characters. Padding the start with zeros and the end with nines turns "any time on these days" into one closed string range:

Granularity	Kept prefix	`start` becomes	`end` becomes
Year (4)	`2016`	`2016:00:00:00:00:00`	`2017:99:99:99:99:99`
Day (10)	`2016:01:01`	`2016:01:01:00:00:00`	`2017:01:01:99:99:99`
Hour (13)	`2016:01:01:01`	`2016:01:01:01:00:00`	`2017:01:01:23:99:99`

The padded values are not real times, but they don't need to be. They only need to sort below or above every real timestamp with that prefix.

Bucket index and bucket count#

The bucket_counts loop in the template rests on two formulas. A time t belongs to bucket (t - start) // delta. The number of buckets is the bucket index of end, plus one, so (end - start) // delta + 1. With minute buckets (delta = 60) and start = 0:

`end`	`(end - start) // 60 + 1`	Buckets
59	1	[0, 59]
60	2	[0, 59], [60, 60]
119	2	[0, 59], [60, 119]

The last bucket can be shorter than delta, because it is cut off at end.

Pitfalls#

These mistakes cause the most wrong answers.

insort is not $O(\log n)$ . Finding the spot is, but inserting into a Python list shifts everything after it, so each insert is $O(n)$ . If timestamps arrive in order, a plain append keeps the list sorted.
Wrong tuple sentinels. (lo, 0) misses a negative id; (hi, 0) cuts off ids above 0 at the end time. Pick sentinels below and above every possible second field.
Comparing variable-width strings. "9:00" sorts after "10:00". The string trick needs fixed width with zero padding.
Bucket count off by one. (end - start) // delta is the index of the last bucket, so the length is that plus one.
Scanning the whole list per query. Bisect to start first, then stop at end.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with Time Based Key-Value Store.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Design Log Storage System

Keep a sorted list of (timestamp, id). Map each granularity to a prefix length (Year 4, Month 7, Day 10, Hour 13, Minute 16, Second 19). Pad the start with "0000:00:00:00:00:00"[k:] and the end with "9999:99:99:99:99:99"[k:], then bracket with (lo, -1) and (hi, float("inf")).

Hint: Design Log Storage System: cost

retrieve is $O(\log n + m)$ for m results. put with insort is $O(n)$ because of the list shift. If writes dominate, use SortedList from sortedcontainers ( $O(\log n)$ insert), or append and sort lazily before the next query.

Hint: Tweet Counts Per Frequency

Keep a sorted list of times per tweet name. Map the frequency to seconds once: minute 60, hour 3,600, day 86,400. Then run the bucket-count loop: bisect to startTime and walk forward while <= endTime.

Hint: Time Based Key-Value Store

Keep key -> [(timestamp, value), ...], appended in order, so each list stays sorted for free. "Value at time t" is the entry just before bisect_right(times, t), or "" if that index is 0.

Hint: Design Hit Counter

Hits arrive in order, so append each time. getHits(t) is len(times) - bisect_right(times, t - 300). Any window size works on the same list, which a ring buffer can't do, but every timestamp is kept, so production code must prune. The trade-off table is in Sliding Time Window.

Key takeaways#

Two bisects bracket a closed range: bisect_left(lo) to bisect_right(hi).
Store (timestamp, id) tuples and use sentinels below and above every id to bracket a timestamp.
Fixed-width time strings sort chronologically, so a granularity is a prefix length plus padding.
Bucket of t is (t - start) // delta; the number of buckets is (end - start) // delta + 1.
In-order arrivals can be appended; out-of-order ones need insort ( $O(n)$ ) or a SortedList.

Core idea#

Keep timestamps in a sorted list. Two binary searches find both ends of a range in $O(\log n)$ , and the answer is the slice between them.

Key points#

bisect_left(a, x) is the first index with item >= x. bisect_right(a, x) is the first with item > x.
The closed range [lo, hi] is a[bisect_left(a, lo):bisect_right(a, hi)].
Store (timestamp, id) tuples. Bracket with (lo, -1) and (hi, float("inf")).
Fixed-width strings like "YYYY:MM:DD:HH:MM:SS" sort in time order.
Granularity is a prefix length (Year 4, Day 10, Hour 13). Pad the start with zeros and the end with nines.
Bucket of t is (t - start) // delta. The bucket count is (end - start) // delta + 1.
Hit Counter: len(times) - bisect_right(times, t - 300). Any window works, but every timestamp is kept.
Time Based Key-Value Store: the value is the entry before bisect_right(times, t), or "" at index 0.

Template#

range(events, lo, hi):                  # events: sorted (ts, id)
    i = bisect_left(events, (lo, -1))
    j = bisect_right(events, (hi, float("inf")))
    return the ids in events[i:j]
bucket_counts(times, start, end, delta):
    counts = ((end - start) // delta + 1) zeros
    i = bisect_left(times, start)       # skip times before start
    while i < length and times[i] <= end:
        counts[(times[i] - start) // delta] += 1
        i += 1
    return counts

Pitfalls#

Calling insort $O(\log n)$ . The list shift makes it $O(n)$ . Append in-order data, or use SortedList.
Wrong tuple sentinels. (lo, 0) misses a negative id.
Comparing variable-width strings. "9:00" sorts after "10:00".
Bucket count off by one.
Scanning the whole list instead of bisecting to start first.

Say it in an interview#

"Two bisects bracket the range, so each query is O(log n) plus the results."
"Fixed-width timestamps sort as strings, so granularity is a prefix plus padding."