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

All the answers prior to mine did not give really an answer.

Let us think on a potential solution.

There is a more or less standard approach for counting something in a container.

We can use an associative container like a std::map or a std::unordered_map. And here we associate a "key", in this case the word, to a count, with a value, in this case the count of the specific word.

And luckily the maps have a very nice index operator[]. This will look for the given key and, if found, return a reference to the value. If not found, then it will create a new entry with the key and return a reference to the new entry. So, in both cases, we will get a reference to the value used for counting. And then we can simply write:

std::unordered_map<char,int> counter{};
counter[word]++;

And that looks really intuitive.

After this operation, you have already the frequency table. Either sorted by the key (the word), by using a std::map or unsorted, but faster accessible with a std::unordered_map.

Now you want to sort according to the frequency/count. Unfortunately this is not possible with maps.

Therefore we need to use a second container, like a ```std::vector`````which we then can sort unsing std::sort for any given predicate, or, we can copy the values into a container, like a std::multiset that implicitely orders its elements.

For getting out the words of a std::string we simply use a std::istringstream and the standard extraction operator >>. No big deal at all.

And because writing all this long names for the std containers, we create alias names, with the using keyword.

After all this, we now write ultra compact code and fulfill the task with just a few lines of code:

#include <iostream>
#include <string>
#include <sstream>
#include <utility>
#include <set>
#include <unordered_map>
#include <type_traits>
#include <iomanip>

// ------------------------------------------------------------
// Create aliases. Save typing work and make code more readable
using Pair = std::pair<std::string, unsigned int>;

// Standard approach for counter
using Counter = std::unordered_map<Pair::first_type, Pair::second_type>;

// Sorted values will be stored in a multiset
struct Comp { bool operator ()(const Pair& p1, const Pair& p2) const { return (p1.second == p2.second) ? p1.first<p2.first : p1.second>p2.second; } };
using Rank = std::multiset<Pair, Comp>;
// ------------------------------------------------------------

std::istringstream text{ " 4444 55555 1 22 4444 333 55555 333 333  4444  4444 55555  55555 55555 22 "};

int main() {

    Counter counter;
    
    // Count
    for (std::string word{}; text >> word; counter[word]++);

    // Sort
    Rank rank(counter.begin(), counter.end());

    // Output
    for (const auto& [word, count] : rank) std::cout << std::setw(15) << word << " : " << count << '\n';
}

Answer 2

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.

Answer 3

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 4

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.