Implement a rate-limited hit counter

Q: Implement a rate-limited hit counter

This question evaluates a candidate's understanding of designing efficient time-windowed data structures and algorithmic analysis, including space-time trade-offs and amortized complexity.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are designing a hit counter that records the number of hits received in the past 5 minutes.

Implement a class HitCounter with the following methods:

void hit(int timestamp) : Records a hit at the given timestamp (in seconds). The timestamp is given in seconds granularity and is strictly increasing across all calls.
int getHits(int timestamp) : Returns the number of hits received in the past 5 minutes (i.e., the past 300 seconds) including the current second, at the given timestamp .

Constraints:

1 <= timestamp <= 10^9 .
Methods will be called in non-decreasing order of timestamp .
The number of calls to both hit and getHits is up to 10^5.

Describe the data structures and algorithms you would use to implement HitCounter so that both operations are efficient in time and memory. Do not write code; just specify the design and complexity.

Implement a rate-limited hit counter

Overview

Comments (0)