Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
1  
Use a hash table. –  Yuval Filmus Jun 5 at 5:17
    
Using a hashtable does not solve the problem. Furthermore, hashtable is legacy Java. –  user2712937 Jun 5 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 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 at 5:38
2  
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 at 6:39
show 2 more comments

3 Answers 3

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. -- $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.

share|improve this answer
    
+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 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 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 at 20:26
    
I'm wondering if there is a space efficient linear time algorithm. –  saadtaame Jun 5 at 23:22
3  
@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 at 1:05
add comment

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.

share|improve this answer
    
The algorithm is incorrect (it does not sort). I am no longer sure linear time is even possible. –  Raphael Jun 5 at 8:57
add comment

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.

Radix sort based solution

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.

The top few longest words in English are ridiculously long, but then one could cap the word length at a reasonable number (such as 30 or smaller) and truncate words accepting the margin of error that might come with it.

share|improve this answer
    
(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 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 at 23:12
    
(3) Whatever hash function you choose, I can come up with an input where that specific function degrades. And choosing the hash function after knowing the input is usually not an option. (And remember that the comment you were presumably addressing was about the worst case, not the typical case.) –  FrankW Jun 12 at 4:34
    
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 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 at 18:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.