Remove one point from a cover of integer intervals

Question: Remove one point from a cover of integer intervals

Companies: Databricks

Difficulty: Medium

Problem statement

You are given a list of non-overlapping half-open intervals. An interval [start, end] with start < end covers the integers start, start + 1, ..., end - 1. Reading the intervals in the order they are given, and each interval from left to right, produces a flattened sequence of covered integers. The list is not necessarily sorted.

Implement remove_covered_point(intervals, idx), which removes the integer at 0-based position idx of the flattened sequence and returns the resulting list of intervals.

• Keep the input order. Do not sort or merge intervals.
• Removing a point from the middle of an interval splits it into two intervals.
• Never return an empty interval (start == end).
• Raise an error if idx is negative or not less than the number of covered integers.
• Intervals can be very long (lengths up to 10^9), so do not expand them into points.

Example 1

intervals = [[10, 13], [2, 4]]   # flattened: 10, 11, 12, 2, 3
idx = 1                          # removes 11
-> [[10, 11], [12, 13], [2, 4]]

Example 2

intervals = [[5, 6], [0, 2]]     # flattened: 5, 0, 1
idx = 0                          # removes 5; its interval disappears
-> [[0, 2]]

Part 2. The same cover now receives many removals in a row. Support remove(idx) (returns the removed integer) and to_intervals() efficiently.

Approach

Clarify first. Each interval [start, end) covers the integers start, start + 1, ..., end - 1. The intervals do not overlap, but the list is not necessarily sorted: the flattened order is the input order, interval by interval. Ask three things before coding:

• Order. Is the "flattened sequence" sorted by value, or does it follow the input order? Here it follows the input order, so do not sort.
• Empty pieces. If removing the point leaves an empty piece, drop it. Never emit [x, x).
• Bad index. What happens when idx is negative or at least the total number of covered points? Raising IndexError is a fine default.

Brute force. Expand every interval into its points, delete position idx, then compress consecutive runs back into intervals. This is correct but costs O(total points), and a single interval like [0, 10^9) makes it useless. Mention it and move on.

Optimal: walk the lengths. You never need the points, only the interval lengths. Keep remaining = idx. For each interval, if remaining >= end - start, the target is later: subtract the length and copy the interval unchanged. Otherwise the target is the integer p = start + remaining, and the interval breaks into at most two pieces:

• left piece [start, p) if start < p,
• right piece [p + 1, end) if p + 1 < end.

Copy the remaining intervals unchanged and stop. The cases interviewers check all fall out of these two conditions: removing the first point (no left piece), the last point (no right piece), a middle point (both pieces, so the list grows by one), and a single-point interval (neither piece, so the interval disappears).

Invariant. Before visiting interval i, remaining equals idx minus the number of points in intervals 0..i-1. So the first interval with remaining < length holds the target, at offset remaining.

Many removals. If the interviewer asks for a stream of removals on the same cover, re-scanning is O(n) per call, and each split makes the list longer. The CoverEditor class below keeps the original intervals fixed and stores, per interval, a sorted list of removed points. A Fenwick tree over the live count of each interval finds the interval that holds the idx-th live point in O(log n). Inside that interval, a binary search on value finds the point: the number of live points <= x is x - start + 1 - (removed points <= x). to_intervals() rebuilds the current cover on demand.

Code

from __future__ import annotations

from bisect import bisect_right, insort

Interval = list[int]  # [start, end), end exclusive


def remove_covered_point(intervals: list[Interval], idx: int) -> list[Interval]:
    """Remove the idx-th covered integer (0-based, in input order).

    Returns a new list; the input is not modified. Raises IndexError if idx
    is outside the covered points.
    """
    if idx < 0:
        raise IndexError("idx must be non-negative")
    result: list[Interval] = []
    remaining = idx
    for i, (start, end) in enumerate(intervals):
        length = end - start
        if remaining >= length:          # target is in a later interval
            remaining -= length
            result.append([start, end])
            continue
        point = start + remaining        # the integer to delete
        if start < point:
            result.append([start, point])
        if point + 1 < end:
            result.append([point + 1, end])
        result.extend([s, e] for s, e in intervals[i + 1:])
        return result
    raise IndexError("idx is past the last covered point")


class CoverEditor:
    """Many removals: Fenwick tree over the live count of each interval."""

    def __init__(self, intervals: list[Interval]) -> None:
        self.intervals = [(s, e) for s, e in intervals]
        self.removed: list[list[int]] = [[] for _ in intervals]
        self.n = len(intervals)
        self.tree = [0] * (self.n + 1)
        for i, (s, e) in enumerate(self.intervals):
            self._add(i, e - s)

    def _add(self, i: int, delta: int) -> None:
        i += 1
        while i <= self.n:
            self.tree[i] += delta
            i += i & -i

    def size(self) -> int:
        total, i = 0, self.n
        while i > 0:
            total += self.tree[i]
            i -= i & -i
        return total

    def _find(self, k: int) -> tuple[int, int]:
        """Interval holding the k-th live point, and k's offset inside it."""
        pos, step = 0, 1 << self.n.bit_length()
        while step:
            nxt = pos + step
            if nxt <= self.n and self.tree[nxt] <= k:
                pos = nxt
                k -= self.tree[nxt]
            step >>= 1
        return pos, k

    def remove(self, idx: int) -> int:
        """Delete the idx-th live point and return its value."""
        if not 0 <= idx < self.size():
            raise IndexError("idx out of range")
        i, k = self._find(idx)
        start, end = self.intervals[i]
        gone = self.removed[i]
        lo, hi = start, end - 1          # smallest x with k+1 live points <= x
        while lo < hi:
            mid = (lo + hi) // 2
            if mid - start + 1 - bisect_right(gone, mid) >= k + 1:
                hi = mid
            else:
                lo = mid + 1
        insort(gone, lo)
        self._add(i, -1)
        return lo

    def to_intervals(self) -> list[Interval]:
        out: list[Interval] = []
        for (start, end), gone in zip(self.intervals, self.removed):
            cur = start
            for p in gone:
                if cur < p:
                    out.append([cur, p])
                cur = p + 1
            if cur < end:
                out.append([cur, end])
        return out

Complexity

Let n be the number of intervals.

• remove_covered_point: O(n) time to scan and copy, O(n) space for the new list. It never depends on interval lengths.
• CoverEditor.__init__: O(n log n) (or O(n) with a linear Fenwick build), O(n) space.
• CoverEditor.remove: O(log n) to find the interval, O(log L * log r) for the value search (L is the interval length, r its removed count), plus O(r) for insort. Swap the per-interval list for a balanced tree or SortedList to make it O(log r).
• CoverEditor.to_intervals: O(n + R) where R is the total number of removals.

Test cases

• [[10, 13], [2, 4]], idx = 1 (point 11, middle) → [[10, 11], [12, 13], [2, 4]].
• [[10, 13], [2, 4]], idx = 0 (first point of an interval) → [[11, 13], [2, 4]].
• [[10, 13], [2, 4]], idx = 2 (last point of an interval) → [[10, 12], [2, 4]].
• [[10, 13], [2, 4]], idx = 3 (point 2, in the second interval, so input order matters) → [[10, 13], [3, 4]].
• [[5, 6], [0, 2]], idx = 0 (single-point interval) → [[0, 2]].
• [[0, 1000000000]], idx = 500000000 → [[0, 500000000], [500000001, 1000000000]] instantly, with no expansion.
• idx = -1 or idx = 5 on [[10, 13], [2, 4]] → IndexError.
• CoverEditor([[10, 13], [2, 4]]): remove(1) returns 11; then remove(1) returns 12; to_intervals() → [[10, 11], [2, 4]].
• Randomized check: apply CoverEditor.remove and remove_covered_point to the same random covers until empty and compare after every step.

Follow-ups

• Remove many points (a stream of removals). Re-scanning is O(n) per call. Use CoverEditor: a Fenwick tree (or a segment tree) over live counts gives O(log n) lookup by rank, and per-interval removed sets keep splits implicit, so the index structure never has to grow.
• Merge adjacent intervals. Some versions then ask you to "simplify" the cover: merge intervals that touch in the flattened order, e.g. [1, 3) followed by [3, 5) becomes [1, 5). Do one pass, merging when prev.end == cur.start. Ask whether only neighbors in the list merge, or whether you must sort first (that changes the flattened order, so usually not).
• Insert a point at an index. The mirror operation: find the interval that holds position idx the same way, then either extend a neighbor (if the new value is start - 1 or end) or split and insert a one-point interval. Validate that the new value is not already covered.
• Remove a range of positions [i, j). Find the intervals holding i and j - 1, keep the left piece of the first and the right piece of the last, and drop everything in between. Still one pass, O(n).
• Answer "what value is at position idx" without removing. Precompute prefix sums of lengths once and bisect them: O(log n) per query, the same idea the Fenwick tree makes dynamic.

Interviewer expectations

Mid-level (L4)

• Gets the half-open semantics right and handles first, last, middle, and single-point removals without emitting empty intervals.
• Works from lengths, not by expanding points.
• Tests the edge cases out loud, including an out-of-range index.

Senior (L5)

• Notices that the flattened order is the input order and does not sort.
• States the invariant on remaining and explains why the scan is O(n) regardless of interval sizes.
• Handles a follow-up such as merging adjacent intervals or range removal cleanly in the same structure.

Staff (L6+)

• For a stream of removals, proposes rank lookup with prefix sums or a Fenwick tree and explains why splitting the list in place is costly.
• Discusses the trade-off between keeping splits implicit (removed sets per interval) and materializing them, and when to_intervals should run.
• Brings up input validation (overlaps, start >= end) and immutability of the input as API decisions.