0

Count reverse-complement DNA strand pairs

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Count reverse-complement DNA strand pairs

Companies: Amazon

Difficulty: Medium

Problem statement

You are given a list of DNA strands. Each strand is a non-empty string over the alphabet A, C, G, T.

The reverse complement of a strand is formed by reversing it and then replacing each base with its partner: A with T, T with A, C with G, and G with C. For example, the reverse complement of AACG is CGTT.

Two strands at indices i < j form a special pair when strands[j] is the reverse complement of strands[i]. Because taking the reverse complement twice gives back the original strand, the relation is symmetric.

Implement:

  • count_special_pairs(strands: list[str]) -> int: the number of special pairs.
  • list_special_pairs(strands: list[str]) -> list[tuple[int, int]]: every special pair (i, j) with i < j, sorted.

Raise ValueError if a strand is empty or contains a character outside ACGT.

Constraints

  • 0 <= len(strands) <= 10^5
  • The total length of all strands is at most 10^6.
  • Strands may repeat. Every copy counts as a separate index.

Example 1

strands = ["AACG", "CGTT", "GGA", "TCC", "CGTT"]
count_special_pairs(strands)  -> 3
list_special_pairs(strands)   -> [(0, 1), (0, 4), (2, 3)]

CGTT is the reverse complement of AACG (twice), and TCC is the reverse complement of GGA.

Example 2

strands = ["ACGT", "ACGT", "AC", "CA"]
count_special_pairs(strands)  -> 1

ACGT is its own reverse complement, so its two copies form one pair. AC and CA are only reverses of each other, so they do not form a pair (the reverse complement of AC is GT).

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

Two strands form a special pair when one is the reverse complement of the
other: reverse the strand, then swap A↔T and C↔G. Reverse complement is an
involution (rc(rc(s)) == s), so the relation is symmetric. Checking
strands[j] == rc(strands[i]) covers both directions.

Brute force. Compare every pair (i, j), computing rc(strands[i]) and
comparing strings. That is O(n² · L) for n strands of length up to L. It is
fine to state, but it times out at n = 10^5.

Hash map, one pass. Walk the strands left to right. Keep a map of
strand -> how many times it appeared so far. For each strand s, every
earlier copy of rc(s) forms a pair with it, so add seen[rc(s)] to the
answer, then record s. Each pair (i, j) is counted exactly once, at the
moment j is processed.

Invariant: after processing index j, total equals the number of special
pairs with both indices ≤ j, and seen holds the counts of strands 0..j.

Edge cases that trip people up:

  • Self-complementary strands (palindromes in the DNA sense, e.g. ACGT,
    AT). Here rc(s) == s, so k copies give k·(k−1)/2 pairs. The
    "look left, then insert" order handles this. Inserting first would pair a
    strand with itself.
  • Odd-length strands can never be self-complementary, because the middle
    base would have to be its own complement.
  • Reverse vs. reverse complement. AC and CA are reverses but not a
    pair. AC pairs with GT.
  • Reject characters outside ACGT instead of silently mismatching.

To list the pairs rather than count them, store the indices for each strand
instead of a count. The work is then O(total length + number of pairs). That
is the best possible, since the output itself can be Θ(n²), e.g. n/2 copies of
A and n/2 copies of T.

Code

from collections import defaultdict

_COMPLEMENT = str.maketrans("ACGT", "TGCA")
_VALID = frozenset("ACGT")


def reverse_complement(strand: str) -> str:
    """Reverse the strand and swap A<->T, C<->G."""
    return strand.translate(_COMPLEMENT)[::-1]


def _check(strand: str) -> None:
    if not strand or not set(strand) <= _VALID:
        raise ValueError(f"invalid strand: {strand!r}")


def count_special_pairs(strands: list[str]) -> int:
    """Number of index pairs i < j where strands[j] == reverse_complement(strands[i])."""
    seen: dict[str, int] = defaultdict(int)  # strand -> occurrences so far
    total = 0
    for s in strands:
        _check(s)
        total += seen[reverse_complement(s)]  # partners to the left of s
        seen[s] += 1
    return total


def list_special_pairs(strands: list[str]) -> list[tuple[int, int]]:
    """All special pairs (i, j), i < j, sorted. Output-sensitive: O(total length + pairs)."""
    positions: dict[str, list[int]] = defaultdict(list)
    pairs: list[tuple[int, int]] = []
    for j, s in enumerate(strands):
        _check(s)
        for i in positions.get(reverse_complement(s), []):
            pairs.append((i, j))
        positions[s].append(j)
    pairs.sort()
    return pairs


class SpecialPairCounter:
    """Streaming version: strands arrive one at a time, query the running count."""

    def __init__(self) -> None:
        self._seen: dict[str, int] = defaultdict(int)
        self._total = 0

    def add(self, strand: str) -> int:
        """Add a strand; return how many new special pairs it created."""
        _check(strand)
        new_pairs = self._seen[reverse_complement(strand)]
        self._seen[strand] += 1
        self._total += new_pairs
        return new_pairs

    def remove(self, strand: str) -> int:
        """Remove one copy of a strand; return how many pairs disappeared."""
        if self._seen.get(strand, 0) == 0:
            raise KeyError(strand)
        self._seen[strand] -= 1
        lost = self._seen[reverse_complement(strand)]
        self._total -= lost
        return lost

    @property
    def total(self) -> int:
        return self._total

Complexity

Let n be the number of strands and S the total number of characters.

  • reverse_complement: O(L) time and space for a strand of length L.
  • count_special_pairs: O(S) expected time, since each strand is hashed and
    reverse-complemented once. Space O(S) for the map keys.
  • list_special_pairs: O(S + P log P) time where P is the number of pairs
    (the sort; drop it and output is already grouped by j). Space O(S + P).
  • SpecialPairCounter.add / remove: O(L) each. total is O(1). Space
    O(S) over all live strands.

Test cases

  • ["AACG", "CGTT", "GGA", "TCC", "CGTT"] → count 3, pairs
    [(0, 1), (0, 4), (2, 3)].
  • ["ACGT", "ACGT", "ACGT"] → 3 (self-complementary, C(3,2)).
  • ["AT", "AT"] → [(0, 1)].
  • ["A", "T", "A", "T"] → 4 (each A with each T).
  • ["AC", "CA"] → 0 (reverse only, not reverse complement).
  • ["A"] → 0. [] → 0.
  • ["ACGU"] → ValueError (invalid base).
  • Randomized: 300 random lists of short strands, checked against the O(n²)
    brute force for both the count and the pair list.

Follow-ups

  1. Streaming / deletions. Strands arrive and leave over time; report the
    running count. Keep the same counter map. On add(s) add seen[rc(s)]
    before incrementing. On remove(s) decrement first, then subtract
    seen[rc(s)]. That order is what keeps self-complementary strands correct.
    See SpecialPairCounter.
  2. Very long strands / memory. Store a hash of each strand instead of the
    string. Use a rolling (polynomial) hash and compute the hash of rc(s) in
    the same pass, by reading s backwards with complemented bases. That avoids
    building the reversed string. Mention collisions: use 64-bit or double
    hashing, and verify on a hit when exactness matters.
  3. Allow one mismatch. A pair is special if strands[j] differs from
    rc(strands[i]) in at most one position (equal lengths). For each strand,
    generate L wildcard keys (rc(s) with position p replaced by *) and
    look up how many earlier strands produced the same masked key. Exact matches
    appear under all L keys, so count them separately and subtract (L−1)·exact.
    Cost O(S · L) for the masked strings, or O(S) with hashes.
  4. Partial overlap. Two strands pair if a suffix of one, of length ≥ k,
    is the reverse complement of a prefix of the other (how strands anneal).
    Index the length-k reverse-complemented prefixes in a hash map, or use a
    trie/Aho-Corasick over reverse complements. Then for each strand check its
    suffixes. Discuss O(S · L) vs. automaton approaches.
  5. Distributed data set. Billions of strands across machines. Shard by
    the canonical key min(s, rc(s)), so a strand and its partners land on the
    same shard. Each shard computes C(k,2) for self-complementary keys or
    count[s] · count[rc(s)] otherwise, then sum across shards.

Interviewer expectations

Mid-level (L4)

  • Defines reverse complement correctly and states the O(n²) brute force.
  • Reaches the one-pass hash map and gets the count right on a simple example.
  • Handles empty input and invalid bases when prompted.

Senior (L5)

  • Spots the self-complementary case without a hint and explains why "look up,
    then insert" avoids self-pairing.
  • Gives precise complexity in terms of total characters, not just n.
  • Distinguishes counting from listing, and notes the output can be Θ(n²).
  • Extends cleanly to streaming adds and removes.

Staff (L6+)

  • Proposes the canonical form min(s, rc(s)) and uses it for sharding and
    for the closed-form count.
  • Talks through rolling hashes for long strands, collision risk, and when to
    verify.
  • Handles the one-mismatch and overlap variants with sound complexity
    arguments and clear trade-offs.

Sign in to comment, vote or remix.