Tuesday, October 11, 2011

A Gram of Anagram


Last week attended an interview, and this was the question the interviewer came up with to test my problem solving.

" Give a logic to generate valid anagrams of a word, provided you have a dictionary to confirm the validity"

After a while of scribbling on the blank paper I came up with the following answer.

If I take a dictionary as a Hash Map as every word is unique and the Key is a binary(or Hex) representation of the word. Then if I have a word I can easily find the meaning of it with O(1) complexity.

Now, if we have to generate all the valid anagrams, we need to verify if the generated anagram is in the dictionary, if it is present in dictionary, its a valid one else we need to ignore that.

I will assume that there can be a word of max 100 characters(or more but there is a limit).

So any word we take it as a sequence of indexes like a word "hello" can be represented like "1234". Now the anagrams of "1234" are "1243", "1242" ..etc

The only thing we need to do is to store all such combinations of indexes for a particular number of characters. This is an one time task. And then words can be generated from the combinations by picking the characters from the index.Hence we get the anagrams.

To verify if the anagrams are valid or not, just index into the dictionary and validate.

The only thing need to be handled is the duplicates.That can be done easily. As an when we need to compare with the previous ones that has been searched in dictionary.

And I said the solution emphasizes on performance.

I don't know if this is the answer the interviewer was expecting or something else but I can guess it now as I did not get any response for further rounds.

Really need to work on my problem solving skills.