no I missed the chance bcoz of this question.
Arun,
On Sat, Aug 15, 2009 at 12:45 PM, Dufus <rahul.dev.si...@gmail.com> wrote:
>
> 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)
>
> >
>
--
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
-~----------~----~----~----~------~----~------~--~---
