Design Hit Counter

Design a hit counter which counts the number of hits received in the past 5 minutes (that is, the past 300 seconds). Implement the HitCounter class:

• HitCounter() Initializes the object of the hit counter system.
• void hit(int timestamp) Records a hit that happened at timestamp (in seconds). Several hits may happen at the same timestamp.
• int getHits(int timestamp) Returns the number of hits in the past 5 minutes from timestamp. You may assume that calls are made in chronological order, so timestamp is monotonically increasing.

HitCounter hitCounter = new HitCounter(); hitCounter.hit(1); hitCounter.hit(2); hitCounter.hit(3); hitCounter.getHits(4); // return 3 hitCounter.hit(300); hitCounter.getHits(300); // return 4 hitCounter.getHits(301); // return 3

Multiple hits in the same second share the same bucket, but all of them still count within the 300-second window.

Apple-Specific Notes

In the Apple phone screen, the API is usually described as increment() and getValue() (no timestamp argument — it reads wall-clock time). Once you start coding, parameterize the timestamp as in the LeetCode formulation so the solution is testable; the interviewer will accept this. The 5-minute expiration window is the same as the LeetCode 300-second window.

Follow-up: High-Throughput increment()

Question: What if increment() is called hundreds of millions of times? The per-hit bookkeeping becomes too expensive. Expected direction (rate limiter / token bucket):

• Don't record every hit individually. Instead, cap the rate at which hits are admitted into the counter using a token bucket or leaky bucket.
• Admitted hits update the bucket array as usual; excess hits are dropped (or counted into a coarse overflow bucket).
• Alternative: batch hits with an atomic counter per second and flush into the bucket array once per second, turning N increments into one update. Discussion points:
• Accuracy vs. throughput trade-off — sampling / rate-limiting loses precision but keeps the counter cheap under load.
• If exact counts are required, shard the counter across threads/cores and aggregate on read (getValue) instead of on write.
• At extreme scale, move the counter out of process: a distributed counter backed by Redis INCR with TTL, or a stream aggregator (Kafka + Flink).