# Design a Concurrent, Memory-Bounded Tally Service Design and implement the core of a `TallyService` with two operations: - `bump(timestamp)`: record one event at the given timestamp. - `query(start_time, end_time)`: return the number of recorded events whose timestamps lie in the inclusive range `[start_time, end_time]`. Begin with an exact in-memory design, then adapt it for high concurrency and bounded memory. If bounded memory requires retention or time-bucket approximation, make that contract explicit. Explain how bucket size affects accuracy and how queries remain fast. ### Constraints & Assumptions - Timestamps use one monotonic unit but calls can arrive concurrently and slightly out of order. - The service must define behavior for queries outside its retention window. - Counter overflow, clock source, and acceptable approximation must be clarified. - A process-local design is sufficient for the base problem; discuss durability as a follow-up. ### Clarifying Questions to Ask - Must every arbitrary range be exact, or may boundary buckets be approximate? - What retention horizon and timestamp resolution are required? - How late can events arrive, and can future timestamps occur? - What are the expected read-to-write ratio and contention level? ### What a Strong Answer Covers - A correct exact baseline and its time/space costs - An explicit impossibility trade-off between finite memory, infinite history, exact timestamps, and arbitrary queries - Thread-safe bucket rotation and counter updates - Prefix, tree, or hierarchical aggregation for faster queries - Boundary semantics, late events, overflow, and testing ### Follow-up Questions - How would you shard the service across machines? - How would you make bumps durable and idempotent? - Can a ring buffer be reset safely while another thread increments it? - What structure supports many queries at multiple time resolutions?