I said that to the interviewer push all elements in max heap and delete k
times
but it requires heap of size 'n'
and he asked me for the most optimal version
of using heap of size 'K' only.
On Fri, Aug 14, 2009 at 4:46 PM, umesh kewat <umesh1...@gmail.com> wrote:
> Do just opposite thing to get result delete k elements from Max heap of
> element der u also get k largest numbers....
>
> On Fri, Aug 14, 2009 at 3:25 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.
>>
>>
>>
>>
>
>
> --
> Thanks & Regards
>
> Umesh kewat
> 09966796569
>
>
>
>
>
> >
>
--
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
-~----------~----~----~----~------~----~------~--~---
