Delete a Character From Cover
Company: Databricks
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given a source string `book` and a cipher represented by a list of inclusive index intervals `cover = [(l1, r1), ..., (lm, rm)]`. The decoded cipher text is formed by concatenating `book[l1..r1]`, `book[l2..r2]`, and so on in the given cover order. The intervals may refer to substrings from arbitrary locations in `book`, so they do not need to be sorted by index.
Given an index `k` in the decoded cipher text:
1. Delete the `k`-th character of the decoded cipher and return an updated `cover` that represents the new text.
2. Return the result in simplified form. A cover is simplified if no two adjacent intervals can be replaced by a single interval from `book` whose substring equals their concatenation. If multiple merged intervals are possible, return the leftmost valid one.
Explain how you would handle deleting a character inside one interval, deleting at an interval boundary, and intervals that become empty after deletion.
Quick Answer: This question evaluates proficiency in string manipulation, interval arithmetic, and data-structure updates with attention to index mapping and edge-case handling such as deletions at interval boundaries and intervals that become empty; it belongs to the Coding & Algorithms category and specifically tests string and interval operations.