Group a list of words into anagrams.
Sort each word's characters to get a canonical key, then bucket words by that key using a hash map. This turns an O(n²) brute-force comparison into a clean O(n · k log k) single pass, where k is the max word length.
How to think about it
The interviewer is checking whether you reach for pairwise comparison or for a canonical key. Comparing every word against every other to test “are these anagrams?” is O(n²) and fiddly. The senior move is to notice that anagrams are equivalent under a transformation — sort their letters and they collapse to the same string — so you can fingerprint each word once and let a hash map do the grouping.
The fingerprint is the whole trick. "eat", "tea", and "ate" all sort to "aet", so that sorted string becomes a bucket key. Walk the list once: for each word compute key = "".join(sorted(word)), append the original word to buckets[key], and at the end the dict’s values are your groups. One pass, one defaultdict, no word ever compared against another.
A worked example
from collections import defaultdict
def group_anagrams(words):
buckets = defaultdict(list)
for word in words:
key = "".join(sorted(word)) # canonical fingerprint
buckets[key].append(word)
return list(buckets.values())
# Sort within each group and across groups so the printout is stable
def show(words):
groups = [sorted(g) for g in group_anagrams(words)]
groups.sort()
print(groups)
show(["eat", "tea", "tan", "ate", "nat", "bat"])
show(["a", "b", "a"]) # single-character words
show(["", "a", ""]) # empty string is its own group
show(["listen", "silent", "hello"])[['ate', 'eat', 'tea'], ['bat'], ['nat', 'tan']]
[['a', 'a'], ['b']]
[['', ''], ['a']]
[['hello'], ['listen', 'silent']]The first line is the payoff: six words fell into three buckets without a single pairwise check — eat/tea/ate share the key aet, tan/nat share ant, and bat stands alone. The last line shows the same mechanism shrug off a near-miss: listen and silent are anagrams and group together, while hello keeps to itself. (The sorting around the print is only to make the output deterministic; the real grouping is order-independent, and a hash map’s bucket order is not something to rely on.)