Implement recent-requests counter

Q: Implement recent-requests counter

This question evaluates a candidate's ability to design efficient in-memory data structures and manage time-windowed event counting, testing algorithmic reasoning and performance optimization for high-throughput services.

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 an in-memory component for a web service that needs to track how many requests ("hits") it has received in the last 5 minutes.

Implement a class that supports two operations:

void hit(int timestamp)
Records a hit at time timestamp (in seconds).
You may assume:
- Timestamps are given in strictly increasing order across all calls.
- There may be multiple hits at the same timestamp .
int getHits(int timestamp)
Returns the number of hits that occurred in the past 5 minutes (i.e., in the inclusive interval [timestamp - 299, timestamp] ), where timestamp is also specified in seconds and is >= any previous timestamp seen.

Additional details and constraints:

You only need to store data for the last 5 minutes at any point in time; older data should be discarded or ignored.
Optimize for many calls to hit and getHits per second.
Aim for better than O(n) per query, where n is the total number of hits ever seen.

Define the class interface and implement the methods hit and getHits.

Implement recent-requests counter

Overview

Comments (0)