Names that are almost the same: A Sample Coding Interview Solution

The coding question

You're given a name and a list of names. Return the names that become the original if you swap exactly two letters. Then, as a follow-up, return the names that need the fewest letter changes to become an anagram of it.

Ask a few questions first

Ask	What we'll assume
Upper and lower case?	Assume everything's lowercase. In real code, lowercase both sides first.
Does a name identical to the original count?	Only if it has a repeated letter, since swapping two equal letters keeps it the same. So 'anna' counts for 'anna', but 'omar' doesn't count for 'omar'.
Follow-up: what's a letter change?	Replacing one letter with any other letter. The length stays the same, so names of a different length are skipped.
Follow-up: does the original itself count?	No, we'll leave out exact copies.
Follow-up: ties?	Return every name that has the fewest changes. If some are already anagrams, that's 0 changes and those win.
Keep the list's order?	Yes, and keep duplicates if the list has them.

A couple of examples

Input	Output
name = 'omar', names = ['omra', 'amor', 'roma', 'omar', 'oma']	Swap: ['omra', 'amor']. Fewest changes: ['omra', 'amor', 'roma'] (0 changes)
name = 'anna', names = ['anna', 'naan', 'nana', 'aann']	Swap: ['anna', 'nana', 'aann']. Fewest changes: ['naan', 'nana', 'aann'] (0 changes)
name = 'omar', names = ['mark', 'moon', 'oman', 'ramp', 'karl']	Swap: []. Fewest changes: ['mark', 'oman', 'ramp'] (1 change each)
name = 'ab', names = ['ba', 'ab', 'aa']	Swap: ['ba']. Fewest changes: ['ba']

Start with brute force

For each candidate, try swapping every pair of letters and check whether the result equals the original. For the follow-up, try every rearrangement of the original, count how many spots differ from the candidate, and keep the smallest.

Cost: With names of length L, there are about L² swaps and each check costs L, so O(L³) per candidate. The follow-up is far worse: there are L! rearrangements, so even a 10-letter name means millions of tries per candidate.

A better way

For the swap check, you don't need to try swaps. Walk both names once and write down where they differ. If they differ in exactly two spots, i and j, they match when the letters crossed over: original[i] is other[j] and original[j] is other[i]. If they differ nowhere, they match only if the name has a repeated letter. Anything else isn't one swap.

For the follow-up, position doesn't matter, only which letters you have. Count letters with a hash map once for the original. For each other name, count how many of its letters have a partner in the original: for each letter, that's the smaller of the two counts. Every letter without a partner has to change, and since the lengths match, there's always a missing letter to change it into.

So changes = length − shared letters. Keep the smallest number seen so far and the names that hit it.

Swap check: if the lengths are different, it's not a match.
Collect every position where the two names differ.
No differences: match only if some letter appears twice in the name.
Exactly two differences: match if the letters at those spots are crossed. Any other count isn't a match.
Follow-up: count the original's letters once. For each other name, skip exact copies and different lengths.
Work out shared letters (the overlap of the two counts) and changes = length − shared.
If that's a new smallest, start a fresh result list. If it ties, add the name to the list.

The code

solution.pypython

from collections import Counter


def one_swap_away(name, other):
    if len(name) != len(other):
        return False
    diffs = [i for i in range(len(name)) if name[i] != other[i]]
    if not diffs:
        # Same name: swapping two equal letters keeps it the same.
        return len(set(name)) < len(name)
    if len(diffs) != 2:
        return False
    i, j = diffs
    return name[i] == other[j] and name[j] == other[i]


def swap_matches(name, names):
    return [other for other in names if one_swap_away(name, other)]


def changes_to_anagram(target, other):
    # Letters in other with no partner in the original have to change.
    shared = sum((Counter(other) & target).values())
    return len(other) - shared


def closest_anagrams(name, names):
    target = Counter(name)
    best, result = None, []
    for other in names:
        if other == name or len(other) != len(name):
            continue
        changes = changes_to_anagram(target, other)
        if best is None or changes < best:
            best, result = changes, [other]
        elif changes == best:
            result.append(other)
    return result

	Cost	Why
Time	O(N × L)	N names, and each check walks the name once or counts its letters once
Space	O(L + N)	The differences and letter counts are at most the length of a name, plus the result list

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

Names of different lengths. Not a swap match, and skipped for the follow-up.
The same name with no repeated letters, like 'omar'. Not a match for the swap rule.
The same name with a repeated letter, like 'anna'. A match for the swap rule.
Three letters rotated, like 'abc' and 'bca'. They differ in three spots, so not one swap, but they're 0 changes from an anagram.
No name has the same length as the original. The follow-up returns an empty list.
Empty strings. No differences and no repeated letter, so not a swap match.

Common mistakes

Only checking that there are two differences, without checking the letters actually cross. 'ab' and 'cd' differ in two spots but aren't a swap.
Using anagram logic for the swap question. 'roma' is an anagram of 'omar', but it needs more than one swap.
Forgetting the identical-name case, and either always or never counting it.
Counting changes by comparing position by position. 'roma' differs from 'omar' in every spot, but it needs 0 changes to be an anagram.
Counting the original's letters again for every name instead of once.

Follow-up questions

What if you have to answer this for many different original names against the same big list?

For exact anagrams, group the list ahead of time by the letter counts as a tuple. Then the anagrams of any name are one dictionary lookup. For fewest changes you still need to look at each same-length name, but you can group by length to skip the rest.

What about names that are one typo away, like an added or missing letter?

That's edit distance. For a single edit you can walk both names with two pointers and allow one skip. For larger distances, use dynamic programming.

What if names can have accents or other alphabets?

Counting with a hash map still works on any characters. Normalize the text first, so the same letter written two ways counts as one.

How the time adds up

Minutes	What you're doing
0–5	Ask about case, duplicates and identical names
5–10	Brute force: try every swap, and every rearrangement
10–20	Compare positions once, and count shared letters for the follow-up
20–35	Write the code
35–40	Test it on the examples and edge cases
40–45	Follow-up questions

Key concepts used here

Hash maps and sliding windowsSwap nested loops for a single pass.

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by DoorDash.