Amazon Interview Question
Software Engineer / DevelopersAssign a signature to each word. for exaxmple.
stop ---> opst
pots---->opst
do the sorting on signature and then finding the anagrams is a cake wake
I assume your signature is the letters of the word arranged in alphabetical order. If this is the case, the word "tops" would also have a signature of "opst". This isn't game breaking as you can still compare each word matched by signature to verify that they are anagrams. However, this shows that you cannot rely on the signature alone for anagram determination.
i steal this algorithm from someone else because it's very pretty.
1)create a hash table with a key of each letter and assign a unique PRIME number to it as value. So you have 26 letters and 26 prime numbers.
2)for each letter in a word, multiple the letter values you get from the hash table.
3)compare the values!
Ok... this is a repeated question in our careercup site under amazon interview questions.
The best solution I have come across so far is to associate prime numbers for each character (a-z). for each word, multiply their corresponding numbers and compare it with other words for anagram check.
//C#
static bool checkIf2StringsAreAnagrams(string _str1, string _str2)
{
bool isAnagrams = false;
Dictionary<char, int> charset = new Dictionary<char, int>();
for (int i = 0; i < _str1.Length; i++)
{
char key = _str1[i];
if (!charset.ContainsKey(key))
{
charset.Add(key, 1);
}
else
{
charset[key] += 1;
}
}
Dictionary<char, int> charset2 = new Dictionary<char, int>();
for (int i = 0; i < _str2.Length; i++)
{
char key = _str2[i];
if (!charset2.ContainsKey(key))
{
charset2.Add(key, 1);
}
else
{
charset2[key] += 1;
}
}
for (int i = 0; i < charset.Count; i++)
{
char key = charset.Keys.ElementAt(i);
if (charset2.ContainsKey(key))
{
if (charset[key] == charset2[key])
{
isAnagrams = true;
}
else
{
isAnagrams = false; break;
}
}
else
{
isAnagrams = false; break;
}
}
return (isAnagrams);
}
#!/bin/python
def anagram_checker(str1,str2):
# Use empty dictonary for each string
dict1={ }
dict2={ }
for i in str1:
dict1[i]=i
for j in str2:
dict2[j]=j
# beauty of dictonary - the elements are sorted by itself
if dict1 == dict2:
print "The strings are anagrams !!"
else :
print "Strings are not anagrams !!"
anagram_checker('silent','listen')
Merhaba,
Great post. Well though out. This piece reminds me when I was starting out Amazon Interview Question for Software Engineer / Developers after graduating from college.
This is Erin from Amazon Web Services. I took a look at the support case you provided, I see that one of our agents was able to assist and resolve the case.
Please let us know if there is anything else we can help with!
Awesome! Thanks for putting this all in one place. Very useful!
Kind Regards,
Radhey
The best algorithm I found for this problem is:
- Jammanapalli July 24, 20121. Parse each word in the dictionary
2. define a hashtable and search on any hashtable is o(1)
2. Sort each word [best sorting algorithms complexity is nlog(n) ] and and save this sorted word as key in the hash table and store the actual word as value
3. if the key exists already in hashtable, then retrieve the value and append the new word to the existing words string
Note: you just need to parse the whole dictionary only once which is O(n).
so the whole creation of the hashtable is
n*mLogm (m is the average number of letters in a word and n is the total number of words in the dictionary)
and when you want to find anagrams for a given word,
--> sort the word - mlogm (m is the letters in the word)
--> find the sorted one in hashtable - O(1)
thanks
RJ