How do you count hits in the last 5 minutes?

Store each hit's timestamp in a queue in arrival order. When asked for the count at time T, remove timestamps from the front while they are at or before T minus 300 seconds, then return the queue length. Each timestamp enters and leaves once, so the work is amortized constant per call. This assumes timestamps arrive in increasing order; otherwise keep a sorted list and use binary search.

Should a hit counter use a queue or a fixed array of 300 buckets?

A queue stores one entry per hit, so memory grows with traffic in the window, but the code is simple. A fixed array of 300 buckets, indexed by timestamp modulo 300, stores a second and a count in each slot, so memory stays constant however many hits arrive. A query sums the slots whose stored second is still inside the window, which costs 300 steps per query.

How do you handle many hits per second or out-of-order timestamps in a hit counter?

For heavy traffic, group hits by second instead of storing each one: the 300-bucket array or a queue of (second, count) pairs keeps memory bounded. For out-of-order hits, keep timestamps in a sorted structure and count a window with two binary searches. In practice you also cap how late a hit may arrive, so very old data can be dropped and memory stays bounded.

AceOffer·

MediumAbout 40 minFree

Helpful?Is this question helpful?

Back

Part 1 · Count hits in the last 300 seconds

Design a hit counter that reports how many hits arrived recently. Timestamps are integer seconds, and all calls (hits and queries) arrive with timestamp never decreasing. "The past 5 minutes" at time timestamp means hits at times t with timestamp - 300 < t <= timestamp: a hit at time 1 is counted at 300 but not at 301.

Implement HitCounter() with:

hit(timestamp) records one hit at timestamp. Several hits can share a timestamp.
get_hits(timestamp) returns how many hits are in the 300 seconds ending at timestamp, using the window rule above.

Clarify before coding5 questions ▸

Does the window include a hit exactly 300 seconds before the query?
Can several hits share the same timestamp, and can one call carry many hits?
Is the window always 5 minutes, or can callers ask for any length?
Do hits without a user still count toward the total?
Roughly how many hits per second should this handle, and is memory a concern?

Covers the whole problem: what candidates report interviewers adding on questions with this pattern, the mistakes to avoid, and where to go next.

What candidates report interviewers add

Handle very high traffic by grouping hits per second (buckets or a ring buffer) so memory does not grow with the number of hits.12 reports · Databricks, OpenAI, Uber · Part 4

Count hits per key as well as in total.6 reports · OpenAI, Uber · Part 2

Answer for windows other than 5 minutes, such as 10 minutes, 30 minutes or 24 hours.5 reports · Databricks · Part 3

Read time from the clock instead of a parameter, and mock the clock in unit tests.5 reports · Databricks

Make the counter safe when many threads record hits at once.2 reports · Databricks, Uber

Why practise this

Sliding window, two pointers, string matching shows up in 6.8% of the 1,447 coding interview reports we studied, at 10 companies. Find the best contiguous range, or match a pattern within a longer string.

Reported at: Harvey AI, Snowflake, Citadel, Amazon, Databricks, Roblox, Palantir, Anthropic, Waymo, xAI.

This is an original practice problem written by AceOffer to train the pattern. It is not a question any company asked.

Common mistakes5 ▸

Including a hit at exactly timestamp - 300. With this rule it is out of the window.
Throwing old hits away on each query in Part 1 and then being unable to answer a longer window in Part 3.
Counting hits with no user as a user named None.
Looping count times in Part 4, which turns one call with a count of a million into a million appends.
Using bisect_left, so hits at exactly the window edge land on the wrong side.

Where an interviewer could take it next3 ▸

Accept hits that arrive out of order, up to some lateness limit.
Bound memory by keeping only the largest window anyone may ask for.
Report the busiest 300-second window seen so far.

Frequently asked3 ▸

How do you count hits in the last 5 minutes?: Store each hit's timestamp in a queue in arrival order. When asked for the count at time T, remove timestamps from the front while they are at or before T minus 300 seconds, then return the queue length. Each timestamp enters and leaves once, so the work is amortized constant per call. This assumes timestamps arrive in increasing order; otherwise keep a sorted list and use binary search.
Should a hit counter use a queue or a fixed array of 300 buckets?: A queue stores one entry per hit, so memory grows with traffic in the window, but the code is simple. A fixed array of 300 buckets, indexed by timestamp modulo 300, stores a second and a count in each slot, so memory stays constant however many hits arrive. A query sums the slots whose stored second is still inside the window, which costs 300 steps per query.
How do you handle many hits per second or out-of-order timestamps in a hit counter?: For heavy traffic, group hits by second instead of storing each one: the 300-bucket array or a queue of (second, count) pairs keeps memory bounded. For out-of-order hits, keep timestamps in a sorted structure and count a window with two binary searches. In practice you also cap how late a hit may arrive, so very old data can be dropped and memory stays bounded.

Practise next

Rate Limiter · Rate limiting and time-window counts Log File Parser · Parsing structured text Lowest Common Manager (Org Chart) · Tree recursion and traversal

Preparing for a specific company? The company guides collect the questions candidates report, with every part and follow-up.

Python 3

Tests4 tests · not run yet

Run the part to execute this test.

Expected

Test code

c = HitCounter()
c.hit(1)
c.hit(2)
c.hit(3)
print(c.get_hits(4))
c.hit(300)
print(c.get_hits(300))
print(c.get_hits(301))
print(c.get_hits(600))

Design Hit Counter

Medium4 partsabout 40 minSliding window, two pointers, string matching Hash-map counting, grouping and joins Time-based state (expiry, TTL, snapshots)

Count the hits in the last 300 seconds, then per key, then over any window length, then at very high hit rates without storing one entry per hit.

Also known as: Hit counter, Count hits in the last 300 seconds

Why practise this

Reported at: Harvey AI, Snowflake, Citadel, Amazon, Databricks, Roblox, Palantir, Anthropic, Waymo, xAI.

This is an original practice problem written by AceOffer to train the pattern. It is not a question any company asked.

What candidates report interviewers add

Follow-ups candidates reported on questions with this pattern, in our words. Parts marked “from reports” below are built on them.

Handle very high traffic by grouping hits per second (buckets or a ring buffer) so memory does not grow with the number of hits.12 reports · Databricks, OpenAI, Uber · Part 4
Count hits per key as well as in total.6 reports · OpenAI, Uber · Part 2
Answer for windows other than 5 minutes, such as 10 minutes, 30 minutes or 24 hours.5 reports · Databricks · Part 3
Read time from the clock instead of a parameter, and mock the clock in unit tests.5 reports · Databricks
Make the counter safe when many threads record hits at once.2 reports · Databricks, Uber

Questions to ask before you code

Does the window include a hit exactly 300 seconds before the query?
Can several hits share the same timestamp, and can one call carry many hits?
Is the window always 5 minutes, or can callers ask for any length?
Do hits without a user still count toward the total?
Roughly how many hits per second should this handle, and is memory a concern?

Part 1: Count hits in the last 300 seconds

Implement HitCounter() with:

hit(timestamp) records one hit at timestamp. Several hits can share a timestamp.
get_hits(timestamp) returns how many hits are in the 300 seconds ending at timestamp, using the window rule above.

Part 2: Counts per keyfrom reports

Each hit can now name who sent it: hit(timestamp, user). A hit with user=None counts toward the total only.

get_hits(timestamp) keeps returning the total over all hits.
get_user_hits(user, timestamp) returns how many of that user's hits are in the 300 seconds ending at timestamp, or 0 for a user never seen.

Part 3: Any window lengthfrom reports

Callers now want more than the last 5 minutes: the last 10 minutes, the last hour, the last day. Both queries take an optional window in seconds (default 300):

get_hits(timestamp, window) counts hits with timestamp - window < t <= timestamp.
get_user_hits(user, timestamp, window) does the same for one user.

window is a positive integer and can be different on every call, so a structure that only remembers the last 300 seconds is no longer enough.

Part 4: Very high hit ratesfrom reports

Traffic is now bursty: hit(timestamp, user=None, count=1) records count hits at once, as if hit had been called count times. In production count can reach millions per second.

Storing one entry per hit no longer works at that rate. Make memory and the cost of hit grow with the number of distinct seconds that had hits, not with the number of hits, while every earlier query keeps giving the same answers. (The tests use counts small enough that a slow version still finishes in the browser, so check the design yourself.)

Open this page on a laptop or desktop to write and run your code against the tests in the browser.

Approach

Spoilers: try each part before reading its walkthrough.

Part 1: Count hits in the last 300 seconds

Because hits and queries arrive in time order, the hits you still care about always form a contiguous run at the recent end. A deque of timestamps fits this well: hit appends on the right, and get_hits first discards entries on the left that are at or before timestamp - 300, then returns the length. Every timestamp is appended once and removed once, so each call is amortized O(1), and memory is the number of hits in the current window. Repeated timestamps need no special case because each hit is its own entry. The boundary is the main trap: a hit exactly 300 seconds old is outside the window, so the discard test is <=, not <. A fixed array of 300 buckets is an alternative when there are many hits per second. The reference solution jumps ahead to the Part 3 structure, which answers this part too.

Part 2: Counts per key

Per-key counts reuse whatever structure Part 1 used, once per key. The reference keeps one series for the total and a dict from user name to that user's own series, and hit updates the total plus, when a user is given, that user's series. A hit with no user lands only in the total, which keeps it out of every per-user answer. get_user_hits returns 0 for an unknown user without creating an empty entry, so lookups never grow memory. Each query touches a single series, so its cost is the same as Part 1. The design point worth saying aloud is that the total is its own series rather than a sum over users: summing would be O(U) per query and would miss anonymous hits.

Part 3: Any window length

Once the window length changes per call, you cannot discard hits older than 300 seconds. The reference stores each series as two parallel lists: the distinct seconds that had hits, and a running total of hits up to and including each second. Because timestamps arrive in order, both lists stay sorted for free. The hits in (timestamp - window, timestamp] are the running total up to timestamp minus the running total up to timestamp - window, and each of those is one bisect_right on the seconds list. That is O(log s) per query for any window, including a whole day. The trade is that nothing is ever removed, so memory grows with the number of distinct seconds; capping the largest allowed window would let you trim the front.

Part 4: Very high hit rates

With counts in the millions per call, any design that stores one entry per hit breaks. The running-total series from Part 3 already avoids that: when a hit lands on the same second as the last entry, add increases that entry's running total instead of appending, and a new second appends a single entry. So memory is one entry per distinct second per series, whatever the traffic, and count costs nothing extra. This is the per-second aggregation that bucket and ring-buffer designs also use; a fixed ring of 300 slots would bound memory even further but could only answer 300-second windows. Calling hit(t, user, count=1) repeatedly gives exactly the same answers as one call with the summed count.

Hints

Part 1 hint

Keep timestamps in a deque. Before answering, discard leftmost entries that are at or before timestamp - 300; what remains is the answer.

Part 2 hint

Keep one structure for the total and a dict from user to a structure of the same kind, and update both on every hit.

Part 3 hint

Keep, per series, the distinct seconds and a running total of hits up to each one. A window count is then total(up to timestamp) minus total(up to timestamp - window), each found with bisect_right.

Part 4 hint

Merge hits that land on the same second into one entry by adding to its running total, so a count of a million costs one entry, not a million.

Common mistakes

Including a hit at exactly timestamp - 300. With this rule it is out of the window.
Throwing old hits away on each query in Part 1 and then being unable to answer a longer window in Part 3.
Counting hits with no user as a user named None.
Looping count times in Part 4, which turns one call with a count of a million into a million appends.
Using bisect_left, so hits at exactly the window edge land on the wrong side.

Where an interviewer could take it next

Accept hits that arrive out of order, up to some lateness limit.
Bound memory by keeping only the largest window anyone may ask for.
Report the busiest 300-second window seen so far.

Complexity

With per-second running totals, hit is O(1) and each query is O(log s) for s distinct seconds in that series. Memory is O(s) for the total plus each user's series, independent of how many hits arrive per second. A plain deque answers Part 1 in amortized O(1) but stores one entry per hit.

Frequently asked

How do you count hits in the last 5 minutes?: Store each hit's timestamp in a queue in arrival order. When asked for the count at time T, remove timestamps from the front while they are at or before T minus 300 seconds, then return the queue length. Each timestamp enters and leaves once, so the work is amortized constant per call. This assumes timestamps arrive in increasing order; otherwise keep a sorted list and use binary search.
Should a hit counter use a queue or a fixed array of 300 buckets?: A queue stores one entry per hit, so memory grows with traffic in the window, but the code is simple. A fixed array of 300 buckets, indexed by timestamp modulo 300, stores a second and a count in each slot, so memory stays constant however many hits arrive. A query sums the slots whose stored second is still inside the window, which costs 300 steps per query.
How do you handle many hits per second or out-of-order timestamps in a hit counter?: For heavy traffic, group hits by second instead of storing each one: the 300-bucket array or a queue of (second, count) pairs keeps memory bounded. For out-of-order hits, keep timestamps in a sorted structure and count a window with two binary searches. In practice you also cap how late a hit may arrive, so very old data can be dropped and memory stays bounded.

Practise next

Rate Limiter

Rate limiting and time-window counts

Log File Parser

Parsing structured text

Lowest Common Manager (Org Chart)

Tree recursion and traversal

See what candidates report at each company

The company guides collect the questions candidates report, with every part, the follow-ups interviewers added, and how often each one comes up.

Browse the interview guides