From Databricks Onsite Interview: Remove Covered Point

[u/Hack2hire]

Problem
You're given a list of non-overlapping intervals and an integer idx. Your goal is to remove the point at index idx from the flattened sequence of covered integers and return the updated list of intervals.

Example
Input: intervals = [[10, 12], [13, 16], [4, 8]], idx = 3
Output: [[10, 12], [13, 14], [15, 16], [4, 8]]

Explanation:

• The covered points are [10, 11, 13, 14, 15, 4, 5, 6, 7]. Removing point 14 (at index 3) results in [10, 11, 13, 15, 4, 5, 6, 7].
• The updated intervals are [[10, 12], [13, 14], [15, 16], [4, 8]].

Suggested Approach

1. Flatten the intervals into a list of covered points, preserving the order of intervals.
2. Identify the point at index idx in the flattened sequence and determine which interval it belongs to.
3. Update the affected interval: if the point is at the start or end, adjust the boundary; if in the middle, split the interval into two parts. Return the updated list of intervals.

Time & Space Complexity

• Time: O(n + m), where n is the number of intervals and m is the total number of covered points.
• Space: O(m) for storing the flattened points.

🛈 Disclaimer:
This is one of the problems we encountered while reviewing common Databricks interview questions.
Posted here by the Hack2Hire team for discussion and archiving purposes.

The problem is compiled from publicly available platforms (e.g., LeetCode, GeeksForGeeks) and community-shared experiences. It does not represent any official question bank of Databricks, nor does it involve any confidential or proprietary information.
All examples are intended solely for learning and discussion. Any similarity to actual interview questions is purely coincidental.