Valid Anagram

1. The obvious way

   Sort both words and compare them: O(n log n).

2. The key insight

   Two words are anagrams exactly when their letter counts are equal. Count the first word's letters up, then cross them out using the second word. If a letter would go below zero, or the lengths differ, they are not anagrams.

3. The algorithm
   1. Different lengths? Not anagrams. Stop.
   2. Count every letter of the first word on a tally sheet.
   3. Walk through the second word and cross out each letter from the tally.
   4. A letter you cannot cross out (tally already 0)? Not anagrams. Otherwise they are.

Watch it run

tally: r=1 a=1 t=1

from collections import Counter

def is_anagram(first, second):
    if len(first) != len(second):
        return False
    tally = Counter(first)               # letters of the first word
    for letter in second:
        tally[letter] -= 1               # cross one out
        if tally[letter] < 0:            # second has a letter first does not
            return False
    return True

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.