Solve interval merge and string dedup problems
Quick Overview
This set of questions evaluates algorithmic reasoning for array and string manipulation, specifically competencies in interval merging, detection and elimination of adjacent duplicates, and handling grouped removals under input and performance constraints.
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.