Hit Counter

Hit Counter Problem Overview
The "Hit Counter" is a system design interview question often attributed to Google (and LeetCode #362), focusing on Design, Queue, and Hash Table. It requires implementing a class to track hits (page views or events) within the past 5 minutes (300 seconds granularity).[2][5]

Full Problem Statement

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

• Implement HitCounter class with two methods:
  • void hit(int timestamp): Records a hit at the given timestamp (in seconds).
  • int getHits(int timestamp): Returns the number of hits in the past 5 minutes (i.e., from timestamp - 300 + 1 to timestamp).

Timestamps are closed under integer division by 1 second and strictly increasing for sequential calls, though multiple hits can occur at the same timestamp.[5][2]

Input/Output Examples

` 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); // Output: 3

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

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

// get hits at timestamp 301, should return 3 (drops hits 1,2,3 as they're >300 seconds old) counter.getHits(301); // Output: 3 ` All hits at timestamps 1,2,3,300 fall within 300-300+1=1 to 300. At 301, only 300 remains valid.[2]

Constraints

• 1 <= timestamp <= 10^9 (handles up to billions of seconds without overflow).
• Calls to hit and getHits occur in chronological order (timestamps non-decreasing).
• Up to 10^4 calls total (naive queue works but optimize for amortized O(1) getHits).
• Multiple hits possible at identical timestamps (handle duplicates without double-counting incorrectly).
• 5-minute window fixed at 300 seconds.[5][2]