amazon interview prob
algorithm
Solution
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)`.
Problem
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?