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.