Compute max events in any 60-second window
Company: Marshall Wace
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Design a function that, given a non-decreasing list of integer timestamps (seconds), returns the maximum number of events occurring within any contiguous 60-second window (inclusive). Aim for an O(n) time, O(
1) extra-space solution.
Quick Answer: This question evaluates understanding of timestamp and array processing, sliding-window or two-pointer techniques, and the ability to analyze time and space complexity when counting events within fixed-size intervals.
You are analyzing a stream of event timestamps given as a non-decreasing list of integer seconds. The business wants to know the maximum number of events that occur within any contiguous 60-second window (inclusive on both ends).
Write a function that takes the list of timestamps and returns the maximum number of events contained in any such window. A window covering [t, t+60] includes any timestamp x with t <= x <= t+60, so two events exactly 60 seconds apart both count.
Aim for an O(n) time, O(1) extra-space solution. Since the input is already sorted, a two-pointer sliding window achieves this: advance the right pointer over each event, and advance the left pointer forward whenever the span exceeds 60, tracking the largest window size seen.
Constraints
- 0 <= len(timestamps) <= 10^6
- timestamps is sorted in non-decreasing order
- timestamps may contain duplicate values (multiple events in the same second)
- Timestamps are integers and may be negative, zero, or positive
- A 60-second window is inclusive on both ends: events t seconds apart count together when t <= 60
Examples
Input: ([1, 2, 3, 61, 62],)
Expected Output: 4
Explanation: The window from 2 to 62 spans 60 seconds (62-2=60) and contains 2,3,61,62 = 4 events. Including timestamp 1 would span 62-1=61 > 60, so it is excluded.
Input: ([],)
Expected Output: 0
Explanation: No events at all, so the maximum count in any window is 0.
Hints
- The list is already sorted, so you never need to re-scan backwards — a forward two-pointer (sliding window) suffices.
- Expand the window by moving the right pointer one event at a time; whenever timestamps[right] - timestamps[left] exceeds 60, move the left pointer forward to shrink it.
- The window is inclusive, so the condition to shrink is strictly '> 60', not '>= 60'. Track the largest (right - left + 1) you ever observe.