Coding questions · Apple
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.
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.
Rolling Five-Minute Hit Counter
Process record/get operations for a rolling 300-second hit counter and return outputs for get calls, None for records.
Examples
Example 1
Input: ([['recordHit',1], ['recordHit',1], ['get',300], ['get',301]],)
Output: [None, None, 2, 0]
Explanation: Inclusive last 300 seconds.
Example 2
Input: ([['get',10]],)
Output: [0]
Explanation: No hits.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.