String reverse and pairing reversed words

Question

These are questions from an interview:

1. Reverse a string
2. Find matching anagrams in a word list

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

namespace ConsoleApplication2
{
public class ReverseString
{
    public ReverseString()
    {
        string str = "Gilad";
        string res = Reverse(str);

        List<string> wordsList = new List<string>();
        wordsList.Add("batel");            
        wordsList.Add("Gilad");
        wordsList.Add("daliG");
        wordsList.Add("enon");
        wordsList.Add("none");
        wordsList.Add("letab");
        var pairs = PairAnagramWords(wordsList);
    }

    public string Reverse(string str)
    {
        StringBuilder s = new StringBuilder();
        for (int i = str.Length - 1; i >= 0; i--)
        { 
            s.Append(str[i]);
        }
        return s.ToString();
    }

    Dictionary<string, string> PairAnagramWords(List<string> wordsList)
    {
        wordsList.Sort();
        Dictionary<string, string> res = new Dictionary<string, string>();
        foreach (var item in wordsList)
        {
            if (res.ContainsValue(item))
            {
                continue;
            }

            foreach (var item2 in wordsList)
            {
                if (item == item2 || item.Length != item2.Length)
                {
                    continue;
                }
                var reversed = Reverse(item2);
                int i;
                for (i = 0; i < item.Length; i++)
                {
                    if (item[i] != reversed[i])
                    {
                        break;
                    }
                }
                if (i == item.Length)
                {
                    res.Add(item, item2);
                }
            }
        }
        return res;
    }
}

}

I don't like the fact that I'm doing it in \$ O(n^2) \$, although I am checking for no repetitions.

Please review my code's complexity and algorithm. I did the testing inside the constructor just for convenience, although I usually will use unit tests.

Answer 1

Please find my (language agnostic) suggestions below :

1. String reversal:

   • Use the same string variable and swap i and (len-i-1) characters? -> O(n/2).
   • Your program caters to str == reverse(str) and not anagrams in general, i.e gilad == dalig is checked but not gilad == gliad / gladi / ladig / glaid ,etc

2. Anagram finder: Here are the multiple ways to do it:

   • A hash function on each String which generates a unique number for string with same letters. Could be a unique prime mapping to each character and

     H(S) = P1 * p2 * ... => H(gilad) = P(g) * p(i) * P(l) * P(a) * P(d)

   • Sort each string, Sort the array and traverse to find anagrams. {"gilad","glaid","bat","tac","act","tab"} = {"adgil", "adgil" ,"abt", "act", "act", "abt"} // Sort each string = {"abt","abt","act","act", "adgil", "adgil"} // Sort the array. = Traverse to know the anagrams.

   • Use Trie to store sorted strings. Each traversal of the string will point to its anagram i.e Once gilad => adgil is added to the trie, addition of "glaid" = "adgil" will point to its early existence and hence its anagram.

   • Use a HashMap to store the sorted string and you would easily find the anagrams.

Answer 2

Reverse

Your Reverse function is functional, but there are some improvements I could suggest:

1. if you use the StringBuilder approach (which is OK), then you should at least initialize the size of the internal capacity so that resizes are not needed later (for performance reasons). Use StringBuilder s = new StringBuilder(str.Length);
2. While looking at that, why have the variable name s ... that's a poor choice.
3. Consider using a char[] array for the reverse as it reduces some more overheads (again, performance). StringBuilders are useful for many things, but their biggest benefit comes from their dynamic nature. In this case, that nature is not needed.

If it was me, I would have:

    public string Reverse(string forward)
    {
        char[] chars = forward.ToCharArray();
        var last = forward.Length - 1;
        for (int i = last / 2; i >= 0; i--)
        { 
            char temp = chars[i];
            chars[i] = chars[last - i];
            chars[last - i] = temp;
        }
        return new String(chars);
    }

Matching Anagrams

Your code is not matching anagrams. Your code matches words with the reverse of the word. An anagram is any rearranged form of the word. So, you have batel and lateb in your list, but it should also match table. Your code will not do that.

The trick to solving this problem would be to reduce each word to its sorted array of characters. For example, to have a function like:

    public string SortedString(string word)
    {
        char[] chars = word.ToCharArray();
        Array.Sort(chars);
        return new String(chars);
    }

Or, if Linq is your thing:

        return String.Concat(word.OrderBy(c => c));

With the char-sorted words, you can use the sorted version as the key of a dictionary, something like:

Dictionary<string,List<string>> anagrams = ....

And you can then populate that dictionary with lists of words that have the same sorted-char anagram key.

Once you have that, you can return all words that are anagrams of each other.

Answer 3

Your reverse string function method is fine, finding the anagrams as you pointed out yourself is not optimal.

It's not clear from the task whether list of words can contain more then 2 anagrams and what should be returned in this case. But in general the approach should be as follow:

• Use dictionary structure to store unique strings from original list as you go

• If next string or anagram of that string is already in such dictionary - that will indicate that you have a match and need to return this string

• If it's not in dictionary - add it there