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 <[email protected]>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 <
> [email protected]> wrote:
>
>> @divya You're rite. Post a solution if you have one.
>>
>> --
>> Regards,
>> Vignesh
>>
>>
>> On 2 May 2010 13:14, divya jain <[email protected]> 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 <[email protected]> wrote:
>>>
>>>> @Algoose Chase
>>>>
>>>> point taken
>>>> Thanks
>>>>
>>>>
>>>> Mohit Ranjan
>>>> Samsung India Software Operations.
>>>>
>>>>
>>>> On Sat, May 1, 2010 at 8:43 PM, Algoose Chase <[email protected]>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 <[email protected]
>>>>> > 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 <
>>>>>> [email protected]> 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 <[email protected]>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 [email protected].
>>>>>>>> To unsubscribe from this group, send email to
>>>>>>>> [email protected]<algogeeks%[email protected]>
>>>>>>>> .
>>>>>>>> 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 [email protected].
>>>>>> To unsubscribe from this group, send email to
>>>>>> [email protected]<algogeeks%[email protected]>
>>>>>> .
>>>>>> 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 [email protected].
>>>>> To unsubscribe from this group, send email to
>>>>> [email protected]<algogeeks%[email protected]>
>>>>> .
>>>>> 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 [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected]<algogeeks%[email protected]>
>>>> .
>>>> 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 [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected]<algogeeks%[email protected]>
>>> .
>>> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
