Katkat
Back

Design a rolling five-minute hit counter

AppleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates understanding of data-structure selection, amortized time complexity, space-time trade-offs, sliding-window state management for expiring events, and the ability to design a concise API with unit tests.

Design an in-memory hit counter that supports: (

  1. recordHit(timestamp) to log an event, and (
  2. getCountLast5Minutes(now) to return the number of events that occurred in the past 300 seconds. Assume timestamps are integer seconds and non-decreasing across calls. Explain how to expire outdated events efficiently without storing every hit individually, detail your data-structure choices and time/space trade-offs, target O(
  3. amortized per operation with O(
  4. space, and implement the API with unit tests.