CareerCup

1. Get count of each word.
2. Create a MIN heap of word counts with 1st 100 elements.
3. Now for all other word counts , if count is smaller (OR equal) than root (of max heap), ignore it, otherwise replace the root with new greater count and heapify.

At the end, elements in heap will be the 100 most frequently occurring words.

Anuj - How would you solve this with splay trees

How about using a heap to store the words based on frequency. You could also use splay trees.

Create a table and increment count when the words are already present? Sort them according to count or use a heap to pick the top 100.

Was this question asked by HR?

Use a hash to store the word as the key and increment the value as it is parsed.then sort it to find the first 100.

Anyway, you need to store some kind of information about every word seen, you can optimize it further in below ways.

1. For word in dictionary, maintain a array and increment a score there.(Note that you are not storing the word here)
2. Create an index for non-dictionary words and maintain in a hashmap, and update the count in the array as above.

Now construct a heap to find the top 100 occurences. Note that, heap is better than sort, because we don't care about the order of remaining elements.

Use a hash map to map word -> # occurrences. Copy the pairs (key, #occ.) to an array. Use order statistics to find the 100th-highest occurrence. Partition on that number. O(n) + /expected/O(n) = /expected/ O(n).

Heap solutions will be O(n lg n).

Hashtable + Heap . Inspired by other replies.

O(nlogn)

Count using a map and insert them into a heap.

ifstream fin ("test.in");

struct classcomp {
      bool operator() (const pair<string,int>& lhs, const pair<string,int>& rhs) const
            {return lhs.second>rhs.second;}
};

void getCount() {
    map <string, int> count;
    string in;
    while (fin.good()) {
        fin >> in;
        if (count.find(in) == count.end())
            count[in] = 1;
        else
            count[in]++;
    }
    count[in]--;

    set<pair<string,int>, classcomp> heap;

    for (map <string, int>::iterator i = count.begin(); i != count.end(); i++)
        heap.insert(make_pair(i->first, i->second));
    int c = 0;
    for (set<pair<string,int>, classcomp>::iterator i = heap.begin(); c < 100 and i != heap.end(); c++, i++)
        cout << i->first << " " << i->second << endl;
}

Another approach is medians of medians as described in Corman book

Hashtable + DLL.. basically DLL is nothing but the sorted words based on frequency.

since the word count increase by only one we can check wether the word before given word count in DLL is less than then swap nodes of DLL.

Here we need not to worry about top 100 or so.