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.