Find common active intervals across cameras
Company: Verkada
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are now processing data from multiple security cameras.
You are given:
- An integer `N`, the number of cameras.
- A threshold value `T` (a real number).
- For each camera `i` (0-indexed), a vector (array) of time-stamped motion readings:
- `readings[i]` is an array of pairs `[time, motion_level]` for camera `i`.
- For each camera, its readings are sorted by strictly increasing `time`.
For a single camera, define its **active intervals** as in the previous question:
- A camera is considered "active" at a reading if `motion_level > T`.
- Consecutive active readings in that camera's array form one continuous active interval from the first active reading's time to the last active reading's time.
For this problem, we are interested in time intervals during which **all cameras are simultaneously active**.
Task:
1. For each camera, compute its list of active intervals using the above rule.
2. Given all cameras' active interval lists, compute all maximal time intervals during which **every** camera is active (i.e., the intersection of all cameras' active periods).
Return a list of intervals `[start_time, end_time]` representing all such overlapping intervals where all `N` cameras are active at the same time.
Assumptions:
- Each camera's reading list can have different lengths and different timestamp ranges.
- If there is no time when all cameras are active together, return an empty list.
Follow-up discussion:
- Suppose the number of cameras `N` becomes very large (e.g., thousands or more), and each has many readings.
- What is the time and space complexity of your approach?
- Where is the bottleneck in your solution (e.g., per-camera processing vs. multi-camera interval intersection)?
- How might you optimize or restructure the solution to handle a very large number of cameras or very high data volume (e.g., streaming processing, pre-aggregation, or indexing of intervals)?
Quick Answer: This question evaluates competency in interval processing, temporal data aggregation, and multi-stream synchronization, within the Coding & Algorithms domain, and requires practical application-level understanding of interval intersection and time-stamped sensor data handling.
Part 1: Compute Active Intervals for One Camera
You are given the motion readings from a single security camera and a threshold value T. Each reading is a pair [time, motion_level], and the readings are sorted by strictly increasing time.
A reading is considered active if motion_level > T.
A maximal run of consecutive active readings in the array forms one active interval, from the first active reading's time to the last active reading's time.
Return all active intervals for the camera as a list of [start_time, end_time] pairs.
Notes:
- Consecutive means adjacent in the input array.
- A single active reading creates an interval [t, t].
- If there are no active readings, return an empty list.
Constraints
- 0 <= len(readings) <= 200000
- Each reading is [time, motion_level]
- time values are numeric and strictly increasing
- motion_level and T are numeric values
- A reading is active only when motion_level > T (strictly greater, not greater-than-or-equal)
Examples
Input: ([[1, 0.2], [2, 0.7], [3, 0.8], [4, 0.1], [5, 0.9]], 0.5)
Expected Output: [[2, 3], [5, 5]]
Explanation: Readings at times 2 and 3 form one consecutive active run, and time 5 is a single active reading.
Input: ([[1, 0.1], [2, 0.2], [3, 0.5]], 0.5)
Expected Output: []
Explanation: No reading is strictly greater than the threshold.
Input: ([], 1.0)
Expected Output: []
Explanation: Empty input has no active intervals.
Input: ([[10, 1.0]], 1.0)
Expected Output: []
Explanation: The only reading equals the threshold, so it is not active.
Input: ([[0.5, 2.0], [1.0, 1.0], [1.5, 2.1], [2.0, 2.2]], 1.5)
Expected Output: [[0.5, 0.5], [1.5, 2.0]]
Explanation: The first reading is an isolated active interval, and the last two readings form a second active run.
Hints
- Scan the readings once from left to right and track whether you are currently inside an active run.
- When you move from an active reading to an inactive reading, close the current interval.
Part 2: Find Maximal Intervals Where All Cameras Are Simultaneously Active
You are given precomputed active intervals for multiple cameras.
intervals_by_camera[i] contains the active intervals for camera i, where each interval is [start_time, end_time]. Within each camera:
- intervals are sorted by start time
- intervals are non-overlapping
Find all maximal time intervals during which every camera is active at the same time.
Return a list of [start_time, end_time] intervals representing the intersection across all cameras.
Notes:
- Treat intervals as closed intervals.
- If intervals only touch at one time point, that still counts as overlap. For example, [1, 5] and [5, 7] overlap at [5, 5].
- If any camera has no active interval at all, the answer is empty.
Constraints
- 1 <= number of cameras <= 10000
- The total number of intervals across all cameras is at most 200000
- For every interval [start, end], start <= end
- Within each camera's list, intervals are sorted by start time and do not overlap
- Time values may be integers or floating-point numbers
Examples
Input: ([[[1, 5], [8, 10]], [[2, 6], [8, 9]], [[0, 3], [4, 9]]],)
Expected Output: [[2, 3], [4, 5], [8, 9]]
Explanation: These are the maximal segments where all three cameras are active together.
Input: ([[[1, 2]], [[3, 4]]],)
Expected Output: []
Explanation: The cameras are never active at the same time.
Input: ([[], [[1, 2], [3, 5]]],)
Expected Output: []
Explanation: If one camera has no active intervals, there can be no common overlap.
Input: ([[[1, 5]], [[5, 7]], [[0, 5]]],)
Expected Output: [[5, 5]]
Explanation: All cameras overlap exactly at time 5.
Input: ([[[2, 4], [6, 6]]],)
Expected Output: [[2, 4], [6, 6]]
Explanation: With only one camera, the common active intervals are just that camera's intervals.
Hints
- First solve the easier subproblem: how do you intersect two sorted interval lists using two pointers?
- Then repeatedly intersect the running result with the next camera's interval list.