Extend counter to per-client rate limiting

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.

Per-Client Hit Counter

Examples

Example 1

Input: ([['hit', 'a', 1], ['hit', 'a', 2], ['get', 'a', 300], ['get', 'b', 300]],)
Output: [2, 0]

Example 2

Input: ([['hit', 'a', 1], ['hit', 'a', 1], ['get', 'a', 1], ['get', 'a', 301]],)
Output: [2, 0]

Hints

1. Use one deque per active client and discard old timestamps lazily.