|
Given a set of words in a dictionary, write a program to group ....
Microsoft Interview Questions and Answers
(Continued from previous question...)
89. Given a set of words in a dictionary, write a program to group ....
Question:
Given a set of words in a dictionary, write a program to group all words which are anagrams of each other in to sets.
You can use any C++ STLs or other languages like python if you want to code this..
example:
input:
"bat", "tar", "xyz" , "tab", "tar"
output:
[["bat", tab"], ["tar", rat"],"xyz" ]
(Note: In this example, all words are only of three characters but this is not always guaranteed. The input may contain words with any number of characters)
maybe an answer:
1.Take the first string and take a bucket of 26 elements, 1 for each alphabet and scan through the array to fill the buckets.. for example scanning 'bat' gives arr['a']=1, arr['b']=1 and arr['t']=1.. others are zero.
2. now take all the other members like 'tar' 'tab' etc and make check if their buckets are the same as that of 'bat'. If yes, they are anagrams. thus we get all the anagrams of 'bat'.
3. do the same thing for all the elements..
4. space complexity- 0(1)
Time complexity- O(l*n^2)
where l is the avg length of each word and n is the total number of words.
maybe an answer2:
class Anagram
{
private static int GetHash(string input)
{
int hash = 0;
foreach (char c in input)
{
hash += (char.ToLower(c) - 'a');
}
return hash;
}
private static string GetComma(int count, int index)
{
return (index < count - 1) ? ", " : string.Empty;
}
private static void DisplayList<T>(List<T> inputList, Action<List<T>, int> process)
{
Console.Write("[");
for (int j = 0; j < inputList.Count; j++)
{
process(inputList, j);
Console.Write("{0}", GetComma(inputList.Count, j));
}
Console.Write("]");
}
public static void Main()
{
List<string> inputList = new List<string> { "bat", "labl", "rat", "xyz", "ball", "tab", "tar" };
Dictionary<int, List<string>> anagrams = new Dictionary<int, List<string>>();
foreach (string str in inputList)
{
int hash = GetHash(str);
anagrams[hash] = anagrams.ContainsKey(hash) ? anagrams[hash] : new List<string>();
anagrams[hash].Add(str);
}
Action<List<string>, int> ProcessString = (s, i) => Console.Write("\"{0}\"", s[i]);
Console.WriteLine("\n\n\tInput String List: ");
Console.Write("\n\t");
DisplayList(inputList, ProcessString);
Action<List<KeyValuePair<int, List<string>>> , int> ProcessDictionary = (d, i) =>
{
var element = d.ElementAt(i);
DisplayList(element.Value, ProcessString);
};
Console.WriteLine("\n\n\n\tOutput String List: ");
Console.Write("\n\t");
DisplayList(anagrams.ToList(), ProcessDictionary);
Console.WriteLine("\n\n");
}
}
Output:
=======
Input String List:
["bat", "labl", "rat", "xyz", "ball", "tab", "tar"]
Output String List:
[["bat", "tab"], ["labl", "ball"], ["rat", "tar"], ["xyz"]]
(Continued on next question...)
Other Interview Questions
| 