#362 Design Hit Counter
the problem
In plain words
You're building the live "requests in the last 5 minutes" number on a web server's dashboard. Implement HitCounter: hit(timestamp) records one request at that second, and getHits(timestamp) returns how many requests arrived in the last 300 seconds — timestamps in the range (timestamp − 300, timestamp]. Calls come in non-decreasing time order, and many hits can share the same second.
in hit(2), hit(2), hit(150), getHits(150), hit(301), getHits(301), getHits(302), getHits(450), getHits(601)
out 3, 4, 2, 1, 0
At 302 the window is (2, 302], so both hits at second 2 have expired. At 601 it is (301, 601] — even the hit at 301 is out.
- 1 ≤ timestamp ≤ 2·10⁹
- Calls arrive in non-decreasing timestamp order
- Several hits can share one timestamp
- At most 300 calls in total (follow-up: what if there are millions of hits per second?)
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code right here. Stuck for 20 minutes? Open one hint at a time.
This one is LeetCode Premium. You don't need a subscription: solve it right here. The free alternative linked above is the closest free practice; its label says how close it is.
Solve it in the browser
Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternStack & queue designSliding window (variable size)
A hit older than 300 seconds never comes back into the window, so you may forget it. And because only the last 300 seconds matter, 300 counters — one per second, reused every 5 minutes — are enough, however many hits arrive.
solutions
From brute force to optimal
Append every hit to a list; getHits scans the whole list and counts timestamps > t − 300.
- hit:
hits.add(timestamp). - getHits: count the stored timestamps with
ts > t − 300.
n = every hit ever recorded — old hits are re-checked on every read.
Nothing is ever thrown away.
// On LeetCode, name this class HitCounter.class HitCounterScan { private final List<Integer> hits = new ArrayList<>(); // every hit, kept forever public void hit(int timestamp) { hits.add(timestamp); } public int getHits(int timestamp) { int count = 0; for (int t : hits) { if (t > timestamp - 300) count++; // re-checks every old hit on every call } return count; }}Same as Number of Recent Calls: offer each hit; on getHits, poll from the front while the front is ≤ t − 300; return the size.
- hit:
q.offer(timestamp). - getHits: while
q.peek() <= t − 300, poll. - Return
q.size().
Each hit is offered once and polled at most once.
One entry per hit — at a million hits per second that is 3·10⁸ entries.
// On LeetCode, name this class HitCounter.class HitCounterQueue { private final Queue<Integer> window = new ArrayDeque<>(); // one entry per hit, oldest at the front public void hit(int timestamp) { window.offer(timestamp); } public int getHits(int timestamp) { while (!window.isEmpty() && window.peek() <= timestamp - 300) { window.poll(); // too old now, and for every later call too } return window.size(); }}Bucket t % 300 counts the hits of one second and remembers which second. The same bucket comes back every 300 s; if it holds an older second, recycle it.
- hit: b = t % 300. If
second[b] != t, setsecond[b] = tandcount[b] = 0. Thencount[b]++. - getHits: add
count[b]for every bucket witht − second[b] < 300.
The window size is fixed, so a read always scans exactly 300 buckets, whatever the traffic.
Two arrays of 300; memory no longer grows with the number of hits.
class HitCounter { private final int[] second = new int[300]; // the timestamp each bucket currently counts private final int[] count = new int[300]; // how many hits arrived at that timestamp public void hit(int timestamp) { int b = timestamp % 300; // the same bucket comes back every 300 seconds if (second[b] != timestamp) { // it still holds an old second: recycle it second[b] = timestamp; count[b] = 0; } count[b]++; } public int getHits(int timestamp) { int total = 0; for (int b = 0; b < 300; b++) { if (timestamp - second[b] < 300) total += count[b]; // only seconds inside the window } return total; }}in the room
How to say it in the interview
talk track
- Clarify first: is the window (t − 300, t]? Are calls in time order? Can many hits share a second?
- Start with the queue — it is Number of Recent Calls with 300 seconds: offer on hit, poll expired hits on read.
- Raise the follow-up yourself: "with a million hits per second the queue holds 3·10⁸ entries, so I'd count per second in 300 buckets instead."
- Explain the reset:
t % 300repeats every 300 s, so a bucket that holds a different second is stale and starts again from zero.
traps
- Using
>=for the window start: a hit at exactly t − 300 is already outside, because the window is (t − 300, t]. - Bucket version: adding a bucket's count without checking its stored second — counts from 5+ minutes ago leak in.
- Bucket version: reusing a bucket for a new second without resetting its count to 0.
what they ask next
Follow-ups
Millions of hits per second?
That is exactly what the buckets solve: memory stays 300 (second, count) pairs. Or keep the queue but store [second, count] pairs, so a burst in one second is one entry.
Many threads call hit at the same time?
Simplest: synchronize both methods. At scale, keep per-thread or per-shard counters and add them up on read — the idea behind Java's LongAdder.
Timestamps can arrive out of order?
The queue trick breaks. Keep a TreeMap<Integer, Integer> of second → count and add up subMap(t − 299, true, t, true).
before you submit
Edge cases to test
- Many hits in the same second must all count.
- A hit at exactly t − 300 is outside the window.
- After more than 300 s of silence, every old bucket must be ignored even though its count is still stored.
- getHits before any hit returns 0.
practise next
Similar problems
- #933Number of Recent CallsEasyin Queues
- #622Design Circular QueueMediumin Queues
- #146LRU CacheMediumin Linked Lists