thunder.thd
BAN USER<pre lang="" line="1" title="CodeMonkey70443" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class BiggestBST {
private static Node rootBST = null;
private static int maxSize = -1;
public static void main(String[] args) {
Node root = buildTree();
findBST(root);
System.out.println("Biggest BST has root --> " + (rootBST == null ? "NULL" : rootBST.getId()));
}
private static Result findBST(Node n) {
if(n == null) {
return new Result(true, 0);
}
boolean isBST = true;
if(
((n.getLeft() != null) && (n.getLeft().getId() > n.getId()))
||
((n.getRight() != null) && (n.getRight().getId() < n.getId()))
) {
isBST = false;
}
int size = 1;
Result resultL = findBST2(n.getLeft());
if(resultL.isBST) {
size += resultL.size;
}
Result resultR = findBST2(n.getRight());
if(resultR.isBST) {
size += resultR.size;
}
isBST = isBST && resultL.isBST && resultR.isBST;
if(isBST) {
bstMap.put(n, size);
if(size > maxSize) {
maxSize = size;
rootBST = n;
}
}
return new Result(isBST, size);
}
private static class Result {
private boolean isBST;
private int size;
Result(boolean isBST, int size) {
this.isBST = isBST;
this.size = size;
}
}
private static Node buildTree() {
Node root = new Node(5);
root.setLeft(new Node(3));
root.setRight(new Node(6));
root.getLeft().setLeft(new Node(1));
root.getLeft().setRight(new Node(4));
root.getRight().setLeft(new Node(9));
root.getRight().setRight(new Node(10));
root.getRight().getLeft().setLeft(new Node(7));
return root;
}
}
</pre><pre title="CodeMonkey70443" input="yes">
</pre>
A naive approach to this problem is to take each element from the circle and calculate the maximum sum that can be obtained from that point.
It's like running the algorithm of "maximum sum sub array problem" for each array obtained by traversing the circle from every element of the circle, but instead of continuing when the sum is less than 0, you just move to the next array.
At the end get the maximum no. of these maximums.
For e.g, for circle [200 -10 -10 -10 -10 -10 100],
1. first, you will find the subarray which starts with 200 and have the sum of elements maximum; this translates in running the
"maximum sum sub array" algorithm on [200 -10 -10 -10 -10 -10 100]; this will return 250
2. then, you will find the subarray which starts with -10 and have the sum of elements maximum; this translates in running the
"maximum sum sub array" algorithm on [-10 -10 -10 -10 -10 100 200]
calculate the maximum sum that can be obtained; if the starting point is negative then ignore this step and go to next element in the circle
... and so forth
n. till the last element 100, where you will find the subarray which starts with 100 and have the sum of elements maximum; this translates in running the "maximum sum sub array" algorithm on [100 200 -10 -10 -10 -10 -10]; this will return 300
The time complexity will be like O(n*n)
The most efficient sorting algorithm has O(nlogn) time complexity where, for this problem, n is big.
In my above algorithm, the trie structure can be built by traversing the list only once --> O(n) time complexity.
Then:
a. if you wanna find if a number is present or not in the list, it will take you at most 8 (64 / 8) comparisons.
b. if you wanna just return an arbitrary number which is not in the list then you can go and check the number of children for each node and pick the missing child. But, in order to avoid the cases in which you may have an "almost complete trie structure" where there is only a number missing and this number is something like 11111111 --> 11111111 --> 11111111 --> 11111111 --> 11111111 --> 11111111 --> 11111111 --> 11111110 (this no. will appear in the trie in the far right hand side and will force you to do a lot of comparisons in order to reach it), you can do an artifice and mark a node as complete once the sub-trie having this node as root is complete. In this case you will know directly where to go in the trie to pick a number which does not appear in the initial list.
hey guys,
What about using a trie structure to represent those numbers? In which you have each number split in 8 groups of 8 bits (or lower no. of bits).
So, for ex. 123456789123456789 (00000000 11011011 01001101 10100101 11010110 01101000 00101111 100010101) will be represented by the path: 00000000 --> 11011011 --> 01001101 --> 10100101 --> 11010110 --> 01101000 --> 00101111 --> 100010101 in the trie structure.
After the entire trie structure was built it will much easier to find a number which is not in the list.
If the list is too big to fit into memory, we can store the trie structure on the disk.
This is how Lucene stores the numeric values in its index for a fast search.
Sorry, on my previous comment because I didn't add some
- thunder.thd October 11, 2011explanations.
The most important part in that code is the recursive function which for a particular node in the tree returns if the sub-tree having this node as a root is a BST and the size (no. of nodes) of this sub-tree.
So, for each node in the tree it checks the followings:
1. (if left child is not null and its value is less than node's value) && (if right child is not null and its value is greater than node's value)
2. call the function for left child and see if the left sub-tree is BST
3. call the function for right child and see if the right sub-tree is BST
If the above 3 conditions are met then the current node for a BST sub-tree and compute its size based on what the function returns for left and right children.
In this case you will touch each node only once.