Re: [algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..

[patidarc...@gmail.com]

@Dave:

simple, you have to find the first k elements , if you can find the* kth
last element *also then we are done

eg : let you have array [1,6,3,8,9,23,15]  in this you have to find the
first k=3 elements
if we can find 3rd element then from that we can know what the rest 1st &
2nd can be
from selection algorithm we can get 3rd element is *6

*we can traverse again in array & find all the element less than 6 which are
1 & 3
so first k element are 6 , 1 & 3

*note *: selection algorithm does not load whole array at a time it divide
into parts & loads so whether our array is million or billion we don't have
to worry about memory here , it break it into parts & checks

hope my explanation easy
please let me know if you have any question..


On Sat, Mar 26, 2011 at 7:42 PM, Dave  wrote:

> @Patidarachat: Please explain how to use the selection algorithm in
> the presence of the restriction that you can't hold all of the data in
> memory at once.
>
> Dave
>
> On Mar 22, 3:55 am, "patidarc...@gmail.com" 
> wrote:
> > please check this also
> > Selection_algorithm 
> >
> > On Tue, Mar 22, 2011 at 10:13 AM, Rajeev Kumar  >wrote:
> >
> >
> >
> >
> >
> >
> >
> > >http://flexaired.blogspot.com/2011/03/big-file-containing-billions-of.
> ..
> >
> > > On Mon, Mar 21, 2011 at 4:05 AM, Natansh Verma <
> natansh.ve...@gmail.com>wrote:
> >
> > >> @dave -was this a constraint since the beginning? In case it was, I am
> > >> sorry I didn't notice.
> >
> > >> In that case, the heap method ought to work better. I dont think the
> > >> quicksort method will work.
> >
> > >> Sent from my iPhone
> >
> > >> On 20-Mar-2011, at 23:00, Dave  wrote:
> >
> > >> > @Natansh: How do you do this with the constraint that your RAM is so
> > >> > small that you cannot accomodate all of the numbers at once?
> >
> > >> > Dave
> >
> > >> > On Mar 20, 9:04 am, Natansh Verma  wrote:
> > >> >> There's another way... use the partitioning method for quicksort to
> > >> find the
> > >> >> k smallest elements. Then it should take expected time as O(n +
> klogk).
> > >> >> Plus, it is in-place.
> >
> > >> >> On Wed, Mar 16, 2011 at 7:26 PM, asit  wrote:
> > >> >>> I agree with munna
> >
> > >> >>> --
> > >> >>> 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?hl=en.-Hide quoted text -
> >
> > >> >> - Show quoted text -
> >
> > >> > --
> > >> > 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?hl=en.
> >
> > >> --
> > >> 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?hl=en.
> >
> > > --
> > > Thank You
> > > Rajeev Kumar
> >
> > > --
> > > 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?hl=en.
> >
> > Thanks
> > Rajesh Patidar~- Hide quoted text -
> >
> > - Show quoted text -
>
> --
> 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?hl=en.
>
>


-- 
--Thanks--


-- 
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?hl=en.

[algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..

[Dave]

@Patidarachat: Please explain how to use the selection algorithm in
the presence of the restriction that you can't hold all of the data in
memory at once.

Dave

On Mar 22, 3:55 am, "patidarc...@gmail.com" 
wrote:
> please check this also
> Selection_algorithm 
>
> On Tue, Mar 22, 2011 at 10:13 AM, Rajeev Kumar 
> wrote:
>
>
>
>
>
>
>
> >http://flexaired.blogspot.com/2011/03/big-file-containing-billions-of...
>
> > On Mon, Mar 21, 2011 at 4:05 AM, Natansh Verma 
> > wrote:
>
> >> @dave -was this a constraint since the beginning? In case it was, I am
> >> sorry I didn't notice.
>
> >> In that case, the heap method ought to work better. I dont think the
> >> quicksort method will work.
>
> >> Sent from my iPhone
>
> >> On 20-Mar-2011, at 23:00, Dave  wrote:
>
> >> > @Natansh: How do you do this with the constraint that your RAM is so
> >> > small that you cannot accomodate all of the numbers at once?
>
> >> > Dave
>
> >> > On Mar 20, 9:04 am, Natansh Verma  wrote:
> >> >> There's another way... use the partitioning method for quicksort to
> >> find the
> >> >> k smallest elements. Then it should take expected time as O(n + klogk).
> >> >> Plus, it is in-place.
>
> >> >> On Wed, Mar 16, 2011 at 7:26 PM, asit  wrote:
> >> >>> I agree with munna
>
> >> >>> --
> >> >>> 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?hl=en.-Hide quoted text -
>
> >> >> - Show quoted text -
>
> >> > --
> >> > 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?hl=en.
>
> >> --
> >> 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?hl=en.
>
> > --
> > Thank You
> > Rajeev Kumar
>
> > --
> > 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?hl=en.
>
> Thanks
> Rajesh Patidar~- Hide quoted text -
>
> - Show quoted text -

-- 
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?hl=en.

Re: [algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..

[patidarc...@gmail.com]

please check this also
Selection_algorithm 



On Tue, Mar 22, 2011 at 10:13 AM, Rajeev Kumar wrote:

>
> http://flexaired.blogspot.com/2011/03/big-file-containing-billions-of-numbers.html
>
> On Mon, Mar 21, 2011 at 4:05 AM, Natansh Verma wrote:
>
>> @dave -was this a constraint since the beginning? In case it was, I am
>> sorry I didn't notice.
>>
>> In that case, the heap method ought to work better. I dont think the
>> quicksort method will work.
>>
>> Sent from my iPhone
>>
>> On 20-Mar-2011, at 23:00, Dave  wrote:
>>
>> > @Natansh: How do you do this with the constraint that your RAM is so
>> > small that you cannot accomodate all of the numbers at once?
>> >
>> > Dave
>> >
>> > On Mar 20, 9:04 am, Natansh Verma  wrote:
>> >> There's another way... use the partitioning method for quicksort to
>> find the
>> >> k smallest elements. Then it should take expected time as O(n + klogk).
>> >> Plus, it is in-place.
>> >>
>> >>
>> >>
>> >> On Wed, Mar 16, 2011 at 7:26 PM, asit  wrote:
>> >>> I agree with munna
>> >>
>> >>> --
>> >>> 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?hl=en.- Hide quoted text -
>> >>
>> >> - Show quoted text -
>> >
>> > --
>> > 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?hl=en.
>> >
>>
>> --
>> 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?hl=en.
>>
>>
>
>
> --
> Thank You
> Rajeev Kumar
>
> --
> 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?hl=en.
>


Thanks
Rajesh Patidar~

-- 
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?hl=en.

Re: [algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..

[Ankit Sinha]

Thanks dave.. :-)

On Thu, Mar 24, 2011 at 10:54 AM, Dave  wrote:
> @Ankit: You read in the first k numbers and form a max-heap of these
> numbers. This takes O(k) space. Then you read the rest of the file one
> number at a time. If the number is greater than the root of the max
> heap, then it is not one of the k smallest numbers. If it less than
> the root, replace the root with the smaller number and re-establish
> the heap condition. Thus, the memory requirement remains O(k). When
> you reach the end of the data, then the heap contains the k smallest
> numbers. If there are N numbers in the file, the work is O(N * log k).
>
> Dave
>
> On Mar 23, 11:22 pm, Ankit Sinha  wrote:
>> Guys,
>>
>> My intention was to understand how to manage max heap of k size into
>> memory. Means we have millions of numbers that we can't load into RAM
>> then how in the very first go we going to load only k size and how
>> will track of rest numbers. Can anybody code it? Do we need file to
>> store million numbers and then read say first k numbers and then take
>> another chunk?
>>
>> Thanks,
>>
>> Ankit!!
>>
>>
>>
>> On Tue, Mar 22, 2011 at 10:13 AM, Rajeev Kumar  
>> wrote:
>> >http://flexaired.blogspot.com/2011/03/big-file-containing-billions-of...
>>
>> > On Mon, Mar 21, 2011 at 4:05 AM, Natansh Verma 
>> > wrote:
>>
>> >> @dave -was this a constraint since the beginning? In case it was, I am
>> >> sorry I didn't notice.
>>
>> >> In that case, the heap method ought to work better. I dont think the
>> >> quicksort method will work.
>>
>> >> Sent from my iPhone
>>
>> >> On 20-Mar-2011, at 23:00, Dave  wrote:
>>
>> >> > @Natansh: How do you do this with the constraint that your RAM is so
>> >> > small that you cannot accomodate all of the numbers at once?
>>
>> >> > Dave
>>
>> >> > On Mar 20, 9:04 am, Natansh Verma  wrote:
>> >> >> There's another way... use the partitioning method for quicksort to
>> >> >> find the
>> >> >> k smallest elements. Then it should take expected time as O(n + klogk).
>> >> >> Plus, it is in-place.
>>
>> >> >> On Wed, Mar 16, 2011 at 7:26 PM, asit  wrote:
>> >> >>> I agree with munna
>>
>> >> >>> --
>> >> >>> 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?hl=en.-Hide quoted text -
>>
>> >> >> - Show quoted text -
>>
>> >> > --
>> >> > 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?hl=en.
>>
>> >> --
>> >> 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?hl=en.
>>
>> > --
>> > Thank You
>> > Rajeev Kumar
>>
>> > --
>> > 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?hl=en.- Hide quoted text -
>>
>> - Show quoted text -
>
> --
> 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?hl=en.
>
>

-- 
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?hl=en.

Re: [algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..

[Akash Agrawal]

http://tech-queries.blogspot.com/2009/05/find-largest-20-elements-from-billions.html

Regards,
Akash Agrawal
http://tech-queries.blogspot.com/


On Tue, Mar 22, 2011 at 10:13 AM, Rajeev Kumar wrote:

>
> http://flexaired.blogspot.com/2011/03/big-file-containing-billions-of-numbers.html
>
>
> On Mon, Mar 21, 2011 at 4:05 AM, Natansh Verma wrote:
>
>> @dave -was this a constraint since the beginning? In case it was, I am
>> sorry I didn't notice.
>>
>> In that case, the heap method ought to work better. I dont think the
>> quicksort method will work.
>>
>> Sent from my iPhone
>>
>> On 20-Mar-2011, at 23:00, Dave  wrote:
>>
>> > @Natansh: How do you do this with the constraint that your RAM is so
>> > small that you cannot accomodate all of the numbers at once?
>> >
>> > Dave
>> >
>> > On Mar 20, 9:04 am, Natansh Verma  wrote:
>> >> There's another way... use the partitioning method for quicksort to
>> find the
>> >> k smallest elements. Then it should take expected time as O(n + klogk).
>> >> Plus, it is in-place.
>> >>
>> >>
>> >>
>> >> On Wed, Mar 16, 2011 at 7:26 PM, asit  wrote:
>> >>> I agree with munna
>> >>
>> >>> --
>> >>> 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?hl=en.- Hide quoted text -
>> >>
>> >> - Show quoted text -
>> >
>> > --
>> > 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?hl=en.
>> >
>>
>> --
>> 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?hl=en.
>>
>>
>
>
> --
> Thank You
> Rajeev Kumar
>
> --
> 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?hl=en.
>

-- 
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?hl=en.

[algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..

[ligerdave]

@Ankit

Simplify what @Dave had said:

1.you build a max heap with first k numbers
2. always compare array[k+n] where n=1.array.size-k
   if array[k+n] >= k, compare next element in the array
   else replace top with array[k+n] and heapify

so the worst case is like @Dave gave: O((N-5) * log k). in the real
case, very likely you get better coz for many numbers in the array,
you don't have to go down the heap for comparison

On Mar 24, 12:22 am, Ankit Sinha  wrote:
> Guys,
>
> My intention was to understand how to manage max heap of k size into
> memory. Means we have millions of numbers that we can't load into RAM
> then how in the very first go we going to load only k size and how
> will track of rest numbers. Can anybody code it? Do we need file to
> store million numbers and then read say first k numbers and then take
> another chunk?
>
> Thanks,
>
> Ankit!!
>
>
>
>
>
>
>
> On Tue, Mar 22, 2011 at 10:13 AM, Rajeev Kumar  
> wrote:
> >http://flexaired.blogspot.com/2011/03/big-file-containing-billions-of...
>
> > On Mon, Mar 21, 2011 at 4:05 AM, Natansh Verma 
> > wrote:
>
> >> @dave -was this a constraint since the beginning? In case it was, I am
> >> sorry I didn't notice.
>
> >> In that case, the heap method ought to work better. I dont think the
> >> quicksort method will work.
>
> >> Sent from my iPhone
>
> >> On 20-Mar-2011, at 23:00, Dave  wrote:
>
> >> > @Natansh: How do you do this with the constraint that your RAM is so
> >> > small that you cannot accomodate all of the numbers at once?
>
> >> > Dave
>
> >> > On Mar 20, 9:04 am, Natansh Verma  wrote:
> >> >> There's another way... use the partitioning method for quicksort to
> >> >> find the
> >> >> k smallest elements. Then it should take expected time as O(n + klogk).
> >> >> Plus, it is in-place.
>
> >> >> On Wed, Mar 16, 2011 at 7:26 PM, asit  wrote:
> >> >>> I agree with munna
>
> >> >>> --
> >> >>> 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?hl=en.-Hide quoted text -
>
> >> >> - Show quoted text -
>
> >> > --
> >> > 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?hl=en.
>
> >> --
> >> 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?hl=en.
>
> > --
> > Thank You
> > Rajeev Kumar
>
> > --
> > 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?hl=en.

-- 
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?hl=en.

[algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..

[Dave]

@Ankit: You read in the first k numbers and form a max-heap of these
numbers. This takes O(k) space. Then you read the rest of the file one
number at a time. If the number is greater than the root of the max
heap, then it is not one of the k smallest numbers. If it less than
the root, replace the root with the smaller number and re-establish
the heap condition. Thus, the memory requirement remains O(k). When
you reach the end of the data, then the heap contains the k smallest
numbers. If there are N numbers in the file, the work is O(N * log k).

Dave

On Mar 23, 11:22 pm, Ankit Sinha  wrote:
> Guys,
>
> My intention was to understand how to manage max heap of k size into
> memory. Means we have millions of numbers that we can't load into RAM
> then how in the very first go we going to load only k size and how
> will track of rest numbers. Can anybody code it? Do we need file to
> store million numbers and then read say first k numbers and then take
> another chunk?
>
> Thanks,
>
> Ankit!!
>
>
>
> On Tue, Mar 22, 2011 at 10:13 AM, Rajeev Kumar  
> wrote:
> >http://flexaired.blogspot.com/2011/03/big-file-containing-billions-of...
>
> > On Mon, Mar 21, 2011 at 4:05 AM, Natansh Verma 
> > wrote:
>
> >> @dave -was this a constraint since the beginning? In case it was, I am
> >> sorry I didn't notice.
>
> >> In that case, the heap method ought to work better. I dont think the
> >> quicksort method will work.
>
> >> Sent from my iPhone
>
> >> On 20-Mar-2011, at 23:00, Dave  wrote:
>
> >> > @Natansh: How do you do this with the constraint that your RAM is so
> >> > small that you cannot accomodate all of the numbers at once?
>
> >> > Dave
>
> >> > On Mar 20, 9:04 am, Natansh Verma  wrote:
> >> >> There's another way... use the partitioning method for quicksort to
> >> >> find the
> >> >> k smallest elements. Then it should take expected time as O(n + klogk).
> >> >> Plus, it is in-place.
>
> >> >> On Wed, Mar 16, 2011 at 7:26 PM, asit  wrote:
> >> >>> I agree with munna
>
> >> >>> --
> >> >>> 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?hl=en.-Hide quoted text -
>
> >> >> - Show quoted text -
>
> >> > --
> >> > 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?hl=en.
>
> >> --
> >> 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?hl=en.
>
> > --
> > Thank You
> > Rajeev Kumar
>
> > --
> > 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?hl=en.- Hide quoted text -
>
> - Show quoted text -

-- 
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?hl=en.

Re: [algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..

[Ankit Sinha]

Guys,

My intention was to understand how to manage max heap of k size into
memory. Means we have millions of numbers that we can't load into RAM
then how in the very first go we going to load only k size and how
will track of rest numbers. Can anybody code it? Do we need file to
store million numbers and then read say first k numbers and then take
another chunk?

Thanks,

Ankit!!

On Tue, Mar 22, 2011 at 10:13 AM, Rajeev Kumar  wrote:
> http://flexaired.blogspot.com/2011/03/big-file-containing-billions-of-numbers.html
>
> On Mon, Mar 21, 2011 at 4:05 AM, Natansh Verma 
> wrote:
>>
>> @dave -was this a constraint since the beginning? In case it was, I am
>> sorry I didn't notice.
>>
>> In that case, the heap method ought to work better. I dont think the
>> quicksort method will work.
>>
>> Sent from my iPhone
>>
>> On 20-Mar-2011, at 23:00, Dave  wrote:
>>
>> > @Natansh: How do you do this with the constraint that your RAM is so
>> > small that you cannot accomodate all of the numbers at once?
>> >
>> > Dave
>> >
>> > On Mar 20, 9:04 am, Natansh Verma  wrote:
>> >> There's another way... use the partitioning method for quicksort to
>> >> find the
>> >> k smallest elements. Then it should take expected time as O(n + klogk).
>> >> Plus, it is in-place.
>> >>
>> >>
>> >>
>> >> On Wed, Mar 16, 2011 at 7:26 PM, asit  wrote:
>> >>> I agree with munna
>> >>
>> >>> --
>> >>> 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?hl=en.- Hide quoted text -
>> >>
>> >> - Show quoted text -
>> >
>> > --
>> > 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?hl=en.
>> >
>>
>> --
>> 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?hl=en.
>>
>
>
>
> --
> Thank You
> Rajeev Kumar
>
> --
> 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?hl=en.
>

-- 
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?hl=en.

Re: [algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..

[Rajeev Kumar]

http://flexaired.blogspot.com/2011/03/big-file-containing-billions-of-numbers.html

On Mon, Mar 21, 2011 at 4:05 AM, Natansh Verma wrote:

> @dave -was this a constraint since the beginning? In case it was, I am
> sorry I didn't notice.
>
> In that case, the heap method ought to work better. I dont think the
> quicksort method will work.
>
> Sent from my iPhone
>
> On 20-Mar-2011, at 23:00, Dave  wrote:
>
> > @Natansh: How do you do this with the constraint that your RAM is so
> > small that you cannot accomodate all of the numbers at once?
> >
> > Dave
> >
> > On Mar 20, 9:04 am, Natansh Verma  wrote:
> >> There's another way... use the partitioning method for quicksort to find
> the
> >> k smallest elements. Then it should take expected time as O(n + klogk).
> >> Plus, it is in-place.
> >>
> >>
> >>
> >> On Wed, Mar 16, 2011 at 7:26 PM, asit  wrote:
> >>> I agree with munna
> >>
> >>> --
> >>> 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?hl=en.- Hide quoted text -
> >>
> >> - Show quoted text -
> >
> > --
> > 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?hl=en.
> >
>
> --
> 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?hl=en.
>
>


-- 
Thank You
Rajeev Kumar

-- 
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?hl=en.

Re: [algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..

[Natansh Verma]

@dave -was this a constraint since the beginning? In case it was, I am sorry I 
didn't notice.

In that case, the heap method ought to work better. I dont think the quicksort 
method will work.

Sent from my iPhone

On 20-Mar-2011, at 23:00, Dave  wrote:

> @Natansh: How do you do this with the constraint that your RAM is so
> small that you cannot accomodate all of the numbers at once?
> 
> Dave
> 
> On Mar 20, 9:04 am, Natansh Verma  wrote:
>> There's another way... use the partitioning method for quicksort to find the
>> k smallest elements. Then it should take expected time as O(n + klogk).
>> Plus, it is in-place.
>> 
>> 
>> 
>> On Wed, Mar 16, 2011 at 7:26 PM, asit  wrote:
>>> I agree with munna
>> 
>>> --
>>> 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?hl=en.- Hide quoted text -
>> 
>> - Show quoted text -
> 
> -- 
> 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?hl=en.
> 

-- 
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?hl=en.

[algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..

[Dave]

@Natansh: How do you do this with the constraint that your RAM is so
small that you cannot accomodate all of the numbers at once?

Dave

On Mar 20, 9:04 am, Natansh Verma  wrote:
> There's another way... use the partitioning method for quicksort to find the
> k smallest elements. Then it should take expected time as O(n + klogk).
> Plus, it is in-place.
>
>
>
> On Wed, Mar 16, 2011 at 7:26 PM, asit  wrote:
> > I agree with munna
>
> > --
> > 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?hl=en.- Hide quoted text -
>
> - Show quoted text -

-- 
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?hl=en.

Re: [algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..

[Natansh Verma]

There's another way... use the partitioning method for quicksort to find the
k smallest elements. Then it should take expected time as O(n + klogk).
Plus, it is in-place.

On Wed, Mar 16, 2011 at 7:26 PM, asit  wrote:

> I agree with munna
>
> --
> 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?hl=en.
>
>

-- 
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?hl=en.

[algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..

[asit]

I agree with munna

-- 
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?hl=en.

[algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..

[asit]

I agree with munna

-- 
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?hl=en.

[algogeeks] Re: Find the first K smallest element from 1 million sized array ...Amazon Question..

[Aviral Gupta]

http://coders-stop.blogspot.com/2010/12/kth-largest-element.html

On Mar 16, 12:18 pm, Srirang Ranjalkar  wrote:
> there are two ways to do it:
> 1.
>  if k <<< n, then simply have an array of size k. put the firsk k elements
> in the array and sort it. For each number you see which is less than arr[k],
> insert that number in the array and remove one element and sort it again. So
> by the end of the input you are left with k smallest elements and arr[k]
> gives you the kth smallest element.
> O(n.k.lgk) (assuming that sort is of order O(k.lgk))
>
> 2.
> Maintain a max heap of size K, populate it and when you see an element less
> than the max of the heap, insert it and call heapify(). That way by the end
> of your input sequence you'll be left with k smallest elements in the heap.
>
> Thank you,
> Srirang Ranjalkar
>
> --
> " Luck is when hard work meets opportunity "
>
> On Wed, Mar 16, 2011 at 12:38 PM, Sriram gupta wrote:
>
> > Use Max - heap of size K.
>
> > On Wed, Mar 16, 2011 at 10:36 AM, DIPANKAR DUTTA <
> > dutta.dipanka...@gmail.com> wrote:
>
> >> use heap tree to slove this..
> >> plz see careercup post..
>
> >> On Wed, Mar 16, 2011 at 10:31 AM, Ankit Sinha wrote:
>
> >>> Asked in Amazon interview..
>
> >>> Find the first K smallest element from 1 million sized array . Assume
> >>> your ram memory is so small that it cannot accommodate all 1 Million
> >>> element at once.
> >>> Guys provide your inputs on the same...
>
> >>> Thanks,
> >>> Ankit
>
> >>> --
> >>> 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?hl=en.
>
> >> --
> >> DIPANKAR DUTTA
> >> M-TECH,Computer Science & Engg.
> >> E&C Dept,IIT ROORKEE
> >> Uttarakhand , India – 247667
> >> ---
> >> website:http://people.iitr.ernet.in/shp/09535009/Website/index.html
> >> ph no-09045809987
> >> Lab: 286454
> >> email:dipan...@iitr.ernet.in
>
> >>  --
> >> 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?hl=en.
>
> >  --
> > 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?hl=en.

-- 
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?hl=en.