Design Hit Counter - Practice Coding Problems

Design Hit Counter - Problem

Array Binary Search Design Queue Data Stream Medium

Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds).

Your system should accept a timestamp parameter (in seconds granularity), and you may assume that calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing). Several hits may arrive roughly at the same time.

Implement the HitCounter class:

HitCounter() Initializes the object of the hit counter system.
void hit(int timestamp) Records a hit that happened at timestamp (in seconds). Several hits may happen at the same timestamp.
int getHits(int timestamp) Returns the number of hits in the past 5 minutes from timestamp (i.e., the past 300 seconds).

Input & Output

Example 1 — Basic Hit Counter Usage

$ Input: operations = ["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"], values = [[], [1], [2], [3], [4], [300], [300], [301]]

› Output: [null, null, null, null, 3, null, 4, 3]

💡 Note: Initialize counter, record hits at times 1,2,3. At time 4, all 3 hits are within 300 seconds. Hit at time 300. At time 300, all 4 hits are recent. At time 301, hit at time 1 is now 300+ seconds old, so only 3 hits remain.

Example 2 — Multiple Hits Same Time

$ Input: operations = ["HitCounter", "hit", "hit", "getHits"], values = [[], [1], [1], [2]]

› Output: [null, null, null, 2]

💡 Note: Two hits at the same timestamp (time 1). getHits(2) counts both hits since they occurred within the past 300 seconds.

Example 3 — Edge Case Window Boundary

$ Input: operations = ["HitCounter", "hit", "getHits", "getHits"], values = [[], [1], [300], [301]]

› Output: [null, null, 1, 0]

💡 Note: Hit at time 1. At time 300, the hit is exactly 299 seconds ago (within window). At time 301, the hit is exactly 300 seconds ago (outside window).

Constraints

1 ≤ timestamp ≤ 2 * 10⁹
All the calls are being made to the system in chronological order
At most 300 calls will be made to hit and getHits

Visualization

Tap to expand

Understanding the Visualization

Record Hits

Store timestamps of incoming hits

Sliding Window

Maintain only hits within past 300 seconds

Count Valid

Return number of recent hits

Key Takeaway

🎯 Key Insight: Use sliding window to automatically expire old data and maintain only recent hits

Asked in

G Google 25 a Amazon 20 f Facebook 18 M Microsoft 15

The key insight is to maintain only recent hits within a 5-minute sliding window. The sliding window with queue approach provides optimal balance: O(n) time for getHits with automatic cleanup, and O(n) space for recent hits only. For high-frequency scenarios, the bucket array approach offers O(1) operations with fixed O(300) space.

Common Approaches

Approach	Time	Space	Notes
✓ ArrayList Storage	O(n)	O(n)	Store all hits in a list and filter by time window
Sliding Window with Queue	O(n)	O(n)	Use a queue to maintain only recent hits within the 5-minute window
Bucket Array (Fixed Window)	O(1)	O(1)	Use fixed-size circular array with 300 buckets for each second

ArrayList Storage — Algorithm Steps

Store each hit timestamp in a list
For getHits, iterate through all timestamps
Count timestamps >= (current_time - 300)

Visualization

Tap to expand

Step-by-Step Walkthrough

Store Hits

Add each timestamp to the list

Scan All

For getHits, check every stored timestamp

Count Valid

Count timestamps within 300 seconds

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* hits;
    int size;
    int capacity;
} HitCounter;

HitCounter* hitCounterCreate() {
    HitCounter* counter = malloc(sizeof(HitCounter));
    counter->hits = malloc(1000 * sizeof(int));
    counter->size = 0;
    counter->capacity = 1000;
    return counter;
}

void hitCounterHit(HitCounter* obj, int timestamp) {
    if (obj->size >= obj->capacity) {
        obj->capacity *= 2;
        obj->hits = realloc(obj->hits, obj->capacity * sizeof(int));
    }
    obj->hits[obj->size++] = timestamp;
}

int hitCounterGetHits(HitCounter* obj, int timestamp) {
    int count = 0;
    for (int i = 0; i < obj->size; i++) {
        if (obj->hits[i] > timestamp - 300) {
            count++;
        }
    }
    return count;
}

int main() {
    // Simplified implementation for C
    HitCounter* counter = hitCounterCreate();
    
    // Sample execution
    hitCounterHit(counter, 1);
    hitCounterHit(counter, 2);
    hitCounterHit(counter, 3);
    printf("[null,null,null,null,%d,%d,%d]\n", 
           hitCounterGetHits(counter, 4),
           hitCounterGetHits(counter, 300),
           hitCounterGetHits(counter, 301));
    
    free(counter->hits);
    free(counter);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

getHits() scans all n stored timestamps

✓ Linear Growth

Space Complexity

O(n)

Stores all n hit timestamps indefinitely

⚡ Linearithmic Space

35.0K Views

High Frequency

~25 min Avg. Time

980 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

ArrayList Storage — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler