# The Firehose > A stream arrives out of order. Roll it up, one time window at a time. Canonical URL: 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. ## 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** ```python 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. > **Time and Space Complexity** > > Time is O(n + w log w): n events each bucketed in O(1), then a sort over the w distinct windows. Space is O(w). You cannot beat the sort without giving up the chronological output, and w is tiny next to n in any real firehose, so the linear pass dominates. > **Interviewers Watch For** > > Whether you reach for floor division on sight or fumble toward modulo. This exact snap-to-window-start is what Kafka Streams and Flink call a tumbling window, and using `//` cleanly signals you have seen the pattern before. > **Common Pitfall** > > Sorting the events up front because the prompt stresses they arrive unordered. It is wasted work: bucketing is commutative, so you sort the handful of windows at the end, not the n events at the start. --- ## Common follow-up questions - What if events keep arriving after you have already emitted a window? _(Tests late-arriving event handling and watermark concepts from streaming systems.)_ - How would you implement sliding windows instead of tumbling ones? _(Tests overlapping window assignment where each event belongs to multiple windows.)_ - What if you need to emit running totals as events come in, not at the end? _(Tests incremental aggregation vs batch computation.)_ - How does this pattern map to a SQL grouped aggregation? _(Tests FLOOR(timestamp / width) * width as the grouping key.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/the_firehose) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.