How would you implement a top 3 word count in a text editor application?

Question

Sigiloso · Accepted Answer

Using Heap and Hash will solve the problem optimally.
Keep a hash of word as key and count as value. And keep a Min heap of 3 elements.
Build the heap with first 3 elements.
For every new element increase the count in HashMap.
Check if the element is in the heap, then update the count and reheapify.
Else check if the element count is greater than top element of Min heap, if yes then replace that element with our new element and reheapify.
Else don''t touch our heap and keep counting.
This will make sure the heap will always have top 3 elements.
Complexity: O(n) as heapify is constant always.

Garukun · Answer

MaxHeap/priorityQueue whose key is the word itself and the priority is the word count.

When you need the top three words, just pop the heap three times 3*O(logN).

person · Answer

max-Heap

Sigiloso · Answer

Another approach would be to sort in place in n log n. Then scan the sorted list of words and maintain a count of top three.

Sigiloso · Answer

This can be done using Linked Hash. 
Each element of Hash has two pointer. Min pointing to element which comes next in the seq with  count.
When we add new word, either it will be added to hash or updated its count. If count is updated then we need to correct the Min and Max pointer accordingly. Also we need to corecct obj.Min.Max pointer and obj.Max.Min pointer accordingly.
Keep track of the Max and Min element of the heap elements.
Other optimization can be done to improve the worst case scenario like storing head pointer of list of words which has same count.

interview candidate · Answer

Can we use a BST to store word and length values? And then do a pre-order traversal?

Amazon

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas