Re: [algogeeks] Re: a google question
I have formulated a solution, not strictly of O(n), but I guess it's close.
===
1. for(int k=0;kn;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 mb_mani...@yahoo.com wrote:
I guess your solution would also be proved incorrect with the following,
Numbers in bold are the two arrays.
125122 120 110 104 103 102 101
100 99 9897
130255 252 250 240 234 233 232 231 230
229 228 227
128253 250 248 238 232 231 230 229 228
227 226 225
126251 248 246 236 230 229 228 227 226
225 224 223
125250 247 245 235 229 228 227 226 225
224 223 222
105230 227 225 215 209 208 207 206 205
204 203 202
104229 226 224 214 208 207 206 205 204
203 202 201
103228 225 223 213 207 206 205 204 203
202 201 200
102227 224 222 212 206 205 204 203 202
201 200 199
101226 223 221 211 205 204 203 202 201
200 199 198
100225 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 (jlength(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
Re: [algogeeks] Re: a google question
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 999897
130255 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
104229 226 224 214 208 207 206 205 204
203 202 201
103228 225 223 213 207 206 205 204 203
202 201 200
102227 224 222 212 206 205 204 203 202
201 200 199
101226 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 (jlength(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
Re: [algogeeks] Re: a google question
@Gene
I think there is some mistake in this programe.
when the input is :
a[ ] = {30,25,19,16}
b[ ] = {20,18,14,10}
the right result should be 30+20, 30+18, 25+20,30+14
but the output of your programe is 30+20,30+18,25+20,25+18
Best Regards!
2010/5/4 Gene gene.ress...@gmail.com
I propose this solution (it's C89):
#include stdio.h
//int a[] = { 8, 7, 4, 3, 2, 1, 1, 1, 1, 1 };
//int b[] = { 34, 23, 21, 19, 15, 13, 11, 8, 4, 2 };
int a[] = { 6, 5, 4, 3, 2, 1 };
int b[] = { 9, 8, 6, 5, 3, 2 };
void find_pairs(int *a, int *b, int n)
{
int iamax[100], ibmax[100], i, ia, ib;
for (i = 0; i n; i++)
iamax[i] = ibmax[i] = -1;
ia = ib = 0;
for (i = 0; i n; i++) {
printf((%d,%d)\n, a[ia], b[ib]);
if (a[ia + 1] + b[ibmax[ia + 1] + 1] b[ib + 1] +
a[iamax[ib + 1] +
1])
ib = ++ibmax[++ia];
else
ia = ++iamax[++ib];
}
}
int main(void)
{
find_pairs(a, b, sizeof a / sizeof a[0]);
return 0;
}
--
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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: a google question
@Amit Agarwal you are missing some pairs having larger some than you mentioned.. for example 7 + 49 = 56 which is greater than 53 similarly 7 + 48 7 + 47 (3 + 49 =52) (50 +1 = 51) --- Regards Jitendra Kushwaha Undergradute Student Computer Science Eng. MNNIT, Allahabad -- 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.
Re: [algogeeks] Re: a google question
1.Suppose you have Array A and B like this. 2.A = [10,7,3,1] , B = [50,49,48,47,46] 3.Arrange/Assume numbers in a three column table such that First n rows are the made up of A[1] and members of B. Rest m rows are made up of B[1] and members of A. Column 3 keeps sum of column 1 and 2. It would look something like this. ⁃10 50 60 ⁃10 49 59 ⁃10 48 58 ⁃10 47 57 ⁃10 46 56 ⁃50 10 60 ⁃50 7 57 ⁃50 3 53 ⁃50 1 51 4.Now sort the rows based on column 3 in O(n) time. Remember its a merge operation of two sorted lists so O(n+m) time. 5. Pick any number of pairs from top. They are in decreasing order of their value. This algorithm takes time in O(n). But there might be space complexity issues if array size is too large. -Regards Amit Agarwal On Mon, May 3, 2010 at 9:48 PM, Jitendra Kushwaha jitendra.th...@gmail.comwrote: @Varun output for your test cases are as below: arr1[0] + arr2[0] = 38 arr1[0] + arr2[1] = 33 arr1[1] + arr2[0] = 28 arr1[0] + arr2[0] = 38 arr1[0] + arr2[1] = 37 arr1[0] + arr2[2] = 36 what i was talking about worst case was that is if one have to find more than N elements of array c then it is possible that one of the pointer go out of boundry of 1 to N in worst case. On Mon, May 3, 2010 at 6:48 PM, Varun Nagpal varun.nagp...@gmail.comwrote: @Jitendra I dont think so.Try these 2 examples to check: A[1..n] :20 10 0 B[1..n] :18 13 5 Ans :38 33 28 A[1..n] :20 10 0 B[1..n] :18 17 16 Ans :38 37 36 My conjecture is: In the worst case, instead of combination of 1st element of first array with all elements of second array, we need to instead choose 2 elements from first array and than take combination with all elements of second array. Also before doing this we need to choose from which array should these 2 elements be extracted. I have already suggested before how to do this. -- 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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: a google question
@Varun output for your test cases are as below: arr1[0] + arr2[0] = 38 arr1[0] + arr2[1] = 33 arr1[1] + arr2[0] = 28 arr1[0] + arr2[0] = 38 arr1[0] + arr2[1] = 37 arr1[0] + arr2[2] = 36 what i was talking about worst case was that is if one have to find more than N elements of array c then it is possible that one of the pointer go out of boundry of 1 to N in worst case. On Mon, May 3, 2010 at 6:48 PM, Varun Nagpal varun.nagp...@gmail.comwrote: @Jitendra I dont think so.Try these 2 examples to check: A[1..n] :20 10 0 B[1..n] :18 13 5 Ans :38 33 28 A[1..n] :20 10 0 B[1..n] :18 17 16 Ans :38 37 36 My conjecture is: In the worst case, instead of combination of 1st element of first array with all elements of second array, we need to instead choose 2 elements from first array and than take combination with all elements of second array. Also before doing this we need to choose from which array should these 2 elements be extracted. I have already suggested before how to do this. -- 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.
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 (jlength(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.
Re: [algogeeks] Re: a google question
The Question only ask to print first n number and each array array is of size n So in the worst case we will take combination of 1st element of first array with all the element of second array. my above code runs in O(n) taking this considerations... any comments or test case where it fails??? Regards Jitendra Kushwaha Undergradute Student Computer Science Eng. MNNIT, Allahabad -- 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.
Re: [algogeeks] Re: a google question
@satish
ur solution is of o(nlogn) complexty
@ jitendra
suppose p11 and p21 r pointing at index 0 and p12 at 4 and p22 at 1. now
suppose at ths point d s greater than b and c. now u increment p11 and p21.
but it can be a case that a[0] + b[2] is next greatest value bt t wont
work for ur algo.
On 3 May 2010 00:46, Shishir Mittal 1987.shis...@gmail.com wrote:
@Algoose : No, it is not necessary that first n elements must contain A[0]
or B[0]. For e.g.
A = {40,30,15,10}
B = {40,30,15,10}
Required 4 largest values = {40+40, 40+30, 40+30, 30+30}.
@Satish:
A very nice algorithm provided by you.
Complexity Analysis for the algorithm provided by you:
Creation of max-heap of n elements = O(n).
Time to add a new element to the heap after extracting the maximum - O(log
n)
Overall Complexity = O(n log n)
Regards,
Shishir
On Sun, May 2, 2010 at 10:52 PM, Satish satish.mit...@gmail.com wrote:
This problem can be simplified to a variation of merge part of merge
sort algorithm.
- Break the set S having n^2 values into n individual arrays of length
n, say S1, S2,..Sn, where S1 = [a1+b1, a1+b2,...a1+bn].
- One can observe that each Si has entries which are themselves sorted
within Si.
- Perform merge of S1, S2,..Sn where take the largest values of each
Si, and create a heap of these individual max values.
- In each step, return the max value from heap and then add the next
max value from the Si that had the current max value and add it in the
max-heap.
- Repeat this step n times and then exit.
Time: O(n).
Satish
On May 2, 5:41 pm, Algoose Chase harishp...@gmail.com wrote:
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::vectorint,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
--
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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: a google question
@divya
I try to simulate what you said for the given array
index : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
array1:8, 7, 4 ,3 , 2, 1, 1, 1, 1, 1
^ ^
p11 p12
*p11 = 8 and *p12 = 3
index : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
array2:34, 23, 21, 19, 15, 13, 11, 8, 4, 2
^^
p21 p22
*p21 = 34 and *p22 = 23
a = 8 + 34 = 41//arr1[0] + arr2[0]
b = 8 +23 = 31//arr1[0] + arr2[1]
c = 34 + 3 = 37 //arr1[4] + arr2[0] greatest !!!
d = 7 +23 = 30 //arr1[1] + arr2[1]
arr1[0] + arr2[2] = 29 which is less than c..
here is my output
arr1[0] + arr2[0] = 42
arr1[1] + arr2[0] = 41
arr1[2] + arr2[0] = 38
arr1[3] + arr2[0] = 37
arr1[4] + arr2[0] = 36
arr1[5] + arr2[0] = 35
arr1[6] + arr2[0] = 35
arr1[7] + arr2[0] = 35
arr1[8] + arr2[0] = 35
arr1[9] + arr2[0] = 35
i have attached the code try with replacing arr1 and arr2 with
following.and the case u wanted to point out will be taken throught in
following test case..(arr1[0] + arr2[1] = 9+27 = 36 will be taken before
arr1[6] + arr2[0] = 1+34 = 35 )
int arr1[N] = {9,7,4,3,2,1,1,1,1,1};
int arr2[N] = {34,27,21,19,15,13,11,8,4,2};
Regards
Jitendra Kushwaha
--
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.
#include cstdio
#includeiostream
using namespace std;
#define N 10
int main(void)
{
int arr1[N] = {8,7,4,3,2,1,1,1,1,1};
int arr2[N] = {34,23,21,19,15,13,11,8,4,2};
int *p11,*p12,*p21,*p22;
int w=0,x=0,y=0,z=0;
p11 = p12 = arr1;
p21 = p22 = arr2;
int f1;
f1 = 0;
for(int i=0;iN;i++) {
int ans=0;
int a,b,c,d;
a = *p11 + *p21;
b = *p11 + *p22;
c = *p21 + *p12;
d = *(p11+1) + *(p21+1);
//printf(a=%d b=%d c=%d d=%d\n,a,b,c,d); //debug
if(f1==0)ans = a ,p12++ , p22++ , f1=1 , printf( arr1[%d] + arr2[%d] = ,w,y),x++,z++;
else if(b = c b = d )ans = b , p22++ , printf( arr1[%d] + arr2[%d] = ,w,z),z++;
else if(c = b c = d )ans = c , p12++ , printf( arr1[%d] + arr2[%d] = ,x,y),x++;
elseans = d , p11++ , p21++ , printf( arr1[%d] + arr2[%d] = ,w,y),w++,y++;
printf(%d\n,ans);
}
}
Re: [algogeeks] Re: a google question
slight change in value of c c = 34 + 2 = 36 //arr1[4] + arr2[0] greatest !!! my mistake.. -- 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.
Re: [algogeeks] Re: a google question
@Jitendra I dont think so.Try these 2 examples to check: A[1..n] :20 10 0 B[1..n] :18 13 5 Ans :38 33 28 A[1..n] :20 10 0 B[1..n] :18 17 16 Ans :38 37 36 My conjecture is: In the worst case, instead of combination of 1st element of first array with all elements of second array, we need to instead choose 2 elements from first array and than take combination with all elements of second array. Also before doing this we need to choose from which array should these 2 elements be extracted. I have already suggested before how to do this. On Mon, May 3, 2010 at 1:23 PM, Jitendra Kushwaha jitendra.th...@gmail.com wrote: The Question only ask to print first n number and each array array is of size n So in the worst case we will take combination of 1st element of first array with all the element of second array. my above code runs in O(n) taking this considerations... any comments or test case where it fails??? Regards Jitendra Kushwaha Undergradute Student Computer Science Eng. MNNIT, Allahabad -- 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.
[algogeeks] Re: a google question
On May 3, 9:43 am, Jitendra Kushwaha jitendra.th...@gmail.com wrote:
@divya
I try to simulate what you said for the given array
index : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
array1 : 8, 7, 4 ,3 , 2, 1, 1, 1, 1, 1
^ ^
p11 p12
*p11 = 8 and *p12 = 3
index : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
array2 : 34, 23, 21, 19, 15, 13, 11, 8, 4, 2
^ ^
p21 p22
*p21 = 34 and *p22 = 23
a = 8 + 34 = 41 //arr1[0] + arr2[0]
b = 8 +23 = 31 //arr1[0] + arr2[1]
c = 34 + 3 = 37 //arr1[4] + arr2[0] greatest !!!
d = 7 +23 = 30 //arr1[1] + arr2[1]
arr1[0] + arr2[2] = 29 which is less than c..
here is my output
arr1[0] + arr2[0] = 42
arr1[1] + arr2[0] = 41
arr1[2] + arr2[0] = 38
arr1[3] + arr2[0] = 37
arr1[4] + arr2[0] = 36
arr1[5] + arr2[0] = 35
arr1[6] + arr2[0] = 35
arr1[7] + arr2[0] = 35
arr1[8] + arr2[0] = 35
arr1[9] + arr2[0] = 35
i have attached the code try with replacing arr1 and arr2 with
following.and the case u wanted to point out will be taken throught in
following test case..(arr1[0] + arr2[1] = 9+27 = 36 will be taken before
arr1[6] + arr2[0] = 1+34 = 35 )
int arr1[N] = {9,7,4,3,2,1,1,1,1,1};
int arr2[N] = {34,27,21,19,15,13,11,8,4,2};
Regards
Jitendra Kushwaha
--
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.
I propose this solution (it's C89):
#include stdio.h
//int a[] = { 8, 7, 4, 3, 2, 1, 1, 1, 1, 1 };
//int b[] = { 34, 23, 21, 19, 15, 13, 11, 8, 4, 2 };
int a[] = { 6, 5, 4, 3, 2, 1 };
int b[] = { 9, 8, 6, 5, 3, 2 };
void find_pairs(int *a, int *b, int n)
{
int iamax[100], ibmax[100], i, ia, ib;
for (i = 0; i n; i++)
iamax[i] = ibmax[i] = -1;
ia = ib = 0;
for (i = 0; i n; i++) {
printf((%d,%d)\n, a[ia], b[ib]);
if (a[ia + 1] + b[ibmax[ia + 1] + 1] b[ib + 1] + a[iamax[ib +
1] +
1])
ib = ++ibmax[++ia];
else
ia = ++iamax[++ib];
}
}
int main(void)
{
find_pairs(a, b, sizeof a / sizeof a[0]);
return 0;
}
--
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.
[algogeeks] Re: a google question
This problem can be simplified to a variation of merge part of merge
sort algorithm.
- Break the set S having n^2 values into n individual arrays of length
n, say S1, S2,..Sn, where S1 = [a1+b1, a1+b2,...a1+bn].
- One can observe that each Si has entries which are themselves sorted
within Si.
- Perform merge of S1, S2,..Sn where take the largest values of each
Si, and create a heap of these individual max values.
- In each step, return the max value from heap and then add the next
max value from the Si that had the current max value and add it in the
max-heap.
- Repeat this step n times and then exit.
Time: O(n).
Satish
On May 2, 5:41 pm, Algoose Chase harishp...@gmail.com wrote:
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::vectorint,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 1987.shis...@gmail.comwrote:
This problem has been discussed before @
http://groups.google.co.in/group/algogeeks/browse_thread/thread/9c1e1...
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
rvignesh1...@gmail.com wrote:
@divya You're rite. Post a solution if you have one.
--
Regards,
Vignesh
On 2 May 2010 13:14, divya jain sweetdivya@gmail.com 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 shoonya.mo...@gmail.com wrote:
@Algoose Chase
point taken
Thanks
Mohit Ranjan
Samsung India Software Operations.
On Sat, May 1, 2010 at 8:43 PM, Algoose Chase
harishp...@gmail.comwrote:
@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 shoonya.mo...@gmail.com
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(loop0) // 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
shoonya.mo...@gmail.com wrote:
Hi Divya,
A[n] and B[n] are two array
loop=n, i=n-1, j=n-1;
while(loop0) // 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
sweetdivya@gmail.comwrote:
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.comalgogeeks%2bunsubscr...@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] Re: a google question
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)}
I assume each pair is stored as a sum i.e ai + bi and also that I
have paired them in a way such that we find a pair ai bi for some
i in 1..N and and 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(then I think its not possible to solve in
O(n) but in O(nlogn)).
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.
[algogeeks] Re: a google question
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.
