Compute total covered interval length
LinkedInMachine Learning Engineer · Technical Screen
Last updated
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 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.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.