Rafael Romão's Coding Labs

Lab L17 · Java + Go

Implementing a time-window event aggregator

Build a rolling-window aggregator over timestamped integer events. You add events as time moves forward, and query(now, k) returns the count, the maximum and the k largest values among events from the last width time units. Time is driven only by the timestamps you pass in: each call moves a watermark forward, and an event older than the watermark is rejected as late.

The task

Surge pricing watches demand: “how many ride requests in the last 5 minutes, and what were the largest fares?”. Old events must leave the window as time moves, and the answer must be exact, not sampled. Because tests pass time explicitly, there is no wall clock: the watermark is simply the latest time anyone has told the window about. The window is half-open on the left, so an event exactly width old has just left.

window at watermark 11: (1, 11]012468101112145expired (exactly width old)92watermark 11add(8, 7) ✗ latequery(11, 5) → count 2 · max 9 · top [9, 2]
At watermark 11 the window is (1, 11]. The event at time 1 sits on the open edge and is gone; an event stamped 8 that arrives now is rejected even though 8 is inside the window, because time never moves backwards.

What you implement

public final class EventWindow {
    public record Event(long time, long value) {}
    public record Snapshot(int count, OptionalLong maximum, List<Long> top) {}

    public EventWindow(long width, int capacity);   // both > 0; capacity = max events held
    public void add(Event event);                   // advances the watermark to event.time()
    public Snapshot query(long now, int k);         // advances the watermark to now
}

Rules

  • Every add and query advances the watermark to its time. A time below the current watermark, or a negative time → IllegalArgumentException (late). A time equal to the watermark is fine.
  • At watermark t the window holds events with t − width < time <= t. An event exactly width old is expired.
  • If the window already holds capacity events after expiring old ones, add → IllegalStateException; the watermark still advanced.
  • query: count, maximum (empty when no events), top = the k largest values in descending order, duplicates kept. k < 0 → IllegalArgumentException; k = 0 → [].
  • Events with equal times are separate observations; there is no deduplication.

Worked example

  1. width = 10. add(1, 5), add(4, 9), add(4, 2).
  2. query(4, 2) → count 3, max 9, top [9, 5].
  3. query(11, 5) → the event at 1 is exactly 10 old and expires → count 2, max 9, top [9, 2].
  4. add(8, 7) → IllegalArgumentException: the watermark is already 11.

Files and commands

Read the tests first, then replace each TODO in the starter until they pass. Java starter: EventWindow.java · tests: EventWindowTest.java. Go starter: window.go · tests: window_test.go.

cd java
./gradlew test --tests 'labs.windowmetrics.*'

cd go
go test -race -count=1 ./windowmetrics
Reveal the reference solutions

Java: EventWindow.java
Go: window.go

When to use

Use this lab for an exact local aggregation of integer-valued observations in a caller-controlled rolling window. A positive width and positive event capacity are required. Timestamps are nonnegative signed integers in a shared caller-selected unit. The watermark never moves backwards. Events at a timestamp less than the watermark are rejected; equal timestamps are accepted and count as separate observations. There is no deduplication.

At watermark t, the window is open on the left and closed on the right: retain events newer than t minus width and no later than t. An event exactly one width old expires. Querying advances the watermark, so a later-arriving event older than the last query is late even if it would otherwise lie inside the window. This strict policy is not an event-time system with allowed lateness or result corrections.

Steps

  1. Own time. Treat timestamps and queries as explicit state transitions rather than reading a hidden wall clock. Validate nonnegative, nondecreasing time before mutating state. Subtract an earlier nonnegative time from the current one instead of computing a potentially overflowing deadline.
  2. Retain ordered observations. Since admission requires nondecreasing time, expiration removes a prefix. Java uses a deque and Go uses a compacted slice. The event capacity bounds retained observations, not the total duration represented or the rate of calls.
  3. Define admission failure. Each add first advances time and removes expired entries. If capacity remains full, reject the incoming observation. The watermark advancement still stands; rejection does not roll it back. This makes the event loss explicit instead of silently dropping an old live observation and continuing to report an exact count.
  4. Return exact aggregates. Count retained observations, sort their values descending, and select the first K, retaining duplicate values. K may be zero but not negative. Maximum has an explicit absence indicator for an empty window, so zero and negative maxima remain valid results. Return independent result collections.
  5. Test a timeline. With width ten, store values at times zero and five. Query at nine to see both and at ten to see only the newer one. Reject an event at nine after that query, accept one at ten if capacity permits, and advance to twenty to expire it. Include equal timestamps and capacity rejection.
  6. Measure before optimizing. This reference sorts n retained values for each query, taking O(n log n) work. Go compaction is O(n) on advance; Java prefix removals are proportional to expired observations. A monotonic deque can accelerate maxima and a heap can bound top-K selection cost, but neither removes the need to define window semantics and exact retained-state accounting.

Checklist

Recall and variation

Rebuild expiry before reading Go or Java. Variation: replace repeated sorting for maximum with the compact monotonic-deque example. Acceptance: a seeded stream agrees with the exact reference, including duplicate maxima and left-boundary expiry. Top-K and k-way merge are separate tested structures in algorithms.

  • Exact expiry boundary and watermark ownership are documented
  • Late events fail instead of silently corrupting time order
  • Admission failure distinguishes bounded capacity from approximate retention
  • Empty maxima and duplicate top values have unambiguous representations
  • Query result mutation cannot change stored state

Signals

Working: a hand-calculated timeline matches count, maximum, and descending top-K at each boundary.

Going wrong: a query admits later out-of-order data despite its stated policy, a zero maximum means both empty and present, or old entries are dropped under pressure while the result is still called exact.

Related