Microsoft Interview Question Software Engineer in Tests
assign first 26 prime numbers for a to z ...if you are also considering A to Z assign next set of prime numbers to them to..
so lets take an example of two words abc & cab
here, abc => (2*3*5)= 30 [a is alloted 2, b->3, c->5,d->7..so on...)
also, cab => (5*2*3) = 30...thus both these words are anagrams..
I gave the following solution. He didn't ask me to code just give algorithm
1. Create a hash function that sorts the words in alphabetic order, we will use this for our hashing
2. For each word in the dictionary - use the above hash if there is no collision create a new entry, if there is a collision add the word to the list of values.
3. Ignore/remove all entries of size 1. Now we have the list of all anagrams.
Programming pearls have a slightly different solution but I think basically both are same and if I were the interviewer I would have appreciated the original thought rather than repeat a bookish solution. But I don't think he liked it as much as I did :)
My understanding is that hashing is not better approach than Bentley's solution. The reason is - hashing never considers worst case scenario. For example, two words X and Y have same hash values, it doesn't mean they are really anagram. So it needs to compare those words whenever there is a collision.
Dont you read what I wrote, I will create a 'custom' hash function that just sorts words. I wanted to have collisions and those collisions create anagrams.
Then your first point(marked 1.) is purely confusing. Why you need to implement a hash function to sort words in alphabetical order?
Probably you wanted to convey sort "characters of each word" either ascending or descending. If you think one thing, but write/say other thing, then it'd be confusing for everyone.
No offense please.
why not use binary representation instead... use 26bit binary, and for every word create a binary number with 1 if corresponding alphabet is there in the word. Use this binary number as the hash key.
it does not work, if the word has repeated characters.
Ex: if the word is 'butt', then your solution does consider the word 'but' too.
I am a begginer, tried to implement the primes method..it worked but not a very written code
import java.util.HashMap;
/**
* Created with IntelliJ IDEA.
* User: ranger
* Date: 12/18/13
* Time: 8:52 AM
* To change this template use File | Settings | File Templates.
*/
public class FindAnagrams {
public static void main(String[] args){
int[] primes = {3,5,7,11,13,17,19,23,29,31,37,41,43,47,49,53,57,59,61,67,71,73};
String[] s ={"row","tow","bow","wob","book","nook"};
String str=new String();
for(int i=0; i<s.length;i++){
str=str+s[i];
}
HashMap<Character,Integer> h=new HashMap<Character,Integer>();
int i=0;
for(char c1:str.toCharArray()){
if(!h.containsKey(c1)) {
h.put(c1,primes[i++]);
}
}
for(Character c2:h.keySet()){
System.out.println(c2 +" "+ h.get(c2));
}
FindAnagrams f=new FindAnagrams();
f.HashVal(h, s);
}
void HashVal(HashMap h,String[] s){
int[] t=new int[s.length];
for(int i=0;i<s.length;i++){
t[i]=1;
char[] chars=s[i].toCharArray();
for(int j=0;j<chars.length;j++) {
t[i]=t[i]*(Integer)h.get((Character)chars[j]);
}
}
for(int k=0;k<t.length;k++){
for(int m=0;m<t.length;m++){
if(k!=m && t[k]==t[m]){
System.out.println("");
System.out.println("anagrams found "+ s[k] +" " + s[m]);
}
}
}
}
}
good one, but 26 prime method would also work...
- T July 13, 2010