Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Hash table.
let h( ) be your hash function.
But before you hash each string, sort it with a linear string sort, call it f( ).
So you hash like this h(f( string) ).
So all anagrams get hashed to same spot.
Make sure you store "f(string)" when you hash.
private String sort(String str){
char a[] = str.toCharArray();
Arrays.sort(a);
return new String(a);
}
public void que1(String str){
StringTokenizer st = new StringTokenizer(str);
HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
ArrayList<String> arr = null;
while(st.hasMoreTokens()){
String temp = st.nextToken();
String temp1 = sort(temp);
if(map.containsKey(temp1)){
arr = map.get(temp1);
arr.add(temp);
map.put(temp1, arr);
}else{
arr = new ArrayList<String>();
arr.add(temp);
map.put(temp1, arr);
}
}
for(Map.Entry<String, ArrayList<String>> entry : map.entrySet()){
System.out.print(entry.getKey()+" ");
arr = entry.getValue();
for(int i = 0; i< arr.size(); i++){
System.out.print(arr.get(i)+" ");
}
System.out.print("\n");
}
}
I would like to extend the solution of amber by providing comparator function, that compares sorted strings, something like:
bool cmp(string & one, string & two)
{
string oneSorted = sort(one.begin(), one.end());
string twoSorted = sort(two.begin(), two.end());
return oneSorted.compare(twoSorted) < 0;
}
Then you may just apply this comparator to sort i.e a vector of strings:
sort(v_string.begin(), v_string.end(), cmp);
1) Create a HashMap<String, StringBuffer>
Start from the first word, sort it, store this sorted word into HashMap as a key and original word as a value.
2) Iterate through the sentence, take one word at a time, sort it, check sorted word is present as a key into HashMap,
If Yes, Append this new word(original unsorted) to value i.e. StirngBuffer of that key
If Not, Add new (key, value) pair into HashMap.
3) Repeate step 3 for all the unique words.
4)Once all words are checked, iterate through the HashMap and get all the values.
Would you please mention some example if the interviewer has given you any example.
- guptasunny158 September 22, 2013