The Sneaky Twins

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Accordion

Problem

A genomics pipeline scans a long lowercase string sequence for every place a short marker could be hiding, even when its bases have been shuffled into a different order. Return the starting index of every window in sequence, equal in length to marker, that uses exactly the same bases as marker with the same counts. Indices come back in increasing order, and a marker longer than sequence yields nothing.

They look different but they are the same inside.

Example

Input:

sequence = "actgcatac", marker = "act"

Output:

[0,4,6]

Worked solution and explanation

What this really is

Strip the costume and this is an anagram scan: every fixed-width window of sequence whose letters are a reshuffle of marker, counts included. The trap is reading 'same bases' too literally or too loosely. Reach for marker in sequence or sequence.find(marker) and you only see the in-order hit, so the visible case comes back [0] instead of [0, 4, 6]. Compare set(window) to set(marker) instead and you accept windows with the right letters in the wrong amounts, handing back start indices that are not the marker at all. Once you are comparing counts, the next thing that separates candidates is not rebuilding those counts at every position: let one base enter and one leave as the window shifts, and each step costs constant work.

Walking the window

Step 1: Fingerprint the marker

Tally how many times each base appears in marker. That tally, not the order of the bases, is the fingerprint every matching window has to reproduce.

Step 2: Prime the first window

Tally the first len(marker) bases of sequence. If that tally already equals the marker's fingerprint, index 0 is a hit before the slide even starts.

Step 3: Shift one base at a time

Sliding the window one step right is exactly two edits: the base coming in gets its count bumped, the base going out gets decremented. Compare the updated tally to the marker's; when they agree, record the window's start index.

The solution

Sliding window with frequency-map comparison
def find_marker_windows(sequence, marker):
    if len(marker) > len(sequence):
        return []
    target = {}
    for base in marker:
        target[base] = target.get(base, 0) + 1
    width = len(marker)
    window = {}
    for i in range(width):
        base = sequence[i]
        window[base] = window.get(base, 0) + 1
    starts = []
    if window == target:
        starts.append(0)
    for i in range(width, len(sequence)):
        enter = sequence[i]
        window[enter] = window.get(enter, 0) + 1
        leave = sequence[i - width]
        window[leave] -= 1
        if window[leave] == 0:
            del window[leave]
        if window == target:
            starts.append(i - width + 1)
    return starts

Common follow-up questions