Find and Merge Camera Alert Intervals
Company: Verkada
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given surveillance camera readings as time-series data.
Each reading is a pair `(timestamp, value)`, sorted by `timestamp`. A camera is considered to be in an alert state whenever `value > threshold`.
Implement the following:
1. **Single camera:** Given one camera's readings and a threshold, return all maximal alert intervals `[start, end]` based on the recorded timestamps. An interval starts when the readings transition from `value <= threshold` to `value > threshold`, and it ends at the last recorded timestamp before the alert condition stops. If the camera is still above the threshold at the end of the input, close the interval at the final timestamp.
2. **Multiple cameras:** Given alert intervals from multiple cameras, merge them into a single list of non-overlapping intervals representing any time range during which at least one camera was in alert.
Assumptions:
- Timestamps are integers.
- Input readings for each camera are already sorted.
- When merging intervals, treat touching intervals as overlapping; for example, `[1, 3]` and `[3, 5]` should become `[1, 5]`.
Discuss the algorithm, edge cases, and time complexity.
Quick Answer: This question evaluates understanding of time-series processing, interval detection, and interval-merging algorithms, including handling thresholds, touching intervals, and open-ended alerts.
Part 1: Single Camera Alert Intervals
You are given time-series readings from one surveillance camera. Each reading is a pair `(timestamp, value)`, and the readings are sorted by timestamp.
The camera is in an alert state whenever `value > threshold`.
Return all maximal closed alert intervals `[start, end]` using only recorded timestamps:
- An interval starts when the camera enters alert state.
- An interval ends at the last recorded timestamp whose value was still above the threshold, just before the alert state stops.
- If the first reading is already above the threshold, the interval starts at that timestamp.
- If the camera is still above the threshold at the end of the input, close the interval at the final timestamp.
Your task is to compute and return the list of alert intervals in order.
Constraints
- `0 <= len(readings) <= 200000`
- `-10^9 <= timestamp, value, threshold <= 10^9`
- Timestamps are strictly increasing
- An alert reading is defined by `value > threshold`
Examples
Input: ([(1, 1), (2, 6), (4, 7), (5, 3), (8, 9), (10, 2)], 5)
Expected Output: [[2, 4], [8, 8]]