Degenerate DNA Substring Search
Reported by candidates from Benchling's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Benchling reportedly asked this one in June 2024, and the trap is in the query, not the sequences. You're scanning DNA strings for a pattern where some query letters stand for several bases. A plain substring check fails the moment you see an M or an N. It's a sliding window with a set-based character match, plus an indexing follow-up the report describes in detail. If the invite is sitting in your inbox, read this twice. StealthCoder is there as a safety net on the live OA if you blank, but the core idea is small enough to hold in your head.
The problem
Search the uploaded DNA sequences for a substring matching query. Sequence characters are standard bases A, C, G, and T. Query characters may also use IUPAC degenerate bases: R=AG, Y=CT, M=AC, K=GT, W=AT, S=CG B=CGT, D=AGT, H=ACT, V=ACG, N=ACGT Return the distinct matching sequences in lexicographic order. Indexed search follow-up The report also describes indexing each uploaded sequence by its four-base substrings. For a query of at least four bases, form candidate sets for its four-grams and intersect them, then verify each candidate by exact substring matching. The report gives ATTAGATT and query GATTA as a false positive for intersection alone: the required four-grams occur in different positions. For degenerate bases, union all compatible concrete four-gram postings before intersection; verify the original degenerate query against every remaining sequence. Queries shorter than four bases need a direct-scan fallback. Discuss retaining the index for multiple queries. The judged function uses the supplied finite array. Function findDegenerateDnaMatches(sequences: String[], query: String) → String[] Examples Example 1 sequences = ["GATTACA","GATTG"] query = "GATT" return = ["GATTACA","GATTG"] Both sequences contain GATT. Example 2 sequences = ["GATTACA","GATTG"] query = "GATTM" return = ["GATTACA"] M accepts A or C, so only GATTACA matches. Constraints 1 <= sequences.length <= 1000. 1 <= query.length <= 100. 1 <= sequences[i].length <= 1000. Sequence characters are ACGT; query characters are valid standard or degenerate IUPAC bases.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The core trick: map each IUPAC letter to the set of bases it accepts. For every sequence, slide a window of query length across it. At each offset, check that every sequence character is in the allowed set for the matching query character. Stop at the first hit, add the sequence, then sort the distinct results. The pitfall is using built-in indexOf or regex without translating degenerate codes, or returning duplicates when the input repeats a sequence. Use a set, then sort lexicographically. Worst case is 1000 sequences times 1000 offsets times 100 query characters, which is fine. The follow-up wants four-gram postings, intersection, and then verification. Intersection alone gives false positives, like ATTAGATT with GATTA, so always verify. Queries under four bases need a direct scan. If the live OA gets weird, StealthCoder can hand you the clean version while you stay calm.
Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.
You can drill Degenerate DNA Substring Search 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. Made for the candidate who got the OA invite this morning and has 72 hours, not six months.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Benchling's OA.
Benchling reuses patterns across OAs. Made for the candidate who got the OA invite this morning and has 72 hours, not six months. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Degenerate DNA Substring Search FAQ
What's the trick in the Benchling degenerate DNA search?+
Translate each query letter into the set of bases it accepts, then slide a window over each sequence and compare character by character against those sets. Plain substring search only works when the query has A, C, G, T. Anything else needs set membership at each position.
How hard is this problem really?+
The base version is easy to medium. It's a brute-force window match with a lookup table. The difficulty comes from clean edge handling: duplicates in the input, a query longer than a sequence, and sorted distinct output. The indexing follow-up is a design discussion more than heavy code.
Why does four-gram intersection give false positives?+
Intersection only proves each four-gram exists somewhere in the sequence, not that they sit at consecutive, overlapping positions. ATTAGATT contains the four-grams of GATTA (GATT and ATTA) in different places, but never the string GATTA. So you must verify every surviving candidate against the original query.
How should I handle queries shorter than four bases?+
Skip the index and scan directly. A four-gram index can't represent a query with fewer than four characters, so there's nothing to look up. Run the same sliding-window check across all sequences. With these constraints, that's cheap.
How do I prepare for this in 48 hours?+
Write the lookup table and the window matcher from memory once, then test it on both examples, including GATTM returning only GATTACA. Add the dedupe and sort step. Then rehearse explaining the four-gram index, the false positive case, and why you'd keep the index for repeated queries.