Quick Overview

Implement a five-minute hit counter with ordered timestamped operations, repeated hits, and an explicit 300-second expiration boundary.

Count Hits in the Past Five Minutes

Company: Vercel

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a hit counter that reports how many hits occurred during the past five minutes. For this exercise, timestamps are integer seconds, operations arrive in nondecreasing timestamp order, and a query at time `t` counts hits with timestamps in `(t - 300, t]`. These boundary and ordering conventions make the five-minute task deterministic. ### Function Signature `count_recent_hits(operations: list[list[int]]) -> list[int]` ### Input Each operation is a pair `[kind, timestamp]`: - `kind = 0`: record one hit at `timestamp`. - `kind = 1`: query the hit count at `timestamp`. Only hits recorded by earlier operations are visible to a query. Several hits and queries may share the same timestamp; their input order still matters. ### Output Return one integer for each query, in query order. A hit exactly 300 seconds before a query is excluded. If there are no queries, return an empty list. ### Constraints - `0 <= len(operations) <= 200000`. - `0 <= timestamp <= 1000000000`. - Timestamps are nondecreasing across all operations. - Each recorded hit counts once. No other event types occur. ### Examples Input: `operations = [[0,1],[0,2],[0,300],[1,300],[1,301]]` Output: `[3,2]` At time 300, the hit at time 1 is included. At time 301, that hit lies exactly at the excluded lower boundary. Input: `operations = [[1,5],[0,5],[1,5],[0,5],[1,5]]` Output: `[0,1,2]` Input: `operations = []` Output: `[]`

Overview: Implement a five-minute hit counter with ordered timestamped operations, repeated hits, and an explicit 300-second expiration boundary.

You are given a replay log of hit-counter operations and must report, for each query, how many hits occurred during the past five minutes (300 seconds). Timestamps are integer seconds. Each element of `operations` is a pair `[kind, timestamp]`: - `kind = 0`: record one hit at `timestamp`. - `kind = 1`: query the hit count at `timestamp`. Process the operations in the order they are given. A query at time `t` counts every hit whose timestamp lies in the half-open window `(t - 300, t]`. A hit recorded exactly 300 seconds before a query is excluded; a hit recorded 299 seconds before it is included. Only hits recorded by earlier operations in the list are visible to a query. Several hits and queries may share the same timestamp, and in that situation their input order still decides what each query sees. Each recorded hit counts once, and no other event types occur. Return a list holding one integer per query, in query order. If there are no queries, return an empty list. Every returned count is at most the number of operations, which is at most 200000, so all values fit comfortably in a signed 32-bit integer (Java `int`, C++ `int`). ### Example 1 Input: `operations = [[0, 1], [0, 2], [0, 300], [1, 300], [1, 301]]` Output: `[3, 2]` At time 300 the window is `(0, 300]`, so the hits at 1, 2 and 300 all count. At time 301 the window is `(1, 301]`, so the hit at time 1 lies exactly on the excluded lower boundary and two hits remain. ### Example 2 Input: `operations = [[1, 5], [0, 5], [1, 5], [0, 5], [1, 5]]` Output: `[0, 1, 2]` Every operation shares timestamp 5, so only input order matters: the first query sees no hits, the second sees one, and the third sees two.

Constraints

  • 0 <= len(operations) <= 200000.
  • Each operation is a pair [kind, timestamp] with kind in {0, 1}: kind = 0 records one hit at timestamp, kind = 1 queries the hit count at timestamp.
  • 0 <= timestamp <= 1000000000.
  • Timestamps are nondecreasing across all operations.
  • Each recorded hit counts once. No other event types occur.
  • Only hits recorded by earlier operations are visible to a query; hits and queries sharing a timestamp are processed in input order.
  • A query at time t counts hits with timestamps in (t - 300, t]; a hit exactly 300 seconds before the query is excluded.
  • Each returned count is at most 200000, so every value fits in a signed 32-bit integer.

Examples

Input: ([],)

Expected Output: []

Explanation: Minimum valid input: no operations at all, so there are no queries and the result is empty.

Input: ([[1, 0]],)

Expected Output: [0]

Explanation: Single query at time 0 with no prior hits; the window (-300, 0] holds nothing.

Hints

  1. The operations are a replay: walk the list once in order, and remember that a query can only see hits that appeared earlier in the list, even when they share the same timestamp.
  2. Timestamps never decrease, so a hit that is already too old for one query is also too old for every query that comes after it.
  3. Re-read the boundary rule before you write the comparison: a hit exactly 300 seconds before the query is outside the window, while one 299 seconds before is inside.

Loading coding console...

Show the approach

Approach

Algorithm. Replay the operations once, in order, keeping an append-only buffer hits of recorded hit timestamps together with an index head marking the first hit that has not yet expired. A kind = 0 operation appends its timestamp. A kind = 1 operation at time t computes cutoff = t - 300 and advances head past every buffered hit whose timestamp is <= cutoff; the answer is then len(hits) - head, which is appended to the output list.

Why the buffer is sorted. The statement guarantees timestamps are nondecreasing across all operations, so hits are appended in nondecreasing order and hits is always sorted. That makes the expired hits exactly a prefix of the buffer, so a single forward-moving index is enough.

Invariant. Immediately after answering a query at time t, the slice hits[head:] is exactly the set of hits recorded by earlier operations whose timestamp lies in (t - 300, t]. Every hit already recorded satisfies timestamp <= t (timestamps never decrease), so the upper end of the window never removes anything; only the lower end does, and head is advanced precisely past the entries <= t - 300. head never needs to move backwards because cutoff is nondecreasing across queries.

Boundary. The window is half-open: the eviction test is hits[head] <= cutoff, so a hit exactly 300 seconds before the query is dropped and a hit 299 seconds before is kept, matching the stated rule. Using < there would wrongly include the excluded boundary hit.

Ordering. Because the loop processes operations strictly in input order and only appends to hits when it reaches a hit operation, a query sees exactly the hits from earlier list positions, which resolves ties when hits and queries share a timestamp.

Edge cases. An empty operations list produces an empty result. Operations containing no queries produce an empty result. Queries before any hit report 0. A query at timestamp 0 has a negative cutoff, which is handled naturally since no buffered timestamp can be negative. Long gaps between operations simply advance head to the end of the buffer, yielding 0. Buffered hits are never cleared by a query, so later queries still see hits that remain inside their own windows.

Complexity. head only ever increases and is bounded by the number of hits, so the eviction work is amortized constant per operation; the whole replay is linear in the number of operations. Counts are bounded by 200000, so no 64-bit arithmetic is required.

Time complexity:
O(n), where n is the number of operations; each hit is appended once and skipped past at most once, so window eviction is amortized O(1) per operation.
Space complexity:
O(n) for the buffer of recorded hit timestamps plus the output list of query answers.