Summer Lec 1-3

发表于   |   分类于 ，   |     |   阅读次数

§Lec 1 - Trie / Prefix Tree

§Materials

https://en.wikipedia.org/wiki/Trie

https://www.geeksforgeeks.org/trie-insert-and-search/

PPT

§Tries

  • Variable length keys

  • The decision on what path to follow is taken based on portion of the key

  • Static environment, fast retrieval but large space overhead

  • Applications: dictionaries, text searching

  • Trade space for runtime

  • Costly operation to build Trie: assume updating or rebuilding is rare

§Problem

§Implement Trie (Prefix Tree)

  • Use Array/HashMap

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class TrieNode{
        //boolean isWord;
        //String word; //pointer to word
        List<String> words; //contains pointers to passing words
        //TrieNode[] children;
        Map<Character, TrieNode> children;
        
        public TrieNode(){
            this.children = new HashMap<>();
        }
    }

  • In trie implementation, we should confirm that we have frequent search but less frequent add operation

  • 谷歌变种

    • compress: apply, apple; a->p->p->l->… => app->…
    • compound word: cat, copy, copycat; root->cat, root->copy->cat=> copy -back-> cat
§Longest Word in Dictionary
1
2
3
4
5
6
7
8
9
int index = -1; //4bits, save space than pointer(use string, 4bits-32 / 8bits-64) 
/*
=> space improvement: boolean isWord; 
public String dfs(TrieNode cur, StringBuilder temp, String[] ans)
temp.append(entry.getKey());
dfs
temp.deleteCharAt(temp.length()-1);// restore 
*/
cur = cur.children.computeIfAbsent(c, k -> new TrieNode()); //if c not exist, return k
§Runtime

Trie1， boolean isWord， 需要StringBuilder，平均每个node有k child，有l层

Tire2， Stirng word，same runtime

Tire3，List words.，最耗空间，runtime最快，不需要dfs

1
2
3
4
5
6
7
8
apple
->a*->ap*->...(n-1)
->*e->*le->...
->a*e
	->ap*e->app*e->...(n-2)
    ->a*le->a*ple->...
    ->ap*le
    	->...
1
2
3
4
5
6
7
8
space:
n is avg length of one word O(n)
only prefix/only suffix: (n-1) +  n-3 + … -> O(n^2)
prefix+suffix: O(n)
m words with avg length of n
worst case => no overlapping => O(m*n^2)

本题，Trie 的每一个 TrieNode 对应的是 Prefix+Suffix 的一种组合并不是某一个word或几个words

https://leetcode.com/problems/map-sum-pairs/

https://leetcode.com/problems/word-search-ii/

§Lec 2/3 - Graph: Graph Search, Union Find & Topological Sort

§Materials

Graph: Data Structure and Algorithms

Graph and Its Representations

Topological Sorting

§Graph

edges, Adjacency Matrix, Adjacency List (use map)

§Problem

§谷歌难题：maximum number of edges in graph without a cycle

undirected graph, n vertexes: n-1

directed graph, n vertexes: n-1 + n-2 + … + 1 = (n-1)n/2

Number of Connected Components in an Undirected Graph

//bfs. iterate: use heap

//dfs. recursive: stack overflow

//union-find: less memory

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
//dfs | bfs
class Solution {
public:
    void dfs(vector<vector<int>>& adjL, vector<bool>& visited, int cur, int& res){
        visited[cur] = true;
        for (auto v : adjL[cur])
            if (!visited[v])
                dfs(adjL, visited, v, res);
    }
    int countComponents(int n, vector<pair<int, int>>& edges) {
        //adjlist
        vector<vector<int>> adjL = vector<vector<int>>(n,vector<int>(0));
        for (auto edge:edges){
            adjL[edge.first].push_back(edge.second);
            adjL[edge.second].push_back(edge.first);
        }
        vector<bool> visited = vector<bool>(n, false);
        int res = 0;
        
        //dfs
        for (int i = 0; i < n; ++i)
            if (!visited[i])
                dfs(adjL, visited, i, ++res);
        
        //bfs
        vector<bool> visited = vector<bool>(n, false);
        int cur, visitedN = 0;
        queue<int> q;
        while (!q.empty() || visitedN!=n){
            if (q.empty()){
                for (int i = 0; i < n; ++ i)
                    if (!visited[i]){
                        cur = i;
                        ++ res;
                        break;
                    }
            }
            else{
                cur = q.front();
                q.pop();
                if (visited[cur])
                    continue;
            } 
            visited[cur] = true, ++visitedN;
            for (auto v : adjL[cur])
                q.push(v);
        }
        
        return res;
    }
};
//union-find
class Solution {
public:
    int find(vector<int>& par, int cur){
        return par[cur]==cur ? cur : par[cur] = find(par, par[cur]); //compress path
    }
    int countComponents(int n, vector<pair<int, int>>& edges) {
        //union-find
        vector<int> par(n);
        iota(begin(par), end(par), 0); //0..n-1
        for (auto edge:edges){
            int u = find(par, edge.first), v = find(par, edge.second);
            par[u] = v;
            n -= (v!=u);
        } 
        return n;
    }
};
§Clone Graph

Evalualte Division

FB&GG high frequency. 谷歌Variation: Currency Exchange

  1. Process equations and values to build graph
    numMap: map<string, map<string, double>>
    visitedSet: set<string>
    visitKey = num + “:” + denom //如果分子分母有:，这里handle
  2. Process query by the graph

Follow Up: currency rate update->concurrency同步->synchronization/multi-thread

ConcurrentHashMap - https://quip.com/aCoTAb1SQfnD - Lec 16: Multithreading (English)

CopyOnWroteMap (suit for write Rarely)

§Topological Sort

To create a topological sort from a DAG

  1. Remove vertex that has indegree of 0
  2. Update other indegrees of other vertices who are neighbors of removed vertex
  3. Go to 1

cyclic graph -> halt

Alien Dictionary

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
class Solution {
public:
    string alienOrder(vector<string>& words) {
        if (words.size()==0)
            return "";
        unordered_map<char, unordered_set<char>> map;
        unordered_map<char, int> degree;
        //build graph
        for (auto word:words)
            for (auto ch:word)
                degree[ch] = 0;
        for (int i = 0; i < words.size()-1; ++i){
            string cur = words[i];
            string next = words[i+1];
            int len = min(cur.length(),next.length());
            if (cur.length()>next.length() && cur.substr(0,len).compare(next)==0)
                return "";//illegal
            for (int j = 0; j < len; ++j){
                char c1 = cur[j], c2 = next[j];
                if (c1!=c2){
                    if (map.find(c1)==map.end())
                        map[c1] = unordered_set<char>(0);
                    if (map[c1].count(c2)==0){
                        map[c1].insert(c2);
                        degree[c2] += 1;
                    } 
                    break;
                }
            }
        }
        
        //topological
        string res = "";
        char ch;
        queue<char> q;
        for (auto itr = degree.begin(); itr != degree.end(); ++itr){
            if ((*itr).second == 0)
                q.push((*itr).first);
        }
        while (!q.empty()){
            ch = q.front();
            q.pop();
            res += ch;
            if (map.find(ch)!=map.end()){
                for (auto next:map[ch]){
                    degree[next] -= 1;
                    if (degree[next] == 0)
                        q.push(next);
                }
            }
        }
        if (res.length()!=degree.size()) // existcircle
            return "";
        return res;
    }
};

https://leetcode.com/problems/course-schedule/

https://leetcode.com/problems/course-schedule-ii/

§Union-Find
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
class UnionFind {
        int[] id, size;
        int count;
 
        public UnionFind(int len) {
            this.id = new int[len];
            this.size = new int[len];
            this.count = len;
        }
 
        public boolean find(int p, int q) {
            return root(p) == root(q);
        }
 
        public void union(int p, int q) {
            int pi = root(p), qi = root(q);
            if (this.size[pi] < this.size[qi]) {
                this.id[pi] = qi;
                this.size[qi] += this.size[pi];
            } else {
                this.id[qi] = pi;
                this.size[pi] += this.size[qi];
            }
            this.count--;
        }
 
        public int root(int i) {
            while (i != id[i]) {
                id[i] = id[id[i]]; // path compression
                i = id[i];
            }
            return i;
        }
    }

Graph Valid Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int find(vector<int>& par, int cur){
        return par[cur]==cur ? cur : par[cur] = find(par, par[cur]); //compress path
    }
    bool validTree(int n, vector<pair<int, int>>& edges) {
        vector<int> par(n);
        iota(begin(par), end(par), 0); //0..n-1
        for (auto edge:edges){
            int u = find(par, edge.first), v = find(par, edge.second);
            par[u] = v;
            if (v==u)
                return false; //circle
            n -= 1;
        } 
        return n==1;//connected
    }
};

Redundant Connection, Redundant Connection II

  1. If there is a node having two parents. Store them as candidates A and B, and set the second edge invalid.
    [5,1], 5 is parent of 1

  2. Perform normal union find.

    1. It is now valid tree => return candidate B.

    2. It is still not valid tree

      1. Candidates not existing => there is a loop, return current edge.
        [5,1],[1,2],[2,3],[3,4],[4,5], loop => current[4,5]
      2. Candidates existing => return candidate A instead of B.
        [1,5],[4,5],[1,2],[2,3],[3,4], 5 has 2 parents => remove[4,5]
        => union find, f(1)=5, f(2)=5, f(3)=5, f(4)=5, f(5)=5 => remove[1,5] instead

【Amazon-OA2面经】城市连接问题，即MST
给十几个城市供电，连接不同城市的花费不同，让花费最小同时连到所有的边。给出一系列connection类，里面是edge两端的城市名和它们之间的一个cost，找出要你挑一些边，把所有城市连接起来并且总花费最小。不能有环，最后所以城市要连成一个连通块。

Algorithm Steps: (Kruskal’s Algorithm)

  • Sort the graph edges with respect to their weights
  • Start adding edges to the MST from the edge with the smallest weight until the edge of the largest weight
  • Only add edges which doesn’t form a cycle , edges which connect only disconnected components
§Optimal Account Balancing, Social Network Graph Database

pre-process; non-zero debt -> 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
class Solution {
private:
    vector<int> debt;
public:
    int helper(int cur){
        while (cur < debt.size() && debt[cur]==0) 
            ++cur;
    	int res = INT_MAX;
    	for (int i = cur+1, prev = 0; i < debt.size(); ++i)
    	  if (debt[i] != prev && debt[i]*debt[cur] < 0){ // skip already tested or same sign debt
              debt[i] += debt[cur];
              res = min(res, helper(cur+1)+1);
              debt[i] -= debt[cur];
              prev = debt[i];
          }
    	return res < INT_MAX? res : 0;
    }
    int minTransfers(vector<vector<int>>& transactions) {
        unordered_map<int, long> balance; 
        for(auto t: transactions)
            balance[t[0]] -= t[2], balance[t[1]] += t[2];
        for(auto& b: balance) 
            if(b.second != 0)
                debt.push_back(b.second);
        return helper(0);
    }
};
§Minimum Height Tree

keep deleting leaves layer-by-layer, until reach the root.

Specifically, first find all the leaves, then remove them. After removing, some nodes will become new leaves. So we can continue remove them. Eventually, there is only 1 or 2 nodes left. If there is only one node left, it is the root. If there are 2 nodes, either of them could be a possible root.

Time Complexity: Since each node will be removed at most once, the complexity is O(n).

§Implement HashMap

https://www.geeksforgeeks.org/implementing-our-own-hash-table-with-separate-chaining-in-java/