Find the frequency of each letter in a string. then test it
Software QA/Tests Interview Questions from Microsoft
(Continued from previous question...)
Find the frequency of each letter in a string. then test it
Question:
Find the frequency of each letter in a string. then test it
maybe an answer:
Solution1 (worse):
For each char find the occurence by iterating the array.
complexity is O(n^2)
Solution2:
if you are free from modifying the array. Then sort the array and find the occurence.
It takes o(n logn) + o(n) = O(n logn)
Solution3:
If memory is not a constraint, then go with hash table.
It takes O(n) time and O(n)space.
maybe an answer2:
It may be done as following in O(n):
* int count[256]={0};
* now iterate thru each char of the input string and do:
for(i=0;i%lt;strlen(str);i++) {
ch=str[i];
count[ch]++; }
* now iterrate thru count[] to get frequency of each letter
(Continued on next question...)
Other Interview Questions
|