Given a text document as input with a set of strings ....
Software QA/Tests Interview Questions from Microsoft
(Continued from previous question...)
Given a text document as input with a set of strings ....
Question:
Given a text document as input with a set of strings, assume '\n' is the delimiter, print to the console strings grouped by anagrams.
vinay
naviy
inavy
tes
set
maybe an answer:
Here you can use counting sort which run in O(n + k) where k = number of key which are 256 i.e. no. of ASCII values
string CountingSort(string str){
int a[256];
int size = 255;
for(int i = 0; i < 256; i++){
a[i] = 0;
}
//count number of characters in string
for(string::iterator it = str.begin() ; it != str.end(); it++)
a[*it] += 1;
int len = str.length() - 1;
//rebuild string from back to keep sort stable
while(size--){
if(a[size]){
while(a[size]--){
str[len--] = char(size);
}
}
}
return str;
}
(Continued on next question...)
Other Interview Questions
|