Katkat
Back

Implement a rate-limited hit counter

DatabricksSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates a candidate's understanding of designing efficient time-windowed data structures and algorithmic analysis, including space-time trade-offs and amortized complexity.

You are designing a hit counter that records the number of hits received in the past 5 minutes.

Implement a class HitCounter with the following methods:

  • void hit(int timestamp): Records a hit at the given timestamp (in seconds). The timestamp is given in seconds granularity and is strictly increasing across all calls.
  • int getHits(int timestamp): Returns the number of hits received in the past 5 minutes (i.e., the past 300 seconds) including the current second, at the given timestamp.

Constraints:

  • 1 <= timestamp <= 10^9.
  • Methods will be called in non-decreasing order of timestamp.
  • The number of calls to both hit and getHits is up to 10^5.

Describe the data structures and algorithms you would use to implement HitCounter so that both operations are efficient in time and memory. Do not write code; just specify the design and complexity.