Microsoft Interview Question Software Engineer / Developers
Team: MS Office Platform
Country: India
Interview Type: In-Person
According to wikipedia, longest word in major dictionary has 45 letters. In worst case 101^45 is over long max value, which is 2^63-1.
This is my solution. Sort each word in dict, anagrams should have the same string. Use HashMap<String, ArrayList<String>> to store. For a given word, just map.get(sorted(word)). This should also save time of math calculation. Time complexity is O(n*log(k)), k is the length of word.
1.First make all the possible permutations of that word.Lets say word is "apple".So it will give 120 words based on that.
2.As dictionary is always sorted,simply search those words one by one using binary search.
Let's the size of the alphabet of the dictionary is a constant c. Pickup first c prime numbers from a table of primes and assign each letter a unique prime number. Now, the product of the prime numbers associated with letters of a word will be unique and all anagrams will have same product.
Maintain a Set of words. Go through the dictionary and for each word calculate the prime product of the word. If the prime product is equal to the product of the given word then add the word in the set. The set is the answer we are looking for.
overall time complexity is O(n) if maximum word length is O(1).
here is the simple code. O(n). I assumed english dictionary with 26 letters alphabet.
private static int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79,
83, 89, 97, 101};
private static long getPrimeProduct(String word) {
long key = 1;
word = word.toLowerCase();
for (int i = 0; i < word.length(); i++) {
key *= primes[word.charAt(i) - 'a'];
}
return key;
}
public static Set<String> findAllAnagramsInDictionary(final Set<String> dictionary, final String word) {
final Set<String> anagrams = new HashSet<String>();
final long wordKey = getPrimeProduct(word);
for (final String dictionaryWord : dictionary) {
if (wordKey == getPrimeProduct(dictionaryWord)) {
anagrams.add(dictionaryWord);
}
}
return anagrams;
}
This can be done by Hashtable by following way
1. Read each dictionary word
2. Sort the word into Ascending or descending order
3. Add the sorted word as Key and actual dictionary word as value.
4. If Anagram comes then add into value Or add new word
5. Print all words where values are more than one for key
Let's the size of the alphabet of the dictionary is a constant c. Pickup first c prime numbers from a table of primes and assign each letter a unique prime number. Now, the product of the prime numbers associated with letters of a word will be unique and all anagrams will have same product.
Maintain a Set of words. Go through the dictionary and for each word calculate the prime product of the word. If the prime product is equal to the product of the given word then add the word in the set. The set is the answer we are looking for.
overall time complexity is O(n) if maximum word length is O(1).
here is the simple code. O(n). I assumed english dictionary with 26 letters alphabet.
- zahidbuet106 May 29, 2014private static int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101}; private static long getPrimeProduct(String word) { long key = 1; word = word.toLowerCase(); for (int i = 0; i < word.length(); i++) { key *= primes[word.charAt(i) - 'a']; } return key; } public static Set<String> findAllAnagramsInDictionary(final Set<String> dictionary, final String word) { final Set<String> anagrams = new HashSet<String>(); final long wordKey = getPrimeProduct(word); for (final String dictionaryWord : dictionary) { if (wordKey == getPrimeProduct(dictionaryWord)) { anagrams.add(dictionaryWord); } } return anagrams; }