rtiernay
BAN USERpublic class BinarySearchTreeDoublyLinkedListTransformer {
// @formatter:off
private static final Node TREE =
// Level 0
node( 5,
// Level 1
node( 3,
// Level 2
node( 2,
// Level 3
node( 1 ),
null
),
node(
4
)
),
node( 7,
node(
6
),
null
)
);
// @formatter:on
public static void main(String[] args) {
// Test on tree
testTree(TREE);
}
public static void testTree(Node root) {
Node head = transform(root);
Node node = head;
do {
System.out.print(node + " -> ");
node = node.right;
} while (node != head);
}
public static Node transform(Node node) {
// Notes:
// - let "->" and "<-" mean "points to"
// - node.left is logically node.previous
// - node.right is logically node.next
// - leftHead.left is logically leftTail
// - rightHead.left is logically rightTail
// - leftHead.left.right is logically leftTail.next
// - rightHead.left.right is logically rightTail.next
if (node == null) {
return null;
}
Node leftHead = transform(node.left);
Node rightHead = transform(node.right);
Node head;
if (leftHead == null) {
head = node;
} else {
head = leftHead;
// leftTail.next -> node
leftHead.left.right = node;
// leftTail <- node.previous
node.left = leftHead.left;
}
if (rightHead == null) {
// node <- head.previous
head.left = node;
// node.next -> head
node.right = head;
} else {
// rightTail.next <- head.previous
head.left = rightHead.left.right;
// rightTail.next -> head
rightHead.left.right = head;
// node <- rightHead.previous
rightHead.left = node;
}
return head;
}
private static Node node(Object value) {
return node(value, null, null);
}
private static Node node(Object value, Node left, Node right) {
Node node = new Node();
node.value = value;
node.left = left;
node.right = right;
return node;
}
private static class Node {
Node left;
Node right;
Object value;
@Override
public String toString() {
return value.toString();
}
}
}
public class IntegerArrayFourValueSum {
public static void main(String[] args) {
// Test some values
test(10, 2, 3, 4, 5, 9, 7, 8);
}
private static void test(int... values) {
findCombinationsOfFourWithSum(values);
}
private static void findCombinationsOfFourWithSum(int[] values) {
for (int i = 0; i < values.length - 3; i++) {
for (int j = i + 1; j < values.length - 2; j++) {
for (int k = j + 1; k < values.length - 1; k++) {
for (int l = k + 1; l < values.length; l++) {
int total = values[i] + values[j] + values[k] + values[l];
boolean match = total == 23;
if (match) {
System.out.println(values[i] + " " + values[j] + " " + values[k] + " " + values[l]);
}
}
}
}
}
}
}
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
public class FirstUniqueArrayCharacter {
public static void main(String[] args) {
// Test some strings
test("aa");
test("ab");
test("aab");
test("ababcbad");
}
private static void test(String text) {
char[] array = text.toCharArray();
Character c = findFirstUniqueCharacter(array);
System.out.println("First unique character in '" + text + "' is: '" + c + "'");
}
// Time complexity is O(n), space complexity is O(n)
private static Character findFirstUniqueCharacter(char[] array) {
// Linked hash map stores entries in insertion-order by default
Map<Character, Integer> map = new LinkedHashMap<Character, Integer>();
for (char c : array) {
Integer count = map.get(c);
if (count == null) {
count = 0;
}
count++;
map.put(c, count);
}
for (Entry<Character, Integer> entry : map.entrySet()) {
boolean unique = entry.getValue() == 1;
if (unique) {
return entry.getKey();
}
}
return null;
}
}
import static java.lang.Math.floor;
import static java.lang.Math.log;
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTreeCompleteLevelAnalyzer {
// @formatter:off
private static final Node TREE0 =
// Level 0
node( "a", null, null);
// @formatter:on
// @formatter:off
private static final Node TREE1 =
// Level 0
node( "a",
// Level 1
node( "b",
null,
null
),
node( "c",
// Level 2
node(
"d"
),
node(
"e"
)
)
);
// @formatter:on
// @formatter:off
private static final Node TREE2 =
// Level 0
node( "a",
// Level 1
node( "b",
// Level 2
node( "d",
// Level 3
node( "h" ),
node( "i" )
),
node(
"e"
)
),
node( "c",
node(
"f"
),
node(
"g"
)
)
);
// @formatter:on
public static void main(String[] args) {
// Test iterative and recursive versions for a few trees
testTree(TREE0, 0);
testTree(TREE1, 1);
testTree(TREE2, 2);
}
public static void testTree(Node root, int expectedLevel) {
int iterativeLevel = findCompleteLevelIterative(root);
int recursiveLevel = findCompleteLevelRecursive(root);
assert iterativeLevel == recursiveLevel : "Iterative does not match recursive level";
assert iterativeLevel == expectedLevel : "Iterative / recursive level does not match expected level";
}
public static int findCompleteLevelIterative(Node root) {
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
int count = 0;
// Perform a BFS search
while (!queue.isEmpty()) {
Node node = queue.poll();
count++;
if (hasMissingChild(node)) {
// The first node encountered with a missing child signifies the
// last complete level
break;
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
// Find the level based on the fact that 2^level <= count < 2^(level+1)
int level = calculateLevel(count);
return level;
}
public static int findCompleteLevelRecursive(Node root) {
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
int count = findCompleteLevelRecursiveHelper(queue, 0);
int level = calculateLevel(count);
return level;
}
private static int findCompleteLevelRecursiveHelper(Queue<Node> queue, int count) {
if (!queue.isEmpty()) {
Node node = queue.poll();
count++;
final boolean missingChild = node.left == null || node.right == null;
if (missingChild) {
// The first node encountered with a missing child signifies the
// last complete level
return count;
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
return findCompleteLevelRecursiveHelper(queue, count);
}
return count;
}
private static boolean hasMissingChild(Node node) {
return node.left == null || node.right == null;
}
private static int calculateLevel(int count) {
// Find the level based on the fact that 2^level <= count < 2^(level+1)
int level = (int) floor(log(count) / log(2));
return level;
}
private static Node node(Object value) {
return node(value, null, null);
}
private static Node node(Object value, Node left, Node right) {
Node node = new Node();
node.value = value;
node.left = left;
node.right = right;
return node;
}
private static class Node {
Node left;
Node right;
Object value;
@Override
public String toString() {
return value.toString();
}
}
}
- rtiernay September 22, 2012