Re: [algogeeks] Build BST from binary tree without extra space
@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.comalgogeeks%2bunsubscr...@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.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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] MXN matrix
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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Dijkstra For Longest Path?
@chitta koushik No, That might lead to negative edge cycles! 2010/1/15 chitta koushik koushik.infin...@gmail.com How abt negating values and using same single source shortest path algo ? 2010/1/15 saltycookie saltycoo...@gmail.com longest path is NP-hard 2010/1/11 Johan djjord...@gmail.com Ok, so I know that Dijkstra can be used to solve the single-source shortest path problem quite efficiently. I however need to find the single source longest path through a graph. Can Dijkstra be used for this if I transform the edge lengths so that the longest edge is now the shortest etc etc. Does anybody have any references to work done which is similar to the this longest path problem? -- 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. -- 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.
[algogeeks] Re: Good problem
to maximize the minimum distance between any two points:- to maximize the
minimum distance between adjacent points
- for this all points must be equally spaced.
hence, choose 'n' equally spaced points in the range (r1, r2) starting from
r1 and ending at r2.
2009/10/21 saltycookie saltycoo...@gmail.com
Yes, you are quite right. If I am not mistaken, you give a good solution
for finding the minimum maximum distance.
But what about the original problem where we want to find the maximum
minimum distance? I am not clear about the connection between the two
problems.
Thanks.
2009/10/21 Dave dave_and_da...@juno.com
林夏祥 , think again. If we are trying to minimize the maximum distance,
then we want to minimize the upper bound. That is what I specified:
letting c be the upper bound, find the smallest c such that all of the
distances do not exceed c. That gives rise to the inequalities
|x(i)-x(j)| = c.
If necessary, this can be written as two inequalities:
x(i) - x(j) = c and
x(j) - x(i) = c.
Since the relationship is and, we can just use the two inequalities
as part of the constraint conditions.
Dave
On Oct 21, 12:02 am, 林夏祥 saltycoo...@gmail.com wrote:
I don't think LP can solve it. We are to maximize c, not minimize c.
The formulas we have are:
|x(i)-x(j)| = c for all i and j
r1(i) = x(i) = r2(i) for all i
The first inequality actually is combination of two linear equalities:
x(i)
- x(j) = c or x(i) - x(j) = -c. Notice the relation of the two is
or,
and we cannot put them together to get a system of linear inequalities.
2009/10/21 Dave dave_and_da...@juno.com
This is a linear programming problem. The way you formulate the
problem depends on the capabilities of the linear programming software
you have.
Basically, you want to
minimize c
by finding x(1) to x(n) such that
|x(i)-x(j)| = c for all i and j
r1(i) = x(i) = r2(i) for all i
Dave
On Oct 5, 9:22 am, monty 1987 1986mo...@gmail.com wrote:
We have to locate n points on the x-axis
For each point xi
the x co-ordinate of it lies between a
range
[r1i,r2i]
Now we have to decide the location of points such that
minimum { distance between any two points } is maximum.
Any answer is welcomed.
--
此致
敬礼！
林夏祥- Hide quoted text -
- Show quoted text -
--
此致
敬礼！
林夏祥
--
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 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
-~--~~~~--~~--~--~---
[algogeeks] Re: 100!
hope you mean find *sum* of all the digits in number-100! :) 2009/10/11 vicky mehta...@gmail.com find some of all the digits in number-100! -- 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 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 -~--~~~~--~~--~--~---
[algogeeks] Re: minimum difference.
@Varun S VIt wont work for this 1 3 4 5 2009/9/2 Varun S V varun...@gmail.com Since we difference between two minumum elements should suffice, how about finding the min and second minimum element in the array in single scan and returning their difference. This should take not more than O(N) time. Regards, -Varun. On Wed, Sep 2, 2009 at 12:09 AM, Shishir Mittal 1987.shis...@gmail.comwrote: Sort the array and find the minimum of difference of adjacent values of the sorted array. Time Complexity : O(nlogn), Space Complexity : O(1) On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal ankur.mast@gmail.comwrote: given a array of length n. find 2 number such that their differnce is minimum. -- Shishir Mittal Ph: +91 9936 180 121 -- 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 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Find longest interval
let A[i+1] = a[0] + a[1] + ... + a[i]; let B[i+1] = b[0] + b[1] + ... + b[i]; A[0] = B[0] = 0; sum of nos from i to j of a[] = A[j+1] - A[i]; // O(1) time Thus O(n^2) sol can be obtained for this problem by finding the sub-array sum in the range [i, j] for every i, j; But I have not used the fact that the given nos is either 0 or 1. There should be a better way, yet to think about it :) 2009/8/26 ankur aggarwal ankur.mast@gmail.com Find longest interval We are given with two arrays A and B..each of size N...elements of array contains either 1 or 0... we have to find such an interval (p,q)(inclusive) such that the sum of all the elements of A (between this interval) and sum of all elements of B (between this interval ) is equal... i.e. a[p]+a[p+1]+a[q]= b[p]+b[p+1]+b[q] -- 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 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 -~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
@Devi;
Consider this,
N = 2
The array elements should these (N+2), numbers : {1, 2, 3, 4}
If the given array is {4, 3}
Will your code work correctly?
2009/7/31 Devi G devs...@gmail.com
The logic is actually simple. Tot if we mark in some way an element when
it's scanned, we can find the missing numbers in the second scannin.
3,5,1,2,9,10,8,6
When for loop sees '3' it knows elt 3 is there. So multiplies the number at
3rd position by some arbitrary number. (* I've taken the arbitrary number
to be n here but CORRECT ONE IS n+3 cos n will fail in some cases*)
so, when it sees '5' multiplies the number at 5th position by n+3.
It skips when the numbr is greater than n.
n+3 = 11 here.
So,after first loop,
33, 55, 11, 2 , 99, 110, 8, 66.
So now, in the second scan, the indices of all elts that are divisible by
n+3 are present in the array.
elts at 4th and 7th positions are not divisible. hence missing numbers are
4 and 7.
--
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 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
-~--~~~~--~~--~--~---
[algogeeks] Re: Missing numbers
N! overflows... Try to write a program to find the value of 30! You don't have a variable that is large enough to store such a big number... 2009/7/31 sharad kumar aryansmit3...@gmail.com check this out Let x and y be the missing number, Now equation 1 is : x + y = [n(n+1)/2] - S equation 2 is: x * y = N! /P solve both we get elements On Fri, Jul 31, 2009 at 8:27 PM, Devi G devs...@gmail.com wrote: The logic is actually simple. Tot if we mark in some way an element when it's scanned, we can find the missing numbers in the second scannin. 3,5,1,2,9,10,8,6 When for loop sees '3' it knows elt 3 is there. So multiplies the number at 3rd position by some arbitrary number. (* I've taken the arbitrary number to be n here but CORRECT ONE IS n+3 cos n will fail in some cases* ) so, when it sees '5' multiplies the number at 5th position by n+3. It skips when the numbr is greater than n. n+3 = 11 here. So,after first loop, 33, 55, 11, 2 , 99, 110, 8, 66. So now, in the second scan, the indices of all elts that are divisible by n+3 are present in the array. elts at 4th and 7th positions are not divisible. hence missing numbers are 4 and 7. -- 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 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 -~--~~~~--~~--~--~---
