Re: [algogeeks] Re: Urgent...plz help
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 Wed, Aug 17, 2011 at 11:47 PM, Amol Sharma amolsharm...@gmail.comwrote: 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 aditi.garg.6...@gmail.comwrote: @ 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 aditi.garg.6...@gmail.comwrote: thank u so much dave :) On Thu, Aug 18, 2011 at 8:44 AM, Dave dave_and_da...@juno.com 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 end of the million numbers, the heap will contain the smallest 100 numbers. If there are n numbers and you want the smallest k, this algorithm is O(n log k). Dave On Aug 17, 10:05 pm, aditi garg aditi.garg.6...@gmail.com wrote: How to find the set of smallest 100 numbers out of 1 million numbers... -- 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. -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- 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.
Re: [algogeeks] Re: Urgent...plz help
Create a B+ tree and extract the first 100 leaf nodes On Thu, Aug 18, 2011 at 1:05 PM, Ankur Garg ankurga...@gmail.com 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 with Quick Sort ..Also there is one method median of medians one which has worst case complexity as O(n) Regards Ankur On Wed, Aug 17, 2011 at 11:47 PM, Amol Sharma amolsharm...@gmail.comwrote: 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 aditi.garg.6...@gmail.comwrote: @ 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 aditi.garg.6...@gmail.comwrote: thank u so much dave :) On Thu, Aug 18, 2011 at 8:44 AM, Dave dave_and_da...@juno.com 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 end of the million numbers, the heap will contain the smallest 100 numbers. If there are n numbers and you want the smallest k, this algorithm is O(n log k). Dave On Aug 17, 10:05 pm, aditi garg aditi.garg.6...@gmail.com wrote: How to find the set of smallest 100 numbers out of 1 million numbers... -- 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. -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- 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. -- regards Apoorve Mohan -- 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: Urgent...plz help
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 apoorvemo...@gmail.comwrote: Create a B+ tree and extract the first 100 leaf nodes On Thu, Aug 18, 2011 at 1:05 PM, Ankur Garg ankurga...@gmail.com 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 with Quick Sort ..Also there is one method median of medians one which has worst case complexity as O(n) Regards Ankur On Wed, Aug 17, 2011 at 11:47 PM, Amol Sharma amolsharm...@gmail.comwrote: 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 aditi.garg.6...@gmail.comwrote: @ 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 aditi.garg.6...@gmail.comwrote: thank u so much dave :) On Thu, Aug 18, 2011 at 8:44 AM, Dave dave_and_da...@juno.com 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 end of the million numbers, the heap will contain the smallest 100 numbers. If there are n numbers and you want the smallest k, this algorithm is O(n log k). Dave On Aug 17, 10:05 pm, aditi garg aditi.garg.6...@gmail.com wrote: How to find the set of smallest 100 numbers out of 1 million numbers... -- 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. -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- 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. -- regards Apoorve Mohan -- regards Apoorve Mohan -- 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: Urgent...plz help
i agree with amol it cud be max-heap only... Regards, PAYAL GUPTA On Thu, Aug 18, 2011 at 2:26 PM, Apoorve Mohan apoorvemo...@gmail.comwrote: 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 apoorvemo...@gmail.comwrote: Create a B+ tree and extract the first 100 leaf nodes On Thu, Aug 18, 2011 at 1:05 PM, Ankur Garg ankurga...@gmail.com 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 with Quick Sort ..Also there is one method median of medians one which has worst case complexity as O(n) Regards Ankur On Wed, Aug 17, 2011 at 11:47 PM, Amol Sharma amolsharm...@gmail.comwrote: 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 aditi.garg.6...@gmail.comwrote: @ 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 aditi.garg.6...@gmail.com wrote: thank u so much dave :) On Thu, Aug 18, 2011 at 8:44 AM, Dave dave_and_da...@juno.comwrote: @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 there are n numbers and you want the smallest k, this algorithm is O(n log k). Dave On Aug 17, 10:05 pm, aditi garg aditi.garg.6...@gmail.com wrote: How to find the set of smallest 100 numbers out of 1 million numbers... -- 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. -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- 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. -- regards Apoorve Mohan -- regards Apoorve Mohan -- 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: Urgent...plz help
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) while a heap takes only O(nlogk) and kn On Thu, Aug 18, 2011 at 1:18 PM, Apoorve Mohan apoorvemo...@gmail.comwrote: Create a B+ tree and extract the first 100 leaf nodes On Thu, Aug 18, 2011 at 1:05 PM, Ankur Garg ankurga...@gmail.com 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 with Quick Sort ..Also there is one method median of medians one which has worst case complexity as O(n) Regards Ankur On Wed, Aug 17, 2011 at 11:47 PM, Amol Sharma amolsharm...@gmail.comwrote: 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 aditi.garg.6...@gmail.comwrote: @ 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 aditi.garg.6...@gmail.comwrote: thank u so much dave :) On Thu, Aug 18, 2011 at 8:44 AM, Dave dave_and_da...@juno.com 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 end of the million numbers, the heap will contain the smallest 100 numbers. If there are n numbers and you want the smallest k, this algorithm is O(n log k). Dave On Aug 17, 10:05 pm, aditi garg aditi.garg.6...@gmail.com wrote: How to find the set of smallest 100 numbers out of 1 million numbers... -- 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. -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- 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. -- regards Apoorve Mohan -- 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: Urgent...plz help
thank u so much dave :) On Thu, Aug 18, 2011 at 8:44 AM, Dave dave_and_da...@juno.com 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 end of the million numbers, the heap will contain the smallest 100 numbers. If there are n numbers and you want the smallest k, this algorithm is O(n log k). Dave On Aug 17, 10:05 pm, aditi garg aditi.garg.6...@gmail.com wrote: How to find the set of smallest 100 numbers out of 1 million numbers... -- 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. -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- 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: Urgent...plz help
@ 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 aditi.garg.6...@gmail.comwrote: thank u so much dave :) On Thu, Aug 18, 2011 at 8:44 AM, Dave dave_and_da...@juno.com 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 end of the million numbers, the heap will contain the smallest 100 numbers. If there are n numbers and you want the smallest k, this algorithm is O(n log k). Dave On Aug 17, 10:05 pm, aditi garg aditi.garg.6...@gmail.com wrote: How to find the set of smallest 100 numbers out of 1 million numbers... -- 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. -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- 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: Urgent...plz help
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 aditi.garg.6...@gmail.comwrote: @ 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 aditi.garg.6...@gmail.comwrote: thank u so much dave :) On Thu, Aug 18, 2011 at 8:44 AM, Dave dave_and_da...@juno.com 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 end of the million numbers, the heap will contain the smallest 100 numbers. If there are n numbers and you want the smallest k, this algorithm is O(n log k). Dave On Aug 17, 10:05 pm, aditi garg aditi.garg.6...@gmail.com wrote: How to find the set of smallest 100 numbers out of 1 million numbers... -- 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. -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- 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.
