Marshall Wace·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Got a coding question at Marshall Wace for a software engineering role. Pretty focused technical screen, one problem, and they clearly cared about the efficiency angle more than just getting a working solution.

Questions Asked (1)

Given a sorted (non-decreasing) list of integer timestamps in seconds, write a function that returns the maximum number of events falling within any 60-second window, inclusive. They wanted O(n) time and O(1) extra space.

Algorithms & Data Structures

Author's notes

The sliding window part clicked fast enough, two pointers moving through the sorted list.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a sliding window with two pointers to maintain the largest set of timestamps within a 60-second inclusive window. Since the list is sorted, move the right pointer to include each event and advance the left pointer while the window exceeds 60 seconds, tracking the maximum window size. This achieves O(n) time and O(1) extra space.

Pro tip: Clarify that the window is inclusive (difference ≤ 60) and that the input is sorted, which allows the two-pointer technique. Mention that if the input weren't sorted, you'd need to sort first, changing the complexity.

1. Clarify the problem

Confirm that the window is inclusive (timestamps t2 - t1 ≤ 60) and that the list is sorted in non-decreasing order. Ask if the function should return the count or the actual events.

2. Choose the sliding window approach

Explain that two pointers (left and right) can efficiently find the maximum number of events in any 60-second window because the sorted order allows us to maintain a valid window by moving pointers only forward.

3. Walk through the algorithm

Initialize left = 0, max_count = 0. Iterate right from 0 to n-1: while timestamps[right] - timestamps[left] > 60, increment left. Update max_count = max(max_count, right - left + 1).

4. Analyze complexity

State that each element is visited at most twice (once by right, once by left), so time is O(n). Only a few variables are used, so extra space is O(1).

5. Test with examples

Run through a small example, e.g., [1, 2, 3, 61, 62] to show the window slides and the max count is 3. Also test edge cases like empty list or all events within 60 seconds.

Key Points to Mention

The input is sorted, enabling the two-pointer technique.
The window is inclusive: timestamps[right] - timestamps[left] ≤ 60.
Time complexity is O(n) because each element is processed at most twice.
Space complexity is O(1) as only a constant number of variables are used.
Edge cases: empty list, single event, all events within 60 seconds, events exactly 60 seconds apart.
Alternative approaches (e.g., binary search for each event) would be O(n log n), so the sliding window is optimal.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.