[algogeeks] a google question
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.
Re: [algogeeks] MXN matrix
@amit nice sit didn't know about that :) thanks On Thu, Apr 29, 2010 at 3:59 PM, amit kumar loveami...@gmail.com wrote: Answer for question 1: http://geeksforgeeks.org/?p=6257 And, I think the same solution can be extended/manipulated for rectangular matrix with largest number of 1's. Regards, Amit On Wed, Apr 28, 2010 at 10:23 PM, Vivek S s.vivek.ra...@gmail.com wrote: Let Memo[i][j] be the sum of elements in the (sub) rectangle from (0,0) to (i,j) Then use principle of inclusion and exclusion to find the sum of elements from (a, b) to (c, d) in O(1) for N*N matrix, Complexity is O(N^4) On 28 April 2010 13:36, Ashish Mishra amishra@gmail.com wrote: you are given a M x N matrix with 0's and 1's find the matrix with largest number of 1, 1. find the largest square matrix with 1's 2. Find the largest rectangular matrix with 1's -- 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. -- Reduce, Reuse and Recycle Regards, Vivek.S -- 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. -- Ashish Mishra http://ashishmishra.weebly.com/ -- 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] Build BST from binary tree without extra space
thing is that u r using recursion and we don't have to use it(
recussion use memory indirectly) as per the question
On Thu, Apr 29, 2010 at 3:55 PM, Algoose Chase harishp...@gmail.com wrote:
If you mean to convert the binary tree to binary search tree directly , then
BinarytoBST(Node* root)
{
if( root == nulll) return;
BinarytoBST(root-left);
BinarytoBST(root-right);
if( root-left )
Node* NodeL = MAX(root-left);
if ( root-right )
Node* NodeR = MIN(root-right);
if( NodeL-Data root-data)
{
// swap values.
temp = NodeL-data;
NodeL-data = root-data;
root-data = temp;
BinarytoBST(NodeL);
}
if( NodeR-Data = root-data)
{
// swap values.
temp = NodeR-data;
NodeR-data = root-data;
root-data = temp;
BinarytoBST(NodeR);
}
On Thu, Apr 29, 2010 at 11:23 AM, Algoose Chase harishp...@gmail.com
wrote:
Hi,
How do you define without extra space ?
Doing any order traversal either using recursion or using iteration is
going to take extra space .
If you are given a binary tree represented by pointers that points to
children nodes is it possible to do a heap sort without an array ?
On Thu, Apr 29, 2010 at 6:59 AM, sharad kumar aryansmit3...@gmail.com
wrote:
my choice is build a min heap .sort the array with heap sort.then find
the median of the sorted array and build tree
On Wed, Apr 28, 2010 at 10:16 PM, Vivek S s.vivek.ra...@gmail.com
wrote:
@Rajesh Patidar
I think we should do in Post order traversal alone. If we go by
Preorder/Inorder we might lose track of children node that is currently
being inserted into the BST. - correct me if im wrong :)
On 28 April 2010 15:30, Rajesh Patidar patidarc...@gmail.com wrote:
pickup node in any order no matter(pre,post,inorder) and just one by
one. start adding the node into bst no need to use extra space u have
to just ditach the node from binary tree and attach it in bst.
On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra amishra@gmail.com
wrote:
How to build BST from binary tree in place i.e without extra space ??
--
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
--
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.
--
Reduce, Reuse and Recycle
Regards,
Vivek.S
--
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.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
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.
--
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.
[algogeeks] infy color balls
One of my friend ask me this n i am bad in P C (will love if smone can provide me a link to learn it though) nyways prob is: there are infy color balls of k different color you are allowed to pick n balls out of those infy(infinite) balls cond is : you must have all k color balls with u obviously kn Question is how many possibilities for selection you have ? Thanks Ashish -- 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] infy color balls
Answer is k! * k^(n-k). You can select k number of balls in K! ways and then rest of (n-k) balls in k ways. This way you are ensuring that you have all k color balls and n number of balls in total. - Kishen Das On Fri, Apr 30, 2010 at 6:04 AM, Ashish Mishra amishra@gmail.comwrote: One of my friend ask me this n i am bad in P C (will love if smone can provide me a link to learn it though) nyways prob is: there are infy color balls of k different color you are allowed to pick n balls out of those infy(infinite) balls cond is : you must have all k color balls with u obviously kn Question is how many possibilities for selection you have ? Thanks Ashish -- 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] infy color balls
C(n-1,k-1) if balls are similar On Fri, Apr 30, 2010 at 4:34 PM, Ashish Mishra amishra@gmail.comwrote: One of my friend ask me this n i am bad in P C (will love if smone can provide me a link to learn it though) nyways prob is: there are infy color balls of k different color you are allowed to pick n balls out of those infy(infinite) balls cond is : you must have all k color balls with u obviously kn Question is how many possibilities for selection you have ? Thanks Ashish -- 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. -- Man goes to doctor. Says he's depressed. Says life seems harsh and cruel. Says he feels all alone in a threatening world where what lies ahead is vague and uncertain. Doctor says Treatment is simple. Great clown Pagliacci is in town tonight. Go and see him. That should pick you up. Man bursts into tears. Says But, doctor...I am Pagliacci. -- 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] Finding the mode in a set of integers
Here are 3-4 methods to solve http://geeksforgeeks.org/?p=503 On Sat, Apr 17, 2010 at 5:45 AM, Ashim Kapoor ashimkap...@gmail.com wrote: are you referring to the lectures by Dr Naveen Garg ? Or are these lectures different? Please clarify. Thank you, Ashim. On Sat, Apr 17, 2010 at 5:43 AM, rahul rai raikra...@gmail.com wrote: On 4/16/10, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Just got another O(n) solution. Find the n/2 th largest element in the array using the Median of Medians Selection algorithm. =? takes O(n) That's It ! -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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. Work out the CDEEP Algorithms course lectures . It will give all basics -- 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.
[algogeeks] Re: a google question
Nice question:
1. |A| = |B| i.e I assume their cardinality is equal
2. A(n) = { a1, a2 a3, ...aN} such that a1=a2=a3...=aN
3. B(n) = { b1, b2 b3, ...bN} such that b1=b2=b3...=bN
4. S(n^2) = A x B = {(a1,b1), (a1,b2)(a1,bN),
(a2,b1), (a2,b2)(a2,bN),
(aN,b1), (aN,b2)(aN,bN)}
I assume each pair is stored as a sum i.e ai + bi and also that I
have paired them in a way such that we find a pair ai bi for some
i in 1..N and and a(i-1) = b(i-1)
A first observation is that in the worst case, the first 2N numbers in
S will contain the final result of N numbers.
i.e in (a1,b1), (a1,b2)(a1,bN), (a2,b1), (a2,b2)(a2,bN)
In the best case first N numbers in S will contain the final N numbers
(already sorted in decreasing order)
i.e in (a1,b1), (a1,b2)(a1,bN)
Now, if we consider again the worst case scenario, then we can first
divide 2N numbers in two groups of size N each and each of this group
is already sorted in decreasing order.
i.e (a1,b1), (a1,b2)(a1,bN) and (a2,b1), (a2,b2)(a2,bN)
Now we can simply apply Merge Algorithm on these 2 already sorted
arrays of size N each in O(N) time, which solves the problem
I can be wrong only if the the results lie outside first 2N numbers,
which I hope is not the case(then I think its not possible to solve in
O(n) but in O(nlogn)).
On Apr 30, 2:05 pm, divya sweetdivya@gmail.com wrote:
Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G, let's
say they are decreasingly sorted), we define a set S = {(a,b) | a \in
A
and b \in B}. Obviously there are n^2 elements in S. The value of such
a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs
from S with largest values. The tricky part is that we need an O(n)
algorithm.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group
athttp://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: a google question
Nice question:
1. |A| = |B| i.e I assume their cardinality is equal
2. A(n) = { a1, a2 a3, ...aN} such that a1=a2=a3...=aN
3. B(n) = { b1, b2 b3, ...bN} such that b1=b2=b3...=bN
4. S(n^2) = A x B = {(a1,b1), (a1,b2)(a1,bN),
(a2,b1), (a2,b2)(a2,bN),
(aN,b1), (aN,b2)(aN,bN)}
assuming we have added in a way such that we find a pair ai bi,
for some i in 1..N such that a(i-1) = b(i-1)
A first observation is that in the worst case, the first 2N numbers in
S will contain the final result of N numbers.
i.e in (a1,b1), (a1,b2)(a1,bN), (a2,b1), (a2,b2)(a2,bN)
In the best case first N numbers in S will contain the final N numbers
(already sorted in decreasing order)
i.e in (a1,b1), (a1,b2)(a1,bN)
Now, if we consider again the worst case scenario, then we can first
divide 2N numbers in two groups of size N each and each of this group
is already sorted in decreasing order.
i.e (a1,b1), (a1,b2)(a1,bN) and (a2,b1), (a2,b2)(a2,bN)
Now we can simply apply Merge Algorithm on these 2 already sorted
arrays of size N each in O(N) time, which solves the problem
I can be wrong only if the the results lie outside first 2N
numbers(which I hope is not the case).
On Apr 30, 2:05 pm, divya sweetdivya@gmail.com wrote:
Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G, let's
say they are decreasingly sorted), we define a set S = {(a,b) | a \in
A
and b \in B}. Obviously there are n^2 elements in S. The value of such
a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs
from S with largest values. The tricky part is that we need an O(n)
algorithm.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group
athttp://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] value of n
how do I compute n from this equation. n 8lg(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] infy color balls
@Ashish Check this http://www.codechef.com/problems/MARBLES/ Mohit Ranjan Samsung India Software Operations. On Fri, Apr 30, 2010 at 4:34 PM, Ashish Mishra amishra@gmail.comwrote: One of my friend ask me this n i am bad in P C (will love if smone can provide me a link to learn it though) nyways prob is: there are infy color balls of k different color you are allowed to pick n balls out of those infy(infinite) balls cond is : you must have all k color balls with u obviously kn Question is how many possibilities for selection you have ? Thanks Ashish -- 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.
Re: [algogeeks] value of n
binary search on n On Fri, Apr 30, 2010 at 10:15 PM, Amit Agarwal lifea...@gmail.com wrote: how do I compute n from this equation. n 8lg(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. -- 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.
