Interview Questions

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