Design a rolling five-minute hit counter
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
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(
1) amortized per operation with O(
300) space, and implement the API with unit tests.
Quick Answer: 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.
Process record/get operations for a rolling 300-second hit counter and return outputs for get calls, None for records.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([['recordHit',1], ['recordHit',1], ['get',300], ['get',301]],)
Expected Output: [None, None, 2, 0]
Explanation: Inclusive last 300 seconds.
Input: ([['get',10]],)
Expected Output: [0]
Explanation: No hits.
Input: ([['hit',1], ['hit',400], ['get',400]],)
Expected Output: [None, None, 1]
Explanation: Old hit expired.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.