Intervals, Sliding Windows, And Time-Ordered State

What's being tested

Apple interviewers are probing time-ordered state management: intervals, expiring events, sorted timelines, and resource counts over time. You need to choose the right structure—queue, heap, two pointers, sweep line, or buckets—and explain complexity, boundary semantics, and edge cases clearly.

Patterns & templates

• Sliding window queue for rolling counters — store timestamps or (timestamp, count) pairs; evict while ts <= now - window; O(1) amortized.

• Fixed-size circular buckets for hit counters — bucket by timestamp % 300; reset stale buckets; O(300) query or maintain running sum.

• Sweep line for interval overlap — convert [start, end) into (start, +1), (end, -1); sort events; max prefix sum gives rooms.

• Min-heap of end times for meeting rooms — sort by start, pop ended meetings, push current end; O(n log n) time, O(n) space.

• Two-pointer merge over sorted starts/ends — sort starts and ends separately; advance start for new room, end for freed room; watch tie rules.

• Time-series single-pass optimization — track best prior minimum and current profit; O(n) time, O(1) space; don’t sort prices.

• State-machine scanning for brackets or edge detection — stack for nesting, previous-state variables for discrete transitions; validate empty and malformed input.

Common pitfalls

Pitfall: Treating interval ends as inclusive by default; most scheduling problems use half-open intervals [start, end) so back-to-back meetings do not conflict.

Pitfall: Designing a hit counter that stores every event when the interviewer expects bounded memory for high-throughput repeated timestamps.

Pitfall: Giving only the final algorithm without clarifying timestamp monotonicity, duplicate times, clock granularity, and whether queries can arrive out of order.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.