FastPrep
Problem · Array

Cipher Cover Interval Editing

Learn this problem
● MediumDatabricks logoDatabricksFULLTIMEONSITE INTERVIEW

Problem statement

A book is a source string. The ordered list cover describes a cipher: for every inclusive interval [start, end], append book[start..end] to the cipher in list order.

Delete the cipher character at the zero-based flattened index position by updating the cover rather than changing book. Return the updated list of intervals.

Cover update rules

  • If the selected character is the first endpoint of a multi-character interval, increase that interval's start by 1.
  • If it is the last endpoint of a multi-character interval, decrease that interval's end by 1.
  • If it is strictly inside an interval, replace that interval with its nonempty left and right pieces, in that order.
  • If the selected interval contains exactly one character, remove that interval.

The order of cover defines the cipher. Intervals may be unsorted and may overlap. Deleting one cipher occurrence changes only the interval that produced that occurrence; another interval may continue to reference the same position in book. Preserve all unaffected interval boundaries and do not merge adjacent intervals.

Function

deleteCipherCharacter(book: String, cover: int[][], position: int) → int[][]

Examples

Example 1

book = "abcdefghij"cover = [[1,4],[7,9]]position = 2return = [[1,2],[4,4],[7,9]]

The first interval contributes bcde, so flattened position 2 is d at book index 3. Removing that interior character splits [1,4] into [1,2] and [4,4].

Example 2

book = "abcdef"cover = [[4,5],[0,2]]position = 0return = [[5,5],[0,2]]

The cipher begins with book[4]. Deleting the first character shrinks the first interval from the left. The unsorted interval order is preserved.

Example 3

book = "abcdef"cover = [[1,3],[2,2],[0,1]]position = 3return = [[1,3],[0,1]]

Flattened position 3 comes from the singleton interval [2,2], so that interval is removed. The earlier overlapping interval still references book index 2.

Constraints

  • 1 <= book.length <= 10^5.
  • 1 <= cover.length <= 10^5.
  • Every interval has exactly two integers [start, end] with 0 <= start <= end < book.length.
  • The sum of all inclusive interval lengths is at most 2 * 10^5.
  • 0 <= position < sum(end - start + 1) over all intervals.
  • Intervals may be unsorted and may overlap.

More Databricks problems

drafts saved locally
public int[][] deleteCipherCharacter(String book, int[][] cover, int position) {
    // Write your code here.
}
book"abcdefghij"
cover[[1,4],[7,9]]
position2
expected[[1,2],[4,4],[7,9]]
checking account