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 <gupta.sri...@gmail.com>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 <akki12...@gmail.com>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.
