How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Marshall Wace.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Marshall Wace during technical interviews.

Compute max events in any 60-second window | Marshall Wace Coding Question

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.

Input: ([100],)

Expected Output: 1

Explanation: A single event always fits in a window by itself.

Input: ([0, 60],)

Expected Output: 2

Explanation: 60-0=60 is within the inclusive 60-second window, so both events count.

Input: ([0, 61],)

Expected Output: 1

Explanation: 61-0=61 > 60, so no single window contains both; the best is 1.

Input: ([10, 10, 10, 10],)

Expected Output: 4

Explanation: All four events share the same timestamp, so they all fall in one window.

Input: ([0, 30, 60, 90, 120, 121],)

Expected Output: 3

Explanation: The window 60..120 (span 60) holds 60,90,120 = 3 events; no window holds 4.

Input: ([-5, 0, 50, 54, 55],)

Expected Output: 5

Explanation: 55-(-5)=60 is within the inclusive window, so all 5 events fit together.

Input: ([1, 2, 3, 4, 5, 6, 7, 8, 9, 70],)

Expected Output: 9

Explanation: Events 1..9 all fit in one window (span 8). Adding 70 would span 70-1=69 > 60, so the dense cluster of 9 is the answer.

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.

Quick Overview

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.