The Word Families

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
Equifax

Problem

We're consolidating a search-term log into anagram families: every entry in words belongs to the family holding all of its anagrams, and a term logged twice appears in its family twice. Return the families, each in alphabetical order and listed by their first word.

Different spellings, same letters - they belong together.

Example 1

Input:

words = ["eat","tea","tan","ate","nat","bat"]

Output:

[["ate","eat","tea"],["bat"],["nat","tan"]]

Example 2

Input:

words = ["a"]

Output:

[["a"]]

Worked solution and explanation

What this really is

This is a bucketing problem dressed up as a search-log cleanup. The skill is turning each word into a signature that ignores letter order, so 'tea' and 'ate' collide on the same key, and then honoring an output order the grader checks exactly. Anyone can see that anagrams share letters. What separates candidates is the next move: key on the raw word and you get six singletons back; hold each family in a set and the second 'listen' in ['listen', 'silent', 'listen'] quietly disappears. Skip the two sorts and the families come back in whatever order the dict first saw them, which fails every exact-match case.

Building it

Step 1: Give every word an order-free signature

Sorting a word's letters and joining them back, "".join(sorted(word)), maps 'eat', 'tea' and 'ate' to the same string 'aet'. Two words share a signature exactly when they are anagrams. That is the whole test, and it costs one small sort per word instead of comparing every pair.

Step 2: Bucket into lists, not sets

Each signature points at a list, and every occurrence of a word is appended to it. A list keeps the repeated 'listen'; a set would fold it into one and change the graded answer.

Step 3: Sort inside, then sort across

Sort each family alphabetically, then sort the list of families. Identical words always land in the same family, so no two families can start with the same word, and plain list comparison orders them by first word without a second key.

The solution

Signature buckets, then two sorts
def anagram_groups(words: list) -> list:
    families = {}
    for word in words:
        signature = "".join(sorted(word))
        if signature not in families:
            families[signature] = []
        families[signature].append(word)

    result = []
    for signature in families:
        family = families[signature]
        family.sort()
        result.append(family)

    # No two families share a first word, so sorting the lists
    # compares first words and nothing else.
    result.sort()
    return result
Returning the buckets as built
list(families.values()) gives [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]. The grouping is right, but the order follows first appearance, so the exact-match grade fails.
Sorting inside and across
[['ate', 'eat', 'tea'], ['bat'], ['nat', 'tan']]: each family is alphabetical and the families are listed by their first word, giving the same answer on every run.

Common follow-up questions