Design Hit Counter
Problem
Design a counter with hit(timestamp) and getHits(timestamp), which returns the number of hits in the past 300 seconds (timestamps in (t − 300, t]). Timestamps are in seconds and arrive in non-decreasing order.
Example 1
Input: hit(1), hit(2), hit(3), getHits(4), hit(300), getHits(300), getHits(301) Output: 3, 4, 3
Test cases
Case 1
Input: new HitCounter() .hit(1) .hit(2) .hit(3) .getHits(4) .hit(300) .getHits(300) .getHits(301) Expected: [null,null,null,3,null,4,3]
Case 2
Input: new HitCounter() .hit(1) .hit(1) .getHits(1) .getHits(300) .getHits(301) Expected: [null,null,2,2,0]
Case 3
Input: new HitCounter() .getHits(1) Expected: [0]
View solutionHide solution2 approaches
1. Queue of timestamps
Time O(1) amortisedSpace O(hits in the window)
Push each hit; on getHits drop timestamps older than 300 s from the front.
class HitCounter { constructor() { this.q = []; this.head = 0; } hit(t) { this.q.push(t); } getHits(t) { while (this.head < this.q.length && this.q[this.head] <= t - 300) this.head++; return this.q.length - this.head; }}2. Fixed 300-slot ring buffer
Time hit O(1), getHits O(300)Space O(300)
Bounded memory under heavy traffic: slot t % 300 stores [time, count]; reset a slot when its time is stale.
class HitCounter { constructor() { this.times = new Array(300).fill(0); this.counts = new Array(300).fill(0); } hit(t) { const i = t % 300; if (this.times[i] !== t) { this.times[i] = t; this.counts[i] = 0; } this.counts[i]++; } getHits(t) { let total = 0; for (let i = 0; i < 300; i++) if (t - this.times[i] < 300) total += this.counts[i]; return total; }}The follow-up "what if hits per second are huge?" is asking for this version.