code.runner
BAN USERprivate static boolean testInOrderStack(TreeNode tree1, TreeNode tree2) throws Exception {
Stack<TreeNode> stack1 = new Stack<TreeNode>(5);
Stack<TreeNode> stack2 = new Stack<TreeNode>(5);
Stack<TreeNode> result = new Stack<TreeNode>(5);
// push root
stack1.push(tree1);
stack2.push(tree2);
// hash set to mark roots that are visited
Set<TreeNode> set1 = new HashSet<TreeNode>();
Set<TreeNode> set2 = new HashSet<TreeNode>();
while (!stack1.isEmpty() && !stack2.isEmpty()) {
/* wait until the first push to the result stack that
* stores the in order traversal of the first tree.
*/
boolean waitTree1 = true;
while(waitTree1) {
TreeNode root1 = stack1.pop();
// if already visited root or a leaf node
if ((set1.contains(root1)) || (root1.left == null && root1.right == null)) {
result.push(root1);
waitTree1 = false;
} else {
// put left child
if (root1.left != null) {
stack1.push(root1.left);
}
// put root
stack1.push(root1);
set1.add(root1);// mark root as visited
// put right
if (root1.right != null) {
stack1.push(root1.right);
}
}
}
boolean waitTree2 = true;
while(waitTree2) {
// repeat for tree2
TreeNode root2 = stack2.pop();
// if already visited root or a leaf node
if ((set2.contains(root2)) || (root2.left == null && root2.right == null)) {
// match with result
if (result.peek().data != root2.data) {
System.out.println("They ain't matching!");
return false;
}
waitTree2 = false;
} else {
// get left child
if (root2.left != null) {
stack2.push(root2.left);
}
stack2.push(root2);
set2.add(root2);// mark root as visited
if (root2.right != null) {
stack2.push(root2.right);
}
}
}
}
return true;
}
// Test Code:
public static void testInOrderParallel() throws Exception {
// smaller tree example...
// TreeNode tree1 = new TreeNode(5);
// tree1.left = new TreeNode(3);
// tree1.right = new TreeNode(7);
//
// TreeNode tree2 = new TreeNode(3);
// tree2.right = new TreeNode(5);
// tree2.right.right = new TreeNode(7);
// Complex tree example...
TreeNode tree1 = new TreeNode(6);
tree1.left = new TreeNode(4);
tree1.left.right = new TreeNode(5);
tree1.right = new TreeNode(8);
tree1.right.left = new TreeNode(7);
TreeNode tree2 = new TreeNode(7);
tree2.left = new TreeNode(5);
tree2.left.left = new TreeNode(4);
tree2.left.right = new TreeNode(6);
tree2.right = new TreeNode(8);
System.out.println(testInOrderStack(tree1, tree2));
}
Returns all the pair of indices of a sub-array whose sum is such that
low <= sum <= high. For example, 2,1,4,3,1,2,8,5,3,6 with low 3 and high 8 starting at index 0 should return indices like [0..1]->3 (valid) [0..2]->7 (valid) [0..3]->10 (invalid) then start at index 1
[1..2]-> 5 (valid) [1..3]-> 8 (valid) [1..4]-> 9 (invalid) etc.
Time complexity: O(n^2)
public static List<Pair> getRangePairs(final int[] array, int low, int high) {
List<Pair> result = new ArrayList<Pair>();
int sum = 0;
for(int i =0; i<array.length; i++) {
// read the current value at i
sum = array[i];
// point j to next index of i and keep adding until sum > high
for(int j=i+1; j<array.length; j++) {
sum = sum + array [j];
if(sum >= low && sum <= high) {
result.add(new Pair(i,j));
} else if(sum > high) {
break;
}
}
}
return result;
}
public class Pair {
private int start;
private int end;
public Pair(int start, int end) {
this.start = start;
this.end = end;
}
public int getStart() {
return start;
}
public int getEnd() {
return end;
}
}
public static void main(String[] args) {
int[] array = new int[] {2,1,4,3,1,2,8,5,3,6};
List<Pair> pairs = getRangePairs(array, 3, 8);
for(final Pair p : pairs) {
System.out.println("[" + p.getStart() + ", " + p.getEnd() + "]");
}
}
// Output:
[0, 1]
[0, 2]
[1, 2]
[1, 3]
[2, 3]
[2, 4]
[3, 4]
[3, 5]
[4, 5]
[7, 8]
Given a string and a dictionary, returns all substrings of the string that exist in the dictionary. Time complexity is O(n^2)
public static List<String> getSubStringsFromDictionary(final String str, final List<String> dictionary) {
List<String> result = new ArrayList<String>();
for(int i=0; i<str.length(); i++) {
String s = String.valueOf(str.charAt(i));
// check for each characters, for example, a is substring of abc
if(dictionary.contains(s)) {
result.add(s);
}
// check for subsequent chars, for example, ab, abc, abcd etc.
for(int j=i+1; j<str.length(); j++) {
s = s + String.valueOf(str.charAt(j));
if(dictionary.contains(s)) {
result.add(s);
}
}
}
return result;
}
// test
public static void main(String[] args) {
List<String> dictionary = Arrays.asList("abc", "kx",
"acd", "bc", "abj", "ab", "bcd");
System.out.println(getSubStringsFromDictionary("abcd", dictionary));
}
// output: [ab, abc, bc, bcd]
//O(nlogn), while loop for each level of the tree, for loop for each node at that level.
// Typical TreeNode of a BST
// TreeNodeWrapper
- code.runner October 14, 2016