Algorithm Question Discussion

每日一题：

No.1:

Jumping River Question:

Use an array to represent a river. 0 means water and 1 means stone. Start point is R[0], and initial speed is 1, every step you can decide to keep current speed or increase by 1. For jump over the river, you only can stay on stone for every step.

Question is what's the minimum step you have to take for jumping over the river.

跳河问题。给一个0/1数组R代表一条河，0代表水，1代表石头。起始位置R[0]等于1，

初速度为1. 每一步可以选择以当前速度移动，或者当前速度加1再移动。只能停留在石

头上。问最少几步可以跳完整条河流。

给定数组为R=[1,1,1,0,1,1,0,0]，最少3步能过河：

第一步先提速到2，再跳到R[2]；

第二步先提速到3，再跳到R[5]；

第三步保持速度3，跳出数组范围，成功过河。

http://www.mitbbs.com/article_t1/JobHunting/32617501_0_1.html

/** * Created by christopherhuang on 12/28/14. */public class JumpOverTheRiver { public int jump(int[] river) { List<Map<Integer, Integer>> states = new ArrayList<>(); int min = Integer.MAX_VALUE; for (int i = 0; i < river.length; i++) { states.add(new HashMap<Integer, Integer>()); } states.get(0).put(1, 0); for (int i = 0; i < river.length; i++) { for (int speed : states.get(i).keySet()) { for (int j = 0; j < 2; j++) { int nextStep = speed + i + j; int step = states.get(i).get(speed) + 1; if (nextStep >= river.length) { min = Math.min(min, step); } else if (river[nextStep] == 1) { states.get(nextStep).put(speed + j, step); } } } } return min; } @Test public void testJumpMethod() { int[] river = {1,1,1,0,1,1,0,0}; Assert.assertEquals("The minimum number of steps should be 3", 3, new JumpOverTheRiver().jump(river)); }}

NO.2:

Random question:

You have a function rand1() to random generate number 0 or 1. Can you make a function to generate randN(int n), which will random generate 0,1,2....N? n can be any number, like negative or positive.

给定rand1()：能够产生random数字0,1

用rand1()实现:

rand3()--> 0, 1, 2, 3

rand4()--> 0, 1, 2, 3, 4

randN(int n)--> 0, 1, ..., N n可以是任意整数，包括0、负整数、正整数

，注意edge case

public class Solution { public int randomGenerateNum(int n){ int numOfDigits = 0; int booleanNum = (n<0 ? 1: 0); n = Math.abs(n); int tmp = n; while(tmp > 0){ numOfDigits++; tmp /= 2; } int res = 0; while(true){ for(int i = 0; i<numOfDigits; i++){ res = res*2+rand1(); } if(res <= n){ break; }else{ res = 0; } } return booleanNum == 0 ? res : -res; } private int rand1(){ Random rn = new Random(); return rn.nextInt(2); }}

NO.3:

Longest Increasing Subsequence

Give you an array d[1..9] = 2 1 5 3 6 4 8 9 7, can you get the Longest Increasing Subsequence? It should be 5.

假设存在一个序列d[1..9] = 2 1 5 3 6 4 8 9 7，可以看出来它的LIS长度为5。

(1) DP solution:

O(n2) runtime and O(n) space

(2) O(nlgn) run time Solution:

Link : http://www.felix021.com/blog/read.php?1587

public class Solution { public static int lisFunction(int[] arr){ if(arr == null || arr.length == 0){ throw new IllegalArgumentException("wrong input"); } int[] res = new int[arr.length]; for(int i=0; i<res.length; i++){ res[i] = Integer.MAX_VALUE; } int max = 0; for(int i=0; i<arr.length; i++){ int inde = findIndex(arr[i], res); res[inde] = arr[i]; if(inde > max){ max = inde; } } return max+1; } private static int findIndex(int val, int[] arr){ int left = 0; int right = arr.length-1; while(left <= right){ int mid = (left+right)/2; if(arr[mid] == val){ return mid; }else if(arr[mid] > val){ if(mid == 0){ return 0; } right = mid-1; }else{ if(mid == arr.length-1){ return mid; }else if(arr[mid+1] > val){ return mid+1; } left = mid+1; } } return 0; } public static void main(String[] args){ int[] test = new int[]{1,2,9,8,3,6,7,10}; System.out.println(lisFunction(test)); int[] test2 = new int[]{3,2,4,5}; System.out.println(lisFunction(test2)); int[] test3 = new int[]{2, 1, 5, 3, 6, 4, 8, 9, 7}; System.out.println(lisFunction(test3)); }}

NO.4

Based on a special dictionary, you can have below characters' order, could you know the whole characters order in that dictionary?

wrt

wrf

rft

Answer should be: w,e,r,f,t

给你一个按字母顺序排好的字典（但你不知道字母顺序,非英语），要求找出字母顺序

例：

单词顺序：

wrt

wrf

rft

字母顺序：

w,e,r,f,t

http://www.mitbbs.com/mitbbs_article_t.php?board=JobHunting&gid=32859257&ftype=0

public class ToplogicSort {

HashMap<Character, GraphNode> table = new HashMap<Character, GraphNode>();

public void constructNode(String str){

if(str.length() == 0){

return;

}

if(str.length() == 1){

if(table .containsKey(str.charAt(0))){

return;

} else{

GraphNode tmp = new GraphNode(str.charAt(0));

table.put(str.charAt(0), tmp);

return;

}

for(int i=1; i<str.length(); i++){

char a = str.charAt(i-1);

char b = str.charAt(i);

GraphNode anode ;

if(table .containsKey(a)){

anode = table.get(a);

} else{

anode = new GraphNode(a);

}

GraphNode bnode ;

if(table .containsKey(b)){

bnode = table.get(b);

} else{

bnode = new GraphNode(b);

}

if(!anode.adjacent .containsKey(b)){

anode. adjacent.put(b, bnode);

}

this.table .put(a, anode);

this.table .put(b, bnode);

}

public void sort(){

Stack<Character> stc = new Stack<Character>();

HashSet<Character> visited = new HashSet<Character>();

for(char key : table .keySet()){

GraphNode cur = table.get(key);

if(!visited.contains(key)){

dfs(cur,visited,stc);

}

while(!stc.isEmpty()){

System. out.println(stc.pop());

}

private void dfs(GraphNode cur, HashSet<Character> visited, Stack<Character> stc){

visited.add(cur. val);

for(Character next : cur.adjacent .keySet()){

if(visited.contains(next)){

continue;

}

dfs(cur. adjacent.get(next), visited, stc);

}

stc.push(cur. val);

}

public class Main {

public static void main(String[] args){

ToplogicSort top = new ToplogicSort();

top. constructNode("wrt");

top. constructNode("wrf");

top. constructNode("er");

top. constructNode("et");

top. constructNode("rft");

top. constructNode("we");

top.sort();

}

Topological Sort:

For more detail about this algorithm please check https://sites.google.com/site/codingbughunter/algorithm-code-questions/topological-sort-tutorial

public class Solution{ public static void main(String[] args) { Graph theGraph = new Graph(); theGraph.addVertex('w'); // 0 theGraph.addVertex('r'); // 1 theGraph.addVertex('t'); // 2 theGraph.addVertex('f'); // 3 theGraph.addVertex('e'); // 4 theGraph.addEdge(0, 1); theGraph.addEdge(1, 2); theGraph.addEdge(4, 2); theGraph.addEdge(4, 1); theGraph.addEdge(1, 3); theGraph.addEdge(3, 2); theGraph.addEdge(0, 4);

theGraph.topo(); // do the sort } // end main()}

/**

* Created by jzhang21 on 1/1/15. */public class Graph { private final int MAX_VERTS = 20; private Vertex vertexList[]; // list of vertices private int adjMat[][]; // adjacency matrix private int nVerts; // current number of vertices private char sortedArray[]; // ------------------------------------------------------------- public Graph() // constructor { vertexList = new Vertex[MAX_VERTS]; // adjacency matrix adjMat = new int[MAX_VERTS][MAX_VERTS]; nVerts = 0; for(int j=0; j<MAX_VERTS; j++) // set adjacency for(int k=0; k<MAX_VERTS; k++) // matrix to 0 adjMat[j][k] = 0; sortedArray = new char[MAX_VERTS]; // sorted vert labels } // end constructor // ------------------------------------------------------------- public void addVertex(char lab) { vertexList[nVerts++] = new Vertex(lab); } // ------------------------------------------------------------- public void addEdge(int start, int end) { adjMat[start][end] = 1; } // ------------------------------------------------------------- public void displayVertex(int v) { System.out.print(vertexList[v].label); } // ------------------------------------------------------------- public void topo() // toplogical sort { int orig_nVerts = nVerts; // remember how many verts while(nVerts > 0) // while vertices remain, { // get a vertex with no successors, or -1 int currentVertex = noSuccessors(); if(currentVertex == -1) // must be a cycle { System.out.println("ERROR: Graph has cycles"); return; } // insert vertex label in sorted array (start at end) sortedArray[nVerts-1] = vertexList[currentVertex].label; deleteVertex(currentVertex); // delete vertex } // end while // vertices all gone; display sortedArray System.out.print("Topologically sorted order: "); for(int j=0; j<orig_nVerts; j++) System.out.print( sortedArray[j] ); System.out.println(""); } // end topo // ------------------------------------------------------------- public int noSuccessors() // returns vert with no successors { // (or -1 if no such verts) boolean isEdge; // edge from row to column in adjMat for(int row=0; row<nVerts; row++) // for each vertex, { isEdge = false; // check edges for(int col=0; col<nVerts; col++) { if( adjMat[row][col] > 0 ) // if edge to { // another, isEdge = true; break; // this vertex } // has a successor } // try another if( !isEdge ) // if no edges, return row; // has no successors } return -1; // no such vertex } // end noSuccessors() // ------------------------------------------------------------- public void deleteVertex(int delVert) { if(delVert != nVerts-1) // if not last vertex, { // delete from vertexList for(int j=delVert; j<nVerts-1; j++) vertexList[j] = vertexList[j+1]; // delete row from adjMat for(int row=delVert; row<nVerts-1; row++) moveRowUp(row, nVerts); // delete col from adjMat for(int col=delVert; col<nVerts-1; col++) moveColLeft(col, nVerts-1); } nVerts--; // one less vertex } // end deleteVertex // ------------------------------------------------------------- private void moveRowUp(int row, int length) { for(int col=0; col<length; col++) adjMat[row][col] = adjMat[row+1][col]; } // ------------------------------------------------------------- private void moveColLeft(int col, int length) { for(int row=0; row<length; row++) adjMat[row][col] = adjMat[row][col+1]; } } // end class Graph

public class Vertex {

public char label; // label (e.g. 'A') // ------------------------------------------------------------- public Vertex(char lab) // constructor { label = lab; } } // end class Vertex

NO.5

Given two String arrays, one array has the equal relation of any two element, another one has not equal relation. Like below:

arr1 ={{A,B}{B,C}...} means {“A=B”, "B=C", ...}

arr2 = {{A,C}{F,R}} means {"A!=C", "F!=R", ...}

Judge if there is a conflict in this two arrays.

given两个字符串，分别表示两个元素等和不等，比如：

arr1 = {“A=B”, "B=C", ...}

arr2 = {"A!=C", "F!=R", ...}

判断是否有矛盾，这个例子就有矛盾：A!=C

given提取元素的method: getID(..)，这个不用自己写：String[] sarr = getID(arr1

[0]) --> sarr {A, B}

public class Solution{ public static void main(String[] args){ String[][] and = new String[][]{{"a","b"},{"a","c"},{"a","m"}}; String[][] not = new String[][]{{"a","y"},{"c","b"},{"n","m"}}; System.out.println("res : "+isRight(and,not)); } public static boolean isRight(String[][] and, String[][] not){ ArrayList<HashSet<String>> list = new ArrayList<HashSet<String>>(); for(String[] val : and){ if(list.isEmpty()){ HashSet<String> table = new HashSet<String>(); table.add(val[0]); table.add(val[1]); list.add(table); }else{ for( HashSet<String> tmp : list){ if(tmp.contains(val[0]) || tmp.contains(val[1])){ tmp.add(val[0]); tmp.add(val[1]); continue; } } HashSet<String> next = new HashSet<String>(); next.add(val[0]); next.add(val[1]); list.add(next); } } for(String[] val : not){ for(HashSet<String> tmp : list){ if(tmp.contains(val[0]) && tmp.contains(val[1])){ return false; } } } return true; }}

NO.6

Test if it is a same number after rotate 180 degree. Like 69, after rotating is also 69. But 45 cannot be same after rotate.

给出任意一串数字, 找出旋转180度以后还是原来的值得数字串.

比如, 69旋转180度后还是69.

Solution:

public class Solution{ public static void main(String[] args){ System.out.println("test1 : "+isMirrorNum(-2)); System.out.println("test2 : "+isMirrorNum(12)); System.out.println("test3 : "+isMirrorNum(69)); System.out.println("test4 : "+isMirrorNum(609)); System.out.println("test5 : "+isMirrorNum(69018)); } public static boolean isMirrorNum( int num){ if (num < 0) return false; int tmp = num; int res = 0; while(tmp > 0){ int cur = tmp%10; tmp = tmp/10; cur = rotate(cur); if(cur == -1){ return false; } res=res*10+cur; } return res == num; } public static int rotate(int cur){ switch (cur){ case 6: return 9; case 9: return 6; case 0: return 0; case 1: return 1; case 8: return 8; default: return -1; } }}

NO.7

检查一个字符串是否包含k位a进制数的所有表示形式。

保证原字符串的所有字串都是合法的k位a进制数。"00110, a=2, k=2" => true （包括了00，01，10，11）

Brute Force:

public class Solution{ public static void main(String[] args){ System.out.println(containNum("00110", 2, 2)); System.out.println(containNum("00110", 3, 2)); System.out.println(containNum("112020012210", 3, 2)); } public static boolean containNum(String str, int a, int k){ HashSet<String> table = generateSet(a,k); for(int i=0; i<str.length()-k+1; i++){ if(table.contains(str.substring(i,i+k))){ System.out.println(str.substring(i,i+k)); table.remove(str.substring(i,i+k)); } } if(table.isEmpty()){ return true; } return false; } private static HashSet<String> generateSet(int a, int k){ ArrayList<String> list = new ArrayList<String>(); for(int i=0; i<k; i++){ ArrayList<String> list2 = new ArrayList<String>(); if( i == 0){ for(int j=0 ;j < a; j++){ String tmp = ""+j; list2.add(tmp); } }else{ for(String tmp : list){ for(int j=0 ;j < a; j++){ String tmp2 = tmp+j; list2.add(tmp2); } } } list = list2; } HashSet<String> table = new HashSet<String>(); for(String tmp : list){ table.add(tmp); } return table; }}

NO.8

检查一个字符串是否包含k位a进制数的所有表示形式。

保证原字符串的所有字串都是合法的k位a进制数。"00110, a=2, k=2" => true （包括了00，01，10，11）

Brute Force:

Page updated

Google Sites

Report abuse