Google Interview question
My friend just interviewed by the Google team. Those of you who do not aware of google interviews, the first telephonic interview usually consist of 2 algorithm implementation either in C,C++,JAVA or Python and general questions from your resume (CV).
The question:
Find whether the two strings are anagram or not.(No white spaces included)
The strings which contain same characters with equal number of occurrence in order or without order.
Anagram
e.g,
ARMY EAT
MARY ATE
ALgo steps:
1. get the two string input from user , str1,str2.
2. if (len(str1)!=len(str2))
result : No Anagram , quit.
3.else
sort two strings by quick sort(n log n complexity in ideal case)
4. Compare both strings,
if (str1==str2)
yes anagram
else
no.
This was my friend's answer in just 3 minutes.
Then the interviewer asked : Can you make this more efficient??
!!!!!!
Then she has given a hint,,,, Did you heard about Hasing? now think....
My idea may gives hint ,,,
1. Make a Hash table
Key -value
a - 1
b - 2
c - 3
. .
. .
. .
z 26
2. Get two string from user, str1,str2.
3. call the Hash fun and get the value..
like if I have str1=abc then Hash(str1) = 123
str2=bca then Hash(str2) = 231
4. if Hash(str1) > Hash(str2)
Hash(str1) - Hash(str2)
else
Hash(str2) -Hash(str1)
5. if the return value of above arithmetic is divided by 9 then the string is Anagram
else not.
This seems ok,
But this was also incorrect.
My friend Maulik noticed and found my error because 19-10 also 9 and divisible by 9. then what?
I still don't have any answer.
Any other answers are welcome..