Find Windows Containing a Target
Company: Roblox
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a list of windows, where each window is represented as an inclusive integer interval `[start, end]`, and an integer `target`.
Return all windows that contain `target`. A window contains `target` if `start <= target <= end`.
Requirements:
- Preserve the original order of the matching windows.
- Endpoints are inclusive.
- Windows may overlap.
- The input may be empty.
Example:
Input:
```text
windows = [[1, 5], [6, 10], [3, 7], [8, 12]]
target = 6
```
Output:
```text
[[6, 10], [3, 7]]
```
Explanation: `6` is contained in `[6, 10]` and `[3, 7]`, but not in `[1, 5]` or `[8, 12]`.
Quick Answer: This question evaluates array traversal and interval-containment reasoning, including handling inclusive endpoints, overlapping intervals, and preservation of original ordering.
You are given a list of windows, where each window is an inclusive integer interval [start, end], and an integer target. Return all windows that contain target. A window contains target if start <= target <= end. Preserve the original order of the matching windows. Windows may overlap, and the input may be empty.
Constraints
- 0 <= len(windows) <= 100000
- Each window has exactly 2 integers: [start, end]
- -1000000000 <= start, end, target <= 1000000000
- For every window, start <= end
Examples
Input: ([[1, 5], [6, 10], [3, 7], [8, 12]], 6)
Expected Output: [[6, 10], [3, 7]]
Explanation: The target 6 is inside [6, 10] and [3, 7], but not inside [1, 5] or [8, 12].
Input: ([], 4)
Expected Output: []
Explanation: There are no windows to check, so the result is empty.
Hints
- Each window can be checked independently, so try scanning the list once from left to right.
- Remember that the interval endpoints are inclusive: a window matches when start <= target <= end.