Design Hit Counter

Design a hit counter which counts the number of hits received in the past 5 minutes.

Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1.

It is possible that several hits arrive roughly at the same time.

Example:

HitCounter counter = new HitCounter();

// hit at timestamp 1.
counter.hit(1);

// hit at timestamp 2.
counter.hit(2);

// hit at timestamp 3.
counter.hit(3);

// get hits at timestamp 4, should return 3.
counter.getHits(4);

// hit at timestamp 300.
counter.hit(300);

// get hits at timestamp 300, should return 4.
counter.getHits(300);

// get hits at timestamp 301, should return 3.
counter.getHits(301);

Follow up:
What if the number of hits per second could be very large? Does your design scale?

Let’s walk through this "Hit Counter (Last 5 Minutes)" problem step-by-step in your preferred format:

---

✅ 1. Problem Explanation (In Simple Terms)

You are designing a hit counter that records how many times something (like a webpage) is hit.

• You can call hit(timestamp) whenever a hit happens.

• You can call getHits(timestamp) to know how many hits happened in the last 5 minutes (i.e., within the range [timestamp - 299, timestamp]).

Important details:

• Timestamps are in seconds.

• Timestamps are monotonically increasing (i.e., you won’t get older timestamps after newer ones).

• Multiple hits may happen at the same second.

---

💡 2. Key Insights

1. 5 minutes = 300 seconds, so we only care about the last 300 seconds.

2. Since timestamps are monotonically increasing:

   • We can safely remove expired hits while adding new ones.

3. There are two possible approaches:

   • (A) Store each individual hit → can be memory-expensive for high QPS (not scalable).

   • (B) Store aggregated hits per second, capped to last 300 seconds → much more scalable ✅

---

🧠 3. Steps to Solve (Optimized Design)

We'll use a circular array of fixed size 300 to store hits:

• Each slot represents 1 second in a 5-minute window.

• At index i:

  • times[i] stores the timestamp last recorded at that slot.

  • hits[i] stores the number of hits at that second.

Why circular?

• We can just do index = timestamp % 300, and overwrite old data if needed.

Core Logic:

• In hit(t):

  • Compute index as t % 300.

  • If times[index] !== t, overwrite times[index] = t, and reset hits[index] = 1.

  • Else, just hits[index]++.

• In getHits(t):

  • For all 300 slots:

    • If t - times[i] < 300, include hits[i] in the total

    • Else, ignore (it's too old)

This approach uses O(1) time and space.

---

✅ 4. JavaScript Code (Scalable & Clean)

class HitCounter {
  constructor() {
    this.times = new Array(300).fill(0); // timestamp for each second slot
    this.hits = new Array(300).fill(0);  // number of hits in each slot
  }

  /**
   * Record a hit at the given timestamp
   * @param {number} timestamp
   */
  hit(timestamp) {
    const index = timestamp % 300;
    if (this.times[index] !== timestamp) {
      // overwrite old data
      this.times[index] = timestamp;
      this.hits[index] = 1;
    } else {
      this.hits[index]++;
    }
  }

  /**
   * Return number of hits in past 5 minutes
   * @param {number} timestamp
   * @return {number}
   */
  getHits(timestamp) {
    let total = 0;
    for (let i = 0; i < 300; i++) {
      if (timestamp - this.times[i] < 300) {
        total += this.hits[i];
      }
    }
    return total;
  }
}

---

🔍 5. Dry Run Example

const counter = new HitCounter();

counter.hit(1);   // hit at 1s
counter.hit(2);   // hit at 2s
counter.hit(3);   // hit at 3s

counter.getHits(4);    // [1,2,3] are within last 300s → returns 3

counter.hit(300);      // hit at 300s
counter.getHits(300);  // [1,2,3,300] → returns 4
counter.getHits(301);  // [2,3,300] → returns 3 (hit at 1 is now expired)

---

⏱️ 6. Time & Space Complexity

🚀 Scales well even with millions of hits per second, since we only store at most 300 buckets, one for each second in 5-minute window.

---

🤔 Follow-up: What if there are a LOT of hits per second?

Answer:
✅ The above solution already handles high volume efficiently by aggregating hits into per-second slots, rather than storing each hit individually. So it scales beautifully.

If even higher resolution is needed (say per millisecond), you could:

• Increase the array size (e.g. 300,000 for 5 mins in ms),

• Or bucket hits into intervals (e.g., every 100ms or every 1s), depending on the use case.