## Microsoft Interview Question for Software Engineer / Developers

Team: MS Office Platform
Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
3
of 3 vote

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)) {
}
}

return anagrams;
}

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 2 vote

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.

Comment hidden because of low score. Click to expand.
2

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).

Comment hidden because of low score. Click to expand.
2

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)) {
}
}

return anagrams;
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This can be done by Hashtable by following way
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

Comment hidden because of low score. Click to expand.
0

Will it not be very costly to pre-process all the dictionary word , i mean sorting each word and then storing the in the list ?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.