CareerCup

1. Do External Sort (merge sort in file).
2. Collapse duplicates to "num, word", e.g. "1025, the".
3. While doing step 2, keep a max heap of word frequencies.

This way there is no extra storage needed, but the complexity is O(N*log(N)).

If extra storage is permitted, you can build a hash file, where line number corresponds to hash index. You'll probably end up with using twice the original storage though. Also, random access on disk will probably be less efficient than the sorting in External Sort, since lines will be read sequentially and written back sequentially.

Use Hash-Map and Min Heap

Well, there could be 2 different definition of word.
1. A word in English dictionary, the biggest I have seen so far has 400k words.
2. A sequence of character separated by separator like space, full stop, etc. if we can say that they all from English dictionary or another languages dictionary. Or even if we can be sure that all sequence of words in our terabyte of file belongs to word in any language. Then total set of words is limited can easily loaded into hash table in memory.

Instead of using hashtables, we can use a different data strcuture to indicate the frequency of the occurances. I ve written a basic program for any number of words based upon input.

The structure has count of occurences of a word ending with that node. Based upon the next letter we create an array of 26 letters (assuming all the letters are small , doesnt matter if mixed as well) from the first node. And the process resumes till last letter.

#include <iostream>

struct node;

struct node
{
	int count;
	node* child;
};

int main()
{
	node * fnode = new node[26];
	std::string str;
	int numStr;
	std::cin >> numStr;
	for (int i = 0; i < numStr ; i++)
	{
		
	
	std::cin >> str;
	node * n = fnode + (str[0] - 97);
	for (int i = 1; i < str.length() ; i++)
	{
		if (n->child == NULL)
		{
			n->child  = new node[26];
		}
		n = n->child + (str[i] - 97);
		 
	}
	n->count++;
	std::cout << n->count ;
	}
}

what if we are allowed to use a distributed setup something like mapreduce and we use the hashmap solution on each computer and then finally merge the each solution .
i think this can be solved by map reduce approach

create a min-heap of 10 nodes. Node structure would look like:

srtuct node{
int frequency;
char *word;
node * left;
node *right;
}

The min heap is created based on the frequency of the word. Also maintain a concurrent hashmap backing this. With every insert on the hashmap check if the frequency of the inserted element is greater than the min frequency currently on the min-heap then delete the min-heap element-> place it into the hashmap because later it could re-enter the min-heap. Insert the element from the hashmap back into the min-heap and heapify. The insertion into the min-heap has to be an atomic operation. I think this would have good throughput.

Alternatively map-reduce could also be the way to go..

Since there are terabyte of strings. A Modified trie based solution and Min Heaps too will be a optimal one.
In Trie, The node consists of not "IsEnd" boolean variable but also the Count.
when a new string is inserted and its count is increased. If the count is greater than the top element of the min heap and the heap size is equal to 10, remove the top element and add the element.

When all the strings have been read, pop the elements and store the elements in a array.
print the array in the reverse order which gives the top 10 frequent elements

At the End

Create a hash table, the key is word, and value is a counter. Trace all words, if is not existed in hash, add it with value 1, otherwise, increment the value.

In the same time using a list of pair key value, can hold the most ten frequent repeated words, and if a word after increment has a value of more than the minimum in this list, replace with that and remove the minimum in list.

Notice the total English words! The Second Edition of the 20-volume Oxford English Dictionary contains full entries for 171,476 words in current use, and 47,156 obsolete words. To this may be added around 9,500 derivative words included as subentries.

anyways, this is a simple code to handle this case:

Dictionary<string, int> lookup = new Dictionary<string, int>();
string word = getNextWord();
int maxFrequent = 0;
Dictionary<string, int> topTen = new Dictionary<string,int>();


while (!String.IsNullOrEmpty(word))
{
    if (lookup.ContainsKey(word))
        lookup[word]++;
    else
        lookup.Add(word, 1);
    if (lookup[word] > maxFrequent)
    {
        if (topTen.ContainsKey(word))
            topTen[word] = lookup[word];
        else
        {
            topTen.Add(word, lookup[word]);
            if (topTen.Count() > 10)
            {
                string lessFrequent = findMinTopTen();
                topTen.Remove(lessFrequent);
            }
        }
        maxFrequent = findMinTopTen();
    }
   word = getNextWord();
}

At the end, topTen contains the most ten frequent words items.
findMinTopTen() return the word with less frequent repeat in a list of 10 items. This algorithm is linear and run in O(N) which N is total words in the text and needs O(m) space which m is the number of items in the word set used in the text

Partition the data into subsets(i.e. buckets of reasonable size in RAM), and do parallel processing on each node(bucket). Each node will return the 10 most-frequent strings and their counts, as a sorted array where the index is the rank. This is essentially mergesort, done in parallel.