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 Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at LinkedIn.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at LinkedIn during technical interviews.

Compute total covered interval length | LinkedIn Coding Question

Quick Overview

Compute total covered interval length evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Compute total covered interval length

Company: LinkedIn

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given a list of integer intervals [l, r) (half-open), compute the total length covered by at least one interval. Intervals may overlap or be nested. Return the length and explain time and space complexity. Implement two approaches: (a) sort-and-merge line sweep; (b) a segment tree or interval tree that supports incremental add/remove intervals and querying the total covered length after each update. Discuss handling large coordinate ranges via coordinate compression, treatment of duplicates, and common off-by-one pitfalls.

Quick Answer: Compute total covered interval length evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given a list of integer intervals `[l, r)` (half-open), compute the total length covered by at least one interval. Intervals may overlap or be nested. Return the total covered length as an integer. Because the intervals are half-open `[l, r)`, two intervals that only touch at a single point (e.g. `[1, 2)` and `[2, 4)`) form one contiguous covered span of combined length, with no double counting. Zero-length intervals where `l == r` contribute nothing. The classic approach is a sort-and-merge line sweep: sort the intervals by start, then walk through them maintaining the current merged span, accumulating its length each time a gap appears. This runs in O(n log n) time. The prompt also invites discussing a segment tree with coordinate compression that supports incremental add/remove and querying covered length after each update; for this console you implement the static line-sweep computation. Input: a list of `[l, r]` pairs (each interpreted as the half-open interval `[l, r)`). Output: the integer total covered length.

Constraints

0 <= number of intervals <= 10^5
Each interval is [l, r) with l <= r (l == r is a valid zero-length interval contributing 0)
Coordinates may be negative; -10^9 <= l, r <= 10^9
Intervals may overlap, be nested, or be exact duplicates

Examples

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

Expected Output: 6

Explanation: [1,3) and [2,5) merge into [1,5) (length 4); [7,9) adds 2. Total 6.

Input: ([],)

Expected Output: 0

Explanation: No intervals, so nothing is covered.

Input: ([[0, 10]],)

Expected Output: 10

Explanation: A single interval [0,10) covers length 10.

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

Expected Output: 3

Explanation: [2,3) is nested inside [1,4); covered span is [1,4), length 3.

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

Expected Output: 4

Explanation: Half-open intervals touching at 2 and 4 form one contiguous span [1,5), length 4 — no double counting.

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

Expected Output: 4

Explanation: Duplicates: [1,3) (length 2) and [5,7) (length 2), each counted once. Total 4.

Input: ([[-5, -1], [-3, 2], [10, 12]],)

Expected Output: 9

Explanation: [-5,-1) and [-3,2) merge into [-5,2) (length 7); [10,12) adds 2. Total 9, with negative coordinates.

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

Expected Output: 4

Explanation: [3,3) is zero-length and contributes nothing; covered span is [1,5), length 4.

Hints

Sort the intervals by their start coordinate, then sweep left to right keeping one 'current' merged span.
Since the intervals are half-open [l, r), an interval whose start equals the current end (l == cur_r) still merges into the same contiguous span — use `l <= cur_r` as the overlap test.
Drop zero-length intervals (l == r) up front, and only add the current span's length to the total when the next interval starts a fresh, non-overlapping span.
Coordinate compression plus a segment tree gives an alternative that also supports incremental add/remove, but for a one-shot static query the O(n log n) line sweep is simplest.

Quick Overview