Vultr DocsLatest Content

Design Hit Counter

Updated on 22 May, 2025
Design Hit Counter header image

Problem Statement

The task involves creating a hit counter system to track the number of hits received within the past five minutes, which equates to the last 300 seconds. This system is represented by a class, HitCounter, which provides two primary functionalities through its methods. The first method, hit(int timestamp), records a hit that occurs at a specified timestamp (in seconds granularity). Multiple hits can occur at the same timestamp. The second method, getHits(int timestamp), calculates the count of hits that have occurred in the 300 seconds leading up to a given timestamp. This involves keeping track of the hits in a way that quickly allows retrieval of the number of hits in a moving 5-minute window. The implementation assumes that each timestamp provided to these methods is in non-decreasing order, reflecting chronologically sequential events.

Examples

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 * 109
  • All the calls are being made to the system in chronological order (i.e., timestamp is monotonically increasing).
  • At most 300 calls will be made to hit and getHits.

Approach and Intuition

We can solve the hit counter design problem with the aid of a dynamic data structure that allows for efficient addition, deletion, and querying operations. The main challenge is to quickly sum the hits in the last 300 seconds for any given timestamp.

Here's a breakdown of the approach, derived from the example provided:

  1. Initialization:

    • Initiate a HitCounter class instance. This can be done using an empty database or a suitable data structure that can hold timestamps.

  2. Handling Hits:

    • For each call to the hit(int timestamp) method, record the event. Given that multiple events can occur at the same timestamp, a list or a map (associating each timestamp with its hit count) can be effective.

  3. Querying Hits:

    • When getHits(int timestamp) is invoked, determine how many hits occurred in the last 300 seconds, inclusive of the given timestamp.
    • Efficient querying can be managed using a sliding window approach where old hits (older than 300 seconds from the current timestamp) are removed or ignored.
    • In performing these tasks, ensure data older than 300 seconds from the current timestamp is either deleted or not considered during computations to keep operations efficient and focused on the relevant timeframe only.

Example Process (Based on Provided Example Input and Output)

  1. Instantiate the HitCounter.
  2. Log hits at timestamps 1, 2, and 3.
  3. At timestamp 4, upon querying, identify and return the count of all hits in the last 300 seconds (which are the 3 hits recorded).
  4. At timestamp 300, another hit is logged.
  5. Querying at timestamp 300 should consider all hits from the last 300 seconds, now including the hit at timestamp 300.
  6. At timestamp 301, the hit at timestamp 1 falls out of the 300-second window; therefore, the query only returns hits from timestamps 2, 3, and 300.

By considering these examples, we get a clear view of how the counter maintains a rolling count of hits over a specified period, ensuring that older hits are evacuated from the calculation as needed, thereby maintaining efficiency and accuracy.

Solutions

  • C++
  • Java
cpp 
class HitTracker {
private:
    
    int countHits;
    queue<pair<int, int> > eventLog;
    
public:
    
    /** Constructor for HitTracker */
    HitTracker() {
        countHits = 0;
    }
    
    /** Logs each hit with a timestamp */
    void recordHit(int currentTime) {
        if (eventLog.empty() || eventLog.back().first != currentTime) {
            eventLog.push({currentTime, 1});
        } else {
            eventLog.back().second++;
        }
        countHits++;
    }
    
    /** Returns number of hits within the last 5 minutes */
    int getRecentHits(int currentTime) {
        while (!eventLog.empty()) {
            int timeDifference = currentTime - eventLog.front().first;
            if (timeDifference >= 300) {
                countHits -= eventLog.front().second;
                eventLog.pop();
            }
            else break;
        }
        return countHits;
    }
};

The provided C++ code defines a class HitTracker used to track the number of hits at different times, suitable for monitoring activities on a website or a server. The class uses an integer countHits to store the cumulative number of hits, and a queue of pairs named eventLog to store pairs of timestamps and their associated hit counts.

  • HitTracker() initializes the counter countHits to zero, setting up an empty hit tracking system.
  • recordHit(int currentTime) logs every hit received at a given timestamp. If the time of the latest hit (currentTime) matches the last recorded time in eventLog, it increments the count associated with that time. Otherwise, it adds a new pair to the queue with currentTime as the key and initializes the hit count for this time to one. It then increments the overall countHits counter.
  • getRecentHits(int currentTime) retrieves the count of hits in the last 5 minutes from the given currentTime. It checks each entry in the queue; if the difference between currentTime and the time stored in the entry exceeds 300 seconds (5 minutes), it deducts the count of that specific entry from countHits and removes that entry from the queue. This method continues until it encounters an entry within the last 5 minutes or the queue is exhausted. Finally, it returns the countHits, which now reflects the number of hits in the prior 5 minutes.

Edit the recordHit method and getRecentHits method to maintain accurate tracking and retrieval. Ensure proper cleanup of outdated hits to avoid unnecessary use of memory and to keep the hit counter up to date. With this implementation, efficiently track and retrieve hit data in real-time scenarios.

java 
class EventCounter {

    private int countHits;
    private Deque<Pair<Integer, Integer>> events;

    public EventCounter() {
        this.countHits = 0;
        this.events = new LinkedList<Pair<Integer, Integer>>();
    }

    public void registerHit(int currentTime) {
        if (events.isEmpty() || events.getLast().getKey() != currentTime) {
            events.add(new Pair<Integer, Integer>(currentTime, 1));
        } else {
            int currentCount = events.getLast().getValue();
            events.removeLast();
            events.add(new Pair<Integer, Integer>(currentTime, currentCount + 1));
        }
        countHits++;
    }

    public int countRecentHits(int currentTime) {
        while (!events.isEmpty()) {
            int timeDiff = currentTime - events.getFirst().getKey();
            if (timeDiff >= 300) {
                countHits -= events.getFirst().getValue();
                events.removeFirst();
            }
            else break;
        }
        return countHits;
    }
}

This solution outlines the implementation of an EventCounter class in Java that serves as a hit counter. This class tracks the number of hits at any given time and can report the number of hits over a recent period efficiently:

  • Start by defining the private variables countHits to maintain the current count of total hits and events, a Deque<Pair<Integer, Integer>>, to store the count of hits at each given time.
  • The constructor initializes countHits to zero and events as a new LinkedList to store the hit events as pairs, where each pair contains a timestamp and its associated hit count.
  • Implement the registerHit method to increment the hit count:
    1. If events is empty or the last recorded time isn't the current timestamp, add a new pair with the current time and a count of one.
    2. If the last recorded time is the current time, update the last pair to increment the count by one.
    3. Increment the overall hit count regardless of the time condition.
  • Develop the countRecentHits method to return the count of hits in the last 300 units of time:
    1. Continuously check the oldest event.
    2. If the difference between the current time and this event's time is 300 or more, subtract this event's hit count from countHits and remove the event.
    3. If it's less than 300, stop the loop.
    4. Return the current hit count, which reflects the number of hits within the recent period.

This implementation effectively utilizes a deque to streamline the adding and removing of events, making the solution efficient both in terms of time and space by ensuring older hits are no longer counted once they are beyond the relevant period. The use of pair data structure facilitates tracking of both time stamp and hit count at that particular time, allowing for an efficient way of updating or purging the records.

Comments

No comments yet.