???
BAN USERSwapnil's answer runs correct only if the tree is an integer storing bst. here is another solution for generic types. seperated into functions for ease of understanding
public boolean isBST() {
if (head == null) return true;
T value = head.value;
return (isBSTLeft(head.getLeft(), value) && isBSTRight(head.getRight(), value));
}
private boolean isBSTRight(Node<T> node, T min) {
if (node == null) return true;
T nodeValue = node.getValue();
if (nodeValue.compareTo(min) <= 0) {
return false;
}
return isBSTLeft(node.getLeft(), nodeValue) && isBSTRight(node.getRight(), min);
}
private boolean isBSTLeft(Node<T> node, T max) {
if (node == null) return true;
T nodeValue = node.getValue();
if (nodeValue.compareTo(max) > 0) {
return false;
}
return isBSTLeft(node.getLeft(), max) && isBSTRight(node.getRight(), nodeValue);
}
my solution is log(n)
in the question they ask for the number of pairs, i did find the pairs though.
import java.util.*;
/**
* Input - array of integers size N, integer Threshold.
* Output - the pairs (x, y) of distinct elements with condition x + y <= Threshold.
* Is that possible to implement is with O(n) ?
*/
class FindPairsUnderThreshold {
public List<Map.Entry<Integer, Set<Integer>>> solve(Integer[] integers, Integer threshold) {
// the complexity > O(n), sorted list is the key in this solution
SortedSet<Integer> sortedSet = new TreeSet<Integer>();
// first put values into the sorted set
for (Integer number : integers) {
sortedSet.add(number);
}
// then get the range from the head (smallest value) to the maximum value that satisfies the condition
List<Map.Entry<Integer, Set<Integer>>> result = new ArrayList<Map.Entry<Integer, Set<Integer>>>();
for (Integer number : integers) {
// headSet is not inclusive, +1 is to make it include the exact sum
int diff = threshold - number + 1;
Set<Integer> integerIntegerSortedMap = sortedSet.headSet(diff);
Map.Entry<Integer, Set<Integer>> integerSetPair = new AbstractMap.SimpleEntry<Integer, Set<Integer>>(number, integerIntegerSortedMap);
result.add(integerSetPair);
}
return result;
}
public static void main(String[] args) {
Integer[] integers = {4, 1, 5, 2, 3, -1, 6,};
Integer threshold = 4;
List<Map.Entry<Integer, Set<Integer>>> solution = new FindPairsUnderThreshold().solve(integers, threshold);
for (Map.Entry<Integer, Set<Integer>> entry : solution) {
Integer first = entry.getKey();
for (Integer second : entry.getValue()) {
System.out.print("(" + first + ", " + second + "), ");
}
}
System.out.println(solution);
}
}
My solution is in O(2n)
public int follow(int startNumber, Map<Integer, Pair<Boolean, Integer>> pairMap) {
Pair<Boolean, Integer> currentPair = pairMap.get(startNumber);
if (currentPair == null) {
return 0;
} else {
if (currentPair.getFirst()) {
return currentPair.getSecond();
} else {
currentPair.setFirst(true);
int result = follow(startNumber + 1, pairMap) + 1;
currentPair.setSecond(result);
return result;
}
}
}
public void q1() {
int[] ints = {7,6,5,4,2,3,1};
// first integer , in the pair first is vis9ted, second is the score
Map<Integer, Pair<Boolean, Integer>> pairMap = new HashMap<Integer, Pair<Boolean, Integer>>();
for (Integer i : ints) {
pairMap.put(i, new Pair<Boolean, Integer>(false, 1));
}
int[] results = new int[ints.length];
for (int i = 0; i < ints.length; i++) {
int result = follow(ints[i], pairMap);
results[i] = result;
System.out.println(ints[i] +":"+result);
}
}
here is my solution which (I believe) works correctly and also prints the sequence
- ??? October 09, 2013