Design a hit counter that reports how many hits were received during a configurable time window.

The constructor provides the window duration in seconds. For example, a counter may track hits from the previous 10, 200 or 300 seconds.

Class

HitCounter

Constructor

HitCounter(int windowSizeSeconds)

Parameters

• windowSizeSeconds: The duration of the rolling time window in seconds.

Initially, no hits have been recorded.

Methods

hit

void hit(int timestamp)

Parameters

• timestamp: The time of the hit, measured in seconds.

Record one hit at the specified timestamp. Multiple hits may be recorded at the same timestamp.

getHits

int getHits(int timestamp)

Parameters

• timestamp: The time at which the hit count is requested, measured in seconds.

Returns

Return the number of recorded hits that belong to the configured time window ending at timestamp.

A hit recorded at hitTimestamp is included when timestamp - hitTimestamp < windowSizeSeconds. A hit that is exactly windowSizeSeconds old is excluded.

Rules

• Timestamps use seconds granularity.
• The earliest possible timestamp is 1.
• All method calls are made in non-decreasing timestamp order.
• Several hits may occur at the same timestamp.
• The configured window duration does not change after construction.

Constraints

• 1 ≤ windowSizeSeconds
• 1 ≤ timestamp
• The number of active hits always fits in a 32-bit signed integer.

Examples

Example 1

HitCounter(windowSizeSeconds = 10)

After hit(timestamp = 4) and two calls to hit(timestamp = 8), getHits(timestamp = 9) returns 3.

getHits(timestamp = 14) returns 2. The hit recorded at timestamp 4 is exactly 10 seconds old and is excluded.

Example 2

HitCounter(windowSizeSeconds = 200)

After hit(timestamp = 50) and hit(timestamp = 249), getHits(timestamp = 249) returns 2.

getHits(timestamp = 250) returns 1. The hit recorded at timestamp 50 is exactly 200 seconds old.

Example 3

HitCounter(windowSizeSeconds = 300)

After three calls to hit(timestamp = 900), getHits(timestamp = 1,199) returns 3.

getHits(timestamp = 1,200) returns 0 because all three hits are exactly 300 seconds old.

Follow-up

What if the number of hits received during a single second could be very large? Does your design scale?