Katkat
Back

Design a rolling hit counter API

GoogleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to design an efficient data structure for time-series aggregation using a sliding window approach with O(1) time complexity per operation.

Rolling Hit Counter

Design a thread-safe HitCounter class that supports counting the number of hits received in the past 5 minutes (300 seconds). Hits that occurred more than 300 seconds ago should be automatically excluded from the count.

Implement the following methods:

  • void hit(int timestamp): Records a hit at the given timestamp (in seconds).
  • int getHits(int timestamp): Returns the number of hits recorded in the last 300 seconds preceding the given timestamp.

Constraints

  • timestamp is given in seconds and will always be provided in non-decreasing order.
  • Assume a high volume of calls to hit and getHits.

Example

counter = HitCounter()
counter.hit(1)    # Hit at timestamp 1
counter.hit(2)    # Hit at timestamp 2
counter.hit(3)    # Hit at timestamp 3
counter.getHits(4)  # Returns 3
counter.hit(300)  # Hit at timestamp 300
counter.getHits(300) # Returns 4
counter.getHits(301) # Returns 2 (timestamps 1 and 2 expired)

Edge Cases

  • Multiple hits occurring at the same timestamp.
  • getHits called multiple times for the same timestamp.
  • Very large gaps between timestamp values.

Your implementation should aim for O(1) time complexity for both operations, assuming the number of hits per second is bounded or handled appropriately.

Hints

Hint 1

Consider using an array or a circular buffer to store hit counts for each second in the 300-second window.

Hint 2

Map each incoming timestamp to an index in the buffer using the modulo operator (timestamp % 300).

Hint 3

When accessing a timestamp, check if the data at the calculated index corresponds to the current 300-second window by comparing timestamps.

Follow-up questions

  • How would you optimize this design if the number of hits per second is extremely high, potentially exceeding the capacity of an integer?
  • How would you adapt this system to work in a distributed environment across multiple servers?
  • What are the trade-offs of using a Lock-free approach versus using synchronized locks for the thread-safety requirement?