Design a rolling five-minute hit counter

Q: Design a rolling five-minute hit counter

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Design an in-memory hit counter that supports: (

recordHit(timestamp) to log an event, and (
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(
amortized per operation with O(
space, and implement the API with unit tests.

Design a rolling five-minute hit counter

Overview

Comments (0)