Solve interval merge and string dedup problems
You are given three coding questions from a phone screen. Solve each independently.
1) Merge overlapping intervals
Input: A list of intervals intervals, where each interval is [start, end] and start <= end.
Task: Merge all overlapping intervals and return a list of non-overlapping intervals that cover the same ranges.
Output: The merged intervals, typically sorted by start.
Example:
-
Input:
[[1,3],[2,6],[8,10],[15,18]] -
Output:
[[1,6],[8,10],[15,18]]
Constraints (assume):
-
1 <= n <= 10^5 - Interval endpoints fit in 32-bit signed integers.
2) Remove adjacent duplicates (pair removal)
Input: A string s.
Task: Repeatedly remove adjacent duplicate characters when they appear as a pair (e.g., remove "aa"), until no more such pairs exist.
Output: The final resulting string.
Example:
-
Input:
"abbaca" -
Process:
abbaca -> aaca -> ca -
Output:
"ca"
Constraints (assume):
-
1 <= |s| <= 10^5 - Characters can be treated as ASCII letters/digits.
3) Remove adjacent duplicates in groups of size k
Input: A string s and an integer k >= 2.
Task: Repeatedly remove any group of k identical characters that are adjacent. Continue until no such group exists.
Output: The final resulting string.
Example:
-
Input:
s = "deeedbbcccbdaa", k = 3 -
Output:
"aa"
Constraints (assume):
-
1 <= |s| <= 10^5 -
2 <= k <= 10^5 - Characters can include letters and digits.