Hmm..
@Richa I am assuming the frequency 4,2,7,1 of A,B,C,D word is within
the last N words window(not in the whole window).
If thats true then I think q can be solved be done in two steps:-
Step 1: we can reach the last n elements using two pointers approach
in O(M-N) i.e. O(M) time
// M = number of words in the document
// N = using the same notation as in question.
Step 2: once we reach the first element of last N elements, we can
just put them in max heap (for decreasing order)
where key is the frequency of the elements
We can update the list as user types by extracting the root : O(1)
Inserting the new typed element at root O(1)
heapifying O(K)
_dufus
On Aug 14, 10:45 pm, richa gupta <richa.cs...@gmail.com> wrote:
> @ 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
-~----------~----~----~----~------~----~------~--~---
