Menu
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?
224
A successful outcome from the Debrief part of the Amazon interview process leads to an offer in 9 out of 10 cases. However, as you can anticipate, sometimes things don't follow this script.
Can you expect a repeat Amazon interview question? No. Each interviewer should be assigned 2 completely unique Leadership Principles to test you.
Amazon coding interviews are really challenging. The questions are difficult, specific to Amazon, and cover a wide range of topics. The good news is that the right preparation can make a big difference.
Amazon's Behavioral Interview Is Tricky And Challenging Engineers applying to positions across the board go through a mandatory behavioral interview where they're assessed on a bunch of behavioral aspects. The questions are usually around Amazon's 14 leadership principles that the company values deeply.
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).
87
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
