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 hard 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 and Merge Camera Alert Intervals | Verkada Coding Question

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]]

Explanation: The camera is above the threshold at timestamps 2 and 4, then again at timestamp 8.

Input: ([(1, 7), (3, 8), (6, 4), (9, 5), (10, 6)], 5)

Expected Output: [[1, 3], [10, 10]]

Explanation: The first interval starts immediately at timestamp 1. The value at timestamp 9 equals the threshold, so it is not alert. A new interval starts at 10 and is closed at the end.

Input: ([(1, 1), (2, 2), (3, 5)], 5)

Expected Output: []

Explanation: No value is strictly greater than the threshold.

Input: ([], 0)

Expected Output: []

Explanation: Empty input produces no intervals.

Input: ([(4, 10)], 3)

Expected Output: [[4, 4]]

Explanation: A single reading above the threshold forms a one-point interval.

Hints

Scan the readings once from left to right while tracking whether you are currently inside an alert interval.
Keep the most recent timestamp that was still above the threshold so you know where to close an interval when the alert stops.

Part 2: Merge Alert Intervals From Multiple Cameras

You are given alert intervals from multiple surveillance cameras. Each camera contributes zero or more closed intervals `[start, end]` during which that camera was in alert. Merge all cameras' alert intervals into a single sorted list of non-overlapping intervals representing every time range during which at least one camera was in alert. Important: treat touching intervals as overlapping. For example, `[1, 3]` and `[3, 5]` must be merged into `[1, 5]`. Return the final merged list.

Constraints

`0 <= number of cameras <= 100000`
`0 <= total number of intervals across all cameras <= 200000`
`-10^9 <= start <= end <= 10^9`
Within each camera, intervals are sorted by start time and do not overlap
Touching intervals must be merged

Examples

Input: ([[[1, 3], [8, 10]], [[2, 5]], [[10, 12], [15, 18]]],)

Expected Output: [[1, 5], [8, 12], [15, 18]]

Explanation: Intervals from different cameras overlap or touch, so they are merged.

Input: ([[[1, 1]], [[1, 3]], [[3, 5]]],)

Expected Output: [[1, 5]]

Explanation: All intervals overlap or touch at the endpoints, so they become one interval.

Input: ([[], [[2, 4]], [[6, 7]]],)

Expected Output: [[2, 4], [6, 7]]

Explanation: One camera has no intervals, and the remaining intervals are disjoint.

Input: ([[], []],)

Expected Output: []

Explanation: No camera reports any alert interval.

Input: ([[[4, 9]]],)

Expected Output: [[4, 9]]

Explanation: A single interval is already fully merged.

Hints

First collect all intervals into one list, then sort them by start time.
While merging, if the next interval starts at or before the current merged interval ends, they should be combined.

Quick Overview

This question evaluates understanding of time-series processing, interval detection, and interval-merging algorithms, including handling thresholds, touching intervals, and open-ended alerts.