PR
BAN USERpublic class MergeBinarySearchTrees {
private static class Node {
private Node left;
private Node right;
private int payload;
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("(");
sb.append(payload);
if (left != null) sb.append(left);
if (right != null) sb.append(right);
sb.append(")");
return sb.toString();
}
}
public static void main(String[] args) {
Node n60 = new Node(); n60.payload = 60;
Node n45 = new Node(); n45.payload = 45;
Node n30 = new Node(); n30.payload = 30;
Node n15 = new Node(); n15.payload = 15;
Node n5 = new Node(); n5.payload = 5;
Node n50 = new Node(); n50.payload = 50; n50.left = n45; n50.right = n60;
Node n40 = new Node(); n40.payload = 40; n40.left = n30; n40.right = n50;
Node n10 = new Node(); n10.payload = 10; n10.left = n5; n10.right = n15;
Node n20 = new Node(); n20.payload = 20; n20.left = n10; n20.right = n40;
Node n2 = new Node(); n2.payload = 2;
Node n7 = new Node(); n7.payload = 7;
Node n14 = new Node(); n14.payload = 14;
Node n18 = new Node(); n18.payload = 18;
Node n4 = new Node(); n4.payload = 4; n4.left = n2; n4.right = n7;
Node n16 = new Node(); n16.payload = 16; n16.left = n14; n16.right = n18;
Node n12 = new Node(); n12.payload = 12; n12.left = n4; n12.right = n16;
System.out.println(merge(n20, n12));
}
private static Node merge(Node n1, Node n2) {
List<Node> todo = new LinkedList<Node>();
todo.add(n1);
while(!todo.isEmpty()) {
Node n = todo.remove(0);
if (n.left != null) {
todo.add(0, n.left);
n.left = null;
}
if (n.right != null) {
todo.add(1, n.right);
n.right = null;
}
inject(n, n2);
}
return n2;
}
private static void inject(Node n, Node n2) {
if (n.payload >= n2.payload) {
if (n2.right == null) {
n2.right = n;
return;
}
// otherwise
if (n.payload >= n2.right.payload) {
inject(n, n2.right);
return;
}
// otherwise
if (n2.right.left == null) {
n2.right.left = n;
return;
}
// otherwise
if (n.payload <= n2.right.left.payload) {
inject(n, n2.right.left);
return;
}
// otherwise
Node temp = n2.right.left;
n2.right.left = n;
n.left = temp;
return;
}
// otherwise
if (n2.left == null) {
n2.left = n;
return;
}
// otherwise
if (n.payload < n2.left.payload) {
inject(n, n2.left);
return;
}
// otherwise
if (n2.left.right == null) {
n2.left.right = n;
return;
}
// otherwise
if (n.payload >= n2.left.right.payload) {
inject(n, n2.left.right);
return;
}
// otherwise
Node temp = n2.left.right;
n2.left.right = n;
n.right = temp;
return;
}
}
public class ReducedWordInDictionary {
private static TreeSet<String> dictionary = new TreeSet<String>(LengthComparator.INSTANCE);
static {
dictionary.add("a");
dictionary.add("an");
dictionary.add("be");
dictionary.add("cat");
dictionary.add("car");
dictionary.add("dear");
dictionary.add("down");
dictionary.add("fire");
dictionary.add("hire");
dictionary.add("product");
dictionary.add("row");
dictionary.add("report");
}
public static void main(String[] args) {
System.out.println(find(null, dictionary));
System.out.println(find("", dictionary));
System.out.println(find("a", dictionary));
System.out.println(find("b", dictionary));
System.out.println(find("catalysis", dictionary));
System.out.println(find("preowned", dictionary));
System.out.println(find("preregistered-owned", dictionary));
System.out.println(find("product", dictionary));
System.out.println(find("fibre", dictionary));
}
private static String find(String word, TreeSet<String> dictionary) {
if (word == null || word.isEmpty()) return null;
// otherwise
int length = word.length();
// otherwise
Iterator<String> dit = dictionary.descendingIterator();
boolean isCandidate = false;
while(dit.hasNext()) {
String s = dit.next();
if (!isCandidate && s.length() > length) continue;
// otherwise
isCandidate = true;
// otherwise
if (s == null || s.isEmpty()) break;
// otherwise
if (match(s, word)) return s;
}
return null;
}
private static boolean match(String word, String originalWord) {
int currentIndex = 0;
for (int i = 0; i < word.length(); i++) {
char c1 = word.charAt(i);
int j = currentIndex;
for (; j < originalWord.length(); j++) {
char c2 = originalWord.charAt(j);
if (c1 == c2) {
currentIndex = j+1;
break;
}
// otherwise, continue
}
if (j == originalWord.length()) return false;
}
return true;
}
private static class LengthComparator implements Comparator<String> {
private static Comparator<String> INSTANCE = new LengthComparator();
@Override
public int compare(String s1, String s2) {
if (s1 == null) return s2 == null? 0: -1;
if (s2 == null) return 1;
int l1 = s1.length();
int l2 = s2.length();
if (l1 == l2) return s1.compareTo(s2);
return l1 > l2? 1: -1;
}
}
}
public class LongestPathInBinaryTree {
private static class Node {
Node left;
Node right;
int payload;
public String toString() { return ""+payload; }
}
public static void main(String[] args) {
Node n7 = new Node(); n7.payload = 7;
Node n6 = new Node(); n6.payload = 6;
Node n4 = new Node(); n4.payload = 4;
Node n5 = new Node(); n5.payload = 5; n5.left = n6; n5.right = n7;
Node n2 = new Node(); n2.payload = 2; n2.left = n4; n2.right = n5;
Node n3 = new Node(); n3.payload = 3;
Node n1 = new Node(); n1.payload = 1; n1.left = n2; n1.right = n3;
System.out.println(getLongestPath(n1, 0));
}
private static LinkedList<Node> getLongestPath(Node root, int level) {
LinkedList<Node> result = new LinkedList<Node>();
LinkedList<Node> leftPath = null;
if (root.left != null) leftPath = getLongestPath(root.left, 1);
LinkedList<Node> rightPath = null;
if (root.right != null) rightPath = getLongestPath(root.right, 1);
if (level > 0) {
List<Node> childPath = compare(leftPath, rightPath);
if (childPath != null) result.addAll(childPath);
result.add(root);
}
else {
if (leftPath != null) result.addAll(leftPath);
result.add(root);
if (rightPath != null) {
for (Iterator<Node> it = rightPath.descendingIterator(); it.hasNext();) {
result.add(it.next());
}
}
}
return result;
}
private static List<Node> compare(List<Node> l , List<Node> r) {
if (l == null && r == null) return null;
if (l == null) return r;
if (r == null) return l;
return r.size() >= l.size()? r: l;
}
}
public class LongestChunkedPalindrome {
public static void main(String[] args) {
System.out.println(LCP(null));
System.out.println(LCP(""));
System.out.println(LCP("V"));
System.out.println(LCP("VOLVO"));
System.out.println(LCP("VOLVOV"));
System.out.println(LCP("ghiabcdefhelloadamhelloabcdefghi"));
System.out.println(LCP("ghiabcdefhelloadamhelloabcdefghik"));
}
private static List<String> LCP(String s) {
List<String> result = new LinkedList<String>();
doLCP(s, result, false);
return result;
}
private static boolean doLCP(String s, List<String> result, boolean nested) {
if (s == null || s.length() == 0) return true;
// otherwise
for (int i = 1; i <= s.length()/2; i++) {
String candidate = s.substring(0, i);
if (candidate.equals(s.substring(s.length()-i, s.length()))) {
if (doLCP(s.substring(i, s.length()-i), result, true)) {
result.add(0, candidate);
result.add(candidate);
return true;
}
}
}
// otherwise
if (!nested && s.length() > 1) return false;
// otherwise
result.add(result.size()/2, s);
return true;
}
}
public class DeleteTreeNode {
private static class TreeNode {
int val;
TreeNode[] child;
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("(").append(val);
if (child != null) {
for (TreeNode childd: child) {
if (childd == null) continue;
// otherwise
sb.append(childd.toString());
}
}
sb.append(")");
return sb.toString();
}
}
public static void main(String[] args) {
TreeNode t10 = new TreeNode(); t10.val = 10;
TreeNode t9 = new TreeNode(); t9.val = 9; t9.child = new TreeNode[] { t10 };
TreeNode t8 = new TreeNode(); t8.val = 8;
TreeNode t7 = new TreeNode(); t7.val = 7;
TreeNode t6 = new TreeNode(); t6.val = 6; t6.child = new TreeNode[] { t9 };
TreeNode t5 = new TreeNode(); t5.val = 5; t5.child = new TreeNode[] { t7, t8 };
TreeNode t4 = new TreeNode(); t4.val = 4; t4.child = new TreeNode[] { t5, t6 };
TreeNode t3 = new TreeNode(); t3.val = 3;
TreeNode t2 = new TreeNode(); t2.val = 2;
TreeNode t1 = new TreeNode(); t1.val = 1; t1.child = new TreeNode[] { t2, t3, t4 };
HashSet<TreeNode> set = new HashSet<TreeNode>();
set.add(t4); set.add(t5); set.add(t9);
System.out.println(delete(t1, set));
}
private static List<TreeNode> delete(TreeNode root, HashSet<TreeNode> set) {
List<TreeNode> result = new LinkedList<TreeNode>();
if (set == null || set.isEmpty()) {
result.add(root);
return result;
}
// otherwise
doDelete(root, set, result, true);
return result;
}
private static TreeNode doDelete(TreeNode root, HashSet<TreeNode> set, List<TreeNode> result, boolean isOrphan) {
boolean childrenAreOrphans = false;
childrenAreOrphans = set.remove(root);
if (isOrphan && !childrenAreOrphans) result.add(root);
if (!childrenAreOrphans && set.isEmpty()) return root;
// otherwise
if (root.child != null) {
for (int i = 0; i < root.child.length; i++) {
root.child[i] = doDelete(root.child[i], set, result, childrenAreOrphans);
}
}
return childrenAreOrphans? null: root;
}
}
public class StraightLineWithMaxPoints {
private static interface Graph {
boolean isPointPresent(long x, long y);
long getLength();
long getWidth();
}
private static class ArrayGraph implements Graph {
private final int[][] a;
private final boolean mustTranspose;
/**
* @param a Assumed to be a fully-populated 2-D (0,1) array.
*/
private ArrayGraph(int[][] a) {
this.a = a;
mustTranspose = a.length > a[0].length;
}
@Override
public boolean isPointPresent(long x, long y) {
return mustTranspose?a[(int)y][(int)x]>0:a[(int)x][(int)y]>0;
}
@Override
public long getLength() {
return mustTranspose?a.length:a[0].length;
}
@Override
public long getWidth() {
return mustTranspose?a[0].length:a.length;
}
}
private static class Pair<T> {
T x;
T y;
Pair() {}
Pair(T x, T y) {
this.x = x;
this.y = y;
}
public String toString() {
return "(" + x + "," + y + ")";
}
}
private static class Result {
Pair<Pair<Long>> line;
long pointCount;
public String toString() {
return line + "[" + pointCount + "]";
}
}
public static void main(String[] args) {
ArrayGraph ag1 = new ArrayGraph(new int[][] { new int[] {0, 1, 0}, new int[] {0, 1, 0} });
ArrayGraph ag2 = new ArrayGraph(new int[][] { new int[] {0, 1, 0}, new int[] {0, 0, 1} });
ArrayGraph ag3 = new ArrayGraph(new int[][] { new int[] {0, 1, 0}, new int[] {1, 0, 0} });
ArrayGraph ag4 = new ArrayGraph(new int[][] { new int[] {0, 1, 0}, new int[] {1, 0, 0}, new int[] {0, 0, 0} });
ArrayGraph ag5 = new ArrayGraph(new int[][] { new int[] {0, 0, 1, 0}, new int[] {0, 0, 0, 1}, new int[] {0, 0, 0, 0} });
ArrayGraph ag6 = new ArrayGraph(new int[][] { new int[] {0, 1, 0, 0}, new int[] {0, 0, 1, 0}, new int[] {0, 0, 0, 1} });
ArrayGraph ag01 = new ArrayGraph(new int[][] { new int[] {1, 0, 0}, new int[] {0, 0, 0} });
ArrayGraph ag02 = new ArrayGraph(new int[][] { new int[] {0, 0, 0}, new int[] {1, 0, 0} });
ArrayGraph ag03 = new ArrayGraph(new int[][] { new int[] {0, 0, 0}, new int[] {0, 0, 1} });
ArrayGraph ag04 = new ArrayGraph(new int[][] { new int[] {0, 0, 1}, new int[] {0, 0, 0} });
System.out.println(findLine(ag1));
System.out.println(findLine(ag2));
System.out.println(findLine(ag3));
System.out.println(findLine(ag4));
System.out.println(findLine(ag5));
System.out.println(findLine(ag6));
System.out.println();
System.out.println(findLine(ag01));
System.out.println(findLine(ag02));
System.out.println(findLine(ag03));
System.out.println(findLine(ag04));
}
private static Result findLine(Graph g) {
Result result = new Result();
result.line = new Pair<Pair<Long>>();
final long width = g.getWidth();
final long length = g.getLength();
// horizontal scans --
straightScan(width, length, g, false, result);
if (result.pointCount >= width) return result;
// otherwise
straightScan(length, width, g, true, result);
if (result.pointCount == width) return result;
diagonalScan(width, length, g, true, result);
if (result.pointCount == width) return result;
// otherwise
diagonalScan(width, length, g, false, result);
return result;
}
private static void straightScan(long width, long length, Graph g, boolean transpose, Result result) {
for (long i = 0; i < width; i++) {
if (result.pointCount >= length) break;
// otherwise
long pointCount = 0L;
for (long j = 0; j < length; j++) if (transpose?g.isPointPresent(j, i):g.isPointPresent(i, j)) pointCount++;
if (pointCount > result.pointCount) {
result.line.x = transpose?new Pair<Long>(0L, i):new Pair<Long>(i, 0L);
result.line.y = transpose?new Pair<Long>(length-1, i):new Pair<Long>(i, length-1);
result.pointCount = pointCount;
}
}
}
private static void diagonalScan(long width, long length, Graph g, boolean pointDown, Result result) {
for (long i = 0; i <= length-width; i++) {
long pointCount = 0L;
if (result.pointCount >= width) break;
// otherwise
if (pointDown) {
for (long j = 0; j < width; j++) if (g.isPointPresent(j, i+j)) pointCount++;
}
else {
for (long j = width-1; j >= 0; j--) if (g.isPointPresent(j, i+(width-1-j))) pointCount++;
}
if (pointCount > result.pointCount) {
result.line.x = pointDown?new Pair<Long>(0L, i):new Pair<Long>(width-1, i);
result.line.y = pointDown?new Pair<Long>(width-1, i+width-1):new Pair<Long>(0L, i+width-1);
result.pointCount = pointCount;
}
}
if (pointDown) {
for (long k = 1; k < width; k++) {
long pointCount = 0L;
if (result.pointCount >= width-k) break;
// otherwise
for (long i = 0, j = k; i < width - k; i++, j++) {
if (g.isPointPresent(j, i)) pointCount++;
}
if (pointCount > result.pointCount) {
result.line.x = new Pair<Long>(k, 0L);
result.line.y = new Pair<Long>(width-1, width-k-1);
result.pointCount = pointCount;
}
}
}
else {
for (long k = width-2; k >= 0; k--) {
long pointCount = 0L;
if (result.pointCount >= k+1) break;
// otherwise
for (long i = 0, j = k; i <= k; i++, j--) {
if (g.isPointPresent(j, i)) pointCount++;
}
if (pointCount > result.pointCount) {
result.line.x = new Pair<Long>(k, 0L);
result.line.y = new Pair<Long>(0L, k);
result.pointCount = pointCount;
}
}
}
for (long k = length-width+1; k < length; k++) {
long pointCount = 0L;
if (result.pointCount >= length-k) break;
// otherwise
if (pointDown) {
for (long i = k, j = 0; i < length; i++, j++) {
if (g.isPointPresent(j, i)) pointCount++;
}
}
else {
for (long i = k, j = width-1; i < length; i++, j--) {
if (g.isPointPresent(j, i)) pointCount++;
}
}
if (pointCount > result.pointCount) {
result.line.x = pointDown?new Pair<Long>(0L, k):new Pair<Long>(width-1, k);
result.line.y = pointDown?new Pair<Long>(length-1-k, length-1):new Pair<Long>(width-1-(length-1-k), length-1);
result.pointCount = pointCount;
}
}
}
}
public class PathMatchNumber {
public static void main(String[] args) {
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node3.left = node4; node3.right = node5;
Node node6 = new Node(6);
Node node7 = new Node(7);
node4.left = node6; node4.right = node7;
Node node8 = new Node(8);
Node node9 = new Node(9);
node5.left = node8; node5.right = node9;
System.out.println(match(node3, 359));
System.out.println(match(node3, 38));
System.out.println(match(node3, 47));
System.out.println(match(node3, 6));
}
private static Node match(Node node, Integer number) {
return matchNode(node, String.valueOf(number));
}
private static Node matchNode(Node node, String number) {
boolean matched = matchPath(node, number);
if (matched) return node;
Node matchedNode = null;
if (node.left != null) matchedNode = matchNode(node.left, number);
if (matchedNode != null) return matchedNode;
if (node.right != null) matchedNode = matchNode(node.right, number);
if (matchedNode != null) return matchedNode;
return null;
}
private static boolean matchPath(Node node, String number) {
final String value = String.valueOf(node.value);
if (!number.startsWith(value)) return false;
if (number.length() == value.length()) return true;
// otherwise
boolean matched = false;
if (node.left != null) matched = matchPath(node.left, number.substring(value.length()));
if (matched) return true;
// otherwise
if (node.right != null) matched = matchPath(node.right, number.substring(value.length()));
if (matched) return true;
// otherwise
return false;
}
private static class Node {
private Node left;
private Node right;
private final Integer value;
private Node(Integer value) {
this.value = value;
}
public String toString() {
return String.valueOf(value);
}
}
}
public class ShuffleList {
public static void main(String[] args) {
LinkedList<Integer> l = new LinkedList<>();
l.add(1); l.add(2); l.add(3); l.add(4); l.add(5);
System.out.println(shuffle(l));
}
private static <T> List<T> shuffle(LinkedList<T> l) {
List<T> result = new LinkedList<T>();
int half = l.size()/2;
Iterator<T> it = l.iterator();
Iterator<T> dit = l.descendingIterator();
for (int i = 0; i < half; i++) {
result.add(it.next());
result.add(dit.next());
}
if (result.size() < l.size()) result.add(it.next());
return result;
}
}
package iview;
public class MaxArea {
private static int[][] a = new int[][] { {0, 0, 1},
{0, 0, 1} };
private static int[][] b = new int[][] { {0, 1, 1},
{0, 1, 1} };
private static int[][] c = new int[][] { {0, 1, 1, 1},
{0, 1, 1, 0},
{0, 1, 1, 1}};
private static int[][] d = new int[][] { {0, 1, 1, 1, 0},
{0, 1, 1, 0, 1},
{0, 1, 1, 1, 1},
{0, 1, 1, 1, 1},
{0, 1, 1, 1, 1}};
private static int[][] e = new int[][] { {0, 0, 1},
{0, 1, 0} };
private static int[][] f = new int[][] { {1, 1, 1},
{0, 1, 0} };
public static void main(String[] args) {
System.out.println(findMaxAreaCoords(a));
System.out.println(findMaxAreaCoords(b));
System.out.println(findMaxAreaCoords(c));
System.out.println(findMaxAreaCoords(d));
System.out.println(findMaxAreaCoords(e));
System.out.println(findMaxAreaCoords(f));
}
private static Pair<Pair<Integer, Integer>, Pair<Integer, Integer>> findMaxAreaCoords(int[][] a) {
long maxArea = 0;
Pair<Integer, Integer> upperLeft = null;
Pair<Integer, Integer> lowerRight = null;
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[i].length; j++) {
if (a[i][j] != 1) continue;
// otherwise
int L = 1; // i
for (int k = i+1; k < a.length; k++) {
if (a[k][j] != 1) break;
// otherwise
L++;
}
long localMaxArea = L;
Pair<Integer, Integer> localLowerRight = new Pair(i+L-1, j);
int k;
int l = i;
for (k = j+1; k < a[i].length; k++) {
if (a[i][k] != 1) break;
// otherwise
for (l = i; l < i+L; l++) {
if (a[l][k] != 1) break;
}
long area = (l-i) * (k-j+1);
if (area > localMaxArea) {
localMaxArea = area;
localLowerRight = new Pair(l-1, k);
}
}
// check candidate
if (localMaxArea > maxArea) {
maxArea = localMaxArea;
upperLeft = new Pair<Integer, Integer>(i, j);
lowerRight = localLowerRight;
}
}
}
return new Pair<>(upperLeft, lowerRight);
}
private static class Pair<T1, T2> {
T1 left;
T2 right;
Pair(T1 left, T2 right) {
this.left = left;
this.right = right;
}
public String toString() {
return "<" + left + "," + right + ">";
}
}
}
public class CommonAncestor {
static class Node {
Node(Node parent, Node right, Node left, String label) {
this.parent = parent;
this.right = right;
this.left = left;
this.label = label;
}
String label;
Node left;
Node right;
Node parent;
boolean isRoot() { return parent == null; }
public String toString() {
return label;
}
}
private static Node commonAncestor(Node n1, Node n2) {
Set<Node> n1Ancestors = collectAncestors(n1);
if (n1Ancestors.isEmpty()) return null;
// otherwise
Node n2A = n2.parent;
while(n2A != null) {
if (n1Ancestors.contains(n2A)) return n2A;
// otherwise
n2A = n2A.parent;
}
return null;
}
private static Set<Node> collectAncestors(Node n) {
Set<Node> result = new HashSet<Node>();
Node p = n.parent;
while(p != null) {
result.add(p);
p = p.parent;
}
return result;
}
public static void main(String[] args) {
Node G = new Node(null, null, null, "G");
Node F = new Node(null, null, null, "F");
Node E = new Node(null, null, null, "E");
Node H = new Node(null, null, null, "H");
Node D = new Node(null, G, F, "D"); G.parent = D; F.parent = D;
Node B = new Node(null, D, E, "B"); D.parent = B; E.parent = B;
Node C = new Node(null, null, H, "C"); H.parent = C;
Node A = new Node(null, B, C, "A"); B.parent = A; C.parent = A;
System.out.println(commonAncestor(D, F));
System.out.println(commonAncestor(C, G));
System.out.println(commonAncestor(E, B));
}
}
- PR December 21, 2016