Graph Theory I

 BLANK

1.Topology sort
2.Course Schedual
3.Alien Dictionary

1.Topology sort

127. Topological Sorting

Here we need to keep two important order:

  • Partial order: the order in one full path
  • Total order: the order among paths

DFS

Classic topology sort:

  1. Call DFS(Node) from start node to traverse the node and its neighbour
  2. After traverse this node and its neibours, insert the node into the front of result list
  3. return the final result list
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */    
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        // write your code here
        ArrayList<DirectedGraphNode> list = new ArrayList<DirectedGraphNode>();
        HashSet<DirectedGraphNode> set = new HashSet<DirectedGraphNode>();
        // Use set to flag the visit condition
 
        for(DirectedGraphNode root : graph){
            if(!set.contains(root)) dfs(list, set, root);
        }
        // 现在的 list 是由若干个顺序倒转的 topological order list 组成的
        // 这里的处理类似于 reverse words in a string
        // 把每个单词单独翻转之后,再把整个句子翻转
        // Collections.reverse(list);
 
        return list;
    }
 
    private void dfs(ArrayList<DirectedGraphNode> list, 
                     HashSet<DirectedGraphNode> set, 
                     DirectedGraphNode root){
        set.add(root);
 
        for(DirectedGraphNode node : root.neighbors){
            if(!set.contains(node)) dfs(list, set, node);
        }
        // 到这一步,root 节点的所有 sub path 都已经被访问过了
        // 最后才在 list 中添加元素,得到的是一个反序的 topological order
        list.add(0,root);
    }
}

Here is a notice:
Generally, you’d better use linkedList in java for reducing comsumption of addFirst(). In terms of this problem, a good try is addLast() and reverse() for ArrayList class.

BFS

Classic topology sort:

  1. Use map to store the indegree of all nodes
  2. Travese all start nodes and put the node with indegree = 0 in to queue and list
  3. poll queue and traverse all neighbours and decrese their degree
  4. when node’e indegree equals to 0 and put it into list and queue
  5. loop 3~4 until the queue is empty
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Solution {
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */    
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        // write your code here
        ArrayList<DirectedGraphNode> list = new ArrayList<DirectedGraphNode>();
 
        // Key : node
        // Value : current in-degree count
        HashMap<DirectedGraphNode, Integer> map = new HashMap<>();
        for(DirectedGraphNode node : graph){
            for(DirectedGraphNode neighbor : node.neighbors){
                map.put(neighbor, map.getOrDefault(neighbor, 0)+1);
            }
        }
 
        // Now we know each node's in-degree (out is trivial)
        Queue<DirectedGraphNode> queue = new LinkedList<>();
 
 
        for (DirectedGraphNode node : graph){
            // get all nodes without indegree
            // in othre words, indegree = 0
            if(!map.containsKey(node)){
                queue.offer(node); // queue keep the BFS path
                list.add(node); // list keeps the answer
            }
        }// not all start node with indegree = 0
 
        while(!queue.isEmpty()){
            DirectedGraphNode node = queue.poll();
            for(DirectedGraphNode next : node.neighbors){
                // node "next"'s parent has been processed
                map.put(next, map.get(next) - 1);
                if(map.get(next) == 0){ // Here is heirachy traversal for graph
                    list.add(next);
                    queue.offer(next);
                } 
            }
        }
 
        return list;
    }
}

2.Course Schedual

207. Course Schedule

A detailed blog has been recored here!

DFS

In fact, this problem is the same as check DAG. Overall algorithm seems like backtrack.

  1. Convert adjacency array to adjacency list
  2. Call DFS(), if it visits visited node, returns false, else, returns true
  3. After calling DFS(), reset the current node to non-visited
  4. Traverse all nodes, if there is any one node which returns false, it will return false, verse, true.

BFS

BFS is generally the same as topology sort, but you need to maintain an variable to count the number of nodes with indegree = 0.

210. Course Schedule II

In fact, the problem just requires to get a topological sort for a DAG! In a way, this is just topological sort with possibility of existing cycle.

BFS

Almost the same with BFS course schedual I. Just maintain a result array to record the the node when count increcement itself!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] res= new int[numCourses];
        Arrays.fill(res,-1);
        ArrayList[] graph = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];
        int index = 0;
 
        for(int i = 0; i < numCourses; i++){
            graph[i] = new ArrayList<Integer>();
        }
 
        for(int[] num : prerequisites){
            int parent = num[1];
            int child = num[0];
            graph[parent].add(child);
            indegree[child] ++; 
        }
 
        Queue<Integer> queue = new LinkedList<>();
 
        for(int i = 0; i < numCourses; i++){
            if(indegree[i] == 0){
                queue.offer(i);
                res[index++] = i;
            }
        }
 
        while(!queue.isEmpty()){
            int cur = queue.poll();
            for(int i = 0; i < graph[cur].size(); i++){
                int next = (int) graph[cur].get(i);
                indegree[next] --;
                if(indegree[next] == 0){
                    queue.offer(next);
                    res[index++] = next;
                }
            }
        }
        if(res[numCourses-1] == -1){
            return new int[0];
        }
        return res;
    }
}

DFS

Almost the same as DFS topology sort! Another condition needs to be labeled to check if there is loop in this graph.
Keep the right path information in stack for the recursive ask us to store the path in reversed order, sort of from root to leaf.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // make the adjacency list
        ArrayList<Integer>[] arr = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++) 
            arr[i]  = new ArrayList<>();
 
        for (int[] pair : prerequisites) 
            arr[pair[1]].add(pair[0]);
 
        int[] visited = new int[numCourses];
        // visit array
        // value = 0: not visited
        // value = 1: visited
        // value = 2: find loop 
 
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < numCourses; i++) {
            if (!topologicalSort(arr, i, stack, visited)) 
                //if returns false
                return new int[0];
        }
        int index = 0;
        int[] result = new int[numCourses];
        while (!stack.isEmpty()) {
            result[index++] = stack.pop();
        }
        return result;
    }
 
    private boolean topologicalSort(ArrayList<Integer>[] arr, int v, Stack<Integer> stack, int[] visited) {
        if (visited[v] == 1) //flag if a visit in another path, no need to traverse
            return true;
        if (visited[v] == 2) //flag if another visit in the same path, there is loop
            return false;
        visited[v] = 2;
        for (Integer u : arr[v]) {
            if (!topologicalSort(arr, u, stack, visited)) 
                return false;
        }
        visited[v] = 1; //backtrack, return the lable as visited
        stack.push(v); // push to stack, it is a reversed sequence
        return true;
    }
}

3.Alien Dictionay

269. Alien Dictionary

Almost the same as Course Schedual II, however, this problem requires to build graph on youe own and do topological sort.

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
    // adjacency matrix 
    public String alienOrder(String[] words) {
        boolean[][] graph = new boolean[26][26];
        int[] visited = new int[26];
        buildGraph(words, graph, visited);
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            if (visited[i] == 0) {
                if (!dfs(graph, visited, i, sb)) return "";
            }
        }
        return sb.reverse().toString();
    }
 
    // three state visit DFS (possibly not DAG)
    private boolean dfs(boolean[][] graph, int[] visited, int i, StringBuilder ret) {
        if (visited[i] == 2) return false;
        if (visited[i] == 1) return true;
        visited[i] = 2;
        boolean[] temp = graph[i];
        for (int j = 0; j < temp.length; j++) {
            if(temp[j] && !dfs(graph, visited, j, ret)){
                return false;              
            }
        }
        visited[i] = 1;
        ret.append((char)(i + 'a'));
        return true;
    }
 
    private void buildGraph(String[] words, boolean[][] graph, int[] visited) {
        Arrays.fill(visited, -1);
        // flag all appearing character 
        for (String word : words) {
            for (char c : word.toCharArray()) {
                visited[c - 'a'] = 0;
            }
        }
 
        for (int i = 1; i < words.length; i++) {
            int[] pair = find(words[i-1], words[i]);
            if(pair[0] != -1){
                graph[pair[0]][pair[1]] = true;
            }
        }
    }
 
    private int[] find(String s1, String s2){
        int index = 0;
        while(index < s1.length() && index < s2.length()){
            if(s1.charAt(index) != s2.charAt(index)){
                return new int[]{s1.charAt(index) -'a', s2.charAt(index) -'a'};
            }
            index ++;
        }
        return new int[]{-1, -1};
    }
}

BFS

Also we can use adjacency list, for example, HashMap>.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
    // adjacency matrix 
    public String alienOrder(String[] words) {
        boolean[][] graph = new boolean[26][26];
        int[] indegree = new int[26];
        StringBuilder sb = new StringBuilder();
        buildGraph(words, graph, indegree);
 
        Queue<Integer> queue = new LinkedList<>();
 
        for(int i = 0; i < 26; i++){
            if(indegree[i] == 0){
                queue.offer(i);
            }
        }
        //System.out.println(queue);
        while(!queue.isEmpty()){
            int cur = queue.poll();
            sb.append((char) ('a'  + cur));
            for(int i = 0; i < 26; i++){
                if(graph[cur][i]){
                    indegree[i] --;
                    if(indegree[i] == 0){
                        queue.offer(i);
                    }                    
                }
            }
        }        
        for (int d : indegree) {
            if (d > 0) {
                return "";
            }
        }  
        return sb.toString();       
    }
 
    // For BFS, the graph and indegree are required 
    private void buildGraph(String[] words, boolean[][] graph, int[] indegree) {
        Arrays.fill(indegree, -1);
        // flag all appearing character 
        for (String word : words) {
            for (char c : word.toCharArray()) {
                indegree[c - 'a'] = 0;
            }
        }
 
        for (int i = 1; i < words.length; i++) {
            int[] pair = find(words[i-1], words[i]);
            if(pair[0] != -1){
                if(!graph[pair[0]][pair[1]])
                    indegree[pair[1]] ++;  // prevent a -> b occur twice or more and count for indegree wrongly
                graph[pair[0]][pair[1]] = true;
            }
        }
    }
 
    private int[] find(String s1, String s2){
        int index = 0;
        while(index < s1.length() && index < s2.length()){
            if(s1.charAt(index) != s2.charAt(index)){
                return new int[]{s1.charAt(index) -'a', s2.charAt(index) -'a'};
            }
            index ++;
        }
        return new int[]{-1, -1};
    }
}

Concentration is important! Daily notes!

LC442,

1.SQL
2. Array
3. Math
4. String

1.SQL

178. Rank Scores

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Write your MySQL query statement below
 
SELECT
  Score,
  @rank := @rank + (@prev <> (@prev := Score)) Rank
FROM
  Scores,
  (SELECT @rank := 0, @prev := -1) init  # this is for value initialization
ORDER BY Score desc
 
# := is for assigning value while = is for checking equivalence
 
SELECT
  Score,
  (SELECT count(distinct Score) FROM Scores WHERE Score >= s.Score) Rank
FROM Scores s
ORDER BY Score desc
 
# Here is a tricky part: the s the same as Scores however, int the WHERE clause, Score is Scores.Scores 
# while s copy another same table
 
 
SELECT
  Score,
  (SELECT count(*) FROM (SELECT distinct Score s FROM Scores) tmp WHERE tmp.s >= Scores.Score) Rank
FROM Scores
ORDER BY Score desc
 
# count(*) return the number of tuples in one table
# As is eliminated and derived tables must have alias name
 
SELECT s.Score, count(distinct t.score) Rank
FROM Scores s JOIN Scores t ON s.Score <= t.score
GROUP BY s.Id
ORDER BY s.Score desc
 
# Here is one-to-many self-join
# Use group and count to get the amount of higher scores

2.Array

280. Wiggle Sort

One-pass reorder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    // in fact, this is greedy algorithm: always keep the three element window in specific order
    public void wiggleSort(int[] nums) {
        for(int i=0; i<nums.length; i++)
            if(i%2 == 1){ 
                // means even index (in fact, form zeor instead of one)
               if(nums[i-1] > nums[i]) 
                   swap(nums, i, i-1);
            }else{
                // odd order
                if(i!=0 && nums[i-1]<nums[i]) 
                    swap(nums, i, i-1);                
            }
    }
 
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Use Sort()

In-place but O(nlogn) time complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public void wiggleSort(int[] nums) {
        Arrays.sort(nums);
        for(int i = 1; i<nums.length; i+=2){
            if(i+1 < nums.length){
                swap(nums, i, i+1);
            }
        }   
    }
 
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

3.Math

390. Elimination Game

Use varibale to simulate

Time: O(logn)
Space: Constant

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int lastRemaining(int n) {
        boolean left = true;
        int remaining = n;
        int step = 1;
        int head = 1;
        while (remaining > 1) {
            if (left || remaining % 2 ==1) {
                head = head + step;  
                //head means the left head of this array after this round deletion
            }
            remaining = remaining / 2;
            step = step * 2;
            left = !left;
        }
        return head;
    }
}

Elegant one and faster!

Time: O(logn)
Space: O(logn)
A detailed proof can be referred here!

1
2
3
4
5
class Solution {
    public int lastRemaining(int n) {
        return n == 1 ? 1 : 2*( 1 + n/2 - lastRemaining(n/2));
    }
}

4.String

395. Longest Substring with At Least K Repeating Characters

Divide and conquer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int longestSubstring(String s, int k) {
        // use divide and conquere, each time we eliminate the character
        // that doesn't have enough count.
        if (s.length() < k) return 0;
        int[] count = new int[128];
        for (int i =  0;  i < s.length(); i++) {
            count[s.charAt(i)]++;
        }
        int begin = 0, res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (count[s.charAt(i)] < k) {
                res = Math.max(res, longestSubstring(s.substring(begin, i), k));
                begin = i + 1;
            }
        }
        if (begin == 0) return s.length();
        res = Math.max(res, longestSubstring(s.substring(begin, s.length()), k));
        return res;
    }
}

Step for coding! Daily notes!

 BLANK

1. DP
2. Math
3. String

1. DP

72. Edit Distance

Notice: There is relationship with shortest edit distance and longest common sequence.

DP

Time complexity: O(mn)
Space Complexity: O(mn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m+1][n+1];
        for(int i=1; i<=m; i++) dp[i][0] = i;
        for(int j=1; j<=n; j++) dp[0][j] = j;
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                if(word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i][j-1], dp[i-1][j])) + 1;
                }
            }
        }
        return dp[m][n];
    }
}

Recursion

Time complexity: O(3^n) (n means the Max(m, n); 3 means 3 edit operations)
Space Complexity: O(n)
This is a time-limit-exceeded version:
DP use table to record the path information, while recurssion requires to traverse to the base by times.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minDistance(String word1, String word2) {
        return editDist(word1, word2, word1.length(), word2.length());
    }
 
 
    public int editDist(String str1 , String str2 , int m ,int n){
        if (m == 0) return n;
        if (n == 0) return m;
        if (str1.charAt(m-1) == str2.charAt(n-1))
            return editDist(str1, str2, m-1, n-1);
        return 1 + min (editDist(str1,  str2, m, n-1),    // Insert
                        editDist(str1,  str2, m-1, n),   // Remove
                        editDist(str1,  str2, m-1, n-1) // Replace                     
                        );
    }
 
    public int min(int x,int y,int z){
        if (x<=y && x<=z) return x;
        if (y<=x && y<=z) return y;
        else return z;
    }    
}

2. Math

335. Self Crossing

We have to analyze the scenatios which leads to crossing since the scenarios are finite for this problem. It is not that classic!
Time complexity: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Categorize the self-crossing scenarios, there are 3 of them: 
 * 1. Fourth line crosses first line and works for fifth line crosses second line and so on...
 * 2. Fifth line meets first line and works for the lines after
 * 3. Sixth line crosses first line and works for the lines after
 *
 *      --- Thanks for answer from KuangYuan --
 **/
public class Solution {
    public boolean isSelfCrossing(int[] x) {
        int l = x.length;
        if(l <= 3) return false;
 
        for(int i = 3; i < l; i++){
            if(x[i] >= x[i-2] && x[i-1] <= x[i-3]) 
                return true;  //Fourth line crosses first line and onward
            if(i >=4){
                if(x[i-1] == x[i-3] && x[i] + x[i-4] >= x[i-2]) 
                    return true; // Fifth line meets first line and onward
            }
            if(i >=5){
                if(x[i-2] - x[i-4] >= 0 && x[i] >= x[i-2] - x[i-4] && 
                   x[i-1] >= x[i-3] - x[i-5] && x[i-1] <= x[i-3]) 
                    return true;  // Sixth line crosses first line and onward
            }
        }
        return false;
    }
}

3. String

336. Palindrome Pairs

My own imlementation — based on hashmap

Chinese Version:
预处理所有单词,从左到右判断Pali。如果是,后半部分单词保存在hashmap,一旦完成单词是该部分的reverse,记为一个组合;
相反的,从右到左判断pali,如果是,前半部分保存在hashmap,一旦完成单词是该部分的reverse,记为一个组合。
特别的一点,从右到左时,完整的word不应当保存,以保证数据的单一性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> res = new LinkedList<>();
        helper(words, res);
        helper2(words, res);
        return res;
 
    }
 
    public void helper(String[] words, List<List<Integer>> res){
        HashMap<String, List<Integer>> map = new HashMap<>();
        for(int i = 0; i<words.length; i++){
            for(String str : preProcess(words[i])){
                if(map.containsKey(str)){
                    map.get(str).add(i);
                }else{
                    map.put(str, new LinkedList<Integer>());
                    map.get(str).add(i);
                }
            }
        }
        for(int i = 0; i<words.length; i++){
            StringBuilder sb = new StringBuilder(words[i]);
            String word = sb.reverse().toString();
            if(map.containsKey(word)){                
                for(int j : map.get(word)){
                    if(i != j){
                        List<Integer> list  =new LinkedList<Integer>();
                        list.add(i);
                        list.add(j);
                        res.add(list);
                    }
                }
            }
        }        
    }
 
    public void helper2(String[] words, List<List<Integer>> res){
        HashMap<String, List<Integer>> map = new HashMap<>();
        for(int i = 0; i<words.length; i++){
            for(String str : preProcess2(words[i])){
                if(map.containsKey(str)){
                    map.get(str).add(i);
                }else{
                    map.put(str, new LinkedList<Integer>());
                    map.get(str).add(i);
                }
            }
        }
        for(int i = 0; i<words.length; i++){
            StringBuilder sb = new StringBuilder(words[i]);
            String word = sb.reverse().toString();
            if(map.containsKey(word)){                
                for(int j : map.get(word)){
                    if(i != j){
                        List<Integer> list  =new LinkedList<Integer>();
                        list.add(j);
                        list.add(i);
                        res.add(list);
                    }
                }
            }
        }        
    }    
 
    public List<String> preProcess(String str){
        List<String> list = new LinkedList<>();
        list.add(str);
        for(int i =1; i<=str.length(); i++){
            if(valid(str.substring(0,i))){
                list.add(str.substring(i));
            }
        }
        return list;
    }
 
    public List<String> preProcess2(String str){
        List<String> list = new LinkedList<>();
        // list.add(str);
        for(int i =str.length()-1; i>=0; i--){
            if(valid(str.substring(i))){
                list.add(str.substring(0,i));
            }
        }
        return list;
    }
 
 
    public boolean valid(String str){
        int lo = 0;
        int hi = str.length() -1;
        while(lo < hi){
            if(str.charAt(lo) != str.charAt(hi)){
                return false;
            }
            lo ++;
            hi --;
        }
        return true;   
    }
}

Hashmap-based elegant answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> ret = new ArrayList<>(); 
        if (words == null || words.length < 2) return ret;
        Map<String, Integer> map = new HashMap<String, Integer>();
        for (int i=0; i<words.length; i++) map.put(words[i], i);
        for (int i=0; i<words.length; i++) {
            for (int j=0; j<=words[i].length(); j++) { // notice it should be "j <= words[i].length()"
                String str1 = words[i].substring(0, j);
                String str2 = words[i].substring(j);
                // word = str1 + str2
 
                if (valid(str1)) {
                    String str2rvs = new StringBuilder(str2).reverse().toString();
                    if (map.containsKey(str2rvs) && map.get(str2rvs) != i) {
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(map.get(str2rvs));
                        list.add(i);
                        ret.add(list);
                    }
                }
                if (valid(str2)) {
                    String str1rvs = new StringBuilder(str1).reverse().toString();
                    // check "str.length() != 0" to avoid duplicates
                    // Eliminate the scenario where the (word i, word j) appears twice 
                    if (map.containsKey(str1rvs) && map.get(str1rvs) != i && str2.length()!=0) { 
                        List<Integer> list = new ArrayList<Integer>();
                        list.add(i);
                        list.add(map.get(str1rvs));
                        ret.add(list);
                    }
                }
            }
        }
        return ret;
    }
 
    public boolean valid(String str){
        int lo = 0;
        int hi = str.length() -1;
        while(lo < hi){
            if(str.charAt(lo) != str.charAt(hi)){
                return false;
            }
            lo ++;
            hi --;
        }
        return true;   
    }
}

Trie-based answer

The fastest method, generally, tire requres two method, add() and get()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public class Solution {
    class TrieNode {
        TrieNode[] next;
        int index;
        List<Integer> list;
 
        TrieNode() {
            next = new TrieNode[26];
            index = -1;
            list = new ArrayList<>();
        }
    }
 
    public List<List<Integer>> palindromePairs(String[] words) {
        List<List<Integer>> res = new ArrayList<>();
 
        TrieNode root = new TrieNode();
        for (int i = 0; i < words.length; i++) addWord(root, words[i], i);
        for (int i = 0; i < words.length; i++) search(words, i, root, res);
 
        return res;
    }
 
    private void addWord(TrieNode root, String word, int index) { 
        // modify the value the root refer
        // but the root is different with the reference root in function palindromePairs()
        for (int i = word.length() - 1; i >= 0; i--) {
            int j = word.charAt(i) - 'a';
            if (root.next[j] == null) root.next[j] = new TrieNode();
            if (isPalindrome(word, 0, i)) root.list.add(index);
            root = root.next[j];
        }
 
        root.list.add(index);
        root.index = index;
    }
 
    private void search(String[] words, int i, TrieNode root, List<List<Integer>> res) {
        for (int j = 0; j < words[i].length(); j++) {
            // full word[i] word[j] is not covered here
            if (root.index >= 0 && root.index != i && isPalindrome(words[i], j, words[i].length() - 1)) {
                // root means "" (empty string)
                res.add(Arrays.asList(i, root.index)); // word[i] is splitted
            }
 
            root = root.next[words[i].charAt(j) - 'a'];
            if (root == null) return;
        }
         // full word[i] word[j] is covered here
        for (int j : root.list) { // word[j] is splitted
            if (i == j) continue;
            res.add(Arrays.asList(i, j));
        }
    }
 
    private boolean isPalindrome(String word, int i, int j) {
        while (i < j) {
            if (word.charAt(i++) != word.charAt(j--)) return false;
        }
 
        return true;
    }
}

Happy to come back here!

Since rejected by Facebook, I didn’t post anything on my blog. Now, there is no heavy coursework load or interview preparation pressure, and I can do something my own. Let’s begin with some leetcode coding problems!
1. Array
2. Tree

1. Array

561. Array Partition I

Sort

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        for(int i=0; i<nums.length; i+=2){
            count += nums[i];
        }
        return count;
    }
}

Like bucket sort?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int arrayPairSum(int[] nums) {
        int[] arr = new int[20001];
        int lim = 10000;
        for (int num: nums)
            arr[num + lim]++;
        int d = 0, sum = 0;
        for (int i = -10000; i <= 10000; i++) {
            sum += (arr[i + lim] + 1 - d) / 2 * i; //choose the ceiling value 
            d = (arr[i + lim] + d) % 2; //check current travesing number of values : odd or even
        }
        return sum;
    }
}

540. Single Element in a Sorted Array

Binary-search — naive implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int len = nums.length;
        int lo = 0;
        int hi = len;
        while(lo < hi){
            int mid = (lo + hi)/2;
            if(((mid -lo +1) % 2) == 0){
                if(nums[mid] == nums[mid-1]){
                    lo = mid +1;
                }else{
                    hi = mid;
                }
            }else{
                if(mid+1 < nums.length && nums[mid] == nums[mid+1]){
                    lo = mid +2;
                }else{
                    hi = mid;
                }                
            }
        }
        return nums[lo];
    }
}

Elegant one

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int singleNonDuplicate(int[] nums) {
        int n=nums.length, lo=0, hi=n/2;
        while (lo < hi) {
            int m = (lo + hi) / 2;
            if (nums[2*m]!=nums[2*m+1]) hi = m;
            else lo = m+1;
        }
        return nums[2*lo];
    }
}

2. Tree

388. Longest Absolute File Path

This is a very interesting problem, sort of like in-order of tree, however, we need to go to deeper step by step and have a fast return based on the number of ‘/t’
Time complexity: O(n)
Space complexity: O(logn)

Stack-based traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Stack-based tree traversal
 * different the depth computing methods
 **/
class Solution {
    public int lengthLongestPath(String input) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0); // "dummy" length
        int maxLen = 0;
        for(String s : input.split("\n")){
            int lev = s.lastIndexOf("\t") + 1; // number of "\t" ---  first index is 0 from the array
 
            while(lev+1<stack.size()){
                stack.pop(); // find parent
            } 
            int len = stack.peek() + s.length() - lev +1; // *- lev* remove "/t", *+1* means to add"/"
            stack.push(len);
            // check if it is file
            if(s.contains(".")) 
                maxLen = Math.max(maxLen, len-1);  // only count for file path
        }
        return maxLen;
    }
}

Array-based traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * better version 
 * Not use stack to trace information
 * Just use array to tracke the depth 
 * renew the array with backtrace
 * sort of like inorder trversal 
 **/
class Solution {
    public int lengthLongestPath(String input) {
        String[] paths = input.split("\n");
        int[] stack = new int[paths.length+1];
        int maxLen = 0;
        for(String s : paths){
            int lev = s.lastIndexOf("\t") + 1; 
            int curLen = stack[lev] + s.length() - lev + 1;
            stack[lev+1] = curLen;
 
            if(s.contains(".")) 
                maxLen = Math.max(maxLen, curLen-1);
        }
        return maxLen;
    }
}

Rejected by Facebook~

To be honest, I am a little sad to be rejected by Facebook. Anyway, thanks to Facebook, I find my weakness! As the interviewer from Facebook said, if you don’t know, don’t be sad, which means it is the edge of your knowledge! In fact, I had a poor performance in the interview, poor understanding, poor logic and poor oral English. Anyway, move on and keep fighting!

A note for linux troubleshooting! [updating]

Memory Usage

http://ju.outofmemory.cn/entry/252703

http://bencane.com/2012/08/06/troubleshooting-high-io-wait-in-linux/
Very good english tutorial of troubleshooting of high iOwait

http://www.cnblogs.com/mfryf/archive/2012/03/12/2392012.html
Not very good, but the check standard and idea is useful

https://unix.stackexchange.com/questions/92493/sorting-down-processes-by-memory-usage
Find the memory usage for all process

http://blog.csdn.net/lunar2000/article/details/404111
异常内存消耗问题的处理与观察

http://bert82503.iteye.com/blog/2296732
异常内存消耗实录

http://blog.yufeng.info/archives/2456
内存消耗综合分析

订正一个错误:
wait for io will largely comsume CPU resourses

IO Usage

http://coolnull.com/4444.html
A very good note of io usage probe

Security

https://segmentfault.com/a/1190000002554673
TLS-HTPPS加密

http://www.cnblogs.com/fanzhidongyzby/p/3250405.html
Buffer Overflow攻击

Kernel action

https://stackoverflow.com/questions/3479330/how-is-malloc-implemented-internally
How does malloc() work

Network

http://www.slashroot.in/how-does-traceroute-work-and-examples-using-traceroute-command
How does traceroute work

http://blog.csdn.net/justlinux2010/article/details/8522506
从网卡到TCP(Transport layer) 的包传递

https://www.gitbook.com/book/jerryc8080/understand-tcp-and-udp
TCP和UDP的基础知识

File System

http://blog.csdn.net/v_july_v/article/details/6530142
B+-Tree的文件系统的优势,写的一般,凑活看

http://nfs.sourceforge.net/nfs-howto/ar01s07.html
NFS troubleshooting

http://cn.linux.vbird.org/linux_server/0330nfs.php#What_NFS_perm
鸟叔私房菜——NFS篇章

http://www.porcupine.org/forensics/forensic-discovery/chapter3.html#figure3.2
Where is file name and directory is stored

Linux: ls hangs after NFS connection issues


NFS ls command hanging

Compiler

http://www.jianshu.com/p/84d96a6385b0
编译相关:link and load EFL

http://www.tenouk.com/Bufferoverflowc/Bufferoverflow1c.html
Detailed loading process

Cache

   

Linux Cache 机制探究


linux的cache机制

Others

   

   
https://www.youtube.com/watch?v=qHxO13i7Umc    
讲各种键盘符号的读法    

11/1/2017 Wendesday

 BLANK

1. Backtrack
2.

1. Backtrack

486. Predict the Winner

DFS – a general idea

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean PredictTheWinner(int[] nums) {
        return helper1(nums, 0, nums.length-1, 0, 0);
    }
 
    public boolean helper1(int[] nums, int i, int j, int play1, int play2){
        if(i > j) return play1 >= play2;
        return helper2(nums, i+1, j, play1+nums[i], play2) ||
            helper2(nums, i, j-1, play1+nums[j], play2);
    }
 
    public boolean helper2(int[] nums, int i, int j, int play1, int play2){
        if(i > j) return play1 >= play2;
        return helper1(nums, i, j-1, play1, play2+nums[j]) &&
            helper1(nums, i+1, j, play1, play2 + nums[i]);
    }    
}

2. Stack

402. Remove K Digits

Use array to simulate stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public String removeKdigits(String num, int k) {
        int digits = num.length() - k;
        char[] stack = new char[num.length()];
        int top = 0;
        // k keeps track of how many characters we can remove
        // if the previous character in stk is larger than the current one
        // then removing it will get a smaller number
        // but we can only do so when k is larger than 0
        for (int i = 0; i < num.length(); ++i) {
            char c = num.charAt(i);
            while (top > 0 && stack[top-1] > c && k > 0) {
                top--; // top the the high pointer which marks the stack top
                k--;  // k means the left number which needs to be deleted
            }
            stack[top++] = c;
        }
        // find the index of first non-zero digit
        int index = 0;
        while (index < digits && stack[index] == '0') index++; // mark the first non-zero digit
        return index == digits? "0": new String(stack, index, digits - index); // char[] to string
 
        // Very nice code!
    }
}

General Stack

public class Solution {
public String removeKdigits(String num, int k) {
if(num.length() == k) return “0”;
Deque stack = new LinkedList<>();
for(int i =0; i0 && !stack.isEmpty() && stack.peek() > c ){
//Attention: here must be while
stack.pop();
k–;
}
stack.push(c);
}
for(int i =0; i 1 &&(c = sb.charAt(sb.length()-1)) == ‘0’){
sb.deleteCharAt(sb.length()-1);
}
if(sb.length() == 0) return “0”;
return sb.reverse().toString();
}
}

10/31/2017 Tuesday

 BLANK

1. backtrack
2.

1. backtrack

386. Lexicographical Numbers

BFS

This implementation is a little trick! But it is fast than you use stack to trace the change.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> list = new ArrayList<>(n);
        int curr = 1;
        for (int i = 1; i <= n; i++) {
            list.add(curr);
            if (curr * 10 <= n) { // .. -> ..0
                curr *= 10;
            } else if (curr % 10 != 9 && curr + 1 <= n) {
                // increment curr form ..0 --> ..9
                curr++;
            } else {
                // from ..9 -> .. eg 119 -> 12 or 199 -> 2
                while ((curr / 10) % 10 == 9) {
                    curr /= 10;
                }
                curr = curr / 10 + 1;
            }
        }
        return list;
    }
}

DFS

This is a little loewer, but you can regard this solution as standard DFS solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> list = new LinkedList<>();
        for(int i =1; i<10; i++){
            DFS(list, i, n);
        }
        return list;
 
    }
 
    public void DFS(List<Integer> list, int num, int max){
        if(num > max) return;
        list.add(num);
        for(int i =0; i<=9; i++){  // here can add some prune
            DFS(list, num*10 + i, max);
        }
    }
}