Katkat
Back

Implement recent-requests counter

RobloxMachine Learning Engineer · Technical Screen
EasyMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

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.