## Amazon Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
4
of 4 vote

The best algorithm I found for this problem is:

1. 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

Comment hidden because of low score. Click to expand.
0

I had given same approach, but interviewer said if dictionary is huge and cannot fit in memory, then what approach can be applied.

I had gone with creating a trie of dictionary and then searched the word in it.

Comment hidden because of low score. Click to expand.
2
of 0 vote

Assign 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

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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!

Comment hidden because of low score. Click to expand.
0

it is not helpful. a word could be very long. e.g "palindromic", or some chemical name. and the 26th prime is 101.
so the hash value of a word could be too large, that no primitive type can hold it.

Comment hidden because of low score. Click to expand.
0
of 0 vote

(1)setup the dictionary with trie datastructure
(2)for every word(O(1) get time) search the reversed string (O(1) find time) in the trie
(3)if find print it
(4)if u dont want duplictaes then after finding the anagram, make a boolean flag set for both strings

Comment hidden because of low score. Click to expand.
0
of 0 vote

so totally its take O(n) for n words

Comment hidden because of low score. Click to expand.
0
of 0 vote

How about sorting the two words in lexicographic order and comparing them char-by-char?

Comment hidden because of low score. Click to expand.
0

nlogn comp., which is unnecessary..

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

That is a ridiculous solution.

Comment hidden because of low score. Click to expand.
0

Oh, and I missed this: LOL.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//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))
{
}
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))
{
}
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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

апельсин

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#!/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')``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

fdsdsds

Comment hidden because of low score. Click to expand.
0
of 0 vote

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,

Comment hidden because of low score. Click to expand.
-1
of 1 vote

add ascii values of each character in the strings and compare
better still if u do (strlen)a[0] + (strlen-1)a[1].....a[strlen];

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.