Solve interval merge and string dedup problems
Company: Grammarly
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
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.
Quick Answer: 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.