amazon interview prob

Question

There is a big file of words which is dynamically changing. We are continuously adding some words into it. How would you keep track of top 10 trending words at each moment?

I found this question in a blog but I couldn't understand the answer. The answer is: hash table + min-heap

I understand why hashtable but not min-heap part, can someone help me?

Answer 1

If it's top 10 trending words then you should use a max-heap along with a hash-table.

When a new word is added to the file then:

• Create a new element x with x.key=word and x.count=1.
• Add x to the hash-table. O(1).
• Add x to the max-heap. O(lgn).

When an existing word is added to the file then:

• Find x in the hash-table. O(1).
• Update x.count to x.count++.

When there is a need to retrieve the top 10 trending words then:

• Extract 10 times from the max-heap. 10*O(lgn)=O(10*lgn)=O(lgn).

As you can see, all the needed operations are done in at most O(lgn).