Задача от компании РБК на должность инженера-разработчика: считать огромный файл, найти топ 10 часто встречающихся слов

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
#define lim 100
#define len 15
#define top 10

void RandWords(char *filename, int count)
{
FILE *f=fopen(filename, "wt");
if(!f) exit(1);
int ct=count;
if(ct>1000000) ct = 1000000;
srand(time(NULL));
for(int i = 0; i < ct; i++)
{
char buf[len]={0};
int n=rand()%lim;
sprintf(buf,"%s%d%c","word",n,'\n');
fprintf(f,"%s",buf);
}
fclose(f);
}


void PrintFile(char *filename)
{
FILE *f=fopen(filename, "rt");
if(!f) exit(1);
printf("\nFrom file %s:\n", filename);
char a = 'a';
while(fscanf(f,"%c",&a)!=EOF)
printf("%c",a);
fclose(f);
}

void SortWords(char **words, int *counts)
{
for(int i = 0; i < top; i++)
for(int j = 0; j < top; j++)
{
if(counts[i]>counts[j] && i!=j)
{
char buf[len]={0};
strcpy(buf,words[i]);
strcpy(words[i],words[j]);
strcpy(words[j],buf);
counts[i]^=counts[j]^=counts[i]^=counts[j];
}
}
}

void TopWords(char *filename)
{
char **words, a = 'a', tword[len]={0};
int *counts, ind=0;
counts=(int*)malloc(top*sizeof(int));
if(!counts) exit(1);
for(int i = 0; i < top; i++)
counts[i]=0;
words=(char**)malloc(len*sizeof(char*));
if(!words) exit(1);
for(int i = 0; i < top; i++)
{
words[i]=(char*)malloc(len*sizeof(char));
if(!words[i]) exit(1);
memset(words[i],'\0',len);
}

FILE *f=fopen(filename,"rt");
if(!f) exit(1);

while(fscanf(f,"%c",&a)!=EOF)
{//while !EOF
if(a!='\n') strncat(tword,&a,1);
if(a=='\n' && strlen(tword)>0)
{//
char flag=0, min=0;
strncat(tword,"\0",1);
for(int i = 0; i < top; i++)
{
if(!strcmp(tword,words[i]))
{counts[i]++;flag=i;}
}

for(int i = 0; i < top; i++)
if(counts[i]<counts[min]) min=i;
for(int i = 0; i < top; i++)
if(strlen(words[i])==0) min=i;

if(!flag && strlen(tword)>0)
{
memset(words[min],'\0',len);
strcpy(words[min],tword);
counts[min]=1;
}
else counts[min]++;
memset(tword,'\0',len);
}//
}//while !EOF
fclose(f);

SortWords(words,counts);
printf("\n\nTop of file words:");
for(int i = 0; i < top; i++)
{
printf("\n%s - %d counts", words[i],counts[i]);
free(words[i]);
}
free(words);
free(counts);
}



int main()
{
char *name="test.txt";
RandWords(name, 15000);
PrintFile(name);
TopWords(name);
system("pause");//для Windows
return 0;
}

И в чём проблема?

1. Реализуешь сортировку слиянием (MergeSort) - которая как раз и предназначена для сортировки файлов на диске - с минимумом оперативной памяти.

2. А дальше за один проход по отсортированному массиву получаешь кол-во вхождений каждого слова - что позволяет очень просто выделить top-10 - за этот же один проход.

Оперативную память можно сэкономить ещё больше:

На втором этапе из отсортированного файла слов формируем новый файл, каждая строка которого содержит уникальное слово и кол-во его вхождений в исходный файл.
Сортируем этот файл по кол-ву вхождений - опять же, сортировкой слиянием.
Печатаем первые 10 строк этого файла.

ну так реши и код в студию

Какие блин сортировки и др дерьмо.
Задачу изменяю: считать огромный файл в триллион записей , найти топ 1 часто встречающихся слов. Нах тут сортировка. Ну ладно 2 слова, снова сортировка вам нужна? Да и хрен там даже если 10.
А если за все время вашей работы босс уже требует результат?
Подождите нам надо еще месяц работы, потом будет результат?
Хрясь выключили свет...ё...дайте снова месяц на работу.
Думайте

Тут вроде решение привели.. я в С не разбираюсь, но вот вопрос -
тот код и код вашего друга, будут работать, если слово превышает 1кб? А то в память же надо уложиться.. А в условиях задачки про это молчок :)
...
Я вот когда писал код для базы данных, я захотел ускорить поиск по CLOB-ам, для этого я написал код, который ищет слова в CLOB-ах разделяя их по пробелам, и отдельно сохраняется какое слово в каких CLOB-ах содержится.
Так вот для меня, словом было любое сочетание букв, цифр, значков, потому что там содержался какой то код страничек в перемешку с текстом.
Например такое слово - "a(a){for(n.push(a);n.length>o.maxSize;)n.shift()}function"

Поэтому дабы пресечь ошибку, я делал проверку, если слово превышает длину которую можно сохранить, то оно обрезается до допустимого размера.

придётся писать либо с использованием внешней памяти (предлагалось выше), либо приближённое решение
хочешь впечатлить собеседующих - пиши оба
искать всякие приближенные алгосы можно по "top k frequent items in data stream", но смотреть лучше на взрослые пдф статьи с формулами от всяких китайцев из гугла, а не на индусский код со всяких гавносайтов
алгоритма, решающего задачу точно, за константную память и линейное время, мне неизвестно, и сомневаюсь, что он существует
(если существует, расскажите плз)

Это невозможно! А если там все миллиарды слов разные и нет повторений? Ты никак это без оперативки не разгребёшь. Задача на поиск словаря - одни из смых сложных. Я как-то пробовал составить такой словарь для трёх мушкетёров. Над файлом в 2 мегабайта прога работала десятки минут! Причём всё было полностью в оперативке.

А насколько огромным является файл?