The Firehose

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Amazon

Problem

You're rolling up a stream of metric events, each carrying a numeric timestamp and a numeric value, into fixed-width time windows of size bucket_width, where a window spans [bucket_start, bucket_start + bucket_width). The events arrive unsorted, so collapse every window holding at least one of them into its event count, the total of its values, and the bucket_start it begins at, dropping any window that caught nothing. Return the windows in chronological order, earliest bucket_start first.

A stream arrives out of order. Roll it up, one time window at a time.

Example

Input:

events = [{"value":10,"timestamp":100},{"value":20,"timestamp":250},{"value":15,"timestamp":150},{"value":5,"timestamp":310}], bucket_width = 100

Output:

[{"count":2,"total":25,"bucket_start":100},{"count":1,"total":20,"bucket_start":200},{"count":1,"total":5,"bucket_start":300}]

Worked solution and explanation

What this really is

Strip the streaming-analytics costume off and this is a histogram over a continuous axis: every event's timestamp collapses onto the left edge of the fixed-width window it lands in, and you tally what shares an edge. Almost everyone gets the tally. The people who stumble reach for modulo (which hands you the offset INSIDE the window, not the window's start) or sort the events first because the prompt says they arrive unordered. You never need the order. A histogram does not care what sequence the samples came in, only which window each one falls into.

Break it down

Step 1: Snap each timestamp to its window start

Integer-divide the timestamp by the width, then multiply back: (ts // bucket_width) * bucket_width snaps any timestamp down to the start of its window. ts=150 with width 100 lands in window 100; ts=250 lands in 200. That is the whole trick, and it is order-independent, so the unsorted input never bites you.

Step 2: Accumulate count and total per window

Key a dict on that window start and carry two accumulators per window: a running count and a running total of values. First time you see a window, seed it; every event after just increments. One pass, O(1) per event.

Step 3: Sort the surviving windows and emit

Sorting the dict's items by key gives you the windows earliest-to-latest for free, and because you only ever created a key when an event landed in it, empty windows are absent by construction. Emit one dict per surviving window.

The solution

Floor-division bucketing with dual aggregation
def aggregate_events(events: list[dict], bucket_width: int) -> list[dict]:
    buckets = {}
    for event in events:
        ts = event['timestamp']
        bucket_start = (ts // bucket_width) * bucket_width
        if bucket_start not in buckets:
            buckets[bucket_start] = {'count': 0, 'total': 0}
        buckets[bucket_start]['count'] += 1
        buckets[bucket_start]['total'] += event['value']
    return [
        {
            'count': agg['count'],
            'total': agg['total'],
            'bucket_start': bucket_start,
        }
        for bucket_start, agg in sorted(buckets.items())
    ]
Floor division (correct)
(ts // w) * w maps 100 and 150 to 100, and 250 to 200: the window's START. Distinct windows stay distinct.
Modulo (the trap)
ts % w maps 100 to 0, 150 to 50, 250 to 50: the OFFSET inside a window. Unrelated events collide and every window past the first merges into one.

Common follow-up questions