Summer Lec 4-5

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

§Summer Lec 4: Special Data Structures

§problem

§Flatten 2D Vector
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
class Vector2D {
private:
    vector<vector<int>> vec2d;
    int rowIdx = 0, colIdx = 0;
public:
    Vector2D(vector<vector<int>>& vec2d) {
        this->vec2d = vec2d;
    }
    /*
    OR 
    vector<vector<int>>::iterator i, iEnd;
    vector<int>::iterator j;
    Vector2D(vector<vector<int>>& vec2d) {
        i = vec2d.begin();
        iEnd = vec2d.end();
    }
    */

    int next() {
        if (!hasNext())
            return NULL;
        else
            return vec2d[rowIdx][colIdx++];
    }

    bool hasNext() {
        while (rowIdx < vec2d.size()) {
            if (colIdx < vec2d[rowIdx].size())
                return true;
            colIdx = 0;
            ++rowIdx;
        }
        return false;
    }
};

/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D i(vec2d);
 * while (i.hasNext()) cout << i.next();
 */
§Follow up

Java:

runtiome Exception/unchecked, eg. throw new NoSuchElementException()

checked Exception -> catch or declare

Uber interview, Implement Token Bucket. eg.sleep throws InterruptedException

remove()

§Iterator Design Pattern in Java

implement next(), hasNext(), remove()

good for Lazy Loading: File I/O, DAO, Big Data

§pancake sort
§Max Chunks To Make Sorted, Max Chunks To Make Sorted II
§shallow copy / deep copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//sol 2
        // find (0..n)max/(n..0)min, if at this position, max <= min ->add chunk
        // max < min ->must add chunk, max == min->can add
        // a0[p0]a1[p1]a2...[pn-2]pn-1
        int n = arr.size(), res = 1;
        vector<int> maxN(n), minN(n);
        int maxn = maxN[0] = arr[0];
        int minn = minN[n-2] = arr[n-1];
        for (int i = 1; i < n-1; ++i)
            maxN[i] = maxn = max(maxn, arr[i]);
        for (int i = n-3; i >= 0; --i)
            minN[i] = minn = min(minn, arr[i+1]);
        for (int i = 0; i < n-1; ++i)
            if (maxN[i]<=minN[i])
                ++res;
§76. Minimum Window Substring
§380. Insert Delete GetRandom O(1), 381. Insert Delete GetRandom O(1) - Duplicates allowed

Load Balancer: Randomly choose a server. Runder Robin

Array: O(1) getRandom

HashMap: O(1) insert and remove

1
2
3
4
5
vector<int> nums;
unordered_map<int, int> map;

vector<pair<int,int>> nums; //<num,map-idx>
unordered_map<int, vector<int>> map; //num, nums-idxs

§Summer Lec 5: DP & Airbnb

§Dynamic programming

  1. Deduction formula
  2. Initialization
  3. Space improvement

§problem

§Edit Distance

#####Airbnb interview questions

  • K Edit Distance, KEditDistance.java: Trie + DP

    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
    class TrieNode{
    public:
    	vector<TrieNode*> child;
    	bool isEnd;
    	string word;
    	TrieNode(){
    		child.resize(26);
    		isEnd = false;
    		word = "";
    	}
    	~TrieNode(){
    		for (TrieNode *p : child)
    			if (p)
    				delete p;
    	}
    };
    class Solution {
    private:
    	void insert(string& word, TrieNode* root){
    		TrieNode* cur = root;
    		for (char c:word){
    			int i = c - 'a';
                if (cur->child[i] == NULL) 
                    cur->child[i] = new TrieNode();
                cur = cur->child[i];
    		}
    		cur->isEnd = true;
    		cur->word = word;
    	}
    	void dfs(TrieNode* cur, string& target, int k, vector<int>& dp, vector<string>& res){
    		int l = target.length();
    		if (cur->isEnd && dp[l] <= k)
    			res.push_back(cur->word);

    		vector<int> nextdp(l+1);
    		nextdp[0] = dp[0]+1;
    		for (int i = 0; i < 26; ++i)
    			if (cur->child[i]){
    				for (int j = 1; j <= l; ++j)
    				    //nextdp[j]: target j-1 ~ trie with c
    					if (target[j-1]-'a' == i)
    				        //dp[j-1]: taret j-2 ~ trie without c
    						nextdp[j] = dp[j-1];
    					else
    					    //taret j-2 ~ trie without c ; j-1 ~ without c, j-2 ~ with c
    					    //add c; replace one letter, convert c ~ target[j-1]; add target[j-1]
    					    nextdp[j] = min(min(dp[j-1],dp[j]),nextdp[j-1])+1;
    				dfs(cur->child[i], target, k, nextdp, res);
    			}
    	}
    public:
        /**
         * @param words: a set of stirngs
         * @param target: a target string
         * @param k: An integer
         * @return: output all the strings that meet the requirements
         */
        vector<string> kDistance(vector<string> &words, string &target, int k) {
            TrieNode* root = new TrieNode();
    		int l = target.length();
    		for (string& word:words){
    			//prune
    			//if (word.length() <= l+k && word.length() >= l-k)
    				insert(word,root);
    		    
    		}
    		vector<int> dp(l+1);
    		iota(dp.begin(),dp.end(),0);
            vector<string> res;
            dfs(root, target, k, dp, res);
    		delete root;
    		return res;
        }
    };

    ​

  • Cheapest Flights within K Stops, CheapestFlightsWithinKStops.java

    • Follow up: output the route
§221. Maximal Square

DP

§85. Maximal Rectangle, 764. Largest Plus Sign

§stack/string : Basic Calculator

§224. Basic Calculator, 227. Basic Calculator II
§772. Basic Calculator III
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
class Solution {
public:
    //res pre op num/() ch
    int calculate(string s) {
        s = "+("+s+")++";
        stack<int> stRes;
        stack<int> stPre; //pre num
        stack<char> stOp;
        int res = 0, pre = 0, num = 0;
        char op = '+';
        for (char ch : s){
            if (isdigit(ch))
                num = num*10 + ch-'0';
            else if (ch!=' '){
                if (ch == '('){
                    stRes.push(res), res = 0;
                    stPre.push(pre), pre = 0;
                    stOp.push(op), op = '+';
                }
                else if (ch ==')'){
                    if (op=='+' || op=='-')
                        num = res + pre + (','-op)*num;
                    else if (op=='*')
                        num = res + pre*num;
                    else if (op=='/')
                        num = res + pre/num;
                    res = stRes.top(), stRes.pop();
                    pre = stPre.top(), stPre.pop();
                    op = stOp.top(), stOp.pop();
                }
                else {
                    if (op=='+' || op =='-'){
                        res += pre;
                        pre = (','-op)*num;
                    }
                    else if (op=='*')
                        pre *= num;
                    else if (op=='/')
                        pre /= num;

                    op = ch;
                    num = 0;
                }
                //cout << res <<","<< pre <<","<< num <<","<< op <<endl;
            }
        }
        return res;
    }
};
§770. Basic Calculator IV - undo