Implement a Hit Counter in TypeScript with Jest Tests

This challenge requires you to build a robust hit counter system that can track the number of hits received within a specified time window. This is a common requirement for rate limiting, analytics, and performance monitoring in web applications. You will implement this system in TypeScript and write comprehensive unit tests using Jest to ensure its correctness and reliability.

Problem Description

You need to design and implement a HitCounter class in TypeScript. This class should be capable of:

Recording Hits: Accepting timestamps for incoming requests or events.
Counting Hits within a Window: Providing a method to retrieve the total number of hits that occurred within a specified past time duration.

The HitCounter should efficiently handle a large volume of hits and queries.

Key Requirements:

record(timestamp: number): A method to record a hit at a given timestamp. Timestamps are assumed to be in seconds and monotonically increasing.
getHits(timestamp: number, windowInSeconds: number): A method that returns the number of hits recorded between timestamp - windowInSeconds + 1 and timestamp (inclusive).
Efficiency: The solution should be efficient, especially for getHits, as it might be called frequently.
Clear State Management: The internal state of the hit counter should be managed correctly.

Expected Behavior:

When record is called, the timestamp should be stored.
When getHits is called, it should only count timestamps that fall within the specified window.
If no hits have been recorded, getHits should return 0.
If the windowInSeconds is 0 or negative, getHits should consider only the exact timestamp provided if it exists, or 0 otherwise.

Edge Cases to Consider:

Recording hits at the same timestamp multiple times.
Querying for a window that extends beyond recorded hits.
Querying for a window that ends before any hits were recorded.
The impact of very large numbers of hits and frequent queries.

Examples

Example 1:

Input:
const counter = new HitCounter();
counter.record(1);
counter.record(2);
counter.record(3);
counter.record(3); // Duplicate timestamp

Output:
counter.getHits(4, 3); // Expected: 3

Explanation: At timestamp 4, we want to know the hits in the last 3 seconds. This includes timestamps 2, 3, and 4. The recorded hits are at timestamps 1, 2, 3, and 3. The hits within the window [4-3+1, 4] = [2, 4] are at timestamps 2, 3, and 3. Thus, the count is 3.

Example 2:

Input:
const counter = new HitCounter();
counter.record(1);
counter.record(10);
counter.record(20);

Output:
counter.getHits(15, 10); // Expected: 1
counter.getHits(25, 5); // Expected: 1
counter.getHits(25, 10); // Expected: 2

Explanation:

getHits(15, 10): Window is [15-10+1, 15] = [6, 15]. The only hit within this window is at timestamp 10. Count: 1.
getHits(25, 5): Window is [25-5+1, 25] = [21, 25]. No hits within this window. Count: 0. Wait, the problem statement says inclusive. If the window is 5 seconds, and we are at timestamp 25, we want to count hits from 25-5+1 = 21 up to 25. None exist.
Let's re-evaluate the second getHits call. If the windowInSeconds is 5, and the current timestamp is 25, we are interested in the interval [timestamp - windowInSeconds + 1, timestamp]. So, [25 - 5 + 1, 25] which is [21, 25]. No hits fall in this range.

Let's re-interpret the second query and provide a better example for clarity.

Example 2 (Revised):

Input:
const counter = new HitCounter();
counter.record(1);
counter.record(10);
counter.record(20);

Output:
counter.getHits(15, 10); // Expected: 1 (hit at timestamp 10 is in [6, 15])
counter.getHits(23, 5);  // Expected: 1 (hit at timestamp 20 is in [19, 23])
counter.getHits(25, 10); // Expected: 2 (hits at timestamps 10 and 20 are in [16, 25])

Explanation:

getHits(15, 10): Window is [15 - 10 + 1, 15] which is [6, 15]. The hit at timestamp 10 falls within this range. Count: 1.
getHits(23, 5): Window is [23 - 5 + 1, 23] which is [19, 23]. The hit at timestamp 20 falls within this range. Count: 1.
getHits(25, 10): Window is [25 - 10 + 1, 25] which is [16, 25]. The hits at timestamps 20 fall within this range. Count: 1.

Ah, another clarification needed: The prompt says "monotonically increasing" for timestamps. This implies that counter.record(5); counter.record(3); is not a valid sequence. However, the user could call getHits with a timestamp earlier than the latest recorded hit if they are looking at historical data. Let's ensure the getHits window logic is clear.

Let's assume the definition of the window is [timestamp - windowInSeconds + 1, timestamp].

Example 3:

Input:
const counter = new HitCounter();
counter.record(1);
counter.record(2);
counter.record(3);

Output:
counter.getHits(2, 1);  // Expected: 1 (hit at timestamp 2 is in [2, 2])
counter.getHits(3, 2);  // Expected: 2 (hits at timestamps 2, 3 are in [2, 3])
counter.getHits(1, 1);  // Expected: 1 (hit at timestamp 1 is in [1, 1])
counter.getHits(0, 5);  // Expected: 0 (no hits in [-4, 0])
counter.getHits(5, 2);  // Expected: 0 (no hits in [4, 5])

Explanation: Demonstrates various window sizes and their impact on hit counts, including cases where no hits fall within the window.

Constraints

The number of calls to record can be up to $10^6$.
The number of calls to getHits can be up to $10^6$.
Timestamps are integers and will be non-negative.
windowInSeconds will be a non-negative integer.
Timestamps passed to record will be monotonically increasing.
Timestamps passed to getHits can be any valid timestamp value.

Notes

Consider data structures that allow for efficient insertion and retrieval of hits within a time range.
The definition of the time window is critical: [timestamp - windowInSeconds + 1, timestamp].
Think about how to handle old, irrelevant hits to keep memory usage in check if this were a long-running system (though for this challenge, memory optimization beyond reasonable efficiency is not the primary focus).
Your solution should be written in TypeScript.
You will need to create a Jest test file (.test.ts) to thoroughly test your HitCounter class. Cover the examples provided, as well as edge cases like empty counters, zero windows, and large numbers of hits.

Implement a Hit Counter in TypeScript with Jest Tests

Problem Description

You need to design and implement a HitCounter class in TypeScript. This class should be capable of:

Recording Hits: Accepting timestamps for incoming requests or events.
Counting Hits within a Window: Providing a method to retrieve the total number of hits that occurred within a specified past time duration.

The HitCounter should efficiently handle a large volume of hits and queries.

Key Requirements:

record(timestamp: number): A method to record a hit at a given timestamp. Timestamps are assumed to be in seconds and monotonically increasing.
getHits(timestamp: number, windowInSeconds: number): A method that returns the number of hits recorded between timestamp - windowInSeconds + 1 and timestamp (inclusive).
Efficiency: The solution should be efficient, especially for getHits, as it might be called frequently.
Clear State Management: The internal state of the hit counter should be managed correctly.

Expected Behavior:

When record is called, the timestamp should be stored.
When getHits is called, it should only count timestamps that fall within the specified window.
If no hits have been recorded, getHits should return 0.
If the windowInSeconds is 0 or negative, getHits should consider only the exact timestamp provided if it exists, or 0 otherwise.

Edge Cases to Consider:

Recording hits at the same timestamp multiple times.
Querying for a window that extends beyond recorded hits.
Querying for a window that ends before any hits were recorded.
The impact of very large numbers of hits and frequent queries.

Examples

Example 1:

Input:
const counter = new HitCounter();
counter.record(1);
counter.record(2);
counter.record(3);
counter.record(3); // Duplicate timestamp

Output:
counter.getHits(4, 3); // Expected: 3

Example 2:

Input:
const counter = new HitCounter();
counter.record(1);
counter.record(10);
counter.record(20);

Output:
counter.getHits(15, 10); // Expected: 1
counter.getHits(25, 5); // Expected: 1
counter.getHits(25, 10); // Expected: 2

Explanation:

getHits(15, 10): Window is [15-10+1, 15] = [6, 15]. The only hit within this window is at timestamp 10. Count: 1.
getHits(25, 5): Window is [25-5+1, 25] = [21, 25]. No hits within this window. Count: 0. Wait, the problem statement says inclusive. If the window is 5 seconds, and we are at timestamp 25, we want to count hits from 25-5+1 = 21 up to 25. None exist.
Let's re-evaluate the second getHits call. If the windowInSeconds is 5, and the current timestamp is 25, we are interested in the interval [timestamp - windowInSeconds + 1, timestamp]. So, [25 - 5 + 1, 25] which is [21, 25]. No hits fall in this range.

Let's re-interpret the second query and provide a better example for clarity.

Example 2 (Revised):

Input:
const counter = new HitCounter();
counter.record(1);
counter.record(10);
counter.record(20);

Output:
counter.getHits(15, 10); // Expected: 1 (hit at timestamp 10 is in [6, 15])
counter.getHits(23, 5);  // Expected: 1 (hit at timestamp 20 is in [19, 23])
counter.getHits(25, 10); // Expected: 2 (hits at timestamps 10 and 20 are in [16, 25])

Explanation:

getHits(15, 10): Window is [15 - 10 + 1, 15] which is [6, 15]. The hit at timestamp 10 falls within this range. Count: 1.
getHits(23, 5): Window is [23 - 5 + 1, 23] which is [19, 23]. The hit at timestamp 20 falls within this range. Count: 1.
getHits(25, 10): Window is [25 - 10 + 1, 25] which is [16, 25]. The hits at timestamps 20 fall within this range. Count: 1.

Let's assume the definition of the window is [timestamp - windowInSeconds + 1, timestamp].

Example 3:

Input:
const counter = new HitCounter();
counter.record(1);
counter.record(2);
counter.record(3);

Output:
counter.getHits(2, 1);  // Expected: 1 (hit at timestamp 2 is in [2, 2])
counter.getHits(3, 2);  // Expected: 2 (hits at timestamps 2, 3 are in [2, 3])
counter.getHits(1, 1);  // Expected: 1 (hit at timestamp 1 is in [1, 1])
counter.getHits(0, 5);  // Expected: 0 (no hits in [-4, 0])
counter.getHits(5, 2);  // Expected: 0 (no hits in [4, 5])

Explanation: Demonstrates various window sizes and their impact on hit counts, including cases where no hits fall within the window.

Constraints

The number of calls to record can be up to $10^6$.
The number of calls to getHits can be up to $10^6$.
Timestamps are integers and will be non-negative.
windowInSeconds will be a non-negative integer.
Timestamps passed to record will be monotonically increasing.
Timestamps passed to getHits can be any valid timestamp value.

Notes

Consider data structures that allow for efficient insertion and retrieval of hits within a time range.
The definition of the time window is critical: [timestamp - windowInSeconds + 1, timestamp].
Think about how to handle old, irrelevant hits to keep memory usage in check if this were a long-running system (though for this challenge, memory optimization beyond reasonable efficiency is not the primary focus).
Your solution should be written in TypeScript.
You will need to create a Jest test file (.test.ts) to thoroughly test your HitCounter class. Cover the examples provided, as well as edge cases like empty counters, zero windows, and large numbers of hits.