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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
