@Vipul: This won't work. It would be a bad answer for an interview. There are a million integers, but we don't know their range. So you might need 2^32 bits! Use the heap.
Dave On Dec 25, 9:53 pm, vipul <[email protected]> wrote: > Hi, > > I think this question is very common now a days.. > > Answer is use bit vector. > > Here we are told that 1 million integers. so just create a bit array > of 1m. > > make bit true if it is available. > > start from 1m until you get 10 values with true. > > If interviewer says that it could have duplicate numbers... heap > sounds good solution to go... > > -VIpul > > On Dec 24, 11:20 am, Satya <[email protected]> wrote: > > > > > @Dave, you are right. MAX Heap is correct for your always 11th position > > removal logic. > > ......... > > Satya > > > On Fri, Dec 24, 2010 at 9:45 PM, Satya <[email protected]> wrote: > > > @Dave, I think you meant* *MIN** Heap here? > > > > On Fri, Dec 24, 2010 at 6:46 PM, Dave <[email protected]> wrote: > > > >> @Bittu: Using the first 10 numbers, build a max heap. Then add each > > >> number into the 11th array position (always the 11th position) and > > >> perform the up-heap operation. At the end of the input, discard the > > >> 11th number in the heap. The remaining numbers will be the 10 maximum. > > >> O(n log k) where n = the number of items in the list and k = the > > >> number of maximum items you want. > > > >> Dave > > > >> On Dec 24, 3:32 am, bittu <[email protected]> wrote: > > >> > You Have File of Containing 1 Million Integers You need To Find 10 > > >> > Maximum Integer Out of Them.How You Will Do That ...what is Time & > > >> > space Complexcity of Algorithm that you will use....then optrmize the > > >> > solution.. > > > >> > Constraints- U can't Store Whole File in memory @ one time e.g. if u > > >> > will do that gigabyt eof memory may be reuqired so that should be > > >> > avoided. > > > >> > Regards > > >> > Shashank Mani Narayan > > >> > Birla Instute of Technology,Mesra > > > >> -- > > >> You received this message because you are subscribed to the Google Groups > > >> "Algorithm Geeks" group. > > >> To post to this group, send email to [email protected]. > > >> To unsubscribe from this group, send email to > > >> [email protected]<algogeeks%2bunsubscr...@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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
