Tally Service

Implement a Tally Service with `bump(timestamp)` to record an event and `query(startTime, endTime)` to return the inclusive count for a time range. Follow-ups require thread-safe high-concurrency behavior, bounded memory through a sliding window or time buckets, and faster queries. Requirements Implement a TallyService class with two core operations: bump(timestamp): record one event at the supplied timestamp. query(startTime, endTime): return the cumulative number of events in the inclusive range [startTime, endTime]. Make the service thread-safe and performant under high concurrency. Bound memory usage with a sliding window or time buckets instead of retaining unlimited history. Reduce the time complexity of query so range counts return quickly. Notes The interface leaves the timestamp unit, retention horizon, late-arriving events, concurrency model, and required read consistency unspecified. Clarify them before choosing bucket granularity and synchronization boundaries. The interval is inclusive at both ends. Make that boundary rule explicit in the implementation and tests. A ring of time buckets gives bounded memory and range queries proportional to the number of covered buckets. Store each bucket's epoch or version so a reused slot cannot contribute stale counts; use per-bucket synchronization or sharding to reduce write contention. Aggregate-only buckets are exact for bucket-aligned ranges. For arbitrary boundaries, retain enough detail in the two boundary buckets or explicitly negotiate approximate semantics. Preparation Implement a correct single-threaded baseline, then add bounded retention and a faster range-query path without changing the public API. Write down the synchronization scope for bump and query, and explain how contention changes as the write rate increases. Drill boundary tests at startTime, endTime, the retention cutoff, bucket reuse, and across adjacent buckets.