Implement recent-requests counter

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.