i found this question on some site and it was mentioned there todo in o(n).
i dont have the solution
@ above
ur solution doesnt include the case of ncluding a[i] b[j] it takes only a[i]
b[0] or b[j] a[0]
On 2 May 2010 18:11, 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/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<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.
