How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Verkada.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Verkada during technical interviews.

Find common active intervals across cameras

Quick Overview

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.

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.

Solution

def solution(readings, T):
    intervals = []
    start = None
    last_active_time = None

    for time, motion_level in readings:
        if motion_level > T:
            if start is None:
                start = time
            last_active_time = time
        else:
            if start is not None:
                intervals.append([start, last_active_time])
                start = None
                last_active_time = None

    if start is not None:
        intervals.append([start, last_active_time])

    return intervals

Time complexity: O(n), where n is the number of readings.. Space complexity: O(1) extra space, excluding the output list..

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.

Solution

def solution(intervals_by_camera):
    def intersect_two(a, b):
        i = 0
        j = 0
        result = []

        while i < len(a) and j < len(b):
            start = max(a[i][0], b[j][0])
            end = min(a[i][1], b[j][1])

            if start <= end:
                result.append([start, end])

            if a[i][1] < b[j][1]:
                i += 1
            else:
                j += 1

        return result

    if not intervals_by_camera:
        return []

    current = [[start, end] for start, end in intervals_by_camera[0]]

    for k in range(1, len(intervals_by_camera)):
        current = intersect_two(current, intervals_by_camera[k])
        if not current:
            return []

    return current

Time complexity: O(K), where K is the total number of intervals across all cameras.. Space complexity: O(M), where M is the size of the running intersection/result..

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.

Quick Overview