Shared sightings

Two volunteers walk two transects of the same reserve and each writes down every bird they hear. The warden wants the species both of them found.

The problem

Each volunteer hands in a checklist: a list of three-letter species codes, in the order the birds were heard. A code can repeat — a wren calling four times along the hedge is written four times — and the two walks are different lengths.

Produce the codes that appear on both checklists. Each shared code appears once in the answer, however often it was heard, and the answer is in alphabetical order so two wardens comparing printouts see the same page.

Input. transect_a and transect_b — two lists of species codes, each code a string of three uppercase letters. Either list may be empty.

Output. A sorted list of the codes present in both, with no repeats.

Example.

transect_a = ["RBH", "GRW", "GRW", "SKY"]
transect_b = ["SKY", "GRW", "BUZ"]        ->  ["GRW", "SKY"]

GRW was heard twice on the first walk and once on the second; it is reported once. RBH and BUZ were each heard on one walk only.

A second example, where every entry is the same bird:

transect_a = ["WGT", "WGT", "WGT"]
transect_b = ["WGT", "WGT"]               ->  ["WGT"]

Five entries collapse to one code. Counting matches instead of collecting codes would report two, or three, or six.

Constraints.

• 0 <= len(transect_a) <= 10^5
• 0 <= len(transect_b) <= 10^5
• Every code is exactly three uppercase letters.

Hints

Approach

Brute force

For each of the n codes on the first walk, scan all m codes on the second looking for a match, then check the answer so far to avoid writing a duplicate. That is n * m comparisons — with both walks at their limit, 10^10 of them, before the duplicate check adds more.

The insight

The inner scan answers a membership question, and a hash set answers the same question in constant time.

Rescanning transect_b costs m steps and learns nothing new each time — the list never changes. Reading it once into a set replaces every one of those scans with a single probe. The set also solves the duplicate problem for free: adding a code that is already there does nothing, so the result set holds each shared code exactly once no matter how many times it was heard.

Algorithm

1. Build a set from transect_a.
2. Start an empty result set.
3. Walk transect_b. If the code is in the first set, add it to the result set.
4. Return the result set sorted.

Complexity

Time O(n + m + s log s) — one pass over each list, then a sort of the s shared codes, which is at most 26^3 entries. Space O(n + s) for the lookup set and the result.

Solution

"""Shared sightings — one pass to build a lookup set, one pass to probe it."""


def solve(transect_a, transect_b):
    # A set answers "was this code recorded here?" in constant time, so the
    # second walk never rescans the first list.
    recorded_on_a = set(transect_a)
    both = set()
    for code in transect_b:
        if code in recorded_on_a:
            both.add(code)          # invariant: `both` holds each shared code once
    return sorted(both)

TESTS = [
    ((["RBH", "GRW", "GRW", "SKY"], ["SKY", "GRW", "BUZ"]), ["GRW", "SKY"]),
    ((["WGT", "WGT", "WGT"], ["WGT", "WGT"]), ["WGT"]),
    ((["RBH", "RBH"], ["SKY", "BUZ"]), []),
    (([], ["SKY"]), []),
    ((["SKY"], []), []),
    ((["BUZ", "SKY", "GRW"], ["GRW", "SKY", "BUZ"]), ["BUZ", "GRW", "SKY"]),
]

Pitfalls

• Appending to a list instead of a set. On the second example that returns ["WGT", "WGT"], one entry per match on the second walk, not one per species.
• Using code in transect_a on the raw list. It reads correctly and is still a scan, so the runtime stays at n * m; the set only helps if you build it.
• Returning the set itself. The caller expects sorted output, and set iteration order is not alphabetical — sort before returning.
• Skipping the empty-list case. If one volunteer heard nothing, the answer is [], and any code that indexes transect_b[0] first will fail on it.

Variants

• Ribbon pairs — the same swap from rescan to lookup, but the map has to remember where each value sat, not just that it was seen.