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 Onsite rounds at Bytedance.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Bytedance during technical interviews.

Implement Interval Insert and Dedup | Bytedance Coding Question

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.

Part 1: Insert and Merge Intervals

You are given a list of intervals sorted by start time. The intervals are pairwise non-overlapping. You are also given one new interval. Insert the new interval into the list, merge any overlapping intervals, and return the final list of non-overlapping intervals sorted by start time.

Constraints

0 <= len(intervals) <= 10^4
Each interval is `[start, end]` with 0 <= start <= end <= 10^9
The input intervals are sorted by start time
The input intervals do not overlap each other

Examples

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

Expected Output: [[1,5],[6,9]]

Explanation: The new interval overlaps with [1,3], so they merge into [1,5].

Input: ([[1,2],[3,5],[6,7],[8,10],[12,16]],[4,8])

Expected Output: [[1,2],[3,10],[12,16]]

Explanation: The new interval overlaps with [3,5], [6,7], and [8,10], so they merge into [3,10].

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

Expected Output: [[5,7]]

Explanation: Edge case: inserting into an empty interval list just returns the new interval.

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

Expected Output: [[1,2],[3,4],[5,6]]

Explanation: The new interval does not overlap and belongs at the end.

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

Expected Output: [[1,2],[3,5],[7,9]]

Explanation: The new interval does not overlap and belongs at the beginning.

Hints

First copy all intervals that end before the new interval starts.
Then merge all intervals that overlap the new interval, and finally append the remaining intervals.

Part 2: Remove Extra Duplicates In-Place (At Most Twice)

You are given a sorted integer array `nums`. Modify the array in place so that each distinct value appears at most twice. Use only O(1) extra space. Return the new valid length. Elements beyond the returned length do not matter.

Constraints

0 <= len(nums) <= 10^5
-10^9 <= nums[i] <= 10^9
The array is sorted in non-decreasing order
You must use O(1) extra space

Examples

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

Expected Output: 5

Explanation: The first 5 elements become [1,1,2,2,3].

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

Expected Output: 7

Explanation: The first 7 elements become [0,0,1,1,2,3,3].

Input: ([],)

Expected Output: 0

Explanation: Edge case: an empty array stays empty.

Input: ([5],)

Expected Output: 1

Explanation: Edge case: a single element is always valid.

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

Expected Output: 6

Explanation: Every value already appears at most twice, so the full array is kept.

Hints

Keep a write pointer for where the next valid value should go.
A value is allowed if fewer than 2 elements have been written so far, or if it differs from the element 2 positions before the write pointer.

Part 3: Remove Extra Duplicates In-Place (At Most k Times)

You are given a sorted integer array `nums` and an integer `k`. Modify the array in place so that each distinct value appears at most `k` times. Use only O(1) extra space. Return the new valid length. Elements beyond the returned length do not matter. If `k = 0`, no values should be kept.

Constraints

0 <= len(nums) <= 10^5
0 <= k <= 10^5
-10^9 <= nums[i] <= 10^9
The array is sorted in non-decreasing order
You must use O(1) extra space

Examples

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

Expected Output: 5

Explanation: With k = 2, the first 5 elements become [1,1,2,2,3].

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

Expected Output: 3

Explanation: With k = 1, only one copy of each value is kept, so the first 3 elements become [1,2,3].

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

Expected Output: 7

Explanation: With k = 3, the first 7 elements become [1,1,1,2,2,2,3].

Input: ([],3)

Expected Output: 0

Explanation: Edge case: an empty array always returns 0.

Input: ([1,1,2],0)

Expected Output: 0

Explanation: Edge case: when k = 0, no elements are allowed.

Hints

This is the same idea as the at-most-twice version, but replace the fixed number 2 with `k`.
A value can be written if fewer than `k` elements have been kept so far, or if it differs from the element `k` positions before the write pointer.

Quick Overview

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.