zhangboryan
BAN USERJava Implementation Using Trie idea.
/**
* input: ["zebra", "dog", "duck", "dot", "key", "keyVAlue"]
* output: {zebra: z, dog: dog, duck: du, dot: dot, key: "", keyValue: keyV}
**/
public class ShortestPrefixRepresent {
private TrieNode root = new TrieNode();
public ShortestPrefixRepresent(String[] array) {
for (String item : array) {
putIntoTrie(item);
}
}
public String getShortestPrefix(String target) {
StringBuffer res = new StringBuffer("");
TrieNode p = root;
for (int i = 0; i < target.length(); i++) {
res.append(target.charAt(i));
if (p.subNodes[target.charAt(i)] == null) {
return "";
} else {
if (p.subNodes[target.charAt(i)].count == 1) {
return res.toString();
}
}
p = p.subNodes[target.charAt(i)];
}
return "";
}
private void putIntoTrie(String item) {
TrieNode p = root;
for (int i = 0; i < item.length(); i++){
if (p.subNodes[item.charAt(i)] == null) {
p.subNodes[item.charAt(i)] = new TrieNode();
} else {
p.subNodes[item.charAt(i)].count += 1;
}
p = p.subNodes[item.charAt(i)];
}
}
public static void main(String[] args) {
String[] array = {"zebra", "dog", "duck", "dot", "key", "keyVAlue"};
ShortestPrefixRepresent code = new ShortestPrefixRepresent(array);
for (String item : array) {
System.out.println(item + ": " + code.getShortestPrefix(item));
}
}
}
class TrieNode{
int count = 1;
TrieNode[] subNodes = new TrieNode[256];
}
Java Implementation.
import java.util.*;
public class NumberOfUnsortedPairs{
public int getNumberOfUnsortedPairs(int[] array) {
int res = 0;
if (array == null || array.length == 0) {
return res;
}
MyClass[] myClassArray = new MyClass[array.length];
for (int i = 0; i < array.length; i++) {
myClassArray[i] = new MyClass(array[i]);
}
mergeSort(myClassArray, 0, array.length - 1);
for (MyClass myClass : myClassArray) {
res += myClass.numOfElementSmallerBehindMe;
}
return res;
}
private void mergeSort(MyClass[] myClassArray, int start, int end) {
if (start == end) {
return;
}
int mid = start + (end - start)/2;
mergeSort(myClassArray, start, mid);
mergeSort(myClassArray, mid + 1, end);
merge(myClassArray, start, mid, end);
}
private void merge(MyClass[] myClassArray, int start, int mid, int end) {
MyClass[] left = new MyClass[mid - start + 2];
MyClass[] right = new MyClass[end - mid + 1];
for (int i = 0; i < left.length - 1; i++) {
left[i] = myClassArray[start + i];
}
for (int i = 0; i < right.length - 1; i++) {
right[i] = myClassArray[mid + 1 + i];
}
left[left.length - 1] = new MyClass(Integer.MAX_VALUE);
right[right.length - 1] = new MyClass(Integer.MAX_VALUE);
int leftIndex = 0;
int rightIndex = 0;
int i = start;
int bigerSum = 0;
for (i = start; i <= end; i++) {
if (left[leftIndex].val < right[rightIndex].val) {
myClassArray[i] = left[leftIndex];
myClassArray[i].numOfElementSmallerBehindMe += bigerSum;
leftIndex++;
} else {
bigerSum++;
myClassArray[i] = right[rightIndex];
rightIndex++;
}
}
}
public static void main(String[] args) {
NumberOfUnsortedPairs code = new NumberOfUnsortedPairs();
int[] array = {2, 1, 3};
System.out.println(code.getNumberOfUnsortedPairs(array));
int[] array1 = {3, 2, 1};
System.out.println(code.getNumberOfUnsortedPairs(array1));
}
}
class MyClass{
int val;
int numOfElementSmallerBehindMe = 0;
public MyClass(int val) {
this.val = val;
}
}
Java Implementation.
import java.util.*;
/***
* 5
* 3 9
* 2 4 6
***/
class TreeNode{
int val;
int size;
TreeNode left;
TreeNode right;
public TreeNode(int val, int size) {
this.val = val;
this.size = size;
}
}
public class KthNodeBinaryTree{
public TreeNode getKthNode(TreeNode root, int kth) {
TreeNode curt = root;
if (curt == null) {
return curt;
}
while (curt != null) {
if (kth > curt.size) {
return null;
}
TreeNode left = curt.left;
if (left == null) {
if (kth == 1) {
return curt;
}
curt = curt.right;
kth--;
} else {
if (kth >= left.size + 1) {
kth = kth - left.size;
if (kth == 1) {
return curt;
} else {
kth = kth - 1;
curt = curt.right;
}
} else {
curt = curt.left;
}
}
}
return curt;
}
public static void main(String[] args) {
KthNodeBinaryTree code = new KthNodeBinaryTree();
TreeNode root = new TreeNode(5, 6);
TreeNode node1 = new TreeNode(3, 3);
TreeNode node2 = new TreeNode(9, 2);
TreeNode node3 = new TreeNode(2, 1);
TreeNode node4 = new TreeNode(4, 1);
TreeNode node5 = new TreeNode(6, 1);
root.left = node1;
root.right = node2;
node1.left = node3;
node1.right = node4;
node2.left = node5;
TreeNode res = code.getKthNode(root, Integer.parseInt(args[0]));
System.out.println((res != null ? res.val : "Your input number is larger than the tree size"));
}
}
Java Implementation.
Main idea from BST iterator and 2sum.
public class TwoSumInBST {
private TreeNode curtStart;
private TreeNode curtEnd;
private Stack<TreeNode> stackUp= new Stack<TreeNode>();
private Stack<TreeNode> stackDown = new Stack<TreeNode>();
public boolean getTwoSum(TreeNode root, int target) {
if (root == null) {
return false;
}
this.curtStart = root;
this.curtEnd = root;
TreeNode left = getFromUpToDown();
TreeNode right = getFromDownToUp();
while (left != right) {
int sum = left.value + right.value;
if (sum == target) {
return true;
}
if (sum < target) {
left = getFromUpToDown();
} else {
right = getFromDownToUp();
}
}
return false;
}
private TreeNode getFromUpToDown() {
while (curtStart != null) {
stackUp.push(curtStart);
curtStart = curtStart.left;
}
curtStart = stackUp.pop();
TreeNode res = curtStart;
curtStart = curtStart.right;
return res;
}
private TreeNode getFromDownToUp() {
while (curtEnd != null) {
stackDown.push(curtEnd);
curtEnd = curtEnd.right;
}
curtEnd = stackDown.pop();
TreeNode res = curtEnd;
curtEnd = curtEnd.left;
return res;
}
}
Java Implementation by BFS
import java.util.*;
public class HowManyCountries{
public int countriesNum(int[][] graph) {
int res = 0;
if (graph == null || graph.length == 0 || graph[0].length == 0) {
return res;
}
boolean[][] visited = new boolean[graph.length][graph[0].length];
for (int i = 0; i < graph.length; i++) {
for (int j = 0; j < graph[0].length; j++) {
if (!visited[i][j]) {
res++;
Queue<MyClass> queue = new LinkedList<MyClass>();
queue.add(new MyClass(i, j));
visited[i][j] = true;
bfs(graph, visited, queue, i, j, graph[i][j]);
}
}
}
return res;
}
private void bfs(int[][] graph, boolean[][] visited, Queue<MyClass> queue, int row, int col, int target) {
while (!queue.isEmpty()) {
MyClass cur = queue.poll();
if (cur.row - 1 >= 0 && !visited[cur.row - 1][cur.col] && graph[cur.row - 1][cur.col] == target) {
queue.add(new MyClass(cur.row - 1, cur.col));
visited[cur.row - 1][cur.col] = true;
}
if (cur.col + 1 < visited[0].length && !visited[cur.row][cur.col + 1] && graph[cur.row][cur.col + 1] == target) {
queue.add(new MyClass(cur.row, cur.col + 1));
visited[cur.row][cur.col + 1] = true;
}
if (cur.col - 1 >= 0 && !visited[cur.row][cur.col - 1] && graph[cur.row][cur.col - 1] == target) {
queue.add(new MyClass(cur.row, cur.col - 1));
visited[cur.row][cur.col - 1] = true;
}
if (cur.row + 1 < visited.length && !visited[cur.row + 1][cur.col] && graph[cur.row + 1][cur.col] == target) {
queue.add(new MyClass(cur.row + 1, cur.col));
visited[cur.row + 1][cur.col] = true;
}
}
}
class MyClass{
int row;
int col;
public MyClass(int row, int col) {
this.row = row;
this.col = col;
}
}
public static void main(String[] args) {
HowManyCountries code = new HowManyCountries();
int[][] graph = {
{1,1,1,0},
{1,1,0,0},
{0,0,0,1},
};
System.out.println(code.countriesNum(graph));
}
}
I got my answer n = 45 and the number of distinct solutions is 1029. There is my implementation.
public class FindLeastNWhichHasMoreThan1000Solutions {
public static int getValidY(int n, int disp){
double l = 0.1 ;
double y = 0;
while(l!=0){
int x= n+disp;
y = (n*x)/(x-n);
l = y-(int)y;
}
return (int)y;
}
public static int countN(){
int counter = 0;
int n = 4;
int disp = 1;
while(true){
int y = getValidY(n,disp);
if(n+disp<=y){
counter++;
disp++;
}else{
if(counter<1000){
n++;
disp = 1;
}else{
return n;
}
}
}
}
public static void main(String[] args) {
int n = FindLeastNWhichHasMoreThan1000Solutions.countN();
System.out.println(n);
}
}
public class Multiplication {
private HashMap<String, Integer> map = new HashMap<String, Integer>();
public int getMultiplicationOfTwoNumber(int number, int times){
if(times==1){
return number;
}
if(number < times){
int temp = number;
number = times;
times = temp;
}
String key = number + "," + times;
Object value = map.get(key);
if(value!=null){
return map.get(key);
}
int leftTimes = times/2;
int rightTimes = times - leftTimes;
int leftResult = getMultiplicationOfTwoNumber(number, leftTimes);
int rightResult = getMultiplicationOfTwoNumber(number, rightTimes);
int result = leftResult + rightResult;
map.put(key, result);
return result;
}
public static void main(String[] args){
Multiplication code = new Multiplication();
System.out.println(code.getMultiplicationOfTwoNumber(200, 200));
}
}
I have a idea, that using selection algorithm.
Selection algorithm whose running time is O(n) in the worst case. So on each sever we can use selection algorithm to find the (billion/2)th biggest element, and then we can get 10k integers that are medians of each sever. And then we use same procedure to find the (10k/2)th biggest element, which is the final result. The total time is linear time O(n).
Two pointers, one from the beginning points to nonzero element, the other one is from the end points to nonzero element. We should switch these values.
public class MoveNonzeroLeft {
public static int findNextNonZeroIndex(int[] array, int index){
int nonZeroIndex = 0;
for(int i = index -1; i>0; i--){
if(array[i] != 0){
nonZeroIndex = i;
break;
}
}
return nonZeroIndex;
}
public static int findNextZeroIndex(int[] array, int index){
int zeroIndex = 0;
for(int i = index + 1; i< array.length;i++){
if(array[i] == 0){
zeroIndex = i;
break;
}
}
return zeroIndex;
}
public static void moveNonzeroLeft(int[] array){
int zeroIndex = 0;
int nonZeroIndex = 0;
zeroIndex = findNextZeroIndex(array, 0);
nonZeroIndex = findNextNonZeroIndex(array, array.length);
while(true){
if(zeroIndex < nonZeroIndex){
/*
* swap
*/
int temp = array[nonZeroIndex];
array[nonZeroIndex] = 0;
array[zeroIndex] = temp;
zeroIndex = findNextZeroIndex(array, zeroIndex);
nonZeroIndex = findNextNonZeroIndex(array, nonZeroIndex);
}else{
break;
}
}
}
public static void main(String[] args) {
int[] array = {1, 0, 2, 0, 0, 3, 4};
MoveNonzeroLeft.moveNonzeroLeft(array);
for(int i = 0 ;i < array.length ; i++){
System.out.print(array[i]+" ");
}
}
}
Hi,
in your method you use Integer as a buffer. If the elements in the array is larger than 32... , how to solve this question?
Hi,
I think you us a very good method, for this question. But in your method the Integer value always less than 10. If we can not know the limit of these integer, may be we can not use your way, because the Space Complexity: O(1), counters[] may take lots of memory, right?
Hi,
If the question is three of them are odd appear times and others are even times, I can solve.
I want you can make sure, is the question correct or not?
Hi, can you explain the question more detail? what is the "each integer is present an odd huber of time" meaning? Like give us some example.
- zhangboryan June 21, 2014A question: Binary search should be on a sorted array, right?
Even selection algorithm can take O(M) time, so your method may not be a
linear time in total.
Java Implementation. Time: O(N); Space: O(N); HashMap and Moving Window idea.
This Question looks like a DP problem, but I can't find a DP solution better than this.
Does anybody have one?
- zhangboryan March 12, 2015