Hi will this work ?
since we need Set S with n pairs of largest values , any such pair within the set would (always) contain A[0] or B[0] because they maximize the value of the pair. so // code snippet typedef std::vector<int,int> Pairs; Pairs.push(A[0],B[0]) int i = 1; // index for ListA int j = 1; // index for list B count = 1; while( count <= n) { if( A[0] + B[j] > B[0] + A[i] ) { Pairs.push(A[0],B[j]) j++; } else { Pairs.Add(A[i],B[0]) i++; } count++; } since there are n items in both the lists, j and i wont go beyond n in the while loop On Sun, May 2, 2010 at 3:44 PM, Shishir Mittal <1987.shis...@gmail.com>wrote: > This problem has been discussed before @ > http://groups.google.co.in/group/algogeeks/browse_thread/thread/9c1e1aa8cf1ed437/d451cd9468d985f7 > > I believe, the problem can't be solved in O(n) but only in O(nlog n). > > @Divya: Are you sure the interviewer explicitly asked for an O(n) time > algorithm? > > > On Sun, May 2, 2010 at 1:48 PM, vignesh radhakrishnan < > rvignesh1...@gmail.com> wrote: > >> @divya You're rite. Post a solution if you have one. >> >> -- >> Regards, >> Vignesh >> >> >> On 2 May 2010 13:14, divya jain <sweetdivya....@gmail.com> wrote: >> >>> @Mohit >>> >>> according to ur algo if a[1], b[0] has sum greater than a[0],b[1] >>> then i is incremented i is now 2 so for next iteration u ll compare >>> a[2] b[0] and a[1] b1]. but what about a[0] b[1] this pair s lost forever. >>> think for ths case also. >>> >>> >>> On 2 May 2010 11:22, mohit ranjan <shoonya.mo...@gmail.com> wrote: >>> >>>> @Algoose Chase >>>> >>>> point taken >>>> Thanks >>>> >>>> >>>> Mohit Ranjan >>>> Samsung India Software Operations. >>>> >>>> >>>> On Sat, May 1, 2010 at 8:43 PM, Algoose Chase <harishp...@gmail.com>wrote: >>>> >>>>> @mohit >>>>> >>>>> The idea of DP is fine. >>>>> When you find the Max i dont think you need to include A[i+1]+B[j+1] >>>>> because it can never be greater than both A[i+1]+B[j] and A[i]+B[j+1] >>>>> since >>>>> both the lists are sorted in decreasing order. >>>>> >>>>> >>>>> On Fri, Apr 30, 2010 at 8:47 PM, mohit ranjan <shoonya.mo...@gmail.com >>>>> > wrote: >>>>> >>>>>> oops >>>>>> >>>>>> Sorry didn't read properly >>>>>> last algo was for array sorted in ascending order >>>>>> >>>>>> for this case, just reverse the process >>>>>> >>>>>> >>>>>> A[n] and B[n] are two array >>>>>> >>>>>> loop=n, i=0, j=0; >>>>>> >>>>>> >>>>>> while(loop>0) // for n largest pairs >>>>>> { >>>>>> print A[i]+B[j]; // sum of first index from both array will >>>>>> be max >>>>>> >>>>>> foo = MAX ( A[i+1]+B[j], A[i+1]+B[j+1], A[i]+B[j+1] ) // using >>>>>> DP, moving forward >>>>>> >>>>>> if foo==A[i+1]+B[j]; i++ // only increment A >>>>>> if foo==A[i+1]+B[j+1]; i++; j++ // increment both A and B >>>>>> if foo==A[i]+B[j+1]; j++ // increment only B >>>>>> >>>>>> } >>>>>> >>>>>> >>>>>> >>>>>> Mohit Ranjan >>>>>> Samsung India Software Operations. >>>>>> >>>>>> >>>>>> On Fri, Apr 30, 2010 at 8:40 PM, mohit ranjan < >>>>>> shoonya.mo...@gmail.com> wrote: >>>>>> >>>>>>> Hi Divya, >>>>>>> >>>>>>> >>>>>>> A[n] and B[n] are two array >>>>>>> >>>>>>> loop=n, i=n-1, j=n-1; >>>>>>> >>>>>>> while(loop>0) // for n largest pairs >>>>>>> { >>>>>>> print A[i]+B[j]; // sum of last index from both array will >>>>>>> be max >>>>>>> >>>>>>> foo = MAX ( A[i-1]+B[j], A[i-1]+B[j-1], A[i]+B[j-1] ) // using >>>>>>> DP moving backward >>>>>>> >>>>>>> if foo=A[i-1]+B[j]; i-- // only reduce A >>>>>>> if foo=A[i-1]+B[j-1]; i--; j-- // reduce both A and B >>>>>>> if foo=A[i]+B[j-1]; j-- // reduce only B >>>>>>> } >>>>>>> >>>>>>> Time: O(n) >>>>>>> >>>>>>> >>>>>>> Mohit Ranjan >>>>>>> >>>>>>> >>>>>>> >>>>>>> On Fri, Apr 30, 2010 at 5:35 PM, divya <sweetdivya....@gmail.com>wrote: >>>>>>> >>>>>>>> Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G, >>>>>>>> let's >>>>>>>> say they are decreasingly sorted), we define a set S = {(a,b) | a >>>>>>>> \in >>>>>>>> A >>>>>>>> and b \in B}. Obviously there are n^2 elements in S. The value of >>>>>>>> such >>>>>>>> a pair is defined as Val(a,b) = a + b. Now we want to get the n >>>>>>>> pairs >>>>>>>> from S with largest values. The tricky part is that we need an O(n) >>>>>>>> algorithm. >>>>>>>> >>>>>>>> -- >>>>>>>> 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<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<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.