Elements of Programming Interviews 白班编程记录，求挑刺求反馈

847. Shortest Path Visiting All Nodes
这是昨天写的，因为没有AC所以没有发上来（33/46 passed, TLE），看了答案之后发现整体思路和我的一样，区别在于查重的设计，我没有查重（因为不知道怎么做），而答案使用hashing path characteristics完成了查重，所以AC。对path的hash比较简单，我就不再这里写了。

我的TLE代码如下：

1. class Solution {
   
2. public:
   
3.     int shortestPathLength(vector<vector<int>>& graph) {
   
4.         /* 0. MISC */
   
5.         if(graph.size() < 2)return 0;
   
6.         
   
7.         /* 1. prep */
   
8.         int ans = INT_MAX;
   
9.         
   
10.         /* 2. key algo */
    
11.         for(int i = 0; i < graph.size(); ++i){
    
12.             ans = min(ans, SolutionStartHere(graph, i));
    
13.         }
    
14.             
    
15.         /* 3. answer */
    
16.         return ans;
    
17.     }
    
18.    
    
19.     int SolutionStartHere(const vector<vector<int> >& graph, int start){
    
20.         /* 0. MISC */
    
21.         if(graph.size() < 2)return 0;
    
22.         
    
23.         /* 1. prep */
    
24.         queue<pair<int, pair<int, unordered_set<int> > > > bfsQueue;
    
25.         bfsQueue.emplace(start,  pair<int, unordered_set<int> >(0, unordered_set<int>({start})) );
    
26.         
    
27.         /* 2. key algo */
    
28.         while(!bfsQueue.empty()){
    
29.             auto node = bfsQueue.front();
    
30.             bfsQueue.pop();
    
31.             
    
32.             int vertex = node.first;            
    
33.             for(int neighbor: graph[vertex]){
    
34.                 int pathLen = node.second.first;
    
35.                 unordered_set<int> visited = node.second.second;
    
36.                
    
37.                 visited.emplace(neighbor);
    
38.                 pathLen++;
    
39.                 if(visited.size() == graph.size())return pathLen;
    
40.                
    
41.                 bfsQueue.emplace(neighbor, pair<int, unordered_set<int> >(pathLen, visited) );
    
42.             }
    
43.         }
    
44.             
    
45.         /* 3. answer */
    
46.         return -1; /* error case */
    
47.     }
    
48.    
    
49.     int PickStart(const vector<vector<int> >& graph){
    
50.         int ans = 0, minEdge = graph[0].size();
    
51.         for(int i = 1; i < graph.size(); ++i){
    
52.             if(graph[i].size() < minEdge){
    
53.                 minEdge = graph[i].size();
    
54.                 ans = i;
    
55.             }
    
56.         }
    
57.         return ans;
    
58.     }
    
59. };

复制代码

924. Minimize Malware Spread
标准BFS/DFS，29分钟AC
还有一个解法是Union Find，不过我有些不想写，因为对union find概念不熟练

1. class Solution {
   
2. public:
   
3.     int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
   
4.         /* 0.MISC */
   
5.         
   
6.         /* 1. prep */
   
7.         sort(initial.begin(), initial.end());
   
8.         unordered_set<int> visited;
   
9.         int answer = -1;
   
10.         int maxNum = 0;
    
11.         
    
12.         /* 2. key algo */
    
13.         for(int num: initial){
    
14.             if(visited.find(num) != visited.end())continue;
    
15.             int sizeIsland = SizeIsland(graph, visited, num);
    
16.             if(sizeIsland > maxNum){
    
17.                 answer = num;
    
18.                 maxNum = sizeIsland;
    
19.             }        
    
20.         }
    
21.         
    
22.         /* 3. answer */
    
23.         return answer;
    
24.     }
    
25.    
    
26.     int SizeIsland(const vector<vector<int>>& graph, unordered_set<int>& visited, int start){
    
27.         /* 0.MISC */
    
28.         
    
29.         /* 1. prep */
    
30.         int answer = 0;
    
31.         
    
32.         queue<int> bfsQueue;
    
33.         bfsQueue.emplace(start);
    
34.         
    
35.         /* 2. key algo */
    
36.         while(!bfsQueue.empty()){
    
37.             int node = bfsQueue.front();
    
38.             bfsQueue.pop();
    
39.             ++answer;
    
40.             
    
41.             for(int neighbor = 0; neighbor < graph[node].size(); ++neighbor){
    
42.                 if(graph[node][neighbor] == 0)continue;
    
43.                 if(visited.find(neighbor) != visited.end())continue;
    
44.                
    
45.                 visited.emplace(neighbor);
    
46.                 bfsQueue.emplace(neighbor);
    
47.             }
    
48.         }
    
49.         
    
50.         /* 3. answer */
    
51.         return answer;
    
52.     }
    
53.    
    
54. };

复制代码

339. Nested List Weight Sum
DFS/BFS 12分钟AC

1. /**
   
2. * // This is the interface that allows for creating nested lists.
   
3. * // You should not implement it, or speculate about its implementation
   
4. * class NestedInteger {
   
5. *   public:
   
6. *     // Constructor initializes an empty nested list.
   
7. *     NestedInteger();
   
8. *
   
9. *     // Constructor initializes a single integer.
   
10. *     NestedInteger(int value);
    
11. *
    
12. *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
    
13. *     bool isInteger() const;
    
14. *
    
15. *     // Return the single integer that this NestedInteger holds, if it holds a single integer
    
16. *     // The result is undefined if this NestedInteger holds a nested list
    
17. *     int getInteger() const;
    
18. *
    
19. *     // Set this NestedInteger to hold a single integer.
    
20. *     void setInteger(int value);
    
21. *
    
22. *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
    
23. *     void add(const NestedInteger &ni);
    
24. *
    
25. *     // Return the nested list that this NestedInteger holds, if it holds a nested list
    
26. *     // The result is undefined if this NestedInteger holds a single integer
    
27. *     const vector<NestedInteger> &getList() const;
    
28. * };
    
29. */
    
30. class Solution {
    
31. public:
    
32.     int depthSum(vector<NestedInteger>& nestedList) {
    
33.         /* 0.MISC */
    
34.         
    
35.         /* 1. prep */
    
36.         queue<pair<vector<NestedInteger>, int> > bfsQueue;
    
37.         bfsQueue.emplace(nestedList, 1);
    
38.         int answer = 0;
    
39.         
    
40.         /* 2. key algo */
    
41.         while(!bfsQueue.empty()){
    
42.             auto node = bfsQueue.front();
    
43.             bfsQueue.pop();
    
44.             
    
45.             for(auto child: node.first){
    
46.                 if(child.isInteger())answer += (node.second) * (child.getInteger());
    
47.                 else bfsQueue.emplace(child.getList(), node.second + 1);
    
48.             }
    
49.         }
    
50.         
    
51.         /* 3. answer */
    
52.         return answer;
    
53.     }
    
54. };

复制代码

773. Sliding Puzzle (hard)
48分钟完成
相对典型的rule-based BFS，难度中等，难点在于代码细节
我的的代码比较慢，考虑可以使用的优化是增加heuristic然后采用A* search，不过不想实现了

1. class Solution {
   
2. public:
   
3.     int slidingPuzzle(vector<vector<int>>& board) {
   
4.         /* 0. MISC */
   
5.         if(IsSolved(board))return 0;
   
6.         
   
7.         /* 1. prep */
   
8.         unordered_set<string> visited;
   
9.         queue<pair<string, int>> bfsQueue;
   
10.         bfsQueue.emplace(Encode(board), 0);
    
11.         visited.emplace(Encode(board));
    
12.         
    
13.         /* 2. key algo */
    
14.         while(!bfsQueue.empty()){
    
15.             auto node = bfsQueue.front();
    
16.             bfsQueue.pop();
    
17.             
    
18.             auto nodeBoardStr = node.first;
    
19.             int nodeDist = node.second;
    
20.               
    
21.             for(auto childStr: Children(Decode(nodeBoardStr))){
    
22. 
    
23.                 if(visited.find(childStr) != visited.end())continue;
    
24.                 visited.emplace(childStr);
    
25.                 int childDist = nodeDist + 1;
    
26.                
    
27.                 if(childStr == "123450")return childDist;
    
28.                 bfsQueue.emplace(childStr, childDist);
    
29.             }
    
30.             
    
31.         }
    
32.         
    
33.         /* 3. answer */
    
34.         return -1; /* no solution */
    
35.     }
    
36.    
    
37.     vector<string> Children(vector<vector<int>> board){
    
38.         /* four side swap children generation */
    
39.         
    
40.         /* 0. MISC */
    
41.         
    
42.         /* 1. prep */
    
43.         vector<string> answer;
    
44.         
    
45.         /* 2. key algo */
    
46.         int zi, zj;
    
47.         bool noBreak = true;
    
48.         for(int i = 0; i < board.size() && noBreak; ++i){
    
49.             for(int j = 0; j < board[i].size() && noBreak; ++j){
    
50.                 if(board[i][j] == 0){
    
51.                     zi = i;
    
52.                     zj = j;
    
53.                     noBreak = false;
    
54.                 }
    
55.             }
    
56.         }
    
57.         
    
58.         vector<pair<int, int> > directions =
    
59.         {
    
60.             pair<int, int>(0, 1),
    
61.             pair<int, int>(0, -1),  
    
62.             pair<int, int>(1, 0),  
    
63.             pair<int, int>(-1, 0)  
    
64.         };
    
65.         
    
66.         for(auto dir: directions){
    
67.             int i_ = zi + dir.first, j_ = zj + dir.second;
    
68.             if(InRange(board, i_, j_)){
    
69.                 swap(board[zi][zj], board[i_][j_]);
    
70.                 answer.emplace_back(Encode(board));
    
71.                 swap(board[zi][zj], board[i_][j_]);
    
72.             }
    
73.         }
    
74.         
    
75.         /* 3. answer */
    
76.         return answer;
    
77.     }
    
78.    
    
79.     bool InRange(const vector<vector<int>>& board, int i, int j){
    
80.         return i >= 0 && i < board.size() && j >=0 && j < board[i].size();
    
81.     }
    
82.    
    
83.     bool IsSolved(const vector<vector<int> >& board){
    
84.         return (Encode(board) == "123450");
    
85.     }
    
86.    
    
87.     string Encode(const vector<vector<int> >& board){
    
88.         string ans;
    
89.         for(auto row: board){
    
90.             for(int c: row){
    
91.                 ans += to_string(c);
    
92.             }
    
93.         }
    
94.         return ans;
    
95.     }
    
96.    
    
97.     vector<vector<int> > Decode(const string& s){
    
98.         return {vector<int>({s[0]-'0', s[1]-'0', s[2]-'0'}),
    
99.                 vector<int>({s[3]-'0', s[4]-'0', s[5]-'0'})};
    
100.     }
     
101. };

复制代码

补充内容 (2018-12-5 09:27):
这道题的思路和楼上的LC847是一个类型，非常相似

OK, 事情在逐渐向预期的方向发展。现在有一些希望，也有一些问题，我要仔细分析一下如何解决这些问题。

主要矛盾是这个：我要通过Google的onsite interview，但是我准备的不够充分，感觉过不去，并且现在没有很强的动力准备面试。

对我有利的条件（希望）：
1. 我的面试准备模式一直就是针对Google的准备方针，集中精力攻算法，数据结构和白板模拟，所以我对这套规程比较熟练。
2. Google的面试点是Sunnyvale，根据我的猜测，比较大可能是GCP组，这个组在扩招，所以录取难度会低一点点，以及我已经对相关知识略有涉猎。
3. 尽管手里没有很好的offer，但是还是有一个用来保底的，这样的话我面试时可以保持心态稳定，不至于过度紧张而发挥失常。

对我不利的条件（困难）：
1. 有了一个保底的offer，整个人就咸鱼了，没有做题的动力，不像前几个月背水一战那种感觉
2. 最近有关面试的一堆事搞得我比较心力憔悴，状态一般，并不是思维最为敏锐的时候，并且最近两周刷题强度减弱，手感失掉了很多。
3. 只剩下6个整天可以准备了

我的方法：
1. 化保底offer为动力，动力来源就是我要拿到Google，然后互相compete，拿到更多的真金白银
2. 做白日梦，想象自己在google的相对愉快的工作
3. Take the advantage of sunk cost：我为了google已经准备了半年多了，这么辛苦的拿到onsite，不好好表现一把实在对不起自己过去的努力

实际操作：
1. 对于google，我还有两个大知识点没有强化，一个是DP，另一个是高频机经，小零碎知识点我就不再考虑了。
2. 对于DP，我感觉从今天开始，写8道经典旧DP，写8道medium-hard新DP，在过程中总结，大概是可以执行的并且有效果的强化训练。
3. 对于高频，我决定每天两题，每道题花2小时整透彻（自己想，看讨论，给出绝大部分讨论解的码）
4. 最后，每天2道随机medium-hard题目上白板限时模拟，熟悉感觉。
5. 好好睡觉，每天固定时间睡8小时15分钟
6. 闲时读书

676. Implement Magic Dictionary
随性的写了一道面经题，用prefix table模仿了trie结构，但是我的速度并没有提升很快。用时30分钟左右

1. class MagicDictionary {
   
2. public:
   
3.     /** Initialize your data structure here. */
   
4.     MagicDictionary() {
   
5. 
   
6.     }
   
7.    
   
8.     /** Build a dictionary through a list of words */
   
9.     void buildDict(vector<string> dict) {
   
10.         prefices.emplace("");
    
11.         suffices.emplace("");
    
12.         
    
13.         for(string word: dict){
    
14.             words.emplace(word);
    
15.             
    
16.             string prefix;
    
17.             for(char c: word){
    
18.                 prefix += c;
    
19.                 prefices.emplace(prefix);
    
20.             }
    
21.             
    
22.             string suffix;
    
23.             for(char c: string(word.rbegin(), word.rend())){
    
24.                 suffix += c;
    
25.                 suffices.emplace(suffix);
    
26.             }
    
27.         }
    
28.     }
    
29.    
    
30.     /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
    
31.     bool search(string word) {
    
32.         /* 0. MISC */
    
33.         
    
34.         /* 1. prep */
    
35.         string charSet = "abcdefghijklmnopqrstuvwxyz";
    
36.         string prefix = word, suffix;
    
37.         
    
38.         /* 2. key algo */
    
39.         for(int i = 0; i < word.size(); ++i){
    
40.             char curChar = prefix.back();
    
41.             prefix.pop_back();
    
42.             
    
43.             if(prefices.find(prefix) != prefices.end() &&
    
44.                suffices.find(suffix) != suffices.end()){
    
45.                 for(char c: charSet){
    
46.                     string combineWord = prefix + c + string(suffix.rbegin(), suffix.rend());
    
47.                     if(words.find(combineWord) != words.end() && c != curChar)return true;
    
48.                 }
    
49.             }
    
50.                
    
51.                
    
52.             suffix += curChar;
    
53.         }
    
54.         
    
55.         /* 3. answer */
    
56.         return false;
    
57.     }
    
58.    
    
59. private:   
    
60.     unordered_set<string> words;
    
61.     unordered_set<string> prefices;
    
62.     unordered_set<string> suffices;
    
63.    
    
64. };
    
65. 
    
66. /**
    
67. * Your MagicDictionary object will be instantiated and called as such:
    
68. * MagicDictionary obj = new MagicDictionary();
    
69. * obj.buildDict(dict);
    
70. * bool param_2 = obj.search(word);
    
71. */

复制代码

抱歉，发信息太耗大米，我得省着点花，就这里留言
--好的啊，两周后

GG高频题人车匹配基本版（无tie）
代码就不发了，120行C++，写了64分钟，其中花了30分钟编译。

大木虫 发表于 2018-12-9 06:43
GG高频题人车匹配基本版（无tie）
代码就不发了，120行C++，写了64分钟，其中花了30分钟编译。

总结一些问题：
1. 基本heap版本的代码还是太长了，解决方法是预设API和comparator但是不做implement。以及除去为了编译而加进去的headers和main，这样的话代码就缩到了45行。

2. c++ iterator的syntax长得太复杂，写起来容易让人找不清楚该写啥，容易出错。解决方法是手写速度减半，并且写完检查一遍，这个要作为开始coding是的TO-DO

3. 写之前想清楚代码流程细节，多花一些时间在这上面，可以提升写码速度，是赚的。

大木虫 发表于 2018-12-9 06:43
GG高频题人车匹配基本版（无tie）
代码就不发了，120行C++，写了64分钟，其中花了30分钟编译。

想了想，觉得没必要藏着掖着代码，一道题而已，欢迎大家讨论！

代码可以直接在terminal编译通过，欢迎下载测试

1. /*
   
2. We are looking at a global minimum case here. A person might not get the closest bike for him, but the sum of all person-bike pair is minimized.
   
3. 
   
4. Let’s use a heap to solve this problem.
   
5. 
   
6. Assuming that we can walk pass a person or a bike, then the person-bike distance is simply the Manhattan Distance given that the whole map has a grid representation.
   
7. 
   
8. This is a greedy approach, and it makes sense because a one match replaces only on other match, and a closer match is always better than an further match.
   
9. */
   
10. 
    
11. #include <vector>
    
12. #include <queue>
    
13. #include <utility>
    
14. #include <iostream>
    
15. #include <unordered_set>
    
16. 
    
17. using namespace std;
    
18. 
    
19. vector< pair<pair<int, int>, pair<int, int>> > MatchBike(const vector<string> & grid);
    
20. string Encode(const pair<int, int>& pos);
    
21. pair<int, int> Decode(const string& pos);
    
22. int Dist(const pair<int, int>& pos1, const pair<int, int>& pos2);
    
23. void PrintMatch(const vector< pair<pair<int, int>, pair<int, int>> >& match);
    
24. 
    
25. 
    
26. struct CompMatch{
    
27.     bool operator()(const pair<pair<int, int>, pair<int, int>>& match1,
    
28.                     const pair<pair<int, int>, pair<int, int>>& match2){
    
29.         return (    Dist(match1.first, match1.second) >
    
30.                     Dist(match2.first, match2.second) );
    
31.     }
    
32. };
    
33. 
    
34. int main(int argc, char const *argv[])
    
35. {
    
36.    
    
37.     vector<string> grid =
    
38.     {
    
39.         "B..P.",
    
40.         "..B..",
    
41.         "P....",
    
42.         "....P",
    
43.         "....B",
    
44.     };
    
45. 
    
46.     PrintMatch(MatchBike(grid));
    
47. 
    
48.     return 0;
    
49. }
    
50. 
    
51. vector< pair<pair<int, int>, pair<int, int>> > MatchBike(const vector<string> & grid){
    
52.     /* 0. MISC */
    
53. 
    
54. 
    
55.     /* 1. prep */
    
56.     vector< pair<pair<int, int>, pair<int, int>> > answer;
    
57.     unordered_set<string> people, bikes;
    
58.     for(unsigned int i = 0; i < grid.size(); ++i){
    
59.         for(unsigned int j = 0; j < grid[i].size(); ++j){
    
60.             if(grid[i][j] == 'B')bikes.emplace(move(Encode({i, j})));
    
61.             if(grid[i][j] == 'P')people.emplace(move(Encode({i, j})));
    
62.         }
    
63.     }
    
64. 
    
65.     priority_queue<pair<pair<int, int>, pair<int, int>>,
    
66.                    vector<pair<pair<int, int>, pair<int, int>>>,
    
67.                    CompMatch > matchPq;
    
68.    
    
69.     for(auto pItr = people.begin(); pItr != people.end(); ++pItr){
    
70.         for(auto bItr = bikes.begin(); bItr != bikes.end(); ++bItr){
    
71.             matchPq.emplace(move(Decode(*pItr)), move(Decode(*bItr)));
    
72.         }
    
73.     }
    
74. 
    
75.    
    
76.     /* 2. key algo */
    
77.     while(!people.empty()){
    
78.         auto match = matchPq.top(); matchPq.pop();
    
79. 
    
80.         string personStr = Encode(match.first);
    
81.         string bikeStr = Encode(match.second);
    
82. 
    
83.         if(bikes.find(bikeStr) == bikes.end() ||
    
84.            people.find(personStr) == people.end() )continue;
    
85. 
    
86.         bikes.erase(bikeStr);
    
87.         people.erase(personStr);
    
88. 
    
89.         answer.emplace_back(match);
    
90.     }
    
91. 
    
92.     /* 3. answer */
    
93.     return answer;
    
94. }
    
95. 
    
96. string Encode(const pair<int, int>& pos){
    
97.     return to_string(pos.first) + " " + to_string(pos.second);
    
98. }
    
99. 
    
100. pair<int, int> Decode(const string& pos){
     
101.     int mid = pos.find(" ");
     
102.     int first = stoi(pos.substr(0, mid)), second = stoi(pos.substr(mid + 1));
     
103.     return {first, second};
     
104. }
     
105. 
     
106. int Dist(const pair<int, int>& pos1, const pair<int, int>& pos2){
     
107.     return abs(pos1.first - pos2.first) + abs(pos1.second - pos2.second);
     
108. }
     
109. 
     
110. void PrintMatch(const vector< pair<pair<int, int>, pair<int, int>> >& match){
     
111.     for(auto m: match){
     
112.         cout << "person: (" << m.first.first << ", " << m.first.second << ") ";
     
113.         cout << "bike: (" << m.second.first << ", " << m.second.second << ")" << endl;
     
114.     }
     
115. }
     
116. 
     
117. 
     

复制代码