Dhruva.Bharadwaj
BAN USERpackage google;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
public class FindPath {
public static class Point {
int x;
int y;
public Point(int x, int y) {
super();
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Point)) {
return false;
}
Point point = (Point) o;
return x == point.x && y == point.y;
}
@Override
public int hashCode() {
return Objects.hash(x, y);
}
}
public static void main(String args[]) {
char[][] board2 = { { '0', '2', '1', '1', '1' }, { '0', '1', 'a', '0', 'A' }, { '0', '1', '0', '0', '3' },
{ '0', '1', '0', '0', '1' }, { '0', '1', '1', '1', '1' } };
List<int[]> solution = solve(board2);
for (int[] pos : solution) {
System.out.println(Arrays.toString(pos));
}
}
public static List<int[]> solve(char[][] board) {
Point start = null;
Point goal = null;
HashSet<Point> visited = new HashSet<Point>();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == '2') {
start = new Point(i, j);
} else if (board[i][j] == '3') {
goal = new Point(i, j);
}
}
}
return solve(start, board, visited, goal, new LinkedList<int[]>(), new HashSet<Character>());
}
private static List<int[]> solve(Point cur, char[][] board, HashSet<Point> visited, Point goal,
LinkedList<int[]> solution, HashSet<Character> keys) {
if (cur.equals(goal)) {
return (LinkedList<int[]>) solution.clone();
}
if (Character.isLowerCase(board[cur.x][cur.y])) {
keys.add(board[cur.x][cur.y]);
}
visited.add(new Point(cur.x,cur.y));
int i = cur.x;
int j = cur.y;
solution.add(new int[] { i, j });
List<int[]> up = null;
List<int[]> down = null;
List<int[]> left = null;
List<int[]> right = null;
if (i - 1 >= 0 && board[i - 1][j] != '0' && !visited.contains(new Point(i - 1, j))
&& isOpenableIfDoor(board, i - 1, j, keys)) {
cur.x -= 1;
up = solve(cur, board, visited, goal, solution, keys);
cur.x += 1;
}
if (i + 1 < board.length && board[i + 1][j] != '0' && !visited.contains(new Point(i + 1, j))
&& isOpenableIfDoor(board, i + 1, j, keys)) {
cur.x += 1;
down = solve(cur, board, visited, goal, solution, keys);
cur.x -= 1;
}
if (j - 1 >= 0 && board[i][j - 1] != '0' && !visited.contains(new Point(i, j - 1))
&& isOpenableIfDoor(board, i, j - 1, keys)) {
cur.y -= 1;
left = solve(cur, board, visited, goal, solution, keys);
cur.y += 1;
}
if (j + 1 < board[0].length && board[i][j + 1] != '0' && !visited.contains(new Point(i, j + 1))
&& isOpenableIfDoor(board, i, j + 1, keys)) {
cur.y += 1;
right = solve(cur, board, visited, goal, solution, keys);
cur.y -= 1;
}
List<List<int[]>> res = new LinkedList<List<int[]>>();
res.add(up);
res.add(down);
res.add(left);
res.add(right);
Collections.sort(res, new Comparator<List<int[]>>() {
@Override
public int compare(List<int[]> arg0, List<int[]> arg1) {
if (arg0 != null && arg1 != null) {
return Integer.compare(arg0.size(), arg1.size());
} else if (arg0 != null) {
return -1;
} else if (arg1 != null) {
return 1;
} else {
return 0;
}
}
});
if (Character.isLowerCase(board[cur.x][cur.y])) {
keys.remove(board[cur.x][cur.y]);
}
solution.removeLast();
visited.remove(new Point(i, j));
return res.get(0);
}
private static boolean isOpenableIfDoor(char[][] board, int i, int j, HashSet<Character> keys) {
if (Character.isUpperCase(board[i][j])) {
if (keys.contains(Character.toLowerCase(board[i][j]))) {
return true;
}
return false;
}
return true;
}
}
package google;
import concepts.TreeNode;
public class InsertIntoCompleteBinaryTree {
public enum Result {
foundPos, inserted, notFound
};
public static void main(String args[]) {
TreeNode<Integer> root = new TreeNode<Integer>(1);
root.left = new TreeNode<Integer>(2);
root.right = new TreeNode<Integer>(3);
root.left.left = new TreeNode<Integer>(4);
root.left.right = new TreeNode<Integer>(5);
int maxHeight = findHeight(root, 0);
insert(6, 0, maxHeight, root);
System.out.println(root.right.left);
}
private static Result insert(int elem, int height, int maxHeight, TreeNode<Integer> cur) {
if (cur == null) {
if (height < maxHeight) {
return Result.foundPos;
} else {
return Result.notFound;
}
}
Result res;
if ((res = insert(elem, height + 1, maxHeight, cur.left)) == Result.foundPos) {
cur.left = new TreeNode<Integer>(6);
return Result.inserted;
} else if (res == Result.inserted) {
return res;
} else if ((res = insert(elem, height + 1, maxHeight, cur.right)) == Result.foundPos) {
cur.right = new TreeNode<Integer>(6);
return Result.inserted;
} else {
return res;
}
}
private static int findHeight(TreeNode<Integer> cur, int height) {
if (cur == null) {
return height;
} else {
return findHeight(cur.left, height + 1);
}
}
}
package google;
public class MetaString {
public static void main(String args[]) {
String s1 = "Converse";
String s2 = "Conserve";
System.out.println(isMetaString(s1, s2));
}
private static boolean isMetaString(String string1, String string2) {
String s1 = string1.toLowerCase();
String s2 = string2.toLowerCase();
int diff = 0;
int diffIndex = 0;
if (s1.length() != s2.length() || s1.length() == 0) {
return false;
}
for (int i = 0; i < s1.length(); i++) {
if (s1.charAt(i) == s2.charAt(i)) {
continue;
}
diff++;
if (diff > 2) {
break;
} else if (diff == 1) {
diffIndex = i;
} else {
if (s2.charAt(i) == s1.charAt(diffIndex)) {
continue;
} else {
diff++;
break;
}
}
}
if (diff > 2) {
return false;
}
return true;
}
}
Perform an inorder traversal and then look at the middle element.
- Dhruva.Bharadwaj April 18, 2017package google;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
public class LargestNumberDivisibleBy3 {
public static void main(String args[]) {
int[] input = { 3, 1, 1 };
System.out.println(getHigestNumDivisibleByThree(input));
}
private static int getHigestNumDivisibleByThree(int[] arr) {
int sum = 0;
StringBuilder str = new StringBuilder();
Arrays.sort(arr);
for (int i = arr.length; i > 0; i--) {
sum = sum + arr[i - 1];
str.append(arr[i - 1]);
}
int remainder = sum % 3;
if (remainder == 0)
return Integer.parseInt(str.toString());
str = new StringBuilder();
ArrayList<Integer> removeNum = new ArrayList<Integer>();
int remNumCount = 1;
while (remNumCount <= 2) {
remainder = sum % 3;
while (remainder <= 9 * remNumCount) {
removeNum = contains(arr, remainder, remNumCount);
if (removeNum != null) {
break;
}
remainder = remainder + 3;
}
remNumCount++;
}
if (removeNum == null)
return 0;
for (int i = 0; i < arr.length; i++) {
if (removeNum.contains(arr[i])) {
continue;
}
str.append(arr[i]);
}
return Integer.parseInt(str.toString());
}
private static ArrayList<Integer> contains(int[] arr, int num, int mode) {
if (mode == 1) {
for (int i : arr)
if (i == num) {
ArrayList<Integer> result = new ArrayList<Integer>();
result.add(i);
return result;
}
return null;
} else {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < arr.length; i++) {
if (map.containsKey(num - arr[i])) {
ArrayList<Integer> result = new ArrayList<Integer>();
result.add(arr[i]);
result.add(map.get(num - arr[i]));
return result;
}
map.put(arr[i], i);
}
return null;
}
}
}
package google;
import java.util.NavigableSet;
import java.util.Scanner;
import java.util.TreeSet;
public class LexicographicalNextWord {
public static void main(String args[]) {
NavigableSet<String> words = new TreeSet<String>();
Scanner input = new Scanner(System.in);
System.out.println("Ënter number of words: ");
int numberOfWords = input.nextInt();
for (int i = 0; i < numberOfWords; i++) {
words.add(input.next());
}
System.out.println("Ënter input word: ");
String word = input.next();
String out = null;
if (!words.contains(word)) {
out = words.ceiling(word);
} else {
out = words.higher(word);
}
System.out.println(out == null ? "Error" : out);
}
}
package google;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
public class SplitUsersIntoGroups {
public static void main(String args[]) {
int[][] friendRelations = { { 1, 2 }, { 2, 3 }, { 3, 4 } };
HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
for (int i = 0; i < friendRelations.length; i++) {
checkAndPut(friendRelations[i][0], friendRelations[i][1], map);
checkAndPut(friendRelations[i][1], friendRelations[i][0], map);
}
HashSet<Integer> visited = new HashSet<Integer>();
boolean result = true;
for (int cur : map.keySet()) {
if (!visited.contains(cur)) {
HashSet<Integer> group1 = new HashSet<Integer>();
HashSet<Integer> group2 = new HashSet<Integer>();
boolean curGrp1 = true;
result = result && recurseFindGroupable(group1, group2, curGrp1, cur, map);
visited.addAll(group1);
visited.addAll(group2);
}
}
System.out.println(result);
}
private static boolean recurseFindGroupable(HashSet<Integer> group1, HashSet<Integer> group2, boolean curGrp1,
int cur, HashMap<Integer, ArrayList<Integer>> map) {
HashSet<Integer> curSet = curGrp1 ? group1 : group2;
HashSet<Integer> otherSet = curGrp1 ? group2 : group1;
boolean result = true;
if (curSet.contains(cur)) {
return true;
} else if (otherSet.contains(cur)) {
return false;
} else {
curSet.add(cur);
}
for (int user : map.get(cur)) {
result = result && recurseFindGroupable(group1, group2, !curGrp1, user, map);
}
return result;
}
public static void checkAndPut(int first, int second, HashMap<Integer, ArrayList<Integer>> map) {
if (map.containsKey(first)) {
map.get(first).add(second);
} else {
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(second);
map.put(first, list);
}
}
}
package google;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
public class IsBipartite {
public static class UndirectedGraphNode {
int label;
List<UndirectedGraphNode> neighbors;
UndirectedGraphNode(int x) {
label = x;
neighbors = new ArrayList<UndirectedGraphNode>();
}
}
public static class UndirectedGraph {
protected HashMap<Integer, UndirectedGraphNode> nodes;
public UndirectedGraph(UndirectedGraphNode... nodes) {
this.nodes = new HashMap<Integer, UndirectedGraphNode>();
for (UndirectedGraphNode node : nodes) {
this.nodes.put(node.label,node);
}
}
public UndirectedGraph() {
this.nodes = new HashMap<Integer, UndirectedGraphNode>();
}
public boolean contains(int NodeID){
return nodes.containsKey(NodeID);
}
}
public static void main(String args[]) {
UndirectedGraphNode n1 = new UndirectedGraphNode(1);
UndirectedGraphNode n2 = new UndirectedGraphNode(2);
UndirectedGraphNode n3 = new UndirectedGraphNode(3);
UndirectedGraphNode n4 = new UndirectedGraphNode(4);
UndirectedGraphNode n5 = new UndirectedGraphNode(5);
UndirectedGraphNode n6 = new UndirectedGraphNode(6);
n1.neighbors.add(n2);
n1.neighbors.add(n3);
n1.neighbors.add(n4);
n2.neighbors.add(n1);
n3.neighbors.add(n1);
n4.neighbors.add(n1);
n2.neighbors.add(n5);
n3.neighbors.add(n5);
n5.neighbors.add(n2);
n5.neighbors.add(n3);
n3.neighbors.add(n6);
n6.neighbors.add(n3);
UndirectedGraph undirectedGraph = new UndirectedGraph(n1, n2, n3, n4, n5, n6);
System.out.println(isBipartite(undirectedGraph));
}
public static boolean isBipartite(UndirectedGraph undirectedGraph) {
boolean result = true;
HashSet<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>();
for (int node : undirectedGraph.nodes.keySet()) {
if (!visited.contains(undirectedGraph.nodes.get(node))) {
HashSet<UndirectedGraphNode> set1 = new HashSet<UndirectedGraphNode>();
HashSet<UndirectedGraphNode> set2 = new HashSet<UndirectedGraphNode>();
HashSet<UndirectedGraphNode> curSet = set1;
result = result && recurseFindBipartite(curSet, undirectedGraph.nodes.get(node), set1, set2);
visited.addAll(set1);
visited.addAll(set2);
}
}
return result;
}
private static boolean recurseFindBipartite(HashSet<UndirectedGraphNode> curSet, UndirectedGraphNode curNode,
HashSet<UndirectedGraphNode> set1, HashSet<UndirectedGraphNode> set2) {
HashSet<UndirectedGraphNode> otherSet = (curSet == set1 ? set2 : set1);
if (otherSet.contains(curNode)) {
return false;
}
if (curSet.contains(curNode)) {
return true;
} else {
curSet.add(curNode);
}
boolean result = true;
for (UndirectedGraphNode neighbor : curNode.neighbors) {
result = result && recurseFindBipartite(otherSet, neighbor, set1, set2);
}
return result;
}
}
package google;
import google.ExpressionTreeEvaluation.ExpressionTreeNode.Operator;
public class ExpressionTreeEvaluation {
public static class ExpressionTreeNode {
static enum Operator {
Add, Subtract, Multiply, Divide;
public int performOperation(int operand1, int operand2) {
switch (this) {
case Add:
return operand1 + operand2;
case Subtract:
return operand1 - operand2;
case Multiply:
return operand1 * operand2;
default:
return operand1 / operand2;
}
}
}
public Boolean isLeaf;
public Operator valIfOperator;
public Integer valIfInteger;
ExpressionTreeNode left;
ExpressionTreeNode right;
public ExpressionTreeNode(boolean isLeaf, Operator valIfOperator, Integer valIfInteger) {
this.isLeaf = isLeaf;
if (isLeaf == true && valIfOperator == null && valIfInteger != null) {
this.valIfInteger = valIfInteger;
} else if (isLeaf == false && valIfOperator != null && valIfInteger == null) {
this.valIfOperator = valIfOperator;
} else {
throw new IllegalArgumentException();
}
left = null;
right = null;
}
}
public static void main(String args[]) {
ExpressionTreeNode n1 = new ExpressionTreeNode(false, Operator.Add, null);
ExpressionTreeNode n2 = new ExpressionTreeNode(false, Operator.Divide, null);
ExpressionTreeNode n3 = new ExpressionTreeNode(false, Operator.Add, null);
ExpressionTreeNode n4 = new ExpressionTreeNode(true, null, 5);
ExpressionTreeNode n5 = new ExpressionTreeNode(true, null, 5);
ExpressionTreeNode n6 = new ExpressionTreeNode(true, null, 6);
ExpressionTreeNode n7 = new ExpressionTreeNode(true, null, -1);
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
n3.right = n7;
n3.left = n6;
ExpressionTreeNode en1 = new ExpressionTreeNode(false, Operator.Add, null);
ExpressionTreeNode en2 = new ExpressionTreeNode(true, null, 3);
ExpressionTreeNode en3 = new ExpressionTreeNode(true, null, 3);
en1.left = en2;
en1.right = en3;
System.out.println(evaluateExpression(n1) == evaluateExpression(en1));
}
private static int evaluateExpression(ExpressionTreeNode node) {
if (node.isLeaf) {
return node.valIfInteger;
} else {
int left = evaluateExpression(node.left);
int right = evaluateExpression(node.right);
return node.valIfOperator.performOperation(left, right);
}
}
}
- Dhruva.Bharadwaj May 21, 2017