Word Frequency Statistics

Question

In an pre-interview, I am faced with a question like this:

Given a string consists of words separated by a single white space, print out the words in descending order sorted by the number of times they appear in the string.

For example an input string of “a b b” would generate the following output:

b : 2
a : 1

Firstly, I'd say it is not so clear that whether the input string is made up of single-letter words or multiple-letter words. If the former is the case, it could be simple.

Here is my thought:

int c[26] = {0};
char *pIn = strIn;

while (*pIn != 0 && *pIn != ' ')
{
    ++c[*pIn];
    ++pIn;
}

/* how to sort the array c[26] and remember the original index? */

I can get the statistics of the frequecy of every single-letter word in the input string, and I can get it sorted (using QuickSort or whatever). But after the count array is sorted, how to get the single-letter word associated with the count so that I can print them out in pair later?

If the input string is made of of multiple-letter word, I plan to use a map<const char *, int> to track the frequency. But again, how to sort the map's key-value pair?

The question is in C or C++, and any suggestion is welcome.

Thanks!

Answer 1

I would use a std::map<std::string, int> to store the words and their counts. Then I would use something this to get the words:

while(std::cin >> word) {
    // increment map's count for that word
}

finally, you just need to figure out how to print them in order of frequency, I'll leave that as an exercise for you.

Answer 2

You're definitely wrong in assuming that you need only 26 options, 'cause your employer will want to allow multiple-character words as well (and maybe even numbers?).

This means you're going to need an array with a variable length. I strongly recommend using a vector or, even better, a map.

To find the character sequences in the string, find your current position (start at 0) and the position of the next space. Then that's the word. Set the current position to the space and do it again. Keep repeating this until you're at the end.

By using the map you'll already have the word/count available.

If the job you're applying for requires university skills, I strongly recommend optimizing the map by adding some kind of hashing function. However, judging by the difficulty of the question I assume that that is not the case.

Answer 3

Taking the C-language case:

I like brute-force, straightforward algos so I would do it in this way:

1. Tokenize the input string to give an unsorted array of words. I'll have to actually, physically move each word (because each is of variable length); and I think I'll need an array of char*, which I'll use as the arg to qsort( ).

2. qsort( ) (descending) that array of words. (In the COMPAR function of qsort(), pretend that bigger words are smaller words so that the array acquires descending sort order.)

3.a. Go through the now-sorted array, looking for subarrays of identical words. The end of a subarray, and the beginning of the next, is signalled by the first non-identical word I see. 3.b. When I get to the end of a subarray (or to the end of the sorted array), I know (1) the word and (2) the number of identical words in the subarray.

EDIT new step 4: Save, in another array (call it array2), a char* to a word in the subarry and the count of identical words in the subarray.

1. When no more words in sorted array, I'm done. it's time to print.

2. qsort( ) array2 by word frequency.

3. go through array2, printing each word and its frequency.

I'M DONE! Let's go to lunch.