Implement Interval Insert and Dedup
Company: Bytedance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
This interview round contained two coding problems:
1. **Insert and merge intervals.** You are given a list of non-overlapping intervals sorted by start time, along with one new interval. Insert the new interval into the list, merge any overlaps, and return the resulting sorted list.
2. **Remove extra duplicates in-place.** You are given a sorted integer array. Modify it in place so that each distinct value appears at most twice, using only O(1) extra space, and return the new valid length. Elements beyond the returned length do not matter.
Follow-up: How would you generalize the second problem so that each value may appear at most `k` times instead of 2?
Quick Answer: This question evaluates skills in array and interval data-structure manipulation, in-place modification under space constraints, and general algorithmic reasoning for merging ranges and limiting duplicate occurrences.