Intersect Motion Threshold Periods Across Cameras
Company: Verkada
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Intersect Motion Threshold Periods Across Cameras
Implement `common_motion_periods(streams, threshold, end_time)`. Each camera stream is a nonempty list of `[timestamp, intensity]` readings sorted by strictly increasing integer timestamp. Intensities are integers from `0` through `1000000`, representing values from `0.000000` through `1.000000`; `threshold` uses the same scale.
A reading at timestamp `t` remains in effect at every integer timestamp from `t` through one less than the next reading's timestamp. The final reading remains in effect through `end_time`, inclusive. A camera has no defined intensity before its first reading, so analysis begins at the latest first timestamp among all streams.
Return every maximal inclusive interval `[start, end]` during which every camera's effective intensity is at least `threshold`. Intervals must be sorted by `start` and must not overlap or touch; touching qualifying spans are one maximal interval. With one stream, the function solves the single-camera part.
The discrete time domain, persistence rule, scaling, and explicit horizon are pedagogical assumptions because the source gives timestamp-intensity pairs and inclusive output endpoints without defining interpolation or the last reading's end.
## Function Contract
`common_motion_periods(streams: list[list[list[int]]], threshold: int, end_time: int) -> list[list[int]]`
## Constraints
- `1 <= len(streams) <= 1000`
- Every stream has at least one reading, and its timestamps are strictly increasing.
- Every reading timestamp is in `[0, end_time]`.
- `0 <= threshold <= 1000000`
- `0 <= end_time <= 10^12`
- The total number of readings is at most `200000`.
## Examples
### Example 1
```text
Input:
streams = [[[1, 200000], [3, 700000], [6, 800000], [8, 100000]]]
threshold = 600000
end_time = 10
Output: [[3, 7]]
```
The single camera is above threshold from timestamp 3 through 7; the change at 6 does not break the qualifying period.
### Example 2
```text
Input:
streams = [
[[0, 800000], [5, 300000], [8, 900000]],
[[2, 700000], [6, 900000], [9, 200000]]
]
threshold = 600000
end_time = 10
Output: [[2, 4], [8, 8]]
```
Both cameras qualify from 2 through 4 and again only at timestamp 8.
Quick Answer: Find maximal motion periods for one camera or the simultaneous intersection across many piecewise-constant camera streams. The prompt defines exact integer timestamps, threshold scaling, last-reading horizon, undefined prefixes, inclusive endpoints, and deterministic interval ordering for portable console verification.
Implement common_motion_periods(streams, threshold, end_time). Each nonempty camera stream contains strictly increasing [timestamp, intensity] integer pairs. An intensity applies at every integer time from its reading through one less than the next reading; the final reading applies through end_time. A camera is undefined before its first reading, so analysis starts at the latest first timestamp. Intensities and threshold use the integer scale 0 through 1,000,000. Return the sorted maximal inclusive [start, end] intervals when every camera's effective intensity is at least threshold. Returned intervals cannot overlap or touch; consecutive qualifying spans form one interval. One stream is the single-camera case.
Constraints
- 1 <= streams.length <= 1,000
- Every stream is nonempty with strictly increasing integer timestamps.
- Every reading timestamp is in [0, end_time].
- 0 <= intensity, threshold <= 1,000,000
- 0 <= end_time <= 10^12
- The total number of readings is at most 200,000.
- A reading persists on the discrete integer timeline until the next reading, and the final reading persists through end_time inclusive.
- Return sorted maximal inclusive intervals and merge touching qualifying spans.
Examples
Input: ([[[1, 200000], [3, 700000], [6, 800000], [8, 100000]]], 600000, 10)
Expected Output: [[3, 7]]
Explanation: The first source example merges a qualifying high-to-high change for one camera.
Input: ([[[0, 800000], [5, 300000], [8, 900000]], [[2, 700000], [6, 900000], [9, 200000]]], 600000, 10)
Expected Output: [[2, 4], [8, 8]]
Explanation: The second source example intersects two streams and respects inclusive change boundaries.
Hints
- After the latest first reading, only reading timestamps can change whether all cameras qualify.
- Process every camera change sharing one timestamp as a group before starting the next span.