Hit Counter: Tracking Website Traffic in Real-Time

Imagine you're building a website analytics dashboard. You need a way to track how many times a specific page or feature is accessed over time. This challenge asks you to implement a "hit counter" – a data structure that records timestamps of events (hits) and allows you to efficiently query the number of hits within a given time window. This is a common problem in web analytics, load balancing, and rate limiting.

Problem Description

You need to implement a HitCounter class in TypeScript. This class should have two primary methods:

• hit(timestamp: number): Records a hit event with the given timestamp (in seconds).
• getHits(timestamp: number): Returns the number of hits that occurred within the last 300 seconds (5 minutes) of the given timestamp.

The timestamp parameter represents the time in seconds since the Unix epoch. The HitCounter should efficiently store and retrieve hit data to provide accurate counts within the specified time window.

Key Requirements:

• The HitCounter class must be implemented in TypeScript.
• The hit method should record the timestamp of each hit.
• The getHits method should return the correct count of hits within the last 300 seconds.
• The implementation should be reasonably efficient, considering that the counter might receive a large number of hits.
• The class should be testable using Jest.

Expected Behavior:

The getHits method should accurately count hits within the 300-second window leading up to and including the provided timestamp. For example, if getHits is called with a timestamp of 300, it should count all hits recorded in the interval [0, 300].

Edge Cases to Consider:

• What happens when getHits is called before any hits have been recorded?
• What happens when getHits is called with a timestamp that is far in the future relative to the recorded hits?
• How should the counter handle a large number of hits? Consider memory usage and performance.
• What happens if the timestamp is negative? (Assume timestamps are always non-negative for this problem).

Examples

Example 1:

Input:
hit(1)
hit(2)
getHits(3)
Output:
2
Explanation:
The hits at timestamps 1 and 2 fall within the 300-second window leading up to timestamp 3 (i.e., [ -299, 3 ]).

Example 2:

Input:
hit(1)
hit(2)
hit(3)
hit(4)
hit(5)
getHits(6)
Output:
5
Explanation:
All five hits fall within the 300-second window leading up to timestamp 6 (i.e., [ -299, 6 ]).

Example 3:

Input:
hit(300)
getHits(301)
Output:
1
Explanation:
Only the hit at timestamp 300 falls within the 300-second window leading up to timestamp 301 (i.e., [ 1, 301 ]).

Constraints

• Timestamps are non-negative integers representing seconds since the Unix epoch.
• The time window for counting hits is 300 seconds.
• The number of hits can be potentially very large (e.g., millions or billions). Consider the efficiency of your data structure.
• The hit method will be called frequently.
• The getHits method will be called less frequently than the hit method.

Notes

Consider using a data structure that allows for efficient storage and retrieval of timestamps within a specific range. A simple array might work for small numbers of hits, but it could become inefficient for large datasets. Think about how you can optimize the getHits method to avoid iterating through all recorded hits every time it's called. You might consider using a more specialized data structure like a sorted list or a hash map. Remember to write comprehensive Jest tests to ensure your implementation is correct and handles edge cases properly.