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.