I guess your solution would also be proved incorrect with the following,

Numbers in bold are the two arrays.
        
          125     122     120     110     104     103     102     101     
100     99        98        97 


130    255     252     250     240     234     233     232     231     230     
229     228     227 
128   253     250     248     238     232     231     230     229     228     
227     226     225
126   251     248     246     236     230     229     228     227     226     
225     224     223
125   250     247     245     235     229     228     227     226     225     
224     223     222
105   230     227     225     215     209     208     207     206     205     
204     203     202
104    229     226     224     214     208     207     206     205     204     
203     202     201
103    228     225     223     213     207     206     205     204     203     
202     201     200
102    227     224     222     212     206     205     204     203     202     
201     200     199
101    226     223     221     211     205     204     203     202     201     
200     199     198
100   225     222     220     210     204     203     202     201     200     
199     198     197
99     224     221     219     209     203     202     201     200     199     
198     197     196
98     224     221     219     209     203     202     201     200     199     
198     197     196

 manish...




________________________________
From: Varun Nagpal <varun.nagp...@gmail.com>
To: Algorithm Geeks <algogeeks@googlegroups.com>
Sent: Mon, 3 May, 2010 12:26:24 PM
Subject: Re: [algogeeks] Re: a google question

Guys no one commented on my solution? Any takes on it?


Anyways, below is my solution (in pseudo code)

Pre-condition: A and B are sequences of equal length and sorted in
descending order
Input: Sequences A[1..N] and B[1..N] of equal lengths(N)
Ouput: Sequence C[1..N] containing sorted sum of ordered pairs from
cartesian products of A, B or B,A

Sort(A,B)
{
k = 1
N = length(A) = length(B)
C[1..2*N] = []            // Empty array
cart_prod_order = 0   // 0 -> AxB, 1 -> BxA. 0 is default

// Complexity : O(N)
while(k != N+1)
{
   if (A[k] < B [k])
   {
    cart_prod_order = 1
    break
   }
   else
   {
    k = k + 1
   }
}

// Choose the correct order of Cartesian product sum
// Complexity: Theta(2N) = O(N)
if (cart_prod_order == 1)
{
    // take cartesian product of B and A, storing the sum of ordered
pair (b,a) in each element of C
    C[1..2N] = B[1..2] x A[1..N]
}
else
{
   // take cartesian product of A and B, storing the sum of ordered
pair (a,b) in each element of C
   C[1..2N] = A[1..2] x B[1..N]
}

// Merge
// C[1..N] and C[N+1..2N] are already sorted in descending order
// Complexity: Theta(N)
C[1..2N] = Merge(C[1..N],C[N+1..2N])

return C[1..N]
}

Merge(C,D)
{
i=1,j=1,k=1
E = []
while(i<=length(C) OR j<=length(D))
{
   if(i<=length(C) AND (j>length(D) OR C[i]>D[j]))
   {
    E[k] = C[i]
    i = i + 1
   }
   else
   {
    E[k] = D[j]
    j = j + 1
   }
   k = k + 1
}

return E;
}

On Fri, Apr 30, 2010 at 7:50 PM, banu <varun.nagp...@gmail.com> wrote:
> Nice question:
>
> 1. |A| = |B| i.e I assume their cardinality is equal
>
> 2. A(n) = { a1, a2  a3, ...aN} such that a1>=a2>=a3...>=aN
> 3. B(n) = { b1, b2  b3, ...bN} such that b1>=b2>=b3...>=bN
>
> 4. S(n^2) = A x B = {(a1,b1), (a1,b2)....(a1,bN),
>                              (a2,b1), (a2,b2)....(a2,bN),
>                               ....
>                              (aN,b1), (aN,b2)....(aN,bN)}
>
>  assuming we have added in a way such that we find a pair  ai > bi,
> for some i in 1..N such that a(i-1) = b(i-1)
>
> A first observation is that in the worst case, the first 2N numbers in
> S will contain the final result of N numbers.
> i.e in  (a1,b1), (a1,b2)....(a1,bN), (a2,b1), (a2,b2)....(a2,bN)
>
> In the best case first N numbers in S will contain the final N numbers
> (already sorted in decreasing order)
> i.e in  (a1,b1), (a1,b2)....(a1,bN)
>
> Now, if we consider again the worst case scenario, then we can first
> divide 2N numbers in two groups of size N each and each of this group
> is already sorted in decreasing order.
> i.e  (a1,b1), (a1,b2)....(a1,bN) and (a2,b1), (a2,b2)....(a2,bN)
>
> Now we can simply apply Merge Algorithm on these 2 already sorted
> arrays of size N each in O(N) time, which solves the problem
>
> I can be wrong only if the the results lie outside first 2N
> numbers(which I hope is not the case).
>
>
> On Apr 30, 2:05 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.
>> For more options, visit this group 
>>athttp://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.
>
>

-- 
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.

-- 
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.

Reply via email to