FastPrepDNA Sequence Match

DNA Sequence Match

SpaceX logoSpaceX● MediumFULLTIMEOA
Learn

Problem statement

DNA Sequence Match

A text file is represented by lines, where every line is a DNA string. Find every exact occurrence of target in the file.

Return the matches in line order and then start-index order. Encode each match as lineIndex:startIndex, using zero-based indices. Overlapping matches count separately. Return an empty array when no match exists.

Function

findDnaSequenceMatches(lines: String[], target: String) → String[]

Examples

Example 1

lines = ["AACGTA","CGTA"]target = "CGT"return = ["0:2","1:0"]

CGT begins at index 2 in the first line and index 0 in the second line.

Example 2

lines = ["AAAAA"]target = "AAA"return = ["0:0","0:1","0:2"]

The three occurrences overlap, and all of them are returned.

Example 3

lines = ["ACGT"]target = "TT"return = []

The target does not occur in the file.

Constraints

  • 1 ≤ lines.length ≤ 10,000
  • 0 ≤ lines[i].length and the sum of all line lengths is at most 200,000.
  • 1 ≤ target.length ≤ 100,000
  • Every line and target contains only A, C, G, and T.

More SpaceX problems

See SpaceX hiring insights
public String[] findDnaSequenceMatches(String[] lines, String target) {
    // Write your code here.
}
lines["AACGTA","CGTA"]
target"CGT"
expected["0:2", "1:0"]
Checking account…