sorry bt i dint get the approach. can u please explain a bit more by taking examples...thanks a lot in advance
On 14 May 2010 10:12, Rohit Saraf <rohit.kumar.sa...@gmail.com> wrote: > This was also asked in my Yahoo! Interview this year. :) > > > -------------------------------------------------- > Rohit Saraf > Second Year Undergraduate, > Dept. of Computer Science and Engineering > IIT Bombay > http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> > > > On Fri, May 14, 2010 at 10:10 AM, Rohit Saraf <rohit.kumar.sa...@gmail.com > > wrote: > >> exactly .. >> >> -------------------------------------------------- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14> >> >> >> >> On Fri, May 14, 2010 at 10:07 AM, vignesh radhakrishnan < >> rvignesh1...@gmail.com> wrote: >> >>> This is for kth largest. Change it for kth smallest >>> >>> In fact, this problem is amenable to something very similar to binary >>> search. Suppose my arrays are A and B. The idea is to keep track of two >>> indices, a (for A) and b (for B), such that a + b = k - 1 (it's very >>> important to maintain this invariant). It's easy to check whether A[a] or >>> B[b] is the answer: A[a] is the answer if and only if >>> >>> B[b-1] <= A[a] <= B[b], >>> >>> and B[b] is the answer if and only if >>> >>> A[a-1] <= B[b] <= A[a], >>> >>> where we use the convention that A[-1] = B[-1] = "negative infinity." >>> (This can be determined in constant time.) Moreover, if neither of these is >>> the case, you can divide the problem in half: if A[a] < B[b-1], you restrict >>> your attention to the portion of A above index a and the portion of B below >>> index b, and otherwise (it must be the case that B[b] < A[a-1]), you >>> restrict your attention to the portion of A below index a and the portion of >>> B above index b. (If you start with a and b in the middle of the arrays and >>> always make the new indices be in the middle of the subarrays you're >>> considering at that point, this step will always divide the problem in >>> half.) >>> Thanks to Lux Perpetua <http://forums.devshed.com/member.php?u=74699> >>> source: >>> >>> http://forums.devshed.com/software-design-43/finding-kth-largest-element-in-a-union-of-two-arrays-137322.html >>> >>> >>> On 13 May 2010 19:34, divya <sweetdivya....@gmail.com> wrote: >>> >>>> You are given two sorted lists of size m and n. Give an O(log m+log n) >>>> time algorithm for computing the kth smallest element in the union of >>>> the two lists >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To post to this group, send email to algoge...@googlegroups.com. >>>> To unsubscribe from this group, send email to >>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >>>> . >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>>> >>> >>> >>> -- >>> There are two kinds of people. Those who care for others and The others >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@googlegroups.com. >>> To unsubscribe from this group, send email to >>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@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 algoge...@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.
