This problem can be simplified to a variation of merge part of merge
sort algorithm.
- Break the set S having n^2 values into n individual arrays of length
n, say S1, S2,..Sn, where S1 = [a1+b1, a1+b2,...a1+bn].
- One can observe that each Si has entries which are themselves sorted
within Si.
- Perform merge of S1, S2,..Sn where take the largest values of each
Si, and create a heap of these individual max values.
- In each step, return the max value from heap and then add the next
max value from the Si that had the current max value and add it in the
max-heap.
- Repeat this step n times and then exit.
Time: O(n).
Satish
On May 2, 5:41 pm, Algoose Chase <harishp...@gmail.com> wrote:
> 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/9c1e1...
>
> > 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
> athttp://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 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.
