Group Anagrams

1. The obvious way

   Compare every pair of words as anagrams and merge groups: O(n² x length).

2. The key insight

   Give every word a sticker that is the same for all its anagrams (its letters sorted). A dictionary from sticker to the list of words does all the grouping in one pass.

3. The algorithm
   1. Prepare empty pigeon-holes (a dictionary of lists).
   2. For each word, make its sticker by sorting its letters.
   3. Drop the word into the pigeon-hole with that sticker.
   4. At the end, every non-empty pigeon-hole is one group.

Watch it run

aet: [eat]

from collections import defaultdict

def group_anagrams(words):
    holes = defaultdict(list)                  # sticker -> words
    for word in words:
        sticker = "".join(sorted(word))        # letters in alphabetical order
        holes[sticker].append(word)
    return list(holes.values())

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.