@Ankur: When k = 100, the heap method I proposed is O(n). And if you
have to program it from scratch, it is a lot easier than the median of
medians algorithm.
Dave
On Aug 18, 2:35 am, Ankur Garg wrote:
> U can use selection Algorithm to achieve the same ...it has got expected
> running time comp
@XYZ: There are up to n numbers to put into the heap, and an insertion
into a heap of size k is O(log k).
Dave
On Aug 17, 10:42 pm, XYZ wrote:
> @Dave
>
> How did you get the complexity as O(n log k)
>
> On Aug 18, 8:14 am, Dave wrote:
>
>
>
> > @Aditi: Form a max-heap of the first 100 numbers.
When the interviewer says there are a million numbers to consider, it might
mean that we don't have enough memory to hold all those in a single
datastructure. In which case Dave's solution of using a heap of size 100 is
the better one I suppose. I am sure a B+ tree takes O(nlogn to the base b)
whi
i agree with amol
it cud be max-heap only...
Regards,
PAYAL GUPTA
On Thu, Aug 18, 2011 at 2:26 PM, Apoorve Mohan wrote:
> or rather u can just have 100 iterations of selection sort...u'll get the
> min 100 iterations...and this is inplace as well...
>
>
> On Thu, Aug 18, 2011 at 1:18 PM, Apo
or rather u can just have 100 iterations of selection sort...u'll get the
min 100 iterations...and this is inplace as well...
On Thu, Aug 18, 2011 at 1:18 PM, Apoorve Mohan wrote:
> Create a B+ tree and extract the first 100 leaf nodes
>
> On Thu, Aug 18, 2011 at 1:05 PM, Ankur Garg wrote:
>
Create a B+ tree and extract the first 100 leaf nodes
On Thu, Aug 18, 2011 at 1:05 PM, Ankur Garg wrote:
> U can use selection Algorithm to achieve the same ...it has got expected
> running time complexity as O(n) ...Read Wikipedia to see the proper
> implementation..
>
> Just some tweak wit
U can use selection Algorithm to achieve the same ...it has got expected
running time complexity as O(n) ...Read Wikipedia to see the proper
implementation..
Just some tweak with Quick Sort ..Also there is one method median of medians
one which has worst case complexity as O(n)
Regards
Ankur
On
it will be max heap only.in which root denotes the largest number in
your set of 100 smallest
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
On Thu, Aug 18, 2011 at 9:14 AM, aditi garg wrote:
> @ dave : i hv one doubt,we wud be maintaining a max or a m
@ dave : i hv one doubt,we wud be maintaining a max or a min heap??
On Thu, Aug 18, 2011 at 9:11 AM, aditi garg wrote:
> thank u so much dave :)
>
>
> On Thu, Aug 18, 2011 at 8:44 AM, Dave wrote:
>
>> @Aditi: Form a max-heap of the first 100 numbers. Then as you read the
>> remaining numbers, if
@Dave
How did you get the complexity as O(n log k)
On Aug 18, 8:14 am, Dave wrote:
> @Aditi: Form a max-heap of the first 100 numbers. Then as you read the
> remaining numbers, if a number is less than the root of the max-heap,
> replace the root with it and restore the heap condition. When you
thank u so much dave :)
On Thu, Aug 18, 2011 at 8:44 AM, Dave wrote:
> @Aditi: Form a max-heap of the first 100 numbers. Then as you read the
> remaining numbers, if a number is less than the root of the max-heap,
> replace the root with it and restore the heap condition. When you
> reach the en
@Aditi: Form a max-heap of the first 100 numbers. Then as you read the
remaining numbers, if a number is less than the root of the max-heap,
replace the root with it and restore the heap condition. When you
reach the end of the million numbers, the heap will contain the
smallest 100 numbers.
If th
12 matches
Mail list logo
