# Word Frequency with Ordering in O(n) Complexity

During an interview for a Java developer position, I was asked the following:

Write a function that takes two params:

1. a String representing a text document and
2. an integer providing the number of items to return.

Implement the function such that it returns a list of Strings ordered by word frequency, the most frequently occurring word first. Your solution should run in $O(n)$ time where $n$ is the number of characters in the document.

The following is what I answered (in pseudocode), it is not $O(n)$ but rather $O(n \log n)$ time because of the sort. I cannot figure out how to do it $O(n)$ time.

wordFrequencyMap = new HashMap<String, Integer>();
words = inputString.split(' ');

for (String word : words) {
count = wordFrequencyMap.get(word);
count = (count == null) ? 1 : ++count;
wordFrequencyMap.put(word, count);
}

return wordFrequencyMap.sortByValue.keys


Does someone know or can someone give me some hints?

• Use a hash table. – Yuval Filmus Jun 5 '14 at 5:17
• Using a hashtable does not solve the problem. Furthermore, hashtable is legacy Java. – user2712937 Jun 5 '14 at 5:25
• Hash tables are usually the trick to get the complexity down from $O(n\log n)$ to $O(n)$. Even if they are legacy Java, whatever that means. I haven't checked this particular case, so you may be right. – Yuval Filmus Jun 5 '14 at 5:33
• @YuvalFilmus. Thanks but hash table is pretty much same as hash map, which I am already using (major difference between the 2 data struct is synchronization, which does not apply here). The log(n) in mine comes from sorting the values in the hash map. – user2712937 Jun 5 '14 at 5:38
• By the way, this site focuses on concepts and algorithms, not on code. Therefore, normally we'd ask you to remove the Java code and give a conceptual description of your approach (possibly with concise high-level pseudocode if needed). Also, on this site the relevant question is what data structures and algorithms to use; the specific Java API is off-topic for this site (but you could ask about it on StackOverflow), and similarly, whether Hashtable is legacy Java or not is really irrelevant for this site's purposes. – D.W. Jun 5 '14 at 6:39

I suggest a variation of distribution counting:

1. Read the text and insert all the word encountered into a trie, maintaining in each node a count, how often the word represented by this node has occured. Additionally keep track of the highest word count say maxWordCound . -- $O(n)$
2. Initialize an array of size maxWordCount. Entry type are lists of strings. -- $O(n)$, since the count can't be higher.
3. Traverse the trie and for each node add the corresponding string to the array entry indicated by the count. -- $O(n)$, since the total length of strings is bounded by $n$.
4. Traverse the array in descending order and output the desired number of strings. -- $O(n)$, since that is a bound on both the size of and the amount of data in the array.

You can probably replace the trie by other data structures in the first phase.

• +1, although i am not sure about this. It is O(n) since the number of words to return is bounded by n, the number of characters, but is this what the question asks? Or a result independent of the number of returned words? – Nikos M. Jun 5 '14 at 20:00
• @NikosM. It is; $n$ is a general worst-case upper bound on the number of returned words, not assumptions necessary. – Raphael Jun 5 '14 at 20:24
• @Raphael, yeap correct i am thinking about this since it was asked in an interview, possible tricks in the question.. – Nikos M. Jun 5 '14 at 20:26
• I'm wondering if there is a space efficient linear time algorithm. – saadtaame Jun 5 '14 at 23:22
• @saadtaame, yup, that's an interesting question. Might be worth posting separately as a separate question. It's not just space efficiency; the trie solution is also pointer-intensive, which might make it slower in practice (given how the memory hierarchy works in real machines). "Efficiency" is different from worst-case running time. It's not unusual for a clean $O(n \lg n)$ time algorithm to beat a pointer-intensive $O(n)$ time algorithm, so this question already seems to be ruling out some potential algorithms that might be a better choice in practice. – D.W. Jun 6 '14 at 1:05

Your algorithm does not even run in time $O(n \log n)$; inserting $\Theta(n)$ things in a hashtable costs time $\Omega(n^2)$ already (worst-case).

What follows is wrong; I'm leaving it here for the time being for illustrative purposes.

The following algorithm runs in worst-case time $O(n)$ (assuming an alphabet $\Sigma$ of constant size), $n$ the number of characters in the text.

1. Construct a suffix tree of the text, e.g. with Ukkonen's algorithm.

If the construction does not already do this, add the number of reachable leaves to every (inner) node.

2. Traverse the tree from the root and cut off all branches at the first (white)space.

3. Traverse the tree and sort the list of children of every node by their leaf counts.

4. The yield of the tree (leaves from left to right) is now a list of all words, sorted by frequency.

Regarding runtime:

1. Ukkonen's algorithm (in its enhanced form) runs in time $O(n)$; maintaining leaf counts does not increase the $\Theta$-cost of the algorithm.
2. We have to traverse one node per character of every word that occurs in the text. Since there are at most $n$ different word-character pairs, we visit at most $n$ nodes.
3. We visit at most $n$ nodes (cf 2.) and spend time $O(|\Sigma| \cdot \log |\Sigma|) = O(1)$ per node.
4. We can obtain the yield (which has of course size $O(n)$) by a simple traversal in time $O(n)$ (cf 2.).

More precise bounds can be obtained by parametrising runtime with the number of different words; if there are few, the tree is small after 2.

• The algorithm is incorrect (it does not sort). I am no longer sure linear time is even possible. – Raphael Jun 5 '14 at 8:57

Use a hash table (e.g., HashMap) to collect all words and their frequencies. Then, use counting sort to sort the words in order of decreasing frequency. Since all frequencies are integers in the range $1..n$, counting sort takes $O(n)$ time. The total expected running time is $O(n)$, which is more than likely more than sufficient for all practical purposes (unless the interviewer mentioned something that was left out of your question). Make sure to mention that this is expected running time rather than worst-case running time.

This might not be the answer that a teacher would be looking for in an algorithms class, because it is expected $O(n)$ running time rather than $O(n)$ worst-case running time. If you want to score extra points at the interview question, you can mention casually in an off-hand manner that of course this is expected running time, but it can also be done in $O(n)$ worst-case running time by replacing the hash table with a more sophisticated data structure -- and you'd be happy to elaborate on how you'd choose between algorithms in a situation like this.

Or, if you want to play it a bit safer, before giving an answer, first ask "do you care about the difference between expected $O(n)$ running time and worst-case $O(n)$ running time?". Then tailor your answer accordingly. Be prepared for the interviewer to ask you how you would choose, in practice. (If so, score! That's a question you should be able to hit out of the ballpark.)

• Storing $\Theta(n)$ things in a hashtable takes $\Omega(n^2)$ time in the worst-case already. – Raphael Jun 5 '14 at 7:11
• I can't speak for the interviewers, but I'm hesitant to use their sloppiness as excuse for more of the same. Also, this site is about the science (as you yourself commented above), not about hand-waving "how will I get paid sooner" programming tricks. – Raphael Jun 5 '14 at 20:29
• As long as this understanding is made explicit, I'm fine with that. I have seen too many questions here that were founded in confusion because some implicit "understanding" promoted wrong ideas. – Raphael Jun 5 '14 at 20:35

The gathering of occurrence counts is O(n), so the trick is really only finding the top k occurrence counts.

A heap is a common way to aggregate the top k values, although other methods can be used (see https://en.wikipedia.org/wiki/Partial_sorting).

Assuming k is second param above, and that it's a constant in the problem statement (it appears to be):

1. Build a trie of words with occurrence counts on each node.
2. Initialize a heap of size k.
3. Traverse the trie and min-probe/insert each (leaf, occurrence-count) pair in the top-k heap.
4. Output the top k leaves and counts (this is actually kind of a pain because you need parent pointers to map each leaf back to a word).

Since the heap size is a constant, the heap operations are O(1), so step 3 is O(n).

The heap could also be maintained dynamically while building the trie.

Hashtable based solution

Not sure why hashtable makes the complexity $\Omega(n^2)$ if $n$ is the number of characters (not words).

If you iterate through every character in the document and as you are iterating, calculate the hashcode of the word, you will have gone through $n$ characters. That is, as soon as a letter is encountered, the word begins, so start computing hash until the word ends (there are some special cases for punctuation but those do not affect the complexity). For every word, once the hash is computed, add it to a hashtable. This is to avoid going over every word twice, i.e. first to iterate through the document to find the words and then to insert them in a hashtable, although the complexity in that case could also be $\Omega(n)$.

Collisions in the hashtable are surely a problem, and depending on how big the original hashtable was and how good the hashing algorithm is, one could approach close to $O(1)$ for insertions and keeping counts and thus $O(n)$ for the algorithm, although at the expense of memory. However, I still cannot appreciate how the worst case can be asserted to be $O(n^2)$ if $n$ is the number of characters.

The assumption is that the hashing algorithm is linear in time in relation to the number of characters.

Alternatively, assuming English, since the length of the words is well-known, I would instead create a grid and apply radix sort which is $O(kN)$ where $k$ would be the maximum length of a word in the English language, and $N$ is the total number of words. Given $n$ is the number of characters in the document, and $k$ is a constant, asymptotically this amounts $O(n)$.
Now count the frequency of each word. Since the words are sorted, we will be comparing each word to its preceding word to see if it's the same one or different. If it's the same, we remove the word and add a count to the previous. If different, just make the count 1 and move on. This requires $2n$ comparisons where $n$ is the number of characters, and thus $O(n)$ in complexity as a whole.
• (1) Since in most texts the maximum length of the words is bounded by a constant, the number of words is $\Theta(n)$ as well. (2) Depending on the hash function, it may not be possible to compute the hash on the fly while reading the word. (3) In the worst case, all words hash to the same location in the table, making insert and lookup $\Theta(n)$. – FrankW Jun 11 '14 at 21:51
• Hi FrankW. (2) I am stating that we could pick function (i.e. a rolling hash) that we can compute on the fly. Even if not, the overall complexity does not change as long as hashing is linear time, because reading and hashing would be $O(n+n)$ operations. (3) Of course, but that depends on the choice of algorithm again. There are many algorithms that do substantially better if the words are different. For the same word, you just increase the count on a single entry. As an analogy, when I have to pick a sorting algorithm, worst case can be $O(n^2)$ but I typically pick better :-) – Omer Iqbal Jun 11 '14 at 23:12
• Why does a hash table lead to $O(n^2)$ worst-case complexity? It's because in principle the worst-case running time of a hashtable is very bad. In practice this worst-case almost never seems to eventuate (particularly if you choose the hash function correctly, with randomization and other techniques), and one can even prove theorems to justify why that is so, but if this is a question about asymptotic complexity, practical considerations like that arguably go out the window (or at least that's the argument you may hear). – D.W. Jun 12 '14 at 6:34
• Ordinary hash tables inserts are $O(n^2)$ because a collision requires the item to be placed elsewhere. Here, we do not need to insert the duplicates. 1) Same word repeats: then up the count, this is guaranteed to be $O(1)$ plus hashing time. 2) Different words same hash: that's where the question on how good/bad the hash is, and if the size of the table is just too small. I agree it's $\Omega(1)$, but depending on choices I also stated that "one could approach close to $O(1)$ for insertions and keeping counts". We could discuss what table size and function(s) could get us close to $O(1)$. – Omer Iqbal Jun 12 '14 at 18:31