Implement a `HitCounter` with two operations: - `hit(timestamp)` records one request. - `getHits(timestamp)` returns the number of requests in the last 300 seconds, meaning timestamps in the inclusive range `[timestamp - 299, timestamp]`. Assume operation timestamps are nondecreasing. Explain both a queue-based implementation and a fixed-size circular-buffer implementation. ### Constraints & Assumptions - Multiple hits may share one second. - A query does not itself create a hit. - Old history may be discarded once it cannot affect a future query. ### Clarifying Questions to Ask - Are timestamps guaranteed to be nondecreasing? - Is the 300-second boundary inclusive? - What concurrency guarantees must the class provide? ```hint Aggregate before choosing storage Keeping one entry per second can be much smaller than keeping one entry per hit. ``` ### What a Strong Answer Covers - Boundary arithmetic, eviction, complexity, repeated timestamps, and empty state. - The queue and circular-buffer invariants and their memory trade-offs. - A synchronization strategy if operations are concurrent. ### Follow-up Questions - What changes if events arrive out of order? - How would you support an arbitrary window length? - How would a distributed exact counter differ from this in-memory class?