The Deceptive Anagram Question (nafiulis.me)

^ This was remarked about a correct, but slow algorithm.

I couldn't figure out the deception part either.

"In the same order" is an unnecessary additional complexity. Asking for an O(1) solution demonstrates the exact same thought quality, so it's a bad (overly complicated and longer to answer) interview question for the purpose intended.

also, you can define a order independent hashing function, that just maybe assigns prime numbers to each letter and adds them up....

instead...

hashed_words = {}

anagrams = []

for word in words:

  h = compute_hash(word)

  w = hashed_words.get(h)

  if w == True
  // we've already encountered another anagram, just add it

    anagrams.append(word)

  elsif w

   //case where both w and word are anagrams, so append both to list

   // and set the value to True, so we can shortcircuit this operation in the future

   anagrams.append(w); anagrams.append(word);

   hashed_words[h] = True //flag indicating weve seen this word before

  else

    // first time we are seeing this, so lets just set it

   hashed_words[h] = word

is something author didnt bother to test at all. His word list includes words with apostrophes (hex #27), like basic's, his code accounts only for ascii letters and crashes on that list :)

> its O(26) for list creation

hmm, no? unless python people create lists one element at a time ...tested and yes they do :o :D every additional byte takes ~10ms on my test computer(110K elements loop), hilarious :))) Its cheaper to create two lists outside main loop, and simply copy empty list over the work list instead of creating new list every time (or resetting global list manually), we are talking ~10% of whole algorithms time cheaper. Python is one hilarious way of benchmarking algorithms. Simple x=1 in your main loop will cost tens of milliseconds.

>and its O(26) for creating the tuple

Ehhh :/ Yes, sorting is faster in python, ONLY because sort function is highly optimized low level code, while anything you write yourself will be extremely slow due to interpreted nature of the language. You can easily write O(n) hash routine in low level language (assembler, c) and beat nlogn sort.

>But, I think this time, we can actually use collections.Counter correctly

correctly? yes, faster? NO, ~10% slower. Again seems author simply assumed something is going to work and didnt test.

All in all main lesson from all this should be not use python to gauge algorithms speed, unless you are being hired to write speed critical python code (ahahahaha).

  cnt=Counter(tuple(Counter(w).iteritems()) for w in words)
  print [w for w in words if cnt[tuple(Counter(w).iteritems())] > 1]

  new [] {"pool", "loco", "cool", "stain", "satin", "pretty", "nice", "loop"}
  .Aggregate (
    new { Index = 0, Found = new Dictionary<string, List<WordAndIndex>>() },
    (acc, word) =>
      {
        acc.Found
          .FindOrCreate(word.Sort())
          .Add(new WordAndIndex(word, acc.Index));
						
        return new { Index = acc.Index + 1, Found = acc.Found };
      }
  )
  .Found
  .Where(f => f.Value.Count() > 1)
  .SelectMany(f => f.Value)
  .OrderBy(wordAndIndex => wordAndIndex.Index)
  .Select(wordAndIndex => wordAndIndex.Text)

I was fairly happy with this, but curious to see what he'd come up with in the end. I like it - especially the way it uses indices and zip. Here's my translation to C# (no helpers added here!):

  IEnumerable<string> Anagrams(IEnumerable<string> words)
  {
    Func<string, string> sortLetters =
      (s) => new string(s.ToCharArray().OrderBy(c => c).ToArray());
	
    var sortedWords = words.Select(sortLetters);
		
    var sortedWordsLookup = sortedWords.ToLookup(s => s);
	
    return words.Zip(
      sortedWords,
      (word, normal) => new { word, normal }
    )
    .Where(
      (wordAndSortedWord) =>
        sortedWordsLookup[wordAndSortedWord.normal].Count() > 1
    )
    .Select(wordAndSortedWord => wordAndSortedWord.word);
  }