Design Hit Counter

Medium

Databricks

14 views

Topics:

Arrays

Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds). Implement the HitCounter class:

HitCounter() Initializes the object of the hit counter system.
void hit(int timestamp) Records a hit that happened at timestamp (in seconds). Several hits may happen at the same same timestamp.
int getHits(int timestamp) Returns the number of hits in the past 5 minutes from timestamp (i.e., the past 300 seconds).

You should assume that timestamp is monotonically increasing. You may assume that the earliest timestamp starts at 1.

Implement the HitCounter class:

class HitCounter {
public:
    HitCounter() {}

    void hit(int timestamp) {}

    int getHits(int timestamp) {}
};

Example 1:

Input:
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output:
[null, null, null, null, 3, null, 4, 3]

Explanation:
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300);  // get hits at timestamp 300, return 4.
hitCounter.getHits(301);  // get hits at timestamp 301, return 3.

Constraints:

1 <= timestamp <= 2 * 10⁹
All the calls are being made to the methods in sequential order.
hit will be called at most 3 * 10⁵ times.
getHits will be called at most 3 * 10⁵ times.

Design Hit Counter

Medium

Databricks

14 views

Topics:

Arrays

Design a hit counter which counts the number of hits received in the past 5 minutes (i.e., the past 300 seconds). Implement the HitCounter class:

HitCounter() Initializes the object of the hit counter system.
void hit(int timestamp) Records a hit that happened at timestamp (in seconds). Several hits may happen at the same same timestamp.
int getHits(int timestamp) Returns the number of hits in the past 5 minutes from timestamp (i.e., the past 300 seconds).

You should assume that timestamp is monotonically increasing. You may assume that the earliest timestamp starts at 1.

Implement the HitCounter class:

class HitCounter {
public:
    HitCounter() {}

    void hit(int timestamp) {}

    int getHits(int timestamp) {}
};

Example 1:

Input:
["HitCounter", "hit", "hit", "hit", "getHits", "hit", "getHits", "getHits"]
[[], [1], [2], [3], [4], [300], [300], [301]]
Output:
[null, null, null, null, 3, null, 4, 3]

Explanation:
HitCounter hitCounter = new HitCounter();
hitCounter.hit(1);       // hit at timestamp 1.
hitCounter.hit(2);       // hit at timestamp 2.
hitCounter.hit(3);       // hit at timestamp 3.
hitCounter.getHits(4);   // get hits at timestamp 4, return 3.
hitCounter.hit(300);     // hit at timestamp 300.
hitCounter.getHits(300);  // get hits at timestamp 300, return 4.
hitCounter.getHits(301);  // get hits at timestamp 301, return 3.

Constraints:

1 <= timestamp <= 2 * 10⁹
All the calls are being made to the methods in sequential order.
hit will be called at most 3 * 10⁵ times.
getHits will be called at most 3 * 10⁵ times.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected range of the timestamp values, and how should I handle potentially out-of-order timestamps in the `hit` function?
If `getHits` is called with a timestamp that is less than or equal to the timestamp of a previous hit, should I still only count hits within the last 5 minutes relative to the input timestamp?
What should I return from `getHits` if there are no hits recorded within the last 5 minutes (or at all)? Should I return 0, null, or throw an exception?
Can I assume that the timestamp is given in seconds (or some other specific unit), and that 5 minutes corresponds to exactly 300 seconds?
How often will `hit` and `getHits` be called relative to each other? Is `getHits` called much more frequently than `hit`, or vice versa, as this might influence data structure choices?

Brute Force Solution

Approach

The goal is to track website hits over time. The brute force way is to simply remember every single hit that happens, regardless of how old it is, and then when asked for the hit count, go through all the hits and filter them.

Here's how the algorithm would work step-by-step:

Each time a hit comes in, remember the exact second it happened.
When someone asks for the number of hits in the last five minutes (300 seconds), look at your list of all the hits.
Go through the entire list of hits, one by one.
For each hit, check if it happened within the last 300 seconds.
If it did, count it. If not, ignore it.
After checking every single hit, tell them the total number of hits that happened in the last 300 seconds.

Code Implementation

class HitCounter:

    def __init__(self):
        self.hit_timestamps = []

    def hit(self, timestamp: int) -> None:
        # Store the timestamp of the new hit.
        self.hit_timestamps.append(timestamp)

    def getHits(self, timestamp: int) -> int:
        hits_in_last_300_seconds = 0

        # Iterate through all recorded timestamps.
        for hit_timestamp in self.hit_timestamps:
            # Check if the hit occurred within the last 300 seconds.
            if timestamp - hit_timestamp < 300:
                hits_in_last_300_seconds += 1

        return hits_in_last_300_seconds

Big(O) Analysis

Time Complexity

O(n) – The plain English explanation describes iterating through all recorded hits to count those within the last 300 seconds. The input size, n, is the number of recorded hits. The hit() function is O(1), adding to the end of a list which has constant time complexity. The getHits() function iterates through this entire list of hits once to count the recent ones. Thus, the time complexity of getHits() is O(n), where n is the total number of hits recorded.

Space Complexity

O(N) – The provided solution stores every single hit along with its timestamp. This implies using a data structure, likely a list or array, to store all hit timestamps. As the number of hits increases, the size of this data structure grows linearly. Therefore, the auxiliary space required is proportional to the number of hits, N, where N is the total number of hits recorded. This results in a space complexity of O(N).

Optimal Solution

Approach

The best way to count recent hits is to use a data structure that automatically forgets old information. We want to quickly add new hits and efficiently count only the hits that have occurred within the last five minutes.

Here's how the algorithm would work step-by-step:

Keep a list of timestamps of each hit. Each time a hit happens, record the exact time.
When someone asks how many hits there have been recently, go through the list of timestamps.
Remove all the timestamps that are older than five minutes ago. Get rid of the outdated information.
Count how many timestamps are left. That's how many hits have happened in the last five minutes.
The list naturally 'rolls over' time, always only keeping the most recent hits.

Code Implementation

class HitCounter:
    def __init__(self):
        self.hit_timestamps = []

    def hit(self, timestamp: int) -> None:
        self.hit_timestamps.append(timestamp)

    def getHits(self, timestamp: int) -> int:
        # Remove outdated timestamps from the list.
        while self.hit_timestamps and self.hit_timestamps[0] <= timestamp - 300:
            self.hit_timestamps.pop(0)

        # The remaining timestamps represent hits in the last 5 minutes.
        return len(self.hit_timestamps)

# Your HitCounter object will be instantiated and called as such:
# hit_counter = HitCounter()
# hit_counter.hit(timestamp)
# hits = hit_counter.getHits(timestamp)

Big(O) Analysis

Time Complexity

O(n) – The hit function has a time complexity of O(1) as it simply appends a timestamp to the list. The getHits function iterates through the list of timestamps. Let n be the number of hits recorded. In the worst-case scenario, all the hits occurred within the last five minutes, so we iterate through all n timestamps to count them. Therefore, the getHits function has a time complexity of O(n).

Space Complexity

O(N) – The primary auxiliary space used in this approach is the list of timestamps. In the worst-case scenario, all hits in the last five minutes could have occurred at different timestamps, leading to the storage of N timestamps, where N is the number of hits in the last five minutes. Therefore, the auxiliary space grows linearly with the number of hits in the last five minutes. This results in a space complexity of O(N).

Edge Cases

Case	How to Handle
Timestamp is non-positive (zero or negative)	Treat non-positive timestamps as invalid inputs and either throw an exception, ignore the hit, or assume it's a very old event (timestamp 0), depending on requirements.
Timestamp is smaller than the previous timestamp in hit()	Handle out-of-order timestamps gracefully by either ignoring the hit, throwing an exception to indicate invalid input, or adjusting the internal data structure to maintain chronological order as best as possible.
Large number of hits within a very short time frame, potentially exceeding memory or computational limits	Employ a data structure optimized for space (e.g., a circular buffer) and consider aggregation techniques or sampling if necessary to manage high hit rates.
getHits() is called with a timestamp that is much earlier than any recorded hits	Return 0 in `getHits()` when the provided timestamp is earlier than any recorded hits, as no hits could have occurred within the last 5 minutes from that point.
Integer overflow in timestamp representation or hit counts	Use appropriate data types (e.g., long) to prevent integer overflows when storing timestamps and hit counts, and consider using a big integer library if necessary for extremely large values.
getHits() and hit() are called concurrently from multiple threads	Use thread-safe data structures and synchronization mechanisms (e.g., mutexes, locks) to ensure data consistency and prevent race conditions when `getHits()` and `hit()` are accessed concurrently.
The range of valid timestamps is very large leading to huge memory consumption	Use circular queue or optimized data structure such as hash map with expiration to limit the data held in memory for better scalability.
No hits have been recorded yet	Return 0 in `getHits()` when no hits have been recorded, which is the initial state of the HitCounter.