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 Databricks.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Databricks during technical interviews.

Delete a Character From Cover | Databricks Coding Question

Quick Overview

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.

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.

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]`, ... in the given cover order. The intervals may point to substrings from arbitrary, possibly out-of-order locations in `book`. Given a 0-based index `k` into 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. Two adjacent intervals `(a, b)` and `(c, d)` can be merged into `(a, d)` exactly when `c == b + 1` (they are contiguous in `book`). When several merges are possible, perform them left-to-right so the leftmost valid merge wins. Handle the three boundary situations explicitly: - Deleting **inside** an interval `(l, r)` at decoded offset `p` splits it into `(l, l+p-1)` and `(l+p+1, r)`. - Deleting at an interval **boundary** simply makes one side empty. - An interval that becomes **empty** (left > right) is dropped from the cover. Return the simplified list of intervals (each as an `(l, r)` pair).

Constraints

0 <= k < total length of the decoded text
Each interval (l, r) satisfies 0 <= l <= r < len(book)
Intervals may appear in any order and may reference overlapping regions of book
1 <= len(book) <= 10^5
0 <= number of intervals <= 10^5

Examples

Input: ("abcdef", [(0, 2), (3, 5)], 1)

Expected Output: [(0, 0), (2, 5)]

Explanation: Decoded = 'abcdef'. Delete index 1 ('b') inside interval (0,2): split into (0,0) and (2,2). Now (2,2) is contiguous with (3,5) (2+1==3... wait 2's next is 3), so (2,2) and (3,5) merge into (2,5). Result: [(0,0),(2,5)].

Input: ("abcdef", [(0, 2), (3, 5)], 2)

Expected Output: [(0, 1), (3, 5)]

Explanation: Delete index 2 ('c'), the last char of the first interval. (0,2) splits into (0,1) and empty (3,2)->dropped. (0,1) and (3,5) are not contiguous (1+1=2 != 3), so no merge.

Input: ("abcdef", [(0, 2), (3, 5)], 3)

Expected Output: [(0, 2), (4, 5)]

Explanation: Delete index 3 ('d'), the first char of the second interval. (3,5) splits into empty (3,2)->dropped and (4,5). (0,2) and (4,5) are not contiguous (2+1=3 != 4), so no merge.

Input: ("abcdef", [(2, 2), (3, 5)], 0)

Expected Output: [(3, 5)]

Explanation: Delete index 0 from the single-char interval (2,2); it becomes empty and is dropped, leaving [(3,5)].

Input: ("abcdef", [(0, 0)], 0)

Expected Output: []

Explanation: The only interval has one character; deleting it empties the cover entirely.

Input: ("abcdefgh", [(5, 7), (0, 2)], 0)

Expected Output: [(6, 7), (0, 2)]

Explanation: Out-of-order intervals: decoded = 'fgh'+'abc'. Delete index 0 ('f') inside (5,7): split into empty (5,4)->dropped and (6,7). (6,7) and (0,2) are not contiguous in book, so no merge.

Input: ("abcdef", [(0, 1), (2, 3), (4, 5)], 5)

Expected Output: [(0, 4)]

Explanation: Decoded = 'ab'+'cd'+'ef'. Delete index 5 ('f', last char) inside (4,5): split into (4,4) and empty (6,5)->dropped. Now (0,1),(2,3),(4,4) are all contiguous in book and merge left-to-right into (0,4).

Hints

Walk the cover left to right, subtracting each interval's length from k until you find the interval that contains the k-th decoded character; the local offset is l + remaining_k.
Splitting an interval (l, r) at absolute book index `cut` yields (l, cut-1) and (cut+1, r). Drop either side when its left index exceeds its right index (empty).
Simplification only merges *adjacent* intervals (a, b) and (c, d) when c == b + 1. A single left-to-right pass that extends the previous interval when contiguous gives the leftmost-first merges automatically.
Deleting at a boundary is just the split case where one of the two halves is empty and gets dropped.

Quick Overview