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 <[email protected]>
To: Algorithm Geeks <[email protected]>
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 <[email protected]> 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 <[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].
>> 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 [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.
>
>
--
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.
--
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.
