Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
This is the standard solution.
There is even a more efficient way - map all characters in the alphabet to the first 26 prime numbers and calculate the hash value of a word as the multiplication of those values. Hash is guaranteed to be unique for every different anagram set, and the same for all anagrams within a set. This reduces the complexity from O(nlgn) of sorting to O(n) in the calculation of the hash value.
So u were provided with input of words.. in which u need to tell whether the word(s) is/are anagram of ABC or not..? I am right.?
Maybe I'm missing something but I don't see a big problem.
If a hashmap is used to store the dictionary using hash function
f(x)
, then looking up a word
a
in the dictionary is around O(1) complexity:
1. compute the
f(a)
- O(1)
2. looking up
f(a)
in the hashmap - O(1)
3. handling any conflicts with other words that were hashed as
f(a)
- aprox. O(1) if the hash was implemented well
Maybe I'm missing something but I don't see a big problem.
If a hashmap is used to store the dictionary using hash function
f(x)
, then looking up a word
a
in the dictionary is around O(1) complexity:
1. compute the
f(a)
- O(1)
2. looking up
f(a)
in the hashmap - O(1)
3. handling any conflicts with other words that were hashed as
f(a)
- aprox. O(1) if the hash was implemented well
I think you can assume the dictionary is a trie of words. And your input string is "ABC". Search for characters A, B and C in the children of the root. Let's say you found B. Record this information that B has been found in another data structure. Now follow the branch with root as B. And look for A and C in it children. Let's say you found A. Record this information. Now try to find C in the children of A. If you find it, then you can print the anagram as "BAC". Then backtrack and look for other anagrams accordingly.
See following,
import java.util.ArrayList;
import java.util.Arrays;
public class AnagramsInDict {
public static void main(String[] args){
String s="abc";
String[] anag={"bca", "cab", "xxx", "acb"};
int i=findAnagrams(s, anag);
System.out.println(i);
}
public static int findAnagrams(String s, String[] arr){
ArrayList<String> anagramList=new ArrayList<>();
char[] inString=s.toCharArray();
Arrays.sort(inString);
for(String ss: arr){
boolean isAnagram=true;
char[] elem=ss.toCharArray();
Arrays.sort(elem);
if(elem.length!=inString.length){
isAnagram=false;
}
else
{
for(int o=0; o<elem.length; o++){
if(elem[o]!=inString[o])
{isAnagram=false;}
}
}
if(isAnagram){
anagramList.add(ss);
}
}
return anagramList.size();
}
}
if i got ur question correctly. The problem is: we got a dictionary with some words inserted in the dictionary. Now given a String str we need to find if str or any of its anagram is part of the dictionary.
For the problem stated above, i think trie will be the best suited DS.
Suppose i got a dictionary(trie) and a string "same" and in my dictionary i have the anagram "emas". So my algorithm will start traversal from root and check if any of the chars from the string is a valid child of the root. If so we then move to next the child node and keep on checking for remaining characters till all the characters r completed else return false.
public class AnagramsInDict {
private static String[] dict = new String[] { "BAC", "KPD", "LMK", "LMC",
"XAZ", "IMT" };
private static String[] sorteddDict = new String[dict.length];
public static void main(String[] args) {
createSortedDict();
System.out.println(dictContains("ABC"));
System.out.println(dictContains("MCL"));
System.out.println(dictContains("MCLK"));
}
private static boolean dictContains(String string) {
String temp = sortString(string);
for (int i = 0; i < sorteddDict.length; i++) {
if (sorteddDict[i].equals(temp)) {
return true;
}
}
return false;
}
private static void createSortedDict() {
for (int i = 0; i < dict.length; i++) {
String temp = dict[i];
sorteddDict[i] = sortString(temp);
}
System.out.println(Arrays.toString(sorteddDict));
}
private static String sortString(String temp) {
char[] chars = temp.toCharArray();
Arrays.sort(chars);
String sorted = new String(chars);
return sorted;
}
}
private static void checkStringAnagramIsInMap() {
String str = "ABC";
Map<Integer, String> dict = new HashMap<Integer, String>();
dict.put(stringToInt(str), str);
System.out.println(dict.containsKey(stringToInt(str)));
System.out.println(dict.containsKey(stringToInt("CAB")));
System.out.println(dict.containsKey(stringToInt("BAC")));
}
OK. I just got what you asked.
- Dave September 27, 2014Sorry for writing bullshit (and for the double post).
Why not sorting the characters in the word by a determined order:
'BAC' -> 'ABC'
'CBA' -> 'ABC'
'ACB' -> 'ABC' etc...
and store only sorted words in the dictionary.
when you want to know if an anagram of that word is present, sort it and lookup the sorted word in the dictionary.