I have formulated a solution, not strictly of O(n), but I guess it's close.
===
1. for(int k=0;k<n;k++) {
2
get_max_of_temp_array(maxVal,visited_index_of_A/*Va[i]*/,visited_index_of_b/*Vb[j]*/);
3. Print_Max_of( a[va[i]+1] +b[Vb[j]] , a[va[i]] + b[vb[j+1]]
,maxVal)
4 insert_other_two_of_the_triplet();
5 (i,j)=(index_of_maximum_value printed_above);
6 update_Va_&_Vb_accordingly();
}
insert... on line 6 is to insert the (set-)element in an insertion-sorted
array.
But still not O(n). :(
On Wed, Jul 28, 2010 at 4:11 PM, manish bhatia <[email protected]> wrote:
> 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 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 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 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.
