Re: [algogeeks] Re: google question
@Dave : is it a working code?? i have executed your code but getting wrong output...and value of s is becoming -ve inside loops. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: google question
0.5 ( G(h - 1, i - 1) + G(h - 1, i) ) should be 0.5 ( G(h - 1, i - 1) + G(h
- 1, i+1) )
i am not clear why the parents of a cup in upper row are consecutive?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Feb 28, 2012 at 10:43 AM, Gene gene.ress...@gmail.com wrote:
G is just a helper function. You can in line this function and
eliminate it.
When you do this, you'll end up with
F(h, i) = 0.5 * (l + r)
where l = F(h-1,i-1) - C if 0 = i-1 = h-1 and F(h-1,i-1) C else
0
and r = F(h-1,i) - C if 0 = i = h-1 and F(h-1,i) C else 0
Here l is the left parent's outflow and r is the right parent's.
So you are always computing the h'th row in terms of the (h-1)'th.
For many DPs this means you'll need 2 row buffers. In this one you
only need 1 element back in the current row. You can save this element
in a single variable and get by with one buffer. I.e. note l for a
given value of i is always the previous value of r. And for i=0, l is
always 0 because there is no left parent.
So you end up with
f[0] = L; // fill in the first row
for (ih = 1; ih = h; ih++) { // loop thru rest of rows
double l = 0; // left parent outflow at ii=0 is always 0.
for (ii = 0; ii = ih; ii++) { // loop thru columns
// new right parent outflow
double r = (ii ih f[ii] C) ? f[ii] - C : 0;
f[ii] = 0.5 * (l + r);
l = r; // right parent is left of next row entry
}
}
return (0 = i i = h) ? f[i] : 0;
This is doing the same as Dave's code for all practical purposes. It's
untested but ought to work.
On Feb 27, 10:05 pm, Ashish Goel ashg...@gmail.com wrote:
Gene, your DP is what i was thinking of but in code i could not coreleate
G(h - 1, i - 1) + G(h - 1, i) part (:
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote:
G(h - 1, i - 1) + G(h - 1, i)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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 algogeeks@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: google question
Dave, why the assumption that nothing is coming from left side. Every cup gets something from cup left above and right above itself when they have something extra? Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Mon, Feb 27, 2012 at 8:17 PM, Dave dave_and_da...@juno.com wrote: // nothing coming in from the left -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: google question
Gene, your DP is what i was thinking of but in code i could not coreleate G(h - 1, i - 1) + G(h - 1, i) part (: Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Feb 28, 2012 at 7:50 AM, Gene gene.ress...@gmail.com wrote: G(h - 1, i - 1) + G(h - 1, i) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: google question
@Dave : my code is not that complicated ...if you ignore the helper
function and check fillCup();
it just similar to preorder travesal and pour half to left and right child.
here is the explanation :-
node* fillCup(node *root,float pour,float capacity)
{
float temp;
if(root==NULL)
return NULL;
if(root-data+pour = capacity)
{
if(root-data==0) // if cup is empty then fill cup to full and
reduce pour value for the next level
{
root-data=capacity;
pour=pour-capacity;
}
else
{
// if there is alreday some water in the cup , then it will
fill the cup and reduce pour =pour - empty volume in partially filled cup.
temp=capacity-(root-data);
root-data=capacity;
pour=pour-temp;
if(pour==0)
{
return root;
}
}
}
else
{
// this is for the part where overflow will never happen , even
after adding the poured quantity to the cup.
root-data+=pour;
return root;
}
fillCup(root-left,pour/2,capacity);// pour 1/2 to the left
fillCup(root-right,pour/2,capacity); // pour 1/2 to the right
}
Time complexity = O(n).
your approach is nice but it O(n^2) .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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: google question
@Dave : yeah sorry its O(n) where n is number of nodes.
yeah as i said before its a nice approach...
On Tue, Feb 28, 2012 at 10:15 AM, Dave dave_and_da...@juno.com wrote:
@Atul: I don't have an n in my algorithm, so I'm not sure what your
assessment that my algorithm is O(n^2) means. My algorithm is O(h^2),
where h is the height of the triangle of cups, but the number of cups
is n = h(h+1)/2, which is O(h^2), so my algorithm is O(n), as is
yours.
You'll have to admit that my data structure, an array, is simpler than
your graph.
Dave
On Feb 27, 10:09 pm, atul anand atul.87fri...@gmail.com wrote:
@Dave : my code is not that complicated ...if you ignore the helper
function and check fillCup();
it just similar to preorder travesal and pour half to left and right
child.
here is the explanation :-
node* fillCup(node *root,float pour,float capacity)
{
float temp;
if(root==NULL)
return NULL;
if(root-data+pour = capacity)
{
if(root-data==0) // if cup is empty then fill cup to full and
reduce pour value for the next level
{
root-data=capacity;
pour=pour-capacity;
}
else
{
// if there is alreday some water in the cup , then it will
fill the cup and reduce pour =pour - empty volume in partially filled
cup.
temp=capacity-(root-data);
root-data=capacity;
pour=pour-temp;
if(pour==0)
{
return root;
}
}
}
else
{
// this is for the part where overflow will never happen , even
after adding the poured quantity to the cup.
root-data+=pour;
return root;
}
fillCup(root-left,pour/2,capacity);// pour 1/2 to the left
fillCup(root-right,pour/2,capacity); // pour 1/2 to the right
}
Time complexity = O(n).
your approach is nice but it O(n^2) .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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 algogeeks@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: google question
@Gene , @dave : +1 +1
On Tue, Feb 28, 2012 at 10:49 AM, atul anand atul.87fri...@gmail.comwrote:
@Dave : yeah sorry its O(n) where n is number of nodes.
yeah as i said before its a nice approach...
On Tue, Feb 28, 2012 at 10:15 AM, Dave dave_and_da...@juno.com wrote:
@Atul: I don't have an n in my algorithm, so I'm not sure what your
assessment that my algorithm is O(n^2) means. My algorithm is O(h^2),
where h is the height of the triangle of cups, but the number of cups
is n = h(h+1)/2, which is O(h^2), so my algorithm is O(n), as is
yours.
You'll have to admit that my data structure, an array, is simpler than
your graph.
Dave
On Feb 27, 10:09 pm, atul anand atul.87fri...@gmail.com wrote:
@Dave : my code is not that complicated ...if you ignore the helper
function and check fillCup();
it just similar to preorder travesal and pour half to left and right
child.
here is the explanation :-
node* fillCup(node *root,float pour,float capacity)
{
float temp;
if(root==NULL)
return NULL;
if(root-data+pour = capacity)
{
if(root-data==0) // if cup is empty then fill cup to full and
reduce pour value for the next level
{
root-data=capacity;
pour=pour-capacity;
}
else
{
// if there is alreday some water in the cup , then it will
fill the cup and reduce pour =pour - empty volume in partially filled
cup.
temp=capacity-(root-data);
root-data=capacity;
pour=pour-temp;
if(pour==0)
{
return root;
}
}
}
else
{
// this is for the part where overflow will never happen , even
after adding the poured quantity to the cup.
root-data+=pour;
return root;
}
fillCup(root-left,pour/2,capacity);// pour 1/2 to the left
fillCup(root-right,pour/2,capacity); // pour 1/2 to the right
}
Time complexity = O(n).
your approach is nice but it O(n^2) .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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 algogeeks@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: google question
@all same doubt qstn appears to be of binary tree DS but the diagram given in between qstn is not like Binary tree so sharing is there so how sharing is done plz explain?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: google question
@Ravi: checkout this code...i have created tree where there is sharing of
nodes..
here is my code :-
please let me know is case you find any bug.
#includestdio.h
typedef struct tree{
int idx;
float data;
struct tree *left;
struct tree *right;
}node;
node *createNode(int index)
{
node *temp;
temp=(node *)malloc(sizeof(node));
temp-idx=index;
temp-data=0.0;
temp-left=temp-right=NULL;
return temp;
}
void inorder(node *root)
{
if(root!=NULL)
{
inorder(root-left);
printf(%d ) %f \n,root-idx,root-data);
inorder(root-right);
}
}
node* fillCup(node *root,float pour,float capacity)
{
float temp;
if(root==NULL)
return NULL;
if(root-data+pour = capacity)
{
if(root-data==0)
{
root-data=capacity;
pour=pour-capacity;
}
else
{
temp=capacity-(root-data);
root-data=capacity;
pour=pour-temp;
if(pour==0)
{
return root;
}
}
}
else
{
root-data+=pour;
return root;
}
fillCup(root-left,pour/2,capacity);
fillCup(root-right,pour/2,capacity);
}
int main()
{
node *root;
float pour,capacity;
root=createNode(1);//1
root-left=createNode(2);//2
root-right=createNode(3);//3
root-left-left=createNode(4);//4
root-left-left-left=createNode(7);//7
root-right-right=createNode(6);//6
root-right-right-right=createNode(10);//10
root-left-right=createNode(5);//5
root-right-left=root-left-right;
root-left-left-right=createNode(8); // 8
root-left-right-left=root-left-left-right;
root-left-right-right=createNode(9);//9
root-right-right-left=root-left-right-right;
printf(\nEnter capacity = );
scanf(%f,capacity);
printf(\nEnter quantity poured = );
scanf(%f,pour);
fillCup(root,pour,capacity);
printf(\nPrinting tree\n\n);
inorder(root);
printf(\n\n);
return 1;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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: Google Question--Suggest Algo
@Sourabh - whats the running time?
On Mon, Nov 28, 2011 at 3:28 AM, Ankur Garg ankurga...@gmail.com wrote:
Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
Nice thinking man and thanks :)
On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9])+ F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8])+ F(7, 2) ,
ExpVal (A[12 .. 7])+ F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com
wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com
wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
wrote:
You have an array with *n* elements. The elements are either 0
or 1.
You
want to *split the array into kcontiguous subarrays*. The size
of
each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can
assume that
k n. After you split the array into k subarrays. One element
of
each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly
selected
elements from the k subarrays. Basically means that we will
want to
split
the array in such way such that the sum
Re: [algogeeks] Re: Google Question--Suggest Algo
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
wrote:
You have an array with *n* elements. The elements are either 0 or 1.
You
want to *split the array into kcontiguous subarrays*. The size of
each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can
assume that
k n. After you split the array into k subarrays. One element of
each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly selected
elements from the k subarrays. Basically means that we will want to
split
the array in such way such that the sum of all the expected values
for the
elements selected from each subarray is maximum.
You can assume that n is a power of 2.
Example:
Array: [0,0,1,1,0,0,1,1,0,1,1,0]
n = 12
k = 3
Size of subarrays can be: 2,3,4,5,6
Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
Expected Value of the sum of the elements randomly selected from the
subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.433
Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.8333
Source -
http://stackoverflow.com/questions/8189334/google-combinatorial-optim...
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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: Google Question--Suggest Algo
Cool Solution...I was thinking of DP but wasnt clear on the recurrence...
Nice thinking man and thanks :)
On Mon, Nov 28, 2011 at 2:47 AM, sourabh sourabhd2...@gmail.com wrote:
Consider the example that you have given:
[0,0,1,1,0,0,1,1,0,1,1,0] , here n = 12 and k=3
Now we need to partition the array into 3 contiguous sub arrays such
that :
a) The expected sum value is maximum
b) and the size of each sub array should be between 2 and 6, both
inclusive. In case, this constraint is not satisfied then its not a
valid candidate for the solution even if the partition produces the
max value.
2 = ceil (n / 2k) = ceil (12/6)
6 = floor (3n / 2k) = floor (36/6)
-
As mentioned above the following equation :
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
/**
For understanding how partitioning of the array is represented by the
above equation:
Say there is an array denoted by A[i] and it needs to be divided into
3 contiguous parts, one of the ways to do so would be to take the
following steps :
Let K(partition no.) be initialized to 3.
Let array size N be 12.
a) If N is 0, the goto step 'f'
b) If K == 1 then call it as partition K and goto step 'e'.
c) Lets take X no. of elements from the end of array A of size N and
call it partition K.
d) Decrement K by 1 and N by X { --K; and N-=X;}
d) Goto step 'a'
e) Valid partition and End.
f) Not a valid partition and End.
Now if the above set of steps is run for all values of X such that
2=X=6 , then it will generate all possible candidates (partitions)
as per the given problem statement. And for all the valid
partitions(the ones that will hit step 'e') we need to calculate the
expected sum value.
**/
can be translated into,
// I am using 1-based array indexing for better clarity
// A[x .. y] means all elements from A[y] to A[x]..
F(12, 3) = MAX
{
ExpVal (A[12 .. 11]) + F(10, 2) ,
ExpVal (A[12 .. 10]) + F(9, 2) ,
ExpVal (A[12 .. 9])+ F(8, 2) , //
this will yield the maximum sum..
ExpVal (A[12 .. 8])+ F(7, 2) ,
ExpVal (A[12 .. 7])+ F(6, 2)
}
which is nothing but,
F(12, 3) = MAX
{
1/2 + F(10, 2) ,
2/3 + F(9, 2) ,
2/4 + F(8, 2) , // this will yield the
maximum sum..
3/5 + F(7, 2) ,
4/6 + F(6, 2)
}
Trace the above equation and you should get it..
On Nov 28, 12:57 am, Ankur Garg ankurga...@gmail.com wrote:
Hey Sourabh
Could you please explain the solution in a bit detail perhaps using an
example or so..It wud be really helpful ..Just logic not code
On Mon, Nov 28, 2011 at 1:03 AM, sourabh sourabhd2...@gmail.com wrote:
Looks like a dynamic programming problem
Say F(n,k) denotes the maximum expected sum value for an array of n
elements and partition k , then
F(n,k) = MAX for all r such that ceil(n/2k) = r = floor(3n/2k)
{ (expected value of array elems from A[n] to A[n-r+1]) + F(n-r,
k-1) }
Base condition:
1) F(N, 1) = expected value for array A[n] such that ceil(n/2k) = N
= floor(3n/2k)
2) If any of the sub problems where the array size is not between
ceil(n/2k) and floor(3n/2k) , both inclusive, then its not a valid
candidate for the final solution. This is can be handled by giving
initial value to all such combination a value of -1.
To store that the intermediate computations take an array Max[N][K],
F(N,K) = Max[N][K]
On Nov 28, 12:17 am, sourabh sourabhd2...@gmail.com wrote:
Because in the previous example k = 3.
On Nov 27, 10:46 pm, Piyush Grover piyush4u.iit...@gmail.com
wrote:
Optimal split: [0,0][1,1][0,0][1,1][0,1][1,0]
Expected value of optimal split: 0 + 1 + 0 + 1 + 1/2 + 1/2 = 3
why this is not the optimal split???
On Sun, Nov 27, 2011 at 6:58 PM, Ankur Garg ankurga...@gmail.com
wrote:
You have an array with *n* elements. The elements are either 0
or 1.
You
want to *split the array into kcontiguous subarrays*. The size of
each
subarray can vary between ceil(n/2k) and floor(3n/2k). You can
assume that
k n. After you split the array into k subarrays. One element
of
each
subarray will be randomly selected.
Devise an algorithm for maximizing the sum of the randomly
selected
elements from the k subarrays. Basically means that we will want
to
split
the array in such way such that the sum of all the expected
values
for the
elements selected from each subarray is maximum.
You can assume
Re: [algogeeks] Re: GOOGLE QUESTION
since its a phone number storing problem, you can sort the numbers and store the differences. That way you can generate the required number on the go On Thu, Jun 30, 2011 at 4:39 AM, juver++ avpostni...@gmail.com wrote: @Navneet Please read problem again - it is about memory efficient storing. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/-hsmsOgm2YUJ. To post to this group, send email to algogeeks@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 algogeeks@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: GOOGLE QUESTION
In TRIE , we can store nodes by characters. So it is very easy to search by names and hence their corresponding numbers :) . TRIE saves a lot memory coz it stares a character only once. LIKE :- if i want to save sagar with phone no. 123456789 then we store it in TRIE as : s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | NULL now if we want to add new contact as sagarika,123454321 then it will stored as :- s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | i-NULL | k-NULL | NULL now if we want to store new contact as sag,345678909 s-NULL | a-NULL | g-345678909 | a-NULL | r-123456789 | i-NULL | k-NULL | NULL I hope now you get how it saves a lot memory :) | a- 123454321 On Wed, Jun 29, 2011 at 11:31 PM, ankit sambyal ankitsamb...@gmail.comwrote: @Swathi :We can't use trie data structure to store the phone numbers. The most sound reason is that the users require phone numbers to be sorted by name, but by using the trie data structure we can't get the phone numbers which are sorted by name. Again we can't use trie whose nodes are numbers, because phone numbers are searched by name always. Nobody searches for a name, given a number. And if we use names as the node in the trie, we end up using a lot of space because of pointers. Worst case time complexity of search using trie - O(n) Worst case time complexity of search using fixed array with circular indexing O(log n) because we can use binary search, and search is most frequent query in a list of phone numbers. I hope u got the idea. Another point is that we have very limited memory in a phone, so we have too use fixed array. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: GOOGLE QUESTION
Sorry for the previous post it got a mistake here take a look again :- In TRIE , we can store nodes by characters. So it is very easy to search by names and hence their corresponding numbers :) . TRIE saves a lot memory coz it stares a character only once. LIKE :- if i want to save sagar with phone no. 123456789 then we store it in TRIE as : s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | NULL now if we want to add new contact as sagarika,123454321 then it will stored as :- s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | i-NULL | k-NULL | a-123454321 | NULL now if we want to store new contact as sag,345678909 s-NULL | a-NULL | g-345678909 | a-NULL | r-123456789 | i-NULL | k-NULL | a- 123454321 | NULL I hope now you get how it saves a lot memory :) On Thu, Jun 30, 2011 at 12:21 PM, sagar pareek sagarpar...@gmail.comwrote: In TRIE , we can store nodes by characters. So it is very easy to search by names and hence their corresponding numbers :) . TRIE saves a lot memory coz it stares a character only once. LIKE :- if i want to save sagar with phone no. 123456789 then we store it in TRIE as : s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | NULL now if we want to add new contact as sagarika,123454321 then it will stored as :- s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | i-NULL | k-NULL | NULL now if we want to store new contact as sag,345678909 s-NULL | a-NULL | g-345678909 | a-NULL | r-123456789 | i-NULL | k-NULL | NULL I hope now you get how it saves a lot memory :) | a- 123454321 On Wed, Jun 29, 2011 at 11:31 PM, ankit sambyal ankitsamb...@gmail.comwrote: @Swathi :We can't use trie data structure to store the phone numbers. The most sound reason is that the users require phone numbers to be sorted by name, but by using the trie data structure we can't get the phone numbers which are sorted by name. Again we can't use trie whose nodes are numbers, because phone numbers are searched by name always. Nobody searches for a name, given a number. And if we use names as the node in the trie, we end up using a lot of space because of pointers. Worst case time complexity of search using trie - O(n) Worst case time complexity of search using fixed array with circular indexing O(log n) because we can use binary search, and search is most frequent query in a list of phone numbers. I hope u got the idea. Another point is that we have very limited memory in a phone, so we have too use fixed array. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: GOOGLE QUESTION
I wonder why people have discarded the idea of Hash map here. Searching is obviously the most important task here and if we are to assume that names can be uniformly hashed over a table of 1000 rows with each row containing 1000 names each. Further optimization can be achieved by having names stored in binary search tree for each row. (So it will take max 10 comparisons to search a name) (Need to Keep it a balanced tree) So in all, a total of max 11 operations - 1 Hash + 10 comparisons will be used to search for any phone number. In the above, hashing is to be done on names obviously. On Thu, Jun 30, 2011 at 12:24 PM, sagar pareek sagarpar...@gmail.com wrote: Sorry for the previous post it got a mistake here take a look again :- In TRIE , we can store nodes by characters. So it is very easy to search by names and hence their corresponding numbers :) . TRIE saves a lot memory coz it stares a character only once. LIKE :- if i want to save sagar with phone no. 123456789 then we store it in TRIE as : s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | NULL now if we want to add new contact as sagarika,123454321 then it will stored as :- s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | i-NULL | k-NULL | a-123454321 | NULL now if we want to store new contact as sag,345678909 s-NULL | a-NULL | g-345678909 | a-NULL | r-123456789 | i-NULL | k-NULL | a- 123454321 | NULL I hope now you get how it saves a lot memory :) On Thu, Jun 30, 2011 at 12:21 PM, sagar pareek sagarpar...@gmail.com wrote: In TRIE , we can store nodes by characters. So it is very easy to search by names and hence their corresponding numbers :) . TRIE saves a lot memory coz it stares a character only once. LIKE :- if i want to save sagar with phone no. 123456789 then we store it in TRIE as : s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | NULL now if we want to add new contact as sagarika,123454321 then it will stored as :- s-NULL | a-NULL | g-NULL | a-NULL | r-123456789 | i-NULL | k-NULL | NULL now if we want to store new contact as sag,345678909 s-NULL | a-NULL | g-345678909 | a-NULL | r-123456789 | i-NULL | k-NULL | NULL I hope now you get how it saves a lot memory :) | a- 123454321 On Wed, Jun 29, 2011 at 11:31 PM, ankit sambyal ankitsamb...@gmail.com wrote: @Swathi :We can't use trie data structure to store the phone numbers. The most sound reason is that the users require phone numbers to be sorted by name, but by using the trie data structure we can't get the phone numbers which are sorted by name. Again we can't use trie whose nodes are numbers, because phone numbers are searched by name always. Nobody searches for a name, given a number. And if we use names as the node in the trie, we end up using a lot of space because of pointers. Worst case time complexity of search using trie - O(n) Worst case time complexity of search using fixed array with circular indexing O(log n) because we can use binary search, and search is most frequent query in a list of phone numbers. I hope u got the idea. Another point is that we have very limited memory in a phone, so we have too use fixed array. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- --Navneet -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: GOOGLE QUESTION
@samby You are wrong anyway. Main problem is to reduce memory while storing phone numbers. We have 1 million of phones, they have many common prefixes which can be addressed by trie. For storing names, you may use any data structure which is best for the particular problem. Key is name, and value is a leaf node in trie which represents desired phone number. If one want improve memory usage, they can build ternary trie based on already sorted phones, so it makes it balanced. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/r3vvzArkr1kJ. To post to this group, send email to algogeeks@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: GOOGLE QUESTION
@Navneet Please read problem again - it is about memory efficient storing. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/-hsmsOgm2YUJ. To post to this group, send email to algogeeks@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: GOOGLE QUESTION
Please explain why you think TRIE use more space? To my knowledge TRIE says lot of memory as the common numbers are saved only once.. If you have any good reason then please explain and don't make any single line statements. On Wed, Jun 29, 2011 at 9:21 PM, MONSIEUR monsieur@gmail.com wrote: trie uses more space On Jun 29, 5:52 pm, sudheer kumar chigullapallysudh...@gmail.com wrote: USE TRIE On Wed, Jun 29, 2011 at 6:10 PM, shady sinv...@gmail.com wrote: go through the archives you will definitely find the answer :) On Wed, Jun 29, 2011 at 6:05 PM, MONSIEUR monsieur@gmail.com wrote: What is the most efficient way, memory-wise, to store 1 million phone numbers? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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. -- Thanks and Regards chigullapallysudh...@gmail.com Sudheer -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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: GOOGLE QUESTION
@Swathi :We can't use trie data structure to store the phone numbers. The most sound reason is that the users require phone numbers to be sorted by name, but by using the trie data structure we can't get the phone numbers which are sorted by name. Again we can't use trie whose nodes are numbers, because phone numbers are searched by name always. Nobody searches for a name, given a number. And if we use names as the node in the trie, we end up using a lot of space because of pointers. Worst case time complexity of search using trie - O(n) Worst case time complexity of search using fixed array with circular indexing O(log n) because we can use binary search, and search is most frequent query in a list of phone numbers. I hope u got the idea. Another point is that we have very limited memory in a phone, so we have too use fixed array. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: Google Question
http://anandtechblog.blogspot.com/2011/06/bitonic-merge.html On Fri, Jun 24, 2011 at 2:17 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: 1,2,43,41,5 , 6 Start at a[3] and a[5] Swap them up . Reversing it , we get 1,2,43,5,6,41 This does not work . On Jun 23, 9:05 pm, Swathi chukka.swa...@gmail.com wrote: We just need to find the start and end of the decreasing sequence then we have to reverse the elements in that decreasing sequence by swapping the elements at both the edges... On Thu, Jun 23, 2011 at 2:13 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: @piyush Sinha How can you do it in O(1) space and O(n) time dude .The inplace merging of d sorted arrays take space O(log d) space at least i think .Plus even at every step , we have to do O(log n) comparisions to find the next larger or smaller element .How can this be O(n) ??? WAiting eagerly for a reply On Jun 22, 3:24 pm, Dumanshu duman...@gmail.com wrote: @Piyush: could u plz post the link to the same? On Jun 22, 2:15 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: This question has been discussed over here once...It was concluded that this can be solved in O(n) if we know there is a fixed range up to which the elements keep on increasing and decreasing..for example in an array of 12 elements, we know 3 elements keep on increasing monotonically, then 3 elements keep on decreasing monotonically and so on On 6/22/11, chirag ahuja sparkle.chi...@gmail.com wrote: Given an array of size n wherein elements keep on increasing monotonically upto a certain location after which they keep on decreasing monotonically, then again keep on increasing, then decreasing again and so on. Sort the array in O(n) and O(1). I didn't understand the question, any array of n elements will be like this except when first there is a decrese from index 0 to a higher index. Any ideas about how to solve it in given constraints?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926*-Hidequoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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: Google Question
@Anand : Plz explain ur algo ??? On Fri, Jun 24, 2011 at 10:55 AM, Anand anandut2...@gmail.com wrote: http://anandtechblog.blogspot.com/2011/06/bitonic-merge.html On Fri, Jun 24, 2011 at 2:17 AM, sankalp srivastava richi.sankalp1...@gmail.com wrote: 1,2,43,41,5 , 6 Start at a[3] and a[5] Swap them up . Reversing it , we get 1,2,43,5,6,41 This does not work . On Jun 23, 9:05 pm, Swathi chukka.swa...@gmail.com wrote: We just need to find the start and end of the decreasing sequence then we have to reverse the elements in that decreasing sequence by swapping the elements at both the edges... On Thu, Jun 23, 2011 at 2:13 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: @piyush Sinha How can you do it in O(1) space and O(n) time dude .The inplace merging of d sorted arrays take space O(log d) space at least i think .Plus even at every step , we have to do O(log n) comparisions to find the next larger or smaller element .How can this be O(n) ??? WAiting eagerly for a reply On Jun 22, 3:24 pm, Dumanshu duman...@gmail.com wrote: @Piyush: could u plz post the link to the same? On Jun 22, 2:15 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: This question has been discussed over here once...It was concluded that this can be solved in O(n) if we know there is a fixed range up to which the elements keep on increasing and decreasing..for example in an array of 12 elements, we know 3 elements keep on increasing monotonically, then 3 elements keep on decreasing monotonically and so on On 6/22/11, chirag ahuja sparkle.chi...@gmail.com wrote: Given an array of size n wherein elements keep on increasing monotonically upto a certain location after which they keep on decreasing monotonically, then again keep on increasing, then decreasing again and so on. Sort the array in O(n) and O(1). I didn't understand the question, any array of n elements will be like this except when first there is a decrese from index 0 to a higher index. Any ideas about how to solve it in given constraints?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926*-Hidequoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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 algogeeks@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: Google Question
We just need to find the start and end of the decreasing sequence then we have to reverse the elements in that decreasing sequence by swapping the elements at both the edges... On Thu, Jun 23, 2011 at 2:13 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: @piyush Sinha How can you do it in O(1) space and O(n) time dude .The inplace merging of d sorted arrays take space O(log d) space at least i think .Plus even at every step , we have to do O(log n) comparisions to find the next larger or smaller element .How can this be O(n) ??? WAiting eagerly for a reply On Jun 22, 3:24 pm, Dumanshu duman...@gmail.com wrote: @Piyush: could u plz post the link to the same? On Jun 22, 2:15 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: This question has been discussed over here once...It was concluded that this can be solved in O(n) if we know there is a fixed range up to which the elements keep on increasing and decreasing..for example in an array of 12 elements, we know 3 elements keep on increasing monotonically, then 3 elements keep on decreasing monotonically and so on On 6/22/11, chirag ahuja sparkle.chi...@gmail.com wrote: Given an array of size n wherein elements keep on increasing monotonically upto a certain location after which they keep on decreasing monotonically, then again keep on increasing, then decreasing again and so on. Sort the array in O(n) and O(1). I didn't understand the question, any array of n elements will be like this except when first there is a decrese from index 0 to a higher index. Any ideas about how to solve it in given constraints?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926*-Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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: Google Question
I heard somewhere in some online video lecture that sites like tinyurl
change the address using more than base three {base 6 } and then apply
hash
On 6/4/11, bittu shashank7andr...@gmail.com wrote:
well i can speak much on these question.as these algorithms are part
of web crawler ..but do u mean we have to detect the duplicate files,
by file having same size are duplicates..??
also same question raised by me few days back Detecting Duplicate
Documents but no one seems to interested u can search previous
threads..
Thanks
Shashank
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
Rahul
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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: Google Question
Nishant's soln is incorrect because he assumes, ctrlA and ctrlC are pressed
each time ctrlV is pressed.
As saikat has pointed out, this is incorrect.
According to me:
*buff = 0; //keeps track of last ctrlC*
*for each i*
*{*
* dp(i)=max(dp(i-1)+1, 2*dp(i-3), dp(i-1) + buff)*
* if(dp(i)==2*dp(i-3)) { buff = dp(i-3);}*
*}*
@saikat: for n=10, this gives dp(10) = 20 :D
An O(n) soln.
Cheers
Nikhil Jindal
Delhi College of Engineering (DCE),
Delhi.
On Wed, Jan 19, 2011 at 10:05 PM, nishaanth nishaant...@gmail.com wrote:
How about the following dynamic programming solution.
Let dp[i] be the max no of As with i keystrokes.
dp[i]=max(dp[i-1]+1,2*dp[i-3])
dp[N] is the required solution.
Correct me if i am wrong.
On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote:
http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html
On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote:
Given
1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V
If you can only press the keyboard for N times (with the above four
keys), please write a program to produce maximum numbers of A. If
possible, please also print out the sequence of keys.
So the input parameter is N (No. of keys that you can press), the
output is M (No. of As that you can produce).
Thanks Regards
Shashank Mani
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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: Google Question
@ Nikhil sir : I have coded the same solution, but was waiting for its
correctness to be proved... thanx.. :)
On Fri, Jan 28, 2011 at 1:01 PM, Nikhil Jindal fundoon...@yahoo.co.inwrote:
Nishant's soln is incorrect because he assumes, ctrlA and ctrlC are pressed
each time ctrlV is pressed.
As saikat has pointed out, this is incorrect.
According to me:
*buff = 0; //keeps track of last ctrlC*
*for each i*
*{*
* dp(i)=max(dp(i-1)+1, 2*dp(i-3), dp(i-1) + buff)*
* if(dp(i)==2*dp(i-3)) { buff = dp(i-3);}*
*}*
@saikat: for n=10, this gives dp(10) = 20 :D
An O(n) soln.
Cheers
Nikhil Jindal
Delhi College of Engineering (DCE),
Delhi.
On Wed, Jan 19, 2011 at 10:05 PM, nishaanth nishaant...@gmail.com wrote:
How about the following dynamic programming solution.
Let dp[i] be the max no of As with i keystrokes.
dp[i]=max(dp[i-1]+1,2*dp[i-3])
dp[N] is the required solution.
Correct me if i am wrong.
On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote:
http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html
On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote:
Given
1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V
If you can only press the keyboard for N times (with the above four
keys), please write a program to produce maximum numbers of A. If
possible, please also print out the sequence of keys.
So the input parameter is N (No. of keys that you can press), the
output is M (No. of As that you can produce).
Thanks Regards
Shashank Mani
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
Please access the attached hyperlink for an important electronic
communications disclaimer:
http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Saikat Kumar Debnath
IIIrd year, Computer Science Deptt.,
Delhi Technological University,
(formerly Delhi College of Engineering)
Delhi
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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: Google Question
hope this works :
#includestdio.h
#define MAX(A,B) AB?A:B
#defineMIN(A,B) AB?A:B
int FindMaxA(int n)
{
int i,k,factor,max = 0,cur,prev;
int* arr = new int[n+1];
int p = MIN(n,4);
for( int j = 1;j = p;j++)
arr[j] = j;
for(i=5;i=n;i++)
{
k = i-4;
factor = 2;
prev = 0;
while(k=1)
{
cur = arr[k]*factor;
if( cur max ) //find max among multiples of Arr[k] for k i
max = cur;
if( cur prev )
break; // once the decreasing pattern starts its safe to
break out of loop.
k--;
factor++;
prev = cur;
}
arr[i] = MAX(i,max);
}
int result = arr[n];
delete[] arr;
return result;
}
int main()
{
int n;
scanf(%d,n);
printf(%d\n,FindMaxA(n));
return 0;
}
--
On Fri, Jan 21, 2011 at 11:28 AM, Preetam Purbia
preetam.pur...@gmail.comwrote:
Hi,
I think this method will work
Possible Number of A's = N/2(1+R)
where R=N-(N/2+3)
assuming 11/2 = 5
Thanks
Preetam
On Fri, Jan 21, 2011 at 2:29 AM, Anand anandut2...@gmail.com wrote:
but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C
resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20.
Try this on a notepad. you will only 15A's
On Thu, Jan 20, 2011 at 12:46 PM, Saikat Debnath saikat@gmail.comwrote:
According to me Nishaanth's solution is incorrect, as let for n =10, your
output : m=16
but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C
resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20.
On Thu, Jan 20, 2011 at 9:24 PM, abhijith reddy d
abhijith200...@gmail.com wrote:
I think its correct.
On Jan 19, 9:35 pm, nishaanth nishaant...@gmail.com wrote:
How about the following dynamic programming solution.
Let dp[i] be the max no of As with i keystrokes.
dp[i]=max(dp[i-1]+1,2*dp[i-3])
dp[N] is the required solution.
Correct me if i am wrong.
On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com
wrote:
http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html
On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote:
Given
1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V
If you can only press the keyboard for N times (with the above
four
keys), please write a program to produce maximum numbers of A. If
possible, please also print out the sequence of keys.
So the input parameter is N (No. of keys that you can press), the
output is M (No. of As that you can produce).
Thanks Regards
Shashank Mani
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@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.
--
Regards
Saikat Kumar Debnath
IIIrd year, Computer Science Deptt.,
Delhi Technological University,
(formerly Delhi College of Engineering)
Delhi
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@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 algogeeks@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.
--
Preetam Purbia
http://twitter.com/preetam_purbia
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
Re: [algogeeks] Re: Google Question
According to me Nishaanth's solution is incorrect, as let for n =10, your output : m=16 but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20. On Thu, Jan 20, 2011 at 9:24 PM, abhijith reddy d abhijith200...@gmail.comwrote: I think its correct. On Jan 19, 9:35 pm, nishaanth nishaant...@gmail.com wrote: How about the following dynamic programming solution. Let dp[i] be the max no of As with i keystrokes. dp[i]=max(dp[i-1]+1,2*dp[i-3]) dp[N] is the required solution. Correct me if i am wrong. On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote: http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote: Given 1. A 2. Ctrl+A 3. Ctrl+C 4. Ctrl+V If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys. So the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce). Thanks Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Regards Saikat Kumar Debnath IIIrd year, Computer Science Deptt., Delhi Technological University, (formerly Delhi College of Engineering) Delhi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: Google Question
but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20. Try this on a notepad. you will only 15A's On Thu, Jan 20, 2011 at 12:46 PM, Saikat Debnath saikat@gmail.comwrote: According to me Nishaanth's solution is incorrect, as let for n =10, your output : m=16 but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20. On Thu, Jan 20, 2011 at 9:24 PM, abhijith reddy d abhijith200...@gmail.com wrote: I think its correct. On Jan 19, 9:35 pm, nishaanth nishaant...@gmail.com wrote: How about the following dynamic programming solution. Let dp[i] be the max no of As with i keystrokes. dp[i]=max(dp[i-1]+1,2*dp[i-3]) dp[N] is the required solution. Correct me if i am wrong. On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote: http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote: Given 1. A 2. Ctrl+A 3. Ctrl+C 4. Ctrl+V If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys. So the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce). Thanks Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Regards Saikat Kumar Debnath IIIrd year, Computer Science Deptt., Delhi Technological University, (formerly Delhi College of Engineering) Delhi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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: Google Question
Hi, I think this method will work: Possible Number of A's = N/2(1+R) where R=N-(N/2+3) assuming 11/2 = 5 Thanks Preetam On Fri, Jan 21, 2011 at 2:29 AM, Anand anandut2...@gmail.com wrote: but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20. Try this on a notepad. you will only 15A's On Thu, Jan 20, 2011 at 12:46 PM, Saikat Debnath saikat@gmail.comwrote: According to me Nishaanth's solution is incorrect, as let for n =10, your output : m=16 but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20. On Thu, Jan 20, 2011 at 9:24 PM, abhijith reddy d abhijith200...@gmail.com wrote: I think its correct. On Jan 19, 9:35 pm, nishaanth nishaant...@gmail.com wrote: How about the following dynamic programming solution. Let dp[i] be the max no of As with i keystrokes. dp[i]=max(dp[i-1]+1,2*dp[i-3]) dp[N] is the required solution. Correct me if i am wrong. On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote: http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote: Given 1. A 2. Ctrl+A 3. Ctrl+C 4. Ctrl+V If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys. So the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce). Thanks Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- Regards Saikat Kumar Debnath IIIrd year, Computer Science Deptt., Delhi Technological University, (formerly Delhi College of Engineering) Delhi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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 algogeeks@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. -- Preetam Purbia http://twitter.com/preetam_purbia -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: Google Question
How about the following dynamic programming solution. Let dp[i] be the max no of As with i keystrokes. dp[i]=max(dp[i-1]+1,2*dp[i-3]) dp[N] is the required solution. Correct me if i am wrong. On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com wrote: http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote: Given 1. A 2. Ctrl+A 3. Ctrl+C 4. Ctrl+V If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys. So the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce). Thanks Regards Shashank Mani -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@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: Google Question: Find kth largest of sum of elements in 2 array
this will not work out
a[0]b[0] doesn't mean that a[0]+b[i] is ith largest sum
try
int a[]={10,8,6,4,1};
int b[]={9,6,3,2,1};
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Oct 6, 2010 at 11:36 PM, ligerdave david.c...@gmail.com wrote:
use pointers and lengths of two arrays. depends on what K is, if K
m*n/2, you reverse the pointers. therefore, the worst case is either
O(m) when length of m is shorter or O(n) when length of n is
shorter,
make the pointers pointing to the first elements in both arrays.
A)
4,3,2,2,1
^
B)
5,3,2,1
^
compare them to find out which one is larger, here 5 is larger than 4.
by definition, you know 5 would be bigger than any elements in array
A, and sum of 5 with kth element of array A (here, kth = A.length)
will be the one(kth largest sum(a+b) overall) you are looking for.
if kA.length, shift the pointer of B one number to the right and
repeat the same process.
like i said, if the k m*n/2, start from small
On Oct 6, 6:34 am, sourav souravs...@gmail.com wrote:
you are given 2 arrays sorted in decreasing order of size m and n
respectively.
Input: a number k = m*n and = 1
Output: the kth largest sum(a+b) possible. where
a (any element from array 1)
b (any element from array 2)
The Brute force approach will take O(n*n). can anyone find a better
logic. thnkx in advance.
--
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] a google question
How are we making sure that top n-elements would lie in this 'L' shaped array? Also, why don't we take an extreme case, such that the origin is bottom-left element of the grid, then we have only 2n-1 elements to chose n biggest elements from. So, can we prove that taking Ist quardrant as (n-2)x(n-3) would leave n-biggest out? What is the criterion to chose the Ist quardrant? manish... From: topojoy biswas topojoy.bis...@gmail.com To: algogeeks@googlegroups.com Sent: Thu, 22 July, 2010 10:10:58 AM Subject: Re: [algogeeks] a google question im sry the L should look like this: 109 8 5 321 7 17 16 8 18 17 9 19 18 10 20 19 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 I missed a row in the last mail. On Thu, Jul 22, 2010 at 10:03 AM, topojoy biswas topojoy.bis...@gmail.com wrote: consider these arrays: 10 9 8 5 3 2 1 and 13 12 11 10 9 8 7 form a grid like this: 109 8 5 321 7 17 1615 1210 98 8 18 1716 1311 10 9 9 19 1817 1412 12 10 10 20 1918 1513 12 11 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 basically have an array descending and have one array ascending. If you add them in a grid, check that for any sum, all sums to its right are less than it( in the same row), al sums above it( in the same column) are less than it, all sums below it( in the same row) are greater than it. 109 8 5 321 7 17 1615 1210 98 8 18 1716 1311 10 9 9 19 1817 1412 12 10 10 20 1918 1513 12 11 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 So all sums which form the first quadrant origining at 19 are less than 19. And the 3rd quadrant formed by origining 19 including 19 are strickedly grater than or equal to 19. This means in the added array will look like this: __ ||___|__| ---xmy- x = no of elements in the underlined first quadrant y= no of elements in the 3rd quadrant excluding 19. m= the number of elements in the 2nd and the 4th quadrant including 19. So 19 would lie some whr in the 2n slot of this divided aray picture. So if we make x big enough so that m+y is small enough=O(n), we will reduce our load. so choose x=(n-2)(n-3) which means something like this: --(n-2)--- 109 8 5 321 7 17 1615 1210 98 --- 8 18 1716 1311 10 9 9 19 1817 1412 12 10 (n-3) 10 20 1918 1513 12 11 - 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 Then we will be left with an array of size m+y=5n-6 which is n for all n 2 like this: 109 8 5 321 7 17 16 8 18 17 9 19 18 10 20 19 11 21 20 12 22 2120 1715 14 13 13 23 2221 1816 15 14 Till this point it takes constant time. Now the first column of the L formed is sorted. So is the 2nd column. So is the horizonal part of L which is comprized of two sorted arays (20-13) and (21-14). All of the elements add to 5n-6. We can merge sort them in O(n) time. Take the biggest n elements. On Mon, Jul 19, 2010 at 12:18 PM, ankur aggarwal ankur.mast@gmail.com wrote: this ques was asked by google.. i* could find any gud soln than order n*n -- 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. -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- 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: [algogeeks] a google question
any element to the right of X in the same array is less than X. Any element to the top of X in the same column is less than X. so any element to the nrth east of X is less than X. All the elements to the south west, (including X) are not less than X. To the north west is a mix and to the south east there is a mix. So if we take a big north east, which leaves out only 2n-1 elements in the L they ought to be the largest. this is the same argument when u analyze the order statistics worst case O(n) bound. And this is the same argument u give when given 2 arrays of size N ( not sorted) u want to find whether there could be a sum =some constant C in O(NlogN) time becuas esorting takes NLogN. arrange one array as ascending(Y axis) and one descending(X axis). and form the grid. Property being any element X has its north east contaisn all the elements which are strickely less. and its south west, including it contaisn all elements which are greater than or equal to X. So we start from the top left hand corner and making our entire search start such that the N^2 sums form the south east ( where there is a mix) an then we go downwards if we need a bigger sum, and rightwards if we need a smaller sum. Since the north east and south west is clearly partitioned across any sum u r pointing to right now, and u have already ensured through ur operations that ur north west doesnt contain the sum of ur interest, u proceed south east and never travel back, making a total of 2N moves in the worst case. Its a similar argument. On Mon, Jul 26, 2010 at 2:25 PM, manish bhatia mb_mani...@yahoo.com wrote: How are we making sure that top n-elements would lie in this 'L' shaped array? Also, why don't we take an extreme case, such that the origin is bottom-left element of the grid, then we have only 2n-1 elements to chose n biggest elements from. So, can we prove that taking Ist quardrant as (n-2)x(n-3) would leave n-biggest out? What is the criterion to chose the Ist quardrant? manish... -- *From:* topojoy biswas topojoy.bis...@gmail.com *To:* algogeeks@googlegroups.com *Sent:* Thu, 22 July, 2010 10:10:58 AM *Subject:* Re: [algogeeks] a google question im sry the L should look like this: 109 8 5 321 7 17 16 8 18 17 9 19 18 10 20 19 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 I missed a row in the last mail. On Thu, Jul 22, 2010 at 10:03 AM, topojoy biswas topojoy.bis...@gmail.com wrote: consider these arrays: 10 9 8 5 3 2 1 and 13 12 11 10 9 8 7 form a grid like this: 109 8 5 321 7 17 1615 1210 98 8 18 1716 1311 10 9 9 19 1817 1412 12 10 10 20 1918 1513 12 11 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 basically have an array descending and have one array ascending. If you add them in a grid, check that for any sum, all sums to its right are less than it( in the same row), al sums above it( in the same column) are less than it, all sums below it( in the same row) are greater than it. 109 8 5 321 7 17 1615 *1210 98* 8 18 1716 *1311 10 9* 9 19 1817 *1412 12 10* 10 20 1918 *1513 12 11* 11 *21 2019* 1614 13 12 12 *22 2120* 1715 14 13 13 *23 2221* 1816 15 14 So all sums which form the first quadrant origining at 19 are less than 19. And the 3rd quadrant formed by origining 19 including 19 are strickedly grater than or equal to 19. This means in the added array will look like this: __ ||___|__| ---xmy- x = no of elements in the underlined first quadrant y= no of elements in the 3rd quadrant excluding 19. m= the number of elements in the 2nd and the 4th quadrant including 19. So 19 would lie some whr in the 2n slot of this divided aray picture. So if we make x big enough so that m+y is small enough=O(n), we will reduce our load. so choose x=(n-2)(n-3) which means something like this: --(n-2)--- 109 8 5 321 7 17 1615 1210 98 --- 8 18 1716 1311 10 9 9 19 1817 1412 12 10 (n-3) 10 20 1918 1513 12 11 - 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 Then we will be left with an array of size m+y=5n-6 which is n for all n 2 like this: 109 8 5
Re: [algogeeks] a google question
consider these arrays: 10 9 8 5 3 2 1 and 13 12 11 10 9 8 7 form a grid like this: 109 8 5 321 7 17 1615 1210 98 8 18 1716 1311 10 9 9 19 1817 1412 12 10 10 20 1918 1513 12 11 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 basically have an array descending and have one array ascending. If you add them in a grid, check that for any sum, all sums to its right are less than it( in the same row), al sums above it( in the same column) are less than it, all sums below it( in the same row) are greater than it. 109 8 5 321 7 17 1615 *1210 98* 8 18 1716 *1311 10 9* 9 19 1817 *1412 12 10* 10 20 1918 *1513 12 11* 11 *21 2019* 1614 13 12 12 *22 2120* 1715 14 13 13 *23 2221* 1816 15 14 So all sums which form the first quadrant origining at 19 are less than 19. And the 3rd quadrant formed by origining 19 including 19 are strickedly grater than or equal to 19. This means in the added array will look like this: __ ||___|__| ---xmy- x = no of elements in the underlined first quadrant y= no of elements in the 3rd quadrant excluding 19. m= the number of elements in the 2nd and the 4th quadrant including 19. So 19 would lie some whr in the 2n slot of this divided aray picture. So if we make x big enough so that m+y is small enough=O(n), we will reduce our load. so choose x=(n-2)(n-3) which means something like this: --(n-2)--- 109 8 5 321 7 17 1615 1210 98 --- 8 18 1716 1311 10 9 9 19 1817 1412 12 10 (n-3) 10 20 1918 1513 12 11 - 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 Then we will be left with an array of size m+y=5n-6 which is n for all n 2 like this: 109 8 5 321 7 17 16 8 18 17 9 19 18 10 20 19 11 21 20 12 22 2120 1715 14 13 13 23 2221 1816 15 14 Till this point it takes constant time. Now the first column of the L formed is sorted. So is the 2nd column. So is the horizonal part of L which is comprized of two sorted arays (20-13) and (21-14). All of the elements add to 5n-6. We can merge sort them in O(n) time. Take the biggest n elements. On Mon, Jul 19, 2010 at 12:18 PM, ankur aggarwal ankur.mast@gmail.comwrote: this ques was asked by google.. i* could find any gud soln than order n*n -- 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. -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- 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] a google question
im sry the L should look like this: 109 8 5 321 7 17 16 8 18 17 9 19 18 10 20 19 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 I missed a row in the last mail. On Thu, Jul 22, 2010 at 10:03 AM, topojoy biswas topojoy.bis...@gmail.comwrote: consider these arrays: 10 9 8 5 3 2 1 and 13 12 11 10 9 8 7 form a grid like this: 109 8 5 321 7 17 1615 1210 98 8 18 1716 1311 10 9 9 19 1817 1412 12 10 10 20 1918 1513 12 11 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 basically have an array descending and have one array ascending. If you add them in a grid, check that for any sum, all sums to its right are less than it( in the same row), al sums above it( in the same column) are less than it, all sums below it( in the same row) are greater than it. 109 8 5 321 7 17 1615 *1210 98* 8 18 1716 *1311 10 9* 9 19 1817 *1412 12 10* 10 20 1918 *1513 12 11* 11 *21 2019* 1614 13 12 12 *22 2120* 1715 14 13 13 *23 2221* 1816 15 14 So all sums which form the first quadrant origining at 19 are less than 19. And the 3rd quadrant formed by origining 19 including 19 are strickedly grater than or equal to 19. This means in the added array will look like this: __ ||___|__| ---xmy- x = no of elements in the underlined first quadrant y= no of elements in the 3rd quadrant excluding 19. m= the number of elements in the 2nd and the 4th quadrant including 19. So 19 would lie some whr in the 2n slot of this divided aray picture. So if we make x big enough so that m+y is small enough=O(n), we will reduce our load. so choose x=(n-2)(n-3) which means something like this: --(n-2)--- 109 8 5 321 7 17 1615 1210 98 --- 8 18 1716 1311 10 9 9 19 1817 1412 12 10 (n-3) 10 20 1918 1513 12 11 - 11 21 2019 1614 13 12 12 22 2120 1715 14 13 13 23 2221 1816 15 14 Then we will be left with an array of size m+y=5n-6 which is n for all n 2 like this: 109 8 5 321 7 17 16 8 18 17 9 19 18 10 20 19 11 21 20 12 22 2120 1715 14 13 13 23 2221 1816 15 14 Till this point it takes constant time. Now the first column of the L formed is sorted. So is the 2nd column. So is the horizonal part of L which is comprized of two sorted arays (20-13) and (21-14). All of the elements add to 5n-6. We can merge sort them in O(n) time. Take the biggest n elements. On Mon, Jul 19, 2010 at 12:18 PM, ankur aggarwal ankur.mast@gmail.com wrote: this ques was asked by google.. i* could find any gud soln than order n*n -- 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. -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- Topo. There are days when solitude is a heady wine that intoxicates you with freedom, others when it is a bitter tonic, and still others when it is a poison that makes you beat your head against the wall. ~Colette -- 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] a google question
this ques was asked by google.. it could find any gud soln than order n*n
On Mon, Jul 19, 2010 at 10:55 AM, 王奇凡 wqfhena...@gmail.com wrote:
@Kushwaha
Your programe is wrong.
Try this input:
a[ ] = {30,25,19,16,14};
b[ ] = {20,18,12,10,8};
the right answer should be 50 48 45 43 42
but the program output is 50 48 45 43 37。
2010/5/2 Jitendra Kushwaha jitendra.th...@gmail.com
Here is a solution of O(n) , taking 4 pointers 2 for each array
#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;
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;
else if(b = c b = d )ans = b , p22++ ;
else if(c = b c = d )ans = c , p12++ ;
elseans = d , p11++ , p21++ ,printf(4 );
printf(%d\n,ans);
}
}
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.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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards
Ankur Aggarwal
--
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] a google question
this ques was asked by google.. i* could find any gud soln than order n*n -- 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] a google question
i think ,you can use the idea of merg (merg sort)
--- On Mon, 7/19/10, manish bhatia mb_mani...@yahoo.com wrote:
From: manish bhatia mb_mani...@yahoo.com
Subject: Re: [algogeeks] a google question
To: algogeeks@googlegroups.com
Date: Monday, July 19, 2010, 5:03 PM
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. manish...
From: Ashish Goel ashg...@gmail.com
To: algogeeks@googlegroups.com
Sent: Sun, 18 July, 2010 6:31:08 PM
Subject: Re: [algogeeks] a google question
question please...
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Fri, Jul 16, 2010 at 4:43 PM, manish bhatia mb_mani...@yahoo.com wrote:
It doesn't work
A =
92 87 81 72 70 61 53 22 18 17
B =
79 78 74 68 64 62 57 34 29 24
C (GOLD) =
171 170 166 166 165 161 160 160 159 156
D (TEST) =
171 170 166 166 165 159 155 155 146 145
Result: FAILED!
manish...
From: Jitendra Kushwaha jitendra.th...@gmail.com
To: algogeeks@googlegroups.com
Sent: Sun, 2 May, 2010 9:13:14 PM
Subject: Re: [algogeeks] a google question
Here is a solution of O(n) , taking 4 pointers 2 for each array
#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;
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;
else if(b = c b = d ) ans = b , p22++ ;
else if(c = b c = d ) ans = c , p12++ ;
else ans = d , p11++ , p21++ ,printf(4 );
printf(%d\n,ans);
}
}
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.
--
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.
Re: [algogeeks] a google question
question please...
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Fri, Jul 16, 2010 at 4:43 PM, manish bhatia mb_mani...@yahoo.com wrote:
It doesn't work
A =
92 87 81 72 70 61 53 22 18 17
B =
79 78 74 68 64 62 57 34 29 24
C (GOLD) =
171 170 166 166 165 161 160 160 159 156
D (TEST) =
171 170 166 166 165 159 155 155 146 145
Result: FAILED!
manish...
--
*From:* Jitendra Kushwaha jitendra.th...@gmail.com
*To:* algogeeks@googlegroups.com
*Sent:* Sun, 2 May, 2010 9:13:14 PM
*Subject:* Re: [algogeeks] a google question
Here is a solution of O(n) , taking 4 pointers 2 for each array
#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;
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;
else if(b = c b = d )ans = b , p22++ ;
else if(c = b c = d )ans = c , p12++ ;
elseans = d , p11++ , p21++ ,printf(4 );
printf(%d\n,ans);
}
}
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.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.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] a google question
@Kushwaha
Your programe is wrong.
Try this input:
a[ ] = {30,25,19,16,14};
b[ ] = {20,18,12,10,8};
the right answer should be 50 48 45 43 42
but the program output is 50 48 45 43 37。
2010/5/2 Jitendra Kushwaha jitendra.th...@gmail.com
Here is a solution of O(n) , taking 4 pointers 2 for each array
#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;
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;
else if(b = c b = d )ans = b , p22++ ;
else if(c = b c = d )ans = c , p12++ ;
elseans = d , p11++ , p21++ ,printf(4 );
printf(%d\n,ans);
}
}
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.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] a google question
It doesn't work
A =
92 87 81 72 70 61 53 22 18 17
B =
79 78 74 68 64 62 57 34 29 24
C (GOLD) =
171 170 166 166 165 161 160 160 159 156
D (TEST) =
171 170 166 166 165 159 155 155 146 145
Result: FAILED!
manish...
From: Jitendra Kushwaha jitendra.th...@gmail.com
To: algogeeks@googlegroups.com
Sent: Sun, 2 May, 2010 9:13:14 PM
Subject: Re: [algogeeks] a google question
Here is a solution of O(n) , taking 4 pointers 2 for each array
#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;
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;
else if(b = c b = d )ans = b , p22++ ;
else if(c = b c = d )ans = c , p12++ ;
elseans = d , p11++ , p21++ ,printf(4 );
printf(%d\n,ans);
}
}
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.
Re: [algogeeks] a google question
The nature of the problem involves inserting some elements in heap and
retriving back ..It could be solved in worst case O(n * lg(n)).
Average case O(n) solution is not there I believe.
-Arun prasath N
On Fri, Apr 30, 2010 at 5:35 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.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] a google question
@Algoose Chase
point taken
Thanks
Mohit Ranjan
Samsung India Software Operations.
On Sat, May 1, 2010 at 8:43 PM, Algoose Chase harishp...@gmail.com wrote:
@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.comwrote:
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.comwrote:
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.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.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.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.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] a google question
@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.comwrote:
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.comwrote:
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+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.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.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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
There are two kinds of people. Those who care for others and The others
--
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] a google question
This problem has been discussed before @
http://groups.google.co.in/group/algogeeks/browse_thread/thread/9c1e1aa8cf1ed437/d451cd9468d985f7
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.comwrote:
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+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.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.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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
There are two kinds of people. Those who care for others and The others
--
You received this message because you
Re: [algogeeks] a google question
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/9c1e1aa8cf1ed437/d451cd9468d985f7
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+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.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
Re: [algogeeks] a google question
i found this question on some site and it was mentioned there todo in o(n).
i dont have the solution
@ above
ur solution doesnt include the case of ncluding a[i] b[j] it takes only a[i]
b[0] or b[j] a[0]
On 2 May 2010 18:11, 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/9c1e1aa8cf1ed437/d451cd9468d985f7
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+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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options,
Re: [algogeeks] a google question
OOPs.. sorry
this doesnt work !
On Sun, May 2, 2010 at 6:11 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/9c1e1aa8cf1ed437/d451cd9468d985f7
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+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.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
Re: [algogeeks] a google question
Here is a solution of O(n) , taking 4 pointers 2 for each array
#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;
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;
else if(b = c b = d )ans = b , p22++ ;
else if(c = b c = d )ans = c , p12++ ;
elseans = d , p11++ , p21++ ,printf(4 );
printf(%d\n,ans);
}
}
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] a google question
@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.comwrote:
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.comwrote:
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.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.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.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] a google question
On Fri, Apr 30, 2010 at 4:35 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.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] a google question
Basically the index of ( a + b) in the final array will be ceil(( index of a
+ index of b )/2).
Also if there is a clash of indices you just have to compare the values at
those indices and adjust them.
I have run my concept with below two arrays and it works !!!
Arary A: 1 2 3 4 5 6
Array B: 2 3 5 6 8 9
addition of indices 84511611
addition of values (2+9) ( 1+5) (4+2) (6+8) ( 3+3) ( 5 + 9)
values: 11 6 6 14 9 14
Added indices: 4 5 6 8 11 11 ( These are not sorted indices, you will
know the indices of values in the final array right away after looking at
the indices of a and b )
indices/2: 2 3 3 4 6 6
corresponding final values6 6 6 11 14 14
- Kishen Das
On Fri, Apr 30, 2010 at 7:05 AM, 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.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] a google question
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.comwrote:
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.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.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] a google question
ignore the previous mail it wrongly send.
On Fri, Apr 30, 2010 at 11:12 PM, Rajesh Patidar patidarc...@gmail.com wrote:
let consider the list in two different part one traversing list B with
respect to A and A with B
(a.len,b.len) is always solution
a1=a2=a.len
On Fri, Apr 30, 2010 at 5:35 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 at
http://groups.google.com/group/algogeeks?hl=en.
--
BL/\CK_D!AMOND
--
BL/\CK_D!AMOND
--
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] a google question
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.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.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.
