melchior
BAN USER<pre lang="" line="1" title="CodeMonkey52018" class="run-this">package com.bloomberg;
/**
* Created by IntelliJ IDEA.
* User: andrey
* Date: 10/20/11
* Time: 9:14 PM
*/
class Profit {
public static void main(String[] args) {
process();
}
public static void process() {
int[] price = {-2, -4, 30, -50, 90, -60, 100, 120};
int buy = 0;
int sell = 0;
int profit = 0;
int complexity = 0;
for (int i=0; i<price.length; i++) {
for (int j=i; j<price.length; j++) {
complexity ++;
// sell is more than buy
if (price[j] > price[i]) {
int delta = price[j] - price[i];
if (delta > profit) {
profit = delta;
buy = i;
sell = j;
}
}
}
}
System.out.println("buy at "+price[buy]+" and sell at "+price[sell]);
System.out.println("complexity="+complexity);
}
}
</pre><pre title="CodeMonkey52018" input="yes">
</pre>
boolean isBinarySearchTreeNode(Node node, int left, int right){
if (node == null) return true;
if (node.value < left || node.value > right) return false;
if (node.left != null && node.left.value > node.value) return false;
if (node.right != null && node.right.value < node.value) return false;
return isBinarySearchTreeNode(node.left, left, node.value) && isBinarySearchTreeNode(node.right, node.value, right);
}
The same algorithm was posted by pseudo_coder below.
- melchior October 13, 2011Let's assume that all left children are fine, but the root node is not, with large number of children on the left (balanced or non-balanced tree, does not matter), with "in order" traversal the code will have to reach for the last node on the left and only then go up until finding out that the root itself does not comply. It should be fail-fast, fail-early algorithm, which is "pre-order" here. If we were counting non-complied nodes, then the order is irrelevant. Agreed?
- melchior October 10, 2011<pre lang="" line="1" title="CodeMonkey73917" class="run-this">/**
* Created by IntelliJ IDEA.
* User: andrey
* Date: 10/10/11
* Time: 10:50 AM
*/
public class BinarySearchTreeOrNot {
public static void main(String[] args) {
BinarySearchTreeOrNot test = new BinarySearchTreeOrNot();
test.run();
}
void run() {
// test with binary search tree
Node bst = createBinarySearchTree();
boolean result = isBinarySearchTreeNode(bst);
System.out.println(result);
// test with binary tree
Node bt = createBinaryTree();
result = isBinarySearchTreeNode(bt);
System.out.println(result);
}
boolean isBinarySearchTreeNode(Node node){
if (node == null) return true;
if (node.left != null && node.left.value > node.value) return false;
if (node.right != null && node.right.value < node.value) return false;
return isBinarySearchTreeNode(node.left) && isBinarySearchTreeNode(node.right);
}
Node createBinarySearchTree(){
Node one = new Node(1);
Node four = new Node(4);
Node three = new Node(3);
three.left = one;
three.right = four;
Node five = new Node(5);
Node six = new Node(6);
Node seven = new Node(7);
Node nine = new Node(9);
five.left = three;
five.right = seven;
seven.left = six;
seven.right = nine;
return five;
}
Node createBinaryTree(){
Node five = new Node(5);
Node eight = new Node(8);
Node one = new Node(1);
Node sixteen = new Node(16);
Node three = new Node(3);
Node nine = new Node(9);
Node two = new Node(2);
five.left = eight;
five.right = three;
eight.left = one;
eight.right = sixteen;
three.left = nine;
three.right = two;
return five;
}
class Node {
int value;
Node right;
Node left;
Node(int value){
this.value = value;
}
}
}
</pre><pre title="CodeMonkey73917" input="yes">
</pre>
We should leverage properties of binary search tree: the left child value is less or equal to the node value and the right child value should be greater or equal than the node value. And check that property for each node. The code is using preorder traversal.
Assuming that null child is ok.
@asm - the question does not allow division operator in the solution.
- melchior October 22, 2011