Find Services with the Largest Rolling-Window Request Count
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given logs `(timestamp, service)` and a window duration t seconds, find the largest number of requests made to any one service within a rolling window. Return that count and every service whose best window reaches it. Logs may arrive unsorted, and repeated timestamps are separate requests.
A window includes both endpoints: timestamps whose difference is exactly t can appear together. For t=10, three requests to a service at times 100, 100, and 110 fit in one window. For times 10, 30, 50, 70 with t=60, all four fit.
### Constraints & Assumptions
Assume t is nonnegative. For an empty log list, return no services and count zero. Return service names in sorted order to make the tied-service list deterministic; the source requires all ties but does not prescribe their ordering.
### Clarifying Questions to Ask
- Can input timestamps be unsorted, as in the reported example?
- Are both window endpoints included, and do duplicate log records count separately?
```hint Consider each service's timeline
After sorting a service's timestamps, the best window ending at one request can be represented by a contiguous interval.
```
### What a Strong Answer Covers
- Grouping and sorting without assuming global input order.
- Expiring a timestamp only when the time difference exceeds t.
- Tracking each service's maximum and retaining all global ties.
### Follow-up Questions
- How would already sorted logs simplify processing?
- What state is needed to process an unbounded ordered stream?
Overview: Find every service tied for the highest rolling-window request count using sorted timelines and sliding windows with inclusive timestamp boundaries.
Given logs (timestamp, service) and a window duration t seconds, find the largest number of requests made to any one service within a rolling window. Return that count and every service whose best window reaches it. Logs may arrive unsorted, and repeated timestamps are separate requests.
A window includes both endpoints: timestamps whose difference is exactly t can appear together. For t=10, three requests to a service at times 100, 100, and 110 fit in one window. For times 10, 30, 50, 70 with t=60, all four fit.
Constraints & Assumptions
Assume t is nonnegative. For an empty log list, return no services and count zero. Return service names in sorted order to make the tied-service list deterministic; the source requires all ties but does not prescribe their ordering.
Clarifying Questions to Ask Guidance
Can input timestamps be unsorted, as in the reported example?
Are both window endpoints included, and do duplicate log records count separately?
What a Strong Answer Covers Guidance
Grouping and sorting without assuming global input order.
Expiring a timestamp only when the time difference exceeds t.
Tracking each service's maximum and retaining all global ties.
Follow-up Questions Guidance
How would already sorted logs simplify processing?
What state is needed to process an unbounded ordered stream?