@ Dufus,
suppose words A, B,C, D occurs at the frequacny 4, 2, 7 ,1 then the code
shud be able to list it like C, A, B, D .
On 2009-08-14, Dufus <rahul.dev.si...@gmail.com> wrote:
>
>
> @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.
>
> >
>
--
Richa Gupta
(IT-BHU,India)
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
