ugurdonmez87
BAN USERIt should be O(nlogn) solution if I calculate correctly.
isEqual method runs in O(n) because O(n) = 2O(n/2) + c
getMaxStubTree runs in O(nlogn) because O(n) = 2O(n/2) + O(n)
public class Solution {
public static void main(String [] args) {
Node node6 = new Node(6);
Node node5 = new Node(5);
Node node7 = new Node(7);
Node node4a = new Node(4);
Node node4b = new Node(4);
Node node3a = new Node(3);
Node node3b = new Node(3);
Node node3c = new Node(3);
Node node3d = new Node(3);
Node node1a = new Node(1);
Node node2a = new Node(2);
Node node1b = new Node(1);
Node node2b = new Node(2);
node6.left = node5;
node6.right = node7;
node5.left = node4a;
node5.right = node4b;
node4a.left = node3a;
node4a.right = node3b;
node4b.left = node3c;
node4b.right = node3d;
node3a.left = node1a;
node3a.right = node2a;
node3b.left = node1b;
node3b.right = node2b;
System.out.println(isEqual(node3a, node3b));
System.out.println(isEqual(node3c, node3d));
System.out.println(isEqual(node5, node7));
getMaxSubtree(node6).ifPresent(System.out::println);
}
public static Optional<Result> getMaxSubtree(Node node) {
if (node == null) {
return Optional.empty();
}
int isEqual = isEqual(node.left, node.right);
if (isEqual >= 0) {
return Optional.of(new Result(node, isEqual+1));
}
Optional<Result> leftOptional = getMaxSubtree(node.left);
Optional<Result> rightOptional = getMaxSubtree(node.right);
if (leftOptional.isPresent() && rightOptional.isPresent()) {
return leftOptional.get().height > rightOptional.get().height ?
leftOptional : rightOptional;
} else if (leftOptional.isPresent() && !rightOptional.isPresent()) {
return leftOptional;
} else if (!leftOptional.isPresent() && rightOptional.isPresent()) {
return rightOptional;
} else {
return Optional.empty();
}
}
/**
* if node1 == node2 return the height of the tree
* @param node1
* @param node2
* @return
*/
public static int isEqual(Node node1, Node node2) {
if (node1 == null && node2 == null) {
return 0;
}
if (node1 == null && node2 != null) {
return -1;
}
if (node2 == null && node1 != null) {
return -1;
}
if (node1.value != node2.value) {
return -1;
}
int left = isEqual(node1.left, node2.left);
int right = isEqual(node1.right, node2.right);
if (left >= 0 && right >= 0) {
return Integer.max(left, right) + 1;
} else {
return -1;
}
}
}
class Result {
Node node;
int height;
public Result(Node node, int height) {
this.node = node;
this.height = height;
}
@Override
public String toString() {
return "Result{" +
"node=" + node.value +
", height=" + height +
'}';
}
}
class Node {
final int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
}
}
public class Solution {
public static void main(String [] args) {
printK(4);
System.out.println();
printK(5);
}
public static void printK(int k) {
for (int i = 0; i <= k; i++) {
printPrefix("", i, k);
}
}
public static void printPrefix(String prefix, int one, int length) {
if (one == 0) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("0");
}
System.out.println();
} else if (one == length) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("1");
}
System.out.println();
} else if (length > one) {
String newPrefix = prefix + "0";
printPrefix(newPrefix, one, length-1);
newPrefix = prefix + "1";
printPrefix(newPrefix, one-1, length-1);
}
}
}
O(n^2) solution.
I assume that there is no negative value in the array.
public class Solution {
public static void main(String [] args) {
int [] array = {5,1,2,3,4,8,6,10};
System.out.println(Arrays.toString(getInterval(array, 5, 10)));
}
public static Object [] getInterval(int [] array, int low, int high) {
ImmutableList.Builder<Pair> listBuilder = ImmutableList.builder();
for (int i = 0; i < array.length; i++) {
int sum = array[i];
for (int j = i+1; j < array.length; j++) {
sum += array[j];
if (sum <= high && sum >= low) {
listBuilder.add(new Pair(i,j));
}
if (sum > high) {
break;
}
}
}
return listBuilder.build().toArray();
}
}
class Pair {
final int start;
final int end;
public Pair(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public String toString() {
return "Pair{" +
"start=" + start +
", end=" + end +
'}';
}
}
public class Solution {
public static void main(String [] args) {
String [] array1 = {"cdf", "too", "hgfdt" ,"paa"};
System.out.println(isMatch("abc", "too"));
System.out.println(Arrays.toString(getMatchedWords("abc", array1)));
System.out.println(Arrays.toString(getMatchedWords("acc", array1)));
}
public static String [] getMatchedWords(String pattern, String [] words) {
return Arrays.stream(words)
.filter(s -> isMatch(pattern, s))
.toArray(String[]::new);
}
public static boolean isMatch(String pattern, String word) {
if (pattern.length() != word.length()) {
return false;
}
Map<Character, Character> map = new HashMap<>();
Set<Character> occupied = new HashSet<>();
for (int i = 0; i < pattern.length(); i++) {
if (!map.containsKey(pattern.charAt(i))) {
if (!occupied.contains(word.charAt(i))) {
map.put(pattern.charAt(i), word.charAt(i));
occupied.add(word.charAt(i));
} else {
return false;
}
} else {
if (map.get(pattern.charAt(i)) != word.charAt(i)) {
return false;
}
}
}
return true;
}
}
public class Solution {
public static void main(String [] args) {
System.out.println(decode("p14akkkkkkkkpq"));
}
public static String decode(String string) {
StringBuilder buf = new StringBuilder();
int count = 1;
char prev = string.charAt(0);
for (int i = 1; i < string.length(); i++) {
if (string.charAt(i) == prev) {
count++;
} else {
if (count > 3) {
buf.append(count).append('x').append(prev);
} else {
for (int j = 0; j < count; j++) {
buf.append(prev);
}
}
count = 1;
prev = string.charAt(i);
}
}
if (count > 3) {
buf.append(count).append('x').append(prev);
} else {
for (int j = 0; j < count; j++) {
buf.append(prev);
}
}
return buf.toString();
}
}
public class Solution {
public static int getNumberOfPaths(int [][] adjMatrix, int source, int destination) {
PriorityQueue<Node> queue = new PriorityQueue<>();
queue.add(new Node(0, source, 1));
boolean [] founds = new boolean[adjMatrix.length];
int [] ways = new int[adjMatrix.length];
int [] minCosts = new int[adjMatrix.length];
for (int i = 0; i < adjMatrix.length; i++) {
minCosts[i] = Integer.MAX_VALUE;
}
while (!queue.isEmpty()) {
Node n = queue.poll();
if (founds[n.vertex] == false) {
ways[n.vertex] += n.way;
founds[n.vertex] = true;
break;
}
if (founds[n.vertex] && minCosts[n.vertex] == n.cost) {
ways[n.vertex] += n.way;
continue;
}
if (founds[n.vertex] && minCosts[n.vertex] > n.cost) {
ways[n.vertex] = n.way;
minCosts[n.vertex]= n.cost;
for (int i = 0; i < adjMatrix.length; i++) {
if (adjMatrix[n.vertex][i] != 0) {
if (founds[i] == false) {
queue.add(new Node(n.cost + adjMatrix[n.vertex][i], i, n.way));
}
}
}
continue;
}
for (int i = 0; i < adjMatrix.length; i++) {
if (adjMatrix[n.vertex][i] != 0) {
if (founds[i] == false) {
queue.add(new Node(n.cost + adjMatrix[n.vertex][i], i, n.way));
}
}
}
}
return ways[destination];
}
}
class Node implements Comparable<Node>{
final int cost;
final int vertex;
final int way;
public Node(int cost, int vertex, int way) {
this.cost = cost;
this.vertex = vertex;
this.way = way;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.cost, o.cost);
}
}
public class Solution {
public static void main(String [] args) {
printK(4);
System.out.println();
printK(5);
}
public static void printK(int k) {
for (int i = 0; i <= k; i++) {
printPrefix("", i, k);
}
}
public static void printPrefix(String prefix, int one, int length) {
if (one == 0) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("0");
}
System.out.println();
} else if (one == length) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("1");
}
System.out.println();
} else if (length > one) {
String newPrefix = prefix + "0";
printPrefix(newPrefix, one, length-1);
newPrefix = prefix + "1";
printPrefix(newPrefix, one-1, length-1);
}
}
}
- ugurdonmez87 July 31, 2016public class Solution {
public static void main(String [] args) {
printK(4);
System.out.println();
printK(5);
}
public static void printK(int k) {
for (int i = 0; i <= k; i++) {
printPrefix("", i, k);
}
}
public static void printPrefix(String prefix, int one, int length) {
if (one == 0) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("0");
}
System.out.println();
} else if (one == length) {
System.out.print(prefix);
for (int i = 0; i < length; i++) {
System.out.print("1");
}
System.out.println();
} else if (length > one) {
String newPrefix = prefix + "0";
printPrefix(newPrefix, one, length-1);
newPrefix = prefix + "1";
printPrefix(newPrefix, one-1, length-1);
}
}
}
public class Solution {
public static void main(String [] args) {
System.out.println(deleteConsecutiveDigit(1100));
}
public static int deleteConsecutiveDigit(int value) {
String str = String.valueOf(value);
for (int i = str.length()-2; i >= 0; i--) {
String first = str.substring(i, i+1);
String second = str.substring(i+1, i+2);
if (first.equals(second)) {
str = str.substring(0, i) + str.substring(i+1, str.length());
break;
}
}
return Integer.valueOf(str);
}
}
public class Solution {
public static void main(String [] args) {
int [] array = {20,4,3,2,1,7,8,0};
System.out.println(Arrays.toString(array));
sort(array, 2);
System.out.println(Arrays.toString(array));
int [] array1 = {5,40,20,4,3,2,1,7,8,0};
System.out.println(Arrays.toString(array1));
sortOptimized(array1, 3);
System.out.println(Arrays.toString(array1));
}
public static void sortOptimized(int [] array, int k) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k+1);
for (int i = 0; i <= k; i++) {
priorityQueue.add(array[i]);
}
int index = 0;
for (int i = k+1; i < array.length; i++) {
array[index++] = priorityQueue.poll();
priorityQueue.add(array[i]);
}
while (!priorityQueue.isEmpty()) {
array[index++] = priorityQueue.poll();
}
}
public static void sort(int [] array, int k) {
for (int i = 0; i < k; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j+1] < array[j]) {
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
}
public class Solution {
public static void main(String [] args) {
Triples t1 = new Triples(0, 5, 10);
Triples t2 = new Triples(0, 4, 1);
Triples t3 = new Triples(0, 2, 5);
Triples t4 = new Triples(2, 5, 1);
Triples [] array = {t1, t2, t3, t4};
System.out.println(getCost(0, 5, array));
}
public static int getCost(int start, int end, Triples [] array) {
int sum = 0;
int index = 0;
Arrays.sort(array);
while (index <= end) {
boolean found = false;
for (int i = 0; i < array.length; i++) {
if (array[i].isInclude(index)) {
sum += array[i].cost;
index = array[i].end + 1;
found = true;
break;
}
}
if (!found) {
return -1;
}
}
return sum;
}
}
class Triples implements Comparable<Triples> {
final int start;
final int end;
final int cost;
public Triples(int start, int end, int cost) {
this.start = start;
this.end = end;
this.cost = cost;
}
@Override
public int compareTo(Triples o) {
if (this.cost == o.cost) {
return Integer.compare(this.start, o.end);
}
return Integer.compare(this.cost, o.cost);
}
public boolean isInclude(int index) {
return index <= this.end && index >= this.start;
}
}
public class Solution {
public static void main(String [] args) {
printGoodNumbers(1000000);
}
public static boolean isGoodNumber(int number, List<Integer> cubes) {
int ways = 0;
for (int i = 0; i < cubes.size(); i++) {
for (int j = i+1; j < cubes.size(); j++) {
if (cubes.get(i) + cubes.get(j) == number) {
ways++;
if (ways == 2) {
return true;
}
}
if (cubes.get(i) + cubes.get(j) > number) {
break;
}
}
}
return false;
}
public static void printGoodNumbers(int limit) {
List<Integer> cubes = new ArrayList<>();
int i = 1;
int cube = 1;
while (cube <= limit) {
cubes.add(cube);
i++;
cube = i * i * i;
}
for (int l = 1; l < limit; l++) {
if (isGoodNumber(l, cubes)) {
System.out.println(l);
}
}
}
}
public class Solution {
public static void main(String [] args) {
printTree(4);
System.out.println();
System.out.println();
System.out.println();
printTree(10);
System.out.println();
System.out.println();
System.out.println();
printTree(20);
System.out.println();
System.out.println();
System.out.println();
printTree(25);
printTree(1);
}
public static void printTree(int day) {
if (day < 2) {
System.out.println("You cannot generate christmas tree");
return;
}
if (day > 20) {
System.out.println("Tree is no more");
return;
}
StringBuilder buf = new StringBuilder();
// first level
for (int i = 1, j = day; i <= day*2 + 1; i = i+2, j-- ) {
// space
for (int a = 0; a <= j; a++) {
buf.append(' ');
}
// star
for (int a = 0; a < i; a++) {
buf.append('*');
}
buf.append('\n');
}
for (int b = 1; b < day-1; b++) {
for (int i = 3, j = day-1; i <= day*2 + 1 - b*2; i = i+2, j-- ) {
// space
for (int a = 0; a <= j; a++) {
buf.append(' ');
}
// star
for (int a = 0; a < i; a++) {
buf.append('*');
}
buf.append('\n');
}
}
for (int j = 0; j < 2; j++) {
for (int i = 0; i <= day; i++) {
buf.append(' ');
}
buf.append('*').append('\n');
}
System.out.println(buf.toString());
}
}
public class Solution {
public Obj [] mergeObjArray(Obj [] array1, Obj [] array2) {
List<Obj> results = new ArrayList<>();
Arrays.sort(array1, new SortById());
Arrays.sort(array2, new SortById());
int index1 = 0;
int index2 = 0;
int index = 0;
while (index1 < array1.length && index2 < array2.length) {
if (array1[index1].id == array2[index2].id) {
results.add(new Obj(array1[index1].id, array1[index1].weight + array2[index2].weight));
index1++;
index2++;
} else if (array1[index1].id < array2[index2].id) {
results.add(new Obj(array1[index1].id, array1[index1].weight));
index1++;
} else {
results.add(new Obj(array2[index2].id, array2[index2].weight));
index2++;
}
}
while (index1 < array1.length) {
results.add(new Obj(array1[index1].id, array1[index1].weight));
index1++;
}
while (index2 < array2.length) {
results.add(new Obj(array2[index2].id, array2[index2].weight));
index2++;
}
Arrays.sort(array1, new SortByWeight());
Arrays.sort(array2, new SortByWeight());
Obj [] resultArray = (Obj [])results.toArray();
Arrays.sort(resultArray, new SortByWeight());
return resultArray;
}
}
class Obj {
final int id;
int weight;
public Obj(int id, int weight) {
this.id = id;
this.weight = weight;
}
}
class SortById implements Comparator {
@Override
public int compare(Object o1, Object o2) {
return Integer.compare(((Obj) o1).id, ((Obj) o2).id);
}
}
class SortByWeight implements Comparator {
@Override
public int compare(Object o1, Object o2) {
return Integer.compare(((Obj) o1).weight, ((Obj) o2).weight);
}
}
public class Maze {
private final Point upperCorner;
private final Point lowerCorner;
private final int radius;
private final Point [] sensors;
public Maze(Point upperCorner, Point lowerCorner, int radius, Point[] sensors) {
this.upperCorner = upperCorner;
this.lowerCorner = lowerCorner;
this.radius = radius;
this.sensors = sensors;
}
public List<Point> getPath() {
boolean [][] map = new boolean[upperCorner.y-lowerCorner.y+1][lowerCorner.x-upperCorner.x+1];
for (Point sensor : sensors) {
for (int i = sensor.y - radius; i <= sensor.y + radius; i++) {
for (int j = sensor.x - radius; j <= sensor.x + radius; j++) {
if (i >= lowerCorner.y && i <= upperCorner.y && j >= upperCorner.x && j <= lowerCorner.x) {
map[i][j] = true;
}
}
}
}
for (int i = lowerCorner.y; i <= upperCorner.y; i++ ) {
if (map[i][upperCorner.x] == false) {
// DFT search for solution
Stack<Point> stack = new Stack<>();
stack.add(new Point(i, upperCorner.x));
boolean [][] visited = new boolean[upperCorner.y-lowerCorner.y+1][lowerCorner.x-upperCorner.x+1];
while (!stack.isEmpty()) {
Point p = stack.pop();
if (visited[p.y][p.x]) {
continue;
}
visited[p.y][p.x] = true;
if (p.x == lowerCorner.x) {
// we found solution
// TODO: get the path
}
// add all child to stack if they are not visited
if (p.y+1 <= upperCorner.y && map[p.y+1][p.x] == false) {
stack.add(new Point(p.y+1, p.x));
}
if (p.y-1 >= lowerCorner.y && map[p.y-1][p.x] == false) {
stack.add(new Point(p.y-1, p.x));
}
if (p.x+1 >= lowerCorner.x && map[p.y][p.x+1] == false) {
stack.add(new Point(p.y, p.x+1));
}
if (p.x-1 >= upperCorner.x && map[p.y][p.x-1] == false) {
stack.add(new Point(p.y, p.x-1));
}
}
}
}
// no solution
return null;
}
}
public class LargeInteger {
private List<Integer> number;
public LargeInteger(int [] array) {
this.number = new ArrayList<>();
for (int i = array.length-1; i >= 0; i--) {
this.number.add(array[i]);
}
}
public void increment() {
for (int i = 0; i < this.number.size(); i++) {
if (this.number.get(i) < 9) {
this.number.set(i, this.number.get(i) + 1);
return;
} else {
this.number.set(i, 0);
}
}
this.number.set(this.number.size()-1, 0);
this.number.add(1);
}
@Override
public String toString() {
StringBuilder buf = new StringBuilder();
buf.append("Large Integer").append('\n');
for (int i = this.number.size()-1; i >= 0; i--) {
buf.append(this.number.get(i));
}
return buf.toString();
}
}
public class Solution {
public static Optional<String> getMinimumLengthWord(List<String> dictionary, Set<Character> characterSet) {
int minLength = 0;
String result = null;
for (String str : dictionary) {
if (isIncludeAllChars(str, characterSet)) {
if (str.length() < minLength) {
minLength = str.length();
result = str;
}
}
}
return Optional.ofNullable(result).filter(s -> !s.isEmpty());
}
public static boolean isIncludeAllChars(String word, Set<Character> characterSet) {
int [] array = new int[28];
word.chars().forEach(a -> array[a-'a']++);
return characterSet.stream()
.filter(i -> array[i - 'a'] == 0)
.collect(Collectors.toList())
.isEmpty();
}
}
It is not google question and it is too simple for google. booking.com ask these kind of questions frequently.
- ugurdonmez87 July 26, 2016public class Solution {
public static void main(String [] args) {
String [] words = {"HelloMars", "HelloWorld", "HelloWorldMars", "HiHo"};
CamelCaseNotation ccn = new CamelCaseNotation(words);
System.out.println(ccn.getPattern("H"));
// TODO: it can not split HW
System.out.println(ccn.getPattern("HW"));
System.out.println(ccn.getPattern("Ho"));
System.out.println(ccn.getPattern("HeWorM"));
}
}
class CamelCaseNotation {
private List<CamelCaseString> list;
public CamelCaseNotation(String [] words) {
this.list = new ArrayList<>();
for (String str : words) {
this.list.add(new CamelCaseString(str));
}
}
public List<String> getPattern(String pattern) {
List<String> results = new ArrayList<>();
for (CamelCaseString ccs : list) {
if (ccs.isMatch(pattern)) {
results.add(ccs.getInitial());
}
}
return results;
}
}
class CamelCaseString {
private final String [] strings;
private final String initial;
public CamelCaseString(String string) {
this.initial = string;
this.strings = string.split("(?<!(^|[A-Z]))(?=[A-Z])|(?<!^)(?=[A-Z][a-z])");
}
public String getInitial() {
return initial;
}
public boolean isMatch(String string) {
String [] splited = string.split("(?<!(^|[A-Z]))(?=[A-Z])|(?<!^)(?=[A-Z][a-z])");
for (int i = 0; i < splited.length; i++) {
if (i == strings.length) {
return false;
}
if (!strings[i].startsWith(splited[i])) {
return false;
}
}
return true;
}
}
- ugurdonmez87 July 25, 2016public class Solution {
public static void main(String [] args) {
String [] array = {"DO", "RUN"};
print(array, 2, 9);
}
public static void print(String [] words, int row, int column) {
int word = 0;
int i = 0;
int j = 0;
while (i < row) {
if (words[word].length() <= column-j) {
System.out.print(words[word] + " ");
j = j + 1 + words[word].length();
word++;
word %= words.length;
} else {
System.out.println();
j = 0;
i++;
}
}
}
}
I dont think that it is google question.
public class Solution {
public static void main(String [] args) {
int [][] matrix = { {6,7,8,9,2},
{4,6,7,8,9},
{1,4,6,7,8},
{0,1,4,6,7}};
System.out.println(isToepliz(matrix));
}
public static boolean isToepliz(int [][] matrix) {
int row = matrix.length;
int coloumn = matrix[0].length;
for (int i = 0; i < coloumn; i++) {
int value = matrix[0][i];
for (int first = 0, second = i; first < row && second < coloumn; first++, second++) {
if (matrix[first][second] != value) {
return false;
}
}
}
return true;
}
}
public class Solution {
public static void main(String [] args) {
System.out.println(getPalindrome("aha"));
System.out.println(getPalindrome("ttaatta"));
System.out.println(getPalindrome("abc"));
System.out.println(getPalindrome("gggaaa"));
}
public static String getPalindrome(String str) {
int [] chars = new int[27];
str.chars().forEach(c -> chars[c-'a']++);
StringBuilder buf = new StringBuilder();
for (int i = 0; i < 27; i++) {
if (chars[i] >= 2) {
int count = chars[i] / 2;
chars[i] -= count*2;
while (count > 0) {
buf.append((char) (i+'a'));
count--;
}
}
}
String end = buf.toString();
buf.reverse();
for (int i = 0; i < 27; i++) {
if (chars[i] >= 1) {
buf.append((char) (i+'a'));
break;
}
}
return buf.toString() + end;
}
}
should we find st or mst?
- ugurdonmez87 April 28, 2016/**
*
* @author ugurdonmez
*/
public class IntegerConvert {
public static void main(String [] args) {
IntegerConvert iConvert = new IntegerConvert();
System.out.println(iConvert.convert("one million two hundread"));
System.out.println(iConvert.convert("one million two hundread thousand"));
System.out.println(iConvert.convert("one million two hundread thousand fifty seven"));
System.out.println(iConvert.convert("one million two hundread thousand two hundread fifty seven"));
}
private final HashMap<String, Integer> map;
public IntegerConvert() {
map = new HashMap<>();
map.put("zero", 0);
map.put("one", 1);
map.put("two", 2);
map.put("three", 3);
map.put("four", 4);
map.put("five", 5);
map.put("six", 6);
map.put("seven", 7);
map.put("eight", 8);
map.put("nine", 9);
map.put("ten", 10);
map.put("eleven", 11);
map.put("twelve", 12);
map.put("thirteen", 13);
map.put("fourteen", 14);
map.put("fifteen", 15);
map.put("sixteen", 16);
map.put("seventeen", 17);
map.put("eightteen", 18);
map.put("nineteen", 19);
map.put("twenty", 20);
map.put("thirty", 30);
map.put("fourty", 40);
map.put("fifty", 50);
map.put("sixty", 60);
map.put("seventy", 70);
map.put("enighty", 80);
map.put("ninety", 90);
map.put("hundread", 100);
map.put("thousand", 1000);
map.put("million", 1000000);
map.put("billion", 1000000000);
}
public int convert(String string) {
int value = 0;
String[] words = string.split(" ");
int local = 0;
for ( String s : words ) {
if ( isMultiply(s) && s.equals("hundread") ) {
local *= map.get(s);
} else if (isMultiply(s)){
local *= map.get(s);
value += local;
local = 0;
} else {
local += map.get(s);
}
}
value += local;
return value;
}
public boolean isMultiply(String s) {
if ( s.equals("billion") || s.equals("million") || s.equals("thousand") || s.equals("hundread") ) {
return true;
} else {
return false;
}
}
}
import math
def calculate_distance(p1, p2):
return math.sqrt( (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]) )
def square_rectangle(p1, p2, p3, p4):
distances = []
distances.append(calculate_distance(p1,p2))
distances.append(calculate_distance(p1,p3))
distances.append(calculate_distance(p1,p4))
distances.append(calculate_distance(p2,p3))
distances.append(calculate_distance(p2,p4))
distances.append(calculate_distance(p3,p4))
distances.sort()
if distances[0] == distances[1] and distances[1] == distances[2] and distances[2] == distances[3] and distances[3] != distances[4] and distances[4] == distances[5]:
return "square"
elif distances[0] == distances[1] and distances[1] != distances[2] and distances[2] == distances[3] and distances[3] != distances[4] and distances[4] == distances[5]:
return "rectangle"
else:
return "nothing"
print square_rectangle( [0,1], [1,0], [1,1], [0,0] )
print square_rectangle( [1,1], [1,0], [1,1], [0,0] )
print square_rectangle( [2,1], [2,0], [0,1], [0,0] )
def find_greatest_positive_integer(str):
digits = []
for i in range(0,10):
digits.append(0)
for i in range(0, len(str)):
digits[ int( str[i]) ] = digits[ int(str[i]) ] + 1
result = 0
for i in reversed(range(10)):
for j in range(0, digits[i]):
result = result * 10 + i
return result
print find_greatest_positive_integer("123")
print find_greatest_positive_integer("1239900")
def isDigit(char):
if char >= '0' and char <= '9':
return True
else:
return False
def calculate(char1, char2, op):
if op == '+':
return char1 + char2
elif op == '-':
return char1 - char2
elif op == '*':
return char1 * char2
elif op == '/':
return char1 / char2
def postfix_calculator(str):
stack = []
for i in range(0, len(str)):
if isDigit(str[i]):
stack.append(int(str[i]))
else:
stack.append(calculate( stack.pop(), stack.pop(), str[i]))
return stack.pop()
print postfix_calculator("432+*")
def one_edit_way(str1, str2):
len1 = len(str1)
len2 = len(str2)
if abs(len1 - len2) > 1:
return False
elif len1 == len2:
diff = 0
for i in range(0,len1):
if str1[i] != str2[i]:
diff = diff + 1
if diff == 2:
return False
return True
else:
if len1 > len2 :
i = 0
j = 0
while i < len1:
if str1[i] == str2[j]:
i = i + 1
j = j + 1
if j == len2:
return True
else:
i = i + 1
if i > j + 1:
return False
return True
else:
return one_edit_way(str2, str1)
a = "abc"
b = "ab"
c = "adc"
d = "cab"
print one_edit_way(a,b)
print one_edit_way(a,c)
print one_edit_way(a,d)
import java.util.Scanner;
import java.util.Stack;
/**
*
* @author uğur
*/
public class AddTwoBigInteger {
public static void main (String args[]) {
Scanner scanner = new Scanner(System.in);
String inp1 = scanner.next();
String inp2 = scanner.next();
Stack<Character> stack1 = new Stack<>();
Stack<Character> stack2 = new Stack<>();
for (int i = 0 ; i < inp1.length() ; i++ ) {
stack1.add(inp1.charAt(i));
}
for (int i = 0 ; i < inp2.length() ; i++ ) {
stack2.add(inp2.charAt(i));
}
Stack<Integer> result = new Stack<>();
int carry = 0;
while ( !stack1.isEmpty() || !stack2.isEmpty() ) {
int i1;
int i2;
if (stack1.isEmpty() ) {
i1 = 0;
}
else {
i1 = Character.getNumericValue( stack1.pop() );
}
if (stack2.isEmpty() ) {
i2 = 0;
}
else {
i2 = Character.getNumericValue( stack2.pop() );
}
result.add( (i1 + i2 + carry ) % 10 );
carry = (i1 + i2 + carry ) / 10;
}
if ( carry != 0 ) {
result.add(carry);
}
while( !result.isEmpty() ) {
System.out.print(result.pop());
}
}
}
import java.util.Scanner;
import java.util.Stack;
/**
*
* @author uğur
*/
public class AddTwoBigInteger {
public static void main (String args[]) {
Scanner scanner = new Scanner(System.in);
String inp1 = scanner.next();
String inp2 = scanner.next();
Stack<Character> stack1 = new Stack<>();
Stack<Character> stack2 = new Stack<>();
for (int i = 0 ; i < inp1.length() ; i++ ) {
stack1.add(inp1.charAt(i));
}
for (int i = 0 ; i < inp2.length() ; i++ ) {
stack2.add(inp2.charAt(i));
}
Stack<Integer> result = new Stack<>();
int carry = 0;
while ( !stack1.isEmpty() || !stack2.isEmpty() ) {
int i1;
int i2;
if (stack1.isEmpty() ) {
i1 = 0;
}
else {
i1 = Character.getNumericValue( stack1.pop() );
}
if (stack2.isEmpty() ) {
i2 = 0;
}
else {
i2 = Character.getNumericValue( stack2.pop() );
}
result.add( (i1 + i2 + carry ) % 10 );
carry = (i1 + i2 + carry ) / 10;
}
if ( carry != 0 ) {
result.add(carry);
}
while( !result.isEmpty() ) {
System.out.print(result.pop());
}
}
}
sorry i didn't see only right or down move
- ugurdonmez87 February 04, 2014what if
int arr[][] = {{1,1,1,1},
{1,1,0,1},
{1,0,1,1},
{1,1,1,1}};
import java.util.Scanner;
/**
*
* @author uğur
*/
public class CountNumber {
public static void main (String args[]) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int count = 0;
for (int i = 0 ; i < n ; i++ ) {
if ( !containFour(i)) {
count++;
}
}
System.out.println(count);
}
public static boolean containFour(int i) {
return String.valueOf(i).contains("4");
}
}
- ugurdonmez87 September 12, 2016