Find High-Intensity Time Periods
Company: Hot Agent Startup
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a list of time-series readings, where each reading is `{timestamp, intensity}`, and a numeric `threshold`, return all maximal time periods during which the intensity is strictly greater than the threshold.
Assumptions:
- Readings represent a step function: a reading's intensity remains active from its timestamp until the next reading's timestamp.
- The input may be assumed sorted by timestamp unless the interviewer asks for the unsorted variant.
- The observation window has a known end time; if the final reading is above the threshold, its interval ends at that observation end time.
- Return half-open intervals `[start, end)`.
Example:
```text
readings = [
{timestamp: 1, intensity: 3},
{timestamp: 4, intensity: 8},
{timestamp: 7, intensity: 9},
{timestamp: 10, intensity: 2},
{timestamp: 13, intensity: 6}
]
threshold = 5
observationEnd = 15
```
Output:
```text
[[4, 10), [13, 15)]
```
Discuss edge cases such as empty input, duplicate timestamps, unsorted input, and whether equality should count as above the threshold.
Quick Answer: This question evaluates processing of time-series step-function data, detection of maximal intervals where a numeric intensity exceeds a threshold, and edge-case reasoning such as duplicate timestamps and observation-end boundaries within the Coding & Algorithms category.
Given a list of time-series readings for a step function, return all maximal half-open time intervals [start, end) during which the active intensity is strictly greater than a given threshold.
Each reading becomes active at its timestamp and remains active until the next reading's timestamp. The final effective reading, if it is above the threshold, remains active until observationEnd.
Intervals that are adjacent and continuously above the threshold must be merged into one maximal interval.
For this problem, handle these edge cases explicitly:
- If readings is empty, return an empty list.
- Intensity equal to the threshold does NOT count as above the threshold.
- If multiple readings have the same timestamp, only the last reading at that timestamp in the input is considered effective.
- If the input is unsorted, your function should still return the correct answer.
Constraints
- 0 <= n <= 200000, where n is the number of readings
- timestamps, intensities, threshold, and observationEnd are integers
- Timestamps are not guaranteed to be unique
- Intervals starting at or after observationEnd contribute nothing
- If multiple readings share the same timestamp, the last one in the input wins
Examples
Input: ([{'timestamp': 1, 'intensity': 3}, {'timestamp': 4, 'intensity': 8}, {'timestamp': 7, 'intensity': 9}, {'timestamp': 10, 'intensity': 2}, {'timestamp': 13, 'intensity': 6}], 5, 15)
Expected Output: [[4, 10], [13, 15]]
Explanation: Intensity is above 5 from [4, 7) and [7, 10), which merge into [4, 10). It is above 5 again from [13, 15).
Input: ([], 5, 10)
Expected Output: []
Explanation: With no readings, there are no intervals above the threshold.
Hints
- Think of each effective reading as defining a segment from its timestamp to the next timestamp (or observationEnd for the last reading).
- If the input can be unsorted or contain duplicate timestamps, normalize it first by sorting and collapsing equal timestamps.