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.

What difficulty level is this interview question?

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

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Roblox during technical interviews.

Implement recent-requests counter | Roblox Interview Question

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.

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.