4
\$\begingroup\$

The task was to check for pairs of anagrams in a string list.

  1. I first sorted all the words. and looped over the letters.
  2. The interview continues with a follow-up, to do the same with limited memory. I tried to implement a Hash function.

The dictionary return value is only for my convince in order to see all the pairs. I could just print it into the console instead.

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Security.Cryptography;
    using System.Text;
    using System.Threading.Tasks;

    namespace ConsoleApplication2
    {
    public class ReverseString
    {
        public ReverseString()
        {                 
            List<string> anagarms = new List<string>();
            anagarms.Add("Gilad");
            anagarms.Add("dilaG");
            anagarms.Add("bat");
            anagarms.Add("but");
            anagarms.Add("utb");
            pairs = PairAnagrams(anagarms);
            pairs = PairAnagramsHash(anagarms);
        }

        Dictionary<string, string> PairAnagrams(List<string> wordsList)
        {
            Dictionary<string, string> dictionary = new Dictionary<string, string>();
            foreach(var item in wordsList)
            {
                if (dictionary.ContainsValue(item))
                {
                    continue;
                }
                foreach(var item2 in wordsList)
                {
                    if(item.Length != item2.Length || item.Equals(item2))
                    {
                        continue;
                    }

                    var sortedWord1 = item.ToArray();
                    Array.Sort(sortedWord1);
                    var sortedWord2 = item2.ToArray();
                    Array.Sort<char>(sortedWord2);
                    int i;
                    for (i = 0; i < sortedWord2.Length; i++)
                    {
                        if (sortedWord2[i] != sortedWord1[i])
                        {
                            break;
                        }
                    }
                    if(i == sortedWord1.Length)
                    {
                        dictionary.Add(item, item2);
                    }
                }
            }
            return dictionary;
        }

        Dictionary<string, string> PairAnagramsHash(List<string> wordList)
        {
            Dictionary<string, string> dictionary = new Dictionary<string, string>();

            foreach (var item in wordList)
            {
                foreach (var item2 in wordList)
                {
                    if (item.Equals(item2) || dictionary.ContainsKey(item2))
                    {
                        continue;
                    }
                    if (HashFunction(item) == HashFunction(item2))
                    {
                        dictionary.Add(item, item2);
                    }
                }
            }
            return dictionary;
        }

        public int HashFunction(string word)
        {
              int result = 0;
              var charArray = word.ToArray();
              for (int i = 0; i < word.Length; i++)
              {
                  result += charArray[i] * 37;
              }
              return result;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ limited space, like make your code shorter? Use linq blackwasp.co.uk/LinqAnagramCheck.aspx tipsandtricks.runicsoft.com/CSharp/StringReverse.html I'd also be hesitant about working for companies that make you start programming before you actually work for them unless they pay for it. \$\endgroup\$ – prospector Dec 14 '14 at 20:19
  • \$\begingroup\$ limited memory that is...not space. \$\endgroup\$ – Gilad Dec 14 '14 at 20:36
  • \$\begingroup\$ @Prospector it's not a task it is an interview question. \$\endgroup\$ – Gilad Dec 14 '14 at 20:37
  • \$\begingroup\$ if you actually have to write code and not answer actual questions, then it's a task. \$\endgroup\$ – prospector Dec 14 '14 at 20:40
  • 3
    \$\begingroup\$ @prospector: I would have serious doubts about any organisation hiring developers without evaluating skills with at least a simple programming exercise. \$\endgroup\$ – SylvainD Dec 14 '14 at 21:54
2
\$\begingroup\$

Algorithm of PairAnagrams()

You are calling

var sortedWord1 = item.ToArray();
Array.Sort(sortedWord1);

inside the inner loop, but item won't change there.

One time you are using Array.Sort(sortedWord1); and two lines below Array.Sort<char>(sortedWord2); Be consistent in your style.

This

for (i = 0; i < sortedWord2.Length; i++)
{
    if (sortedWord2[i] != sortedWord1[i])
    {
        break;
    }
}
if (i == sortedWord1.Length)
{
    dictionary.Add(item, item2);
}  

can be replaced by

if (sortedWord1.SequenceEqual(sortedWord2))
{
    dictionary.Add(item, item2);
}  

By using .Where() on the wordList at the for each you can omit the check for length and equal.

By using the .OrderBy() on the chars of the words, there won't be a need to call .ToArray() and Array.Sort().

This reduces the code to

Dictionary<string, string> PairAnagrams(List<string> words)
{
    Dictionary<string, string> pairedAnagrams = new Dictionary<string, string>();
    foreach (var word in words)
    {
        if (pairedAnagrams.ContainsValue(word))
        {
            continue;
        }

        var sortedWord1 = word.OrderBy(c => c);
        int wordLength = word.Length;
        foreach (var word2 in words.Where(w => w.Length == wordLength && !word.Equals(w)))
        {
            if (sortedWord1.SequenceEqual(word2.OrderBy(c => c)))
            {
                pairedAnagrams.Add(word, word2);
            }
        }
    }
    return pairedAnagrams;
}

Constructor

The constructor of an object should be used only for constructing the object. You are misusing it to start the action.

Naming

  • variable names should be correctly spelled. anagarms vs anagrams
  • parameters should't be pre/post fixed by their types. List<string> wordsList-> List<string> words

General

  • no need for using System.Security.Cryptography
\$\endgroup\$
1
\$\begingroup\$

Challenged by a friend, I did this in C the other day. My hash-code proceeded as follows for a string S[i] where i ranges 1 to n.

  1. Assign each letter of the alphabet to an odd prime P(Letter).(P(A)=3,P(B)=5,P(C)=7...)
  2. Set H=0
  3. For each letter S[i] in the string S
  4. Calculate T=(P(S[i])-1)/2
  5. Calculate H=2*H*T+H+T
  6. End Loop
  7. Return H as Hash-code.

This has the nice property that is invariant for the order of letters (essential for anagrams!) and by the Fundamental Theorem of Arithmetic is collision low. Notice the hash-code is H such that 2*H+1 is the product P(S[1])P(S[2])...*P(S[n]). Without that transform the hashcode is 100% biased in the lowest bit. If we use 2 as one of the primes it tends to degrade the hash-code if K such that P(K)=2 occur frequently in the string being hashed.

In terms of performance it can find all the anagram pairs in a 179,000 input table of English words in just over a 1s on a mid-range laptop with a hash-table with only 20K buckets.

That word list was a 179,000 word plain-text English dictionary.

It found no 32-bit collisions. That is where H is 32-bits no two words were found where H(W1)=H(W2).

If it helps I'll dig it out and put it up for review.

Performance is theoretically improved by assigning low primes to the most frequent letters. But given you can't get fewer than zero full-length collisions it hardly seems worth the worry.

\$\endgroup\$
  • 1
    \$\begingroup\$ Gödel would have been proud! +1 \$\endgroup\$ – safkan Dec 21 '14 at 2:20
  • \$\begingroup\$ @safkan Of course his encoding is order dependent. But I suppose any scheme that puts the FTA with symbol encodings is going to bring him to mind. stackoverflow.com/questions/396005/… \$\endgroup\$ – user59064 Dec 21 '14 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.