# Implement Fixed-Window Get and Put QPS Tracking Design a key-value service with `put`, `get`, and load-reporting APIs. Track get and put calls separately over the most recent five minutes using system timestamps and a ring buffer of time buckets. QPS is the window count divided by the smaller of 300 seconds and the server's elapsed running time. Explain the implementation, tests, and how it changes for very long or dynamically selected windows and for sparse traffic. ### Constraints & Assumptions - Use one-second buckets for the five-minute configuration. - Calls may be concurrent. - A bucket reused after one full ring must be reset before incrementing. - The service start time or injected clock must be available so startup QPS uses elapsed time. ### Clarifying Questions to Ask - Does a failed get or put still count as an API call? - Should the current partial second be included in elapsed time? - How exact must arbitrary long-window queries be? ```hint Tag every bucket Store the epoch second associated with a slot so old counts are never mistaken for current counts. ``` ```hint Define the denominator Before 300 seconds have elapsed, divide by actual positive uptime rather than the full window. ``` ### What a Strong Answer Covers - Separate counters for operations, correct ring-bucket rollover, and maintained totals. - The startup denominator edge case and a deterministic clock for testing. - Thread-safety and a consistent snapshot for `get_load`. - Trade-offs among ring buffers, timestamp queues, and hierarchical buckets for sparse or long windows. ### Follow-up Questions - How would you merge load measurements from many service instances? - How would approximate multi-day windows reduce memory while retaining recent precision?