algorithm - Given a file, find the ten most frequently occurring words as efficiently as possible

Question

This is apparently an interview question (found it in a collection of interview questions), but even if it's not it's pretty cool.

We are told to do this efficiently on all complexity measures. I thought of creating a HashMap that maps the words to their frequency. That would be O(n) in time and space complexity, but since there may be lots of words we cannot assume that we can store everything in memory.

I must add that nothing in the question says that the words cannot be stored in memory, but what if that were the case? If that's not the case, then the question does not seem as challenging.

Answer 1

Optimizing for my own time:

sort file | uniq -c | sort -nr | head -10

Possibly followed by awk '{print $2}' to eliminate the counts.