Katkat
Back

Implement a Five-Minute Hit Counter

AppleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

This problem tests your ability to design a high-throughput, time-series data structure that balances memory usage with query performance.

Problem Statement

Design a thread-safe HitCounter class that tracks the number of hits over a sliding window of 300 seconds (5 minutes).

Your implementation must support the following methods:

  • hit(int timestamp): Records a hit at the given timestamp (in seconds). You may assume that hit calls are provided in non-decreasing order of timestamp.
  • getHits(int timestamp): Returns the total number of hits recorded in the range [timestamp - 299, timestamp]. Hits older than 300 seconds should be ignored.

Constraints

  • 1 <= timestamp <= 2 * 10^9
  • The system must handle a high volume of hit calls.
  • The getHits method should be as efficient as possible.

Example

counter = HitCounter()
counter.hit(1)
counter.hit(2)
counter.hit(3)
counter.getHits(4) # returns 3
counter.hit(300)
counter.getHits(300) # returns 4
counter.getHits(301) # returns 3 (only hits at 2, 3, 300 are valid)

Implementation Template

class HitCounter:
    def __init__(self):
        # Initialize data structures
        pass

    def hit(self, timestamp: int) -> None:
        # Record a hit
        pass

    def getHits(self, timestamp: int) -> int:
        # Return count for the last 300 seconds
        pass

Edge Cases to Consider

  • Multiple hits occurring at the exact same timestamp.
  • Large gaps between hit timestamps.
  • Calls to getHits with a timestamp smaller than any previously recorded hit.

Hints

Hint 1

Consider using a data structure that maps timestamps to hit counts, such as a hash map or a list.

Hint 2

Since the window size is fixed at 300 seconds, a circular buffer or a fixed-size array can store counts per second to achieve O(1) space complexity relative to the number of hits.

Hint 3

If you use an array of size 300, ensure you clear or overwrite outdated entries as the window slides forward.

Follow-up questions

  • How would you modify your implementation to support concurrency if multiple threads call `hit` and `getHits` simultaneously?
  • If the window size were to increase to one day, how would your memory usage change and what alternatives might you consider?
  • How would you adapt this design if you needed to support a distributed system where hits are aggregated across multiple physical servers?