How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Design a rolling hit counter API | Google Coding Question

Design a rolling hit counter API

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

### Rolling hit counter (time/space optimized) Design a data structure that records events (“hits”) and can return how many hits happened in the most recent **300 seconds**. Implement two operations: - `hit(t)`: record a hit at integer timestamp `t` (seconds). - `getHits(t)`: return the number of hits with timestamps in the inclusive range **[t-299, t]**. #### Assumptions / requirements - Timestamps are non-decreasing across calls. - Multiple hits may occur at the same timestamp. - You should optimize for time and space (avoid storing every hit individually if many occur at the same second). #### Output Return correct counts for each `getHits` query. #### Complexity discussion Be prepared to justify the time/space complexity of your approach and how it behaves under very high hit volume.

Quick Answer: This question evaluates proficiency with data structures for time-window aggregation and understanding of time/space trade-offs when counting events within a rolling interval.

Design a data structure that records events ("hits") and can answer how many hits happened in the most recent **300 seconds**. Implement two operations: - `hit(t)`: record a hit at integer timestamp `t` (seconds). - `getHits(t)`: return the number of hits whose timestamps lie in the inclusive range **[t - 299, t]** (i.e. the last 300 seconds, including `t`). **Assumptions / requirements** - Timestamps are non-decreasing across calls. - Multiple hits may occur at the same timestamp. - Optimize for time and space: do **not** store every hit individually when many occur at the same second — coalesce hits per second into a bucket and evict buckets that fall out of the 300-second window. **Driver contract (what you implement)** You are given a list `operations`, where each element is a 2-element list `[name, t]`: - `["hit", t]` records a hit at timestamp `t`. - `["getHits", t]` queries the count for the window `[t - 299, t]`. Return a list containing the result of each `getHits` query, in order. (`hit` operations produce no output.) **Example** ``` operations = [["hit",1],["hit",2],["hit",3],["getHits",4],["hit",300],["getHits",300],["getHits",301]] -> [3, 4, 3] ``` At `getHits(4)` the window is `[-295, 4]` and contains hits at 1, 2, 3 → 3. After `hit(300)`, `getHits(300)` window is `[1, 300]` → all 4 hits → 4. `getHits(301)` window is `[2, 301]` drops the hit at t=1 → 3.

Constraints

1 <= number of operations <= 10^5
0 <= t <= 10^9
Timestamps are non-decreasing across calls (each operation's t is >= the previous operation's t).
Window length is fixed at 300 seconds: getHits(t) counts timestamps in [t - 299, t].
Multiple hits may share the same timestamp.

Examples

Input: [["hit", 1], ["hit", 2], ["hit", 3], ["getHits", 4], ["hit", 300], ["getHits", 300], ["getHits", 301]]

Expected Output: [3, 4, 3]

Explanation: getHits(4) window [-295,4] sees hits at 1,2,3 -> 3. After hit(300), getHits(300) window [1,300] sees all 4 -> 4. getHits(301) window [2,301] drops the hit at t=1 -> 3.

Input: [["getHits", 1]]

Expected Output: [0]

Explanation: No hits recorded yet, so the query returns 0.

Input: [["hit", 1], ["hit", 1], ["hit", 1], ["getHits", 1], ["getHits", 300], ["getHits", 301]]

Expected Output: [3, 3, 0]

Explanation: Three hits at the same second t=1 are coalesced into one bucket of count 3. getHits(1) and getHits(300) both include t=1 -> 3. getHits(301) window [2,301] excludes t=1 -> 0.

Input: [["hit", 10], ["hit", 10], ["hit", 10], ["hit", 10], ["getHits", 10], ["hit", 50], ["getHits", 309], ["getHits", 310]]

Expected Output: [4, 5, 1]

Explanation: Four hits at t=10 (one bucket, count 4) plus one at t=50. getHits(10) -> 4. getHits(309) window [10,309] sees both buckets -> 5. getHits(310) window [11,310] drops t=10 -> only the t=50 hit -> 1.

Input: []

Expected Output: []

Explanation: Empty operation list yields no query results.

Input: [["hit", 1000000], ["getHits", 1000000], ["getHits", 1000299], ["getHits", 1000300]]

Expected Output: [1, 1, 0]

Explanation: Large timestamp boundary check. The hit at t=1000000 is in-window for getHits at 1000000 and 1000299 (window [1000000,1000299]) but falls out exactly at getHits(1000300) whose window is [1000001,1000300].

Hints

Naively storing every hit timestamp in a queue works but wastes space when many hits share a second. Bucket hits by second instead: keep (timestamp, count) pairs.
Keep a running total of hits currently inside the window. On every operation, first evict from the front any bucket whose timestamp is <= t - 300, subtracting its count from the running total.
Because timestamps are non-decreasing, the buckets stay sorted by time, so a deque (pop from front to evict, push/increment at the back) gives amortized O(1) per operation.

Quick Overview

This question evaluates proficiency with data structures for time-window aggregation and understanding of time/space trade-offs when counting events within a rolling interval.