@Arun: Did you get the job? (No offence meant)
@Richa: Could you please elaborate what decreasing order means?
Assuming decreasing order means ..last word should be printed in the
end..and if the user adds (appends) new word then it should also be
printed,
this can be done quite elegantly using singly linked list in just one
pass.
_dufus
On Aug 14, 2:55 pm, Arun N <arunn3...@gmail.com> wrote:
> 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
-~----------~----~----~----~------~----~------~--~---
