Implement recent-requests counter
Company: Roblox
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
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`.
Quick Answer: 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.
Process hit/getHits operations for the inclusive interval [timestamp-299,timestamp]. Return outputs for getHits and None for hit.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([['hit',1], ['hit',2], ['getHits',300], ['getHits',301]],)
Expected Output: [None, None, 2, 1]
Explanation: Window moves.
Input: ([['getHits',1]],)
Expected Output: [0]
Explanation: No hits.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.