This question was asked to me in Amazon interview
1)use hash table to store a word and its count
now the problem is reduced to find 'K' largest numbers(based on count) in
the hash table
the optimal solution is to use minheap of size 'K'
add first k elements in the minheap
now take the k+1 element
[as it is min heap the root will have minimum of all 'K' elements]
while(k<n){
if( a[k+1] > root)
pop the root and add to heap and heapify
else if(a[k+1] < root)
go to k+2 element
}
at the end the heap will have "K" elements which is the required answer
time complexity O( n-K + nlogK )
space complexity O(K) for heap
as u get new words u can do the same check to add to heap or discard
Arun,
On Fri, Aug 14, 2009 at 12:53 PM, richa gupta <richa.cs...@gmail.com> wrote:
>
> You have to develop a piece of code that can be attached to a program
> like Microsoft Word, which would list the last "N" words of the
> document in descending order of their occurence, and update the list
> as the user types. What code would you write? Using pseudo code is
> fine, just list the basic things you would consider
>
> --
> Richa Gupta
> (IT-BHU,India)
>
> >
>
--
Potential is not what U have, its what U think U have!!!
It is better to worn out than rust.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
