DNA Sequence Match
Reported by candidates from SpaceX's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
SpaceX reported this one in April 2025, and the data structure it hinges on is just the plain array of strings you're handed. The task: scan every DNA line for exact occurrences of a target and return each hit as lineIndex:startIndex. Overlaps count. It looks like a warm-up, and it mostly is, but the constraints hide a trap. If you have an OA invite and 48 hours, learn the overlap rule and the cost of naive scanning. StealthCoder is the safety net if your mind goes blank mid-assessment, but this one is very doable on your own.
The problem
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.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The core is substring search per line. For each line, find every index i where line starts with target at i, then push lineIndex + ":" + i. The overlap rule means after a match at i you move to i+1, not i+len(target). That's the classic pitfall. Most built-in indexOf loops work fine if you restart from i+1. The second pitfall is cost. Target can be up to 100,000 chars and total text is 200,000, so a naive compare at every position can approach O(n*m) in the worst case, like all A's. Skip lines shorter than the target immediately. For safety, use KMP or Z-function per line, which runs in linear time. Output order falls out naturally from iterating lines then indices. If you blank on KMP during the live OA, StealthCoder can supply the prefix-function code while you keep your head clear.
The honest play: practice the pattern, and have StealthCoder ready for the one you didn't see coming.
You can drill DNA Sequence Match cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass SpaceX's OA.
SpaceX reuses patterns across OAs. Built for the candidate who saw this exact problem leak two days before his OA and wondered if anyone had a play. Works on HackerRank, CodeSignal, CoderPad, and Karat.
DNA Sequence Match FAQ
What's the trick in the SpaceX DNA Sequence Match problem?+
Overlapping matches. After finding a hit at index i, continue searching from i+1, not i plus target length. Example 2 with AAAAA and AAA shows this: you get 0:0, 0:1, 0:2. Miss that and you fail the overlap tests immediately.
Is brute force fast enough here?+
Often yes, but the worst case is risky. With repeated characters like all A's and a long target, naive comparison can hit O(n*m). Skipping lines shorter than the target helps a lot. KMP or a Z-function guarantees linear time per line and removes the doubt.
Can I just use indexOf or find in a loop?+
Yes, if you restart from the previous match index plus 1. Built-in search handles most cases quickly. Watch for languages where the built-in has bad worst-case behavior. If you want a guarantee, write KMP yourself, it's about fifteen lines.
What edge cases should I test before submitting?+
Empty lines, since line length can be 0. A target longer than the line. No matches at all, which must return an empty array. Multiple matches across several lines, and output ordering by line then start index. Also check that indices are zero-based.
How do I prepare for this in 48 hours?+
Practice one string-search implementation, KMP prefix function, until you can write it from memory. Then do a few overlapping-match problems. Format output as a string like line:index, and confirm order. That covers nearly everything this SpaceX question tests.