Extend counter to per-client rate limiting
Company: Roblox
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are extending the recent-requests counter to support **per-client** rate limiting.
Each request now includes a `clientId` identifying the caller. You must track hits separately for each client, still over the last 5 minutes.
Design and implement a class that supports the following operations:
- `void hit(String clientId, int timestamp)`
Records a hit from `clientId` at time `timestamp` (in seconds).
Assumptions:
- Timestamps are given in **strictly increasing** order across all calls.
- There may be multiple hits from the same or different clients at the same `timestamp`.
- `int getHits(String clientId, int timestamp)`
Returns the number of hits made by this specific `clientId` in the **past 5 minutes**, i.e., in the inclusive interval `[timestamp - 299, timestamp]`.
Additional requirements and constraints:
- The system may have **many distinct clients**; most of them will be idle at any given time.
- You only need to keep data that is at most 5 minutes old per client; older hits for that client should be discarded or ignored.
- Aim for time complexity close to O(1) **amortized** per operation and space proportional to the number of hits in the last 5 minutes.
- Your design should be efficient both when there is a single very active client and when there are many moderately active clients.
Define the class interface and implement the methods `hit` and `getHits`.
Quick Answer: This question evaluates competency in designing per-client, time-windowed rate limiting using efficient data structures for time-based eviction and counting within the Coding & Algorithms domain.
Process operations ["hit", clientId, timestamp] and ["get", clientId, timestamp]. get returns hits for that client in the inclusive last-5-minute window [timestamp-299, timestamp].
Constraints
- Timestamps are nondecreasing in the operations list
Examples
Input: ([['hit', 'a', 1], ['hit', 'a', 2], ['get', 'a', 300], ['get', 'b', 300]],)
Expected Output: [2, 0]
Input: ([['hit', 'a', 1], ['hit', 'a', 1], ['get', 'a', 1], ['get', 'a', 301]],)
Expected Output: [2, 0]
Hints
- Use one deque per active client and discard old timestamps lazily.