gonzo
BAN USERHere is a Java version:
public void printAllValuesSmallerThen(Node node, Integer value) {
if (node == null)
return;
this.printAllValuesSmallerThen(node.getLeftChild(), value);
if (node.getData() > value)
return;
else
System.out.print(node.getData() + " ");
this.printAllValuesSmallerThen(node.getRightChild(), value);
}
Consider following example:
0 1 2 3 4 5 6 7 8 9
[1,0,0,0,1,1,1,0,1,0] -> Sum = 5
[1,1,0,0,0,0,0,0,1,0] -> Sum = 3
Improvement from the left: 0 + 1 step
Improvement from the right: 9 - 8 steps
-> trim from the left to index 1
...but the best solution is:
Index: 0 to 4
Diff: 4
Sum: 2
Can you elaborate?
Here is how I understand the question:
0.6% or 6 out of 1000 are actually defect.
2% or 20 out of 1000 are declared defect, but they are not defect.
Meaning out of 1000, 26 would be declared defect.
Now the Question:
Given that a randomly chosen transistor is declared defective by the
tester, compute the probability that it is actually defective.
26 out of my 1000 would be declared defective, but only 6 are
actually defective.
The chances that the transistor chosen is defective is
6 out of 26 = 0.2308 or 23.08%
In other words that would not be a very efficient test. Roughly
three out of four transistors that are thrown out, are not
defective.
Using an InOrderTreeIterator you scan and merge the nodes in on step. Then the list can be rearranged into a tree by using the 'reverse mergesort' suggested further up. If you use the original nodes you need to be careful since the old parent-children links still exist.
They need to be reset. Merge: O(m+n), Insert: O(m+n)
public Node createBinarySearchTreeFromSortedNodeList(List<Node> nodeList) {
return this.createBinarySearchTreeFromSortedNodeListRecursive(nodeList, 0, nodeList.size() - 1);
}
private Node createBinarySearchTreeFromSortedNodeListRecursive(List<Node> nodeList, Integer minIndex, Integer maxIndex) {
Node node = null;
if (maxIndex > nodeList.size() - 1 || minIndex < 0)
return null;
if (minIndex == maxIndex) {
node = nodeList.get(minIndex);
node.setLeftChild(null);
node.setRightChild(null);
node.setParent(null);
return node;
}
else
if (minIndex > maxIndex)
return null;
Integer middle = (maxIndex + minIndex) / 2;
Node leftChild = createBinarySearchTreeFromSortedNodeListRecursive(nodeList, minIndex, middle - 1);
Node rightChild = createBinarySearchTreeFromSortedNodeListRecursive(nodeList, middle + 1, maxIndex);
node = nodeList.get(middle);
node.setLeftChild(leftChild);
node.setRightChild(rightChild);
leftChild.setParent(node);
rightChild.setParent(node);
return node;
}
public class InOrderTreeIterator {
private Node currentNode = null;
private Stack<Node> treeTraverserStack = null;
private Node next = null;
public InOrderTreeIterator(Node root) {
treeTraverserStack = new Stack<Node>();
this.currentNode = root;
this.fetchNextNode();
}
public Node next() {
Node result = next;
this.fetchNextNode();
return result;
}
public boolean hasNext() {
return this.next != null;
}
private void fetchNextNode() {
Node result = null;
boolean done = false;
while (!done) {
if (!this.treeTraverserStack.isEmpty() || currentNode != null) {
if (currentNode != null) {
this.treeTraverserStack.push(currentNode);
currentNode = currentNode.getLeftChild();
}
else {
currentNode = this.treeTraverserStack.pop();
result = currentNode;
currentNode = currentNode.getRightChild();
done = true;
}
}
else
done = true;
}
this.next = result;
}
}
}
- gonzo July 27, 2013Following a version that also maintains a nodes parent:
{
public Node upsideDownTreeRercursive(Node node, Node newRoot) {
Node oldParent = null;
if (node == null)
return null;
if (node == newRoot) {
node.setLeftChild(node.getParent());
node.setParent(null);
return node;
}
if (upsideDownTreeRercursive(node.getLeftChild(), newRoot) != null) {
oldParent = node.getParent();
node.setParent(node.getLeftChild());
node.setLeftChild(oldParent);
return node;
}
if (upsideDownTreeRercursive(node.getRightChild(), newRoot) != null) {
oldParent = node.getParent();
node.setParent(node.getRightChild());
node.setRightChild(oldParent);
return node;
}
return null;
}
Following the simplest solution I can think of:
public Integer findBestStockBuySellPointsSimple(List<Integer> list) {
Integer currentMin, tempMin, currentMax, currentMaxProfit = 0;
tempMin = currentMin = currentMax = list.get(0);
for (Integer price : list) {
if (price < tempMin)
tempMin = price;
if (price - tempMin > currentMaxProfit) {
currentMin = tempMin;
currentMax = price;
currentMaxProfit = currentMax - currentMin;
}
}
return currentMaxProfit;
}
1 - Remember the last lowest price.
2 - If the difference to the current price is bigger than my last
maximum you got a new maximum profit.
As someone mentioned above:
1 - We are looking for a sequence of three consecutive numbers in the array
2 - The array is not sorted, so there can be any positive and negative number sequence
public void findGreatestProduct(List<Integer> list) {
Integer greatestProduct = Integer.MIN_VALUE;
Integer greatestAbsoluteSum = 0;
Integer currentAbsoluteSum = 0;
boolean positive = false;
Integer[] n = new Integer[3];
Integer[] current = new Integer[3];
if (list == null || list.size() < 3) {
System.out.println("The list is to short or empty!");
}
current[0] = current[1] = current[2] = 0;
for (int i = 0; i < list.size() - 2; i++) {
n[0] = list.get(i);
n[1] = list.get(i + 1);
n[2] = list.get(i + 2);
if (n[0] != 0 && n[1] != 0 && n[2] != 0) {
positive = ((( n[0] < 0 ? 1 : 0 ) + ( n[1] < 0 ? 1 : 0 ) + ( n[2] < 0 ? 1 : 0 )) % 2 == 0);
if (positive) {
currentAbsoluteSum = Math.abs(n[0]) + Math.abs(n[1]) + Math.abs(n[2]);
if (currentAbsoluteSum > greatestAbsoluteSum) {
greatestAbsoluteSum = currentAbsoluteSum;
current[0] = n[0];
current[1] = n[1];
current[2] = n[2];
}
}
}
}
greatestProduct = current[0] * current[1] * current[2];
System.out.println( current[0] + " * " + current[1] + " * " + current[2] + " = " + greatestProduct);
}
If the absolute sum of three values is the biggest, it's product will be de biggest given that the number of negative values is even. For that I calculate for all triples of values:
1 - Skip if one of the values is 0 (could be optimized to skip 2 if n[2] is 0)
2 - Is the number of negative values even (negative * negative = positive)?
3 - If the sum of absolute values the greatest, then the product will be the greatest too
Reppamelajoung, Dev Lead at Absolute Softech Ltd
I have worked as a wedding photographer for the past two years, first as a photographer’s assistant and then ...
Good explanations where already given further up. Still for me
it is always easier to understand a concept when I can related
it somehow to the 'real world'
Think of a sports event where always the weakest wins
and moves up to the next round of comparisons. That
would require 7 'matches' to find the winner. Since there
are two sets of three, equals/'ties' can be eliminated
since there is still a third coin 'in the game' with the
same weight that would win in case it was the lightest.
There is only a limited number of combinations
possible:
- two ties on either side of the tree (left or right)
in the first round.
- one tie on each side of the tree in the first round
- only one tie or second one in case x (or y) is
the lightest
- one tie in the second round
Hope it helps.
- gonzo August 15, 2013