Hi all,

My phone screen was a leetcode (sort of) Medium / Hard question. I was told it would be a design question by the recruiter, but of course not! It turned out to be a leet coding type question, lol. No discussion about resume, just kind of a somewhat jumpy Engineering manager instantly asking a coding question, with no quarter given at all. Usually the manager doesn't get into any leetcoding. I was assuming it would be more of a 'How would you do this?' Or 'what are the benefits about this approach', etc. etc.

So, anyways, the question was:

Find all anagrams of a string:

public IList<string> GetAllValidAnagrams(string word)
{
}

That's all he gave. I was like, huh? And of course I asked clarifying questions like "don't we need a dictionary" to make sure it's a word, as he didn't want all 'permutations', he wanted all valid words returned. But, according to leetcode 438, "rac" is a valid anagram of "car". But in reality, there is no valid anagram of car, but there is one for "cat", ("act" for example.) Anyways, that was my first question, so I basically came up with a brute force algo to have two pointers come up with splitting the word in half, and that would come up with all permutations. Heres my code:

            ISet<string> dictionary;
            public MyController(IList<string> validEnglishWords)  //pass in to the constructor the entire dictionary.
            {
             
                dictionary = new HashSet<string>(validEnglishWords);

            }

			 
            public IList<string> GetAllValidAnagrams(string word)
            {
                var result = "";
                permute(word, result);
                return results;
            }

            public void permute(string s, string answer)
            {

                if (s.Length == 0)
                {
					if (dictionary.Contains(answer))  //this just checks whether permutation is in dictionary, and adds if so.
						results.Add(answer);
                }

                for (var i = 0; i < s.Length; i++)
                {
                    var c = s[i];
                    var left = s.Substring(0, i);
                    var right = s.Substring(i + 1);
                    var rest = left + right;
                    permute(rest, answer + c);
                }

            }

I first had dictionary as a list of strings, and changed it to a hashset, as he was wanting optimizations. But, I said I would use a Trie instead of hash. is a Trie the answer I should have mentioned? Also, this algorithm is O(n!), so not so good, but how to improve? Could I have used the dictionary itself to substantially reduce the runtime?

Thanks for the help!