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

Binary tree zig zag traversal
白板21min (18 min code + 3 min test)
开始适应在较小的白板上写码(4*6 ft)

LC 114. Flatten Binary Tree to Linked List
take away: 要看清让转的是单链表还是双链表，不要做多余的事

1. /**
   
2. * Definition for a binary tree node.
   
3. * struct TreeNode {
   
4. *     int val;
   
5. *     TreeNode *left;
   
6. *     TreeNode *right;
   
7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   
8. * };
   
9. */
   
10. class Solution {
    
11. public:
    
12.     void flatten(TreeNode* root) {
    
13.         /* 0. MISC */
    
14.         if(!root)return;
    
15.         
    
16.         /* 1. prep */
    
17.         TreeNode* dummy = new TreeNode(0);
    
18.         TreeNode* current = dummy;
    
19.         
    
20.         /* 2. algo */
    
21.         FlattenTreeRec(root, &current);
    
22. 
    
23.         /* 3. answer */
    
24.         delete dummy;
    
25.     }
    
26.    
    
27.     void FlattenTreeRec(TreeNode* node, TreeNode** current){
    
28.         /* base */
    
29.         if(!node)return;
    
30.         
    
31.         /* pre-order */
    
32.         TreeNode* left = node->left;
    
33.         TreeNode* right = node->right;
    
34.         
    
35.         (*current)->right = node;
    
36.         node->left = NULL;
    
37.         *current = node;
    
38.         
    
39.         /* branch */
    
40.         FlattenTreeRec(left, current);
    
41.         FlattenTreeRec(right, current);        
    
42.     }
    
43. };

复制代码

LC 191. Number of 1 Bits
2分钟bug free白板
1分钟LC打码 AC

LC 84. Largest Rectangle in Histogram
take away: 在pop stack 之前，记得要查是不是empty

白板19分钟，有一个runtime error（忘了检查empty）

1. class Solution {
   
2. public:
   
3.     int largestRectangleArea(vector<int>& heights) {
   
4.         /* 0. MISC */
   
5.         if(heights.empty())return 0;
   
6.         
   
7.         /* 1. prep */
   
8.         stack<pair<int, int> > prev;
   
9.         int answer = 0;
   
10.         
    
11.         /* 2. key algo */
    
12.         for(int i = 0; i < heights.size(); ++i){
    
13.             if(prev.empty()){
    
14.                 prev.emplace(heights[i], i);
    
15.             }else{
    
16.                 int earlyIndex = i;
    
17.                 while(!prev.empty() && prev.top().first >= heights[i]){
    
18.                     earlyIndex = prev.top().second;
    
19.                     answer = max(answer, (i-earlyIndex)*prev.top().first );
    
20.                     prev.pop();
    
21.                 }
    
22.                 prev.emplace(heights[i], earlyIndex);
    
23.             }
    
24.         }
    
25.         
    
26.         while(!prev.empty()){
    
27.             answer = max(answer, (int)(heights.size()-prev.top().second)*prev.top().first );
    
28.             prev.pop();
    
29.         }
    
30.         
    
31.         /* 3. answer */
    
32.         return answer;
    
33.     }
    
34. };

复制代码

785. Is Graph Bipartite?

太烦人了这题写的。。。
一开始求简单写了个naive的错误解法，后来规矩的写了BFS，然后发现这破玩意还有可能不连通，所以又加了连通检查
写了得有1个多小时，而且跑得还特慢，需要复习。。。

1. class Solution {
   
2. public:
   
3.     bool isBipartite(vector<vector<int>>& graph) {
   
4. 
   
5.         unordered_set<int> visited;
   
6.         for(int i = 0; i < graph.size(); ++i){
   
7.             if(visited.find(i) != visited.end())continue;
   
8.             if(!BipartiteBFS(graph, i, visited))return false;
   
9.         }
   
10.         /* 3. answer */
    
11.         return true;
    
12.     }
    
13. 
    
14.     bool BipartiteBFS(const vector<vector<int>>& graph, int start, unordered_set<int> & visited){
    
15.         /* 0. MISC */
    
16.         
    
17.         /* 1. prep */
    
18.         unordered_set<int> red, black;
    
19.         vector<int> currentLevel;
    
20.         currentLevel.emplace_back(start);
    
21.         visited.emplace(start);
    
22.         int level = 0;
    
23.         
    
24.         /* 2. key algo */
    
25.         while(!currentLevel.empty()){
    
26.             vector<int> nextLevel;
    
27.             
    
28.             for(auto num: currentLevel){
    
29.                 if(level%2 == 0){
    
30.                     red.emplace(num);
    
31.                 }else{
    
32.                     black.emplace(num);
    
33.                 }            
    
34.             }
    
35.             
    
36.             for(auto num: currentLevel){                           
    
37.                 for(auto neighbor: graph[num]){                 
    
38.                     if(level%2 == 0){
    
39.                         if(red.find(neighbor) != red.end())return false;
    
40.                     }else{
    
41.                         if(black.find(neighbor) != black.end())return false;
    
42.                     }
    
43.                     if(visited.find(neighbor) == visited.end()){
    
44.                         visited.emplace(num);
    
45.                         nextLevel.emplace_back(neighbor);   
    
46.                     }
    
47.                 }
    
48.             }
    
49.             
    
50.             currentLevel = move(nextLevel);
    
51.             ++level;
    
52.         }
    
53.         return true;
    
54.     }
    
55. };

复制代码

补充内容 (2018-11-3 04:43):
今天的第五道白板，求简单写naive写法的主要原因是累了

赞赞赞赞！

LC 95. Unique Binary Search Trees II
这是一道旧题，当时写的感觉比较难，今天白板50分钟完成（码43分钟，test 7分钟）
白板只有一个syntax typo （见下面take away），已经接近bug free了

take away: emplace_back NULL pointer should specify type: NULL --> (TN*)(NULL)

1. /**
   
2. * Definition for a binary tree node.
   
3. * struct TreeNode {
   
4. *     int val;
   
5. *     TreeNode *left;
   
6. *     TreeNode *right;
   
7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   
8. * };
   
9. */
   
10. 
    
11. typedef TreeNode TN;
    
12. class Solution {
    
13. public:
    
14.     vector<TreeNode*> generateTrees(int n) {
    
15.         /* 0. MISC */
    
16.         if(n <1)return {};
    
17.         
    
18.         /* 1. prep */
    
19.         vector<vector<TN*> > memMatrix(n + 1, vector<TN*>());
    
20.         memMatrix[0].emplace_back((TN*)(NULL));
    
21.         
    
22.         /* 2. key algo */
    
23.         for(int i = 1; i <= n; ++i){
    
24.             for(int j = 1; j <= i; ++j){
    
25.                 vector<TN*> combo = move(ComboTree(memMatrix, i, j));
    
26.                 for(auto tree: combo){
    
27.                     memMatrix[i].emplace_back(tree);
    
28.                 }
    
29.             }
    
30.         }
    
31.         
    
32.         /* 3. answer */
    
33.         return memMatrix.back();
    
34.     }
    
35.    
    
36.     TN* CopyTree(TN* root){
    
37.         if(!root)return NULL;
    
38.         TN* copyRoot = new TN(root->val);
    
39.         copyRoot->left = CopyTree(root->left);
    
40.         copyRoot->right = CopyTree(root->right);
    
41.         return copyRoot;
    
42.     }
    
43.    
    
44.     TN* OffsetTree(int offset, TN* root){
    
45.         if(!root)return NULL;
    
46.         TN* offsetRoot = new TN(root->val + offset);
    
47.         offsetRoot->left = OffsetTree(offset, root->left);
    
48.         offsetRoot->right = OffsetTree(offset, root->right);
    
49.         return offsetRoot;
    
50.     }
    
51.    
    
52.    
    
53.     vector<TN*> ComboTree(const vector<vector<TN*> > & memMatrix, int i, int j){
    
54.         /* 0. MISC */
    
55.         
    
56.         /* 1. prep */
    
57.         vector<TN*> answer;
    
58.         
    
59.         /* 2. key algo */
    
60.         int leftNum = j - 1, rightNum = i - j;
    
61.         vector<TN*> leftSubTrees, rightSubTrees;
    
62.         leftSubTrees = memMatrix[leftNum];
    
63.         
    
64.         for(auto tree: memMatrix[rightNum]){
    
65.             rightSubTrees.emplace_back(OffsetTree(j, tree));
    
66.         }
    
67.         
    
68.         for(auto leftTree: leftSubTrees){
    
69.             for(auto rightTree: rightSubTrees){
    
70.                 TN* root = new TN(j);
    
71.                 root->left = CopyTree(leftTree);
    
72.                 root->right = CopyTree(rightTree);
    
73.                 answer.emplace_back(root);
    
74.             }
    
75.         }
    
76.         
    
77.         /* 3. answer */
    
78.         return answer;
    
79.     }   
    
80. };

复制代码

补充内容 (2018-11-3 21:41):
take away: 对于树的操作都是pointer操作，所以传树object的时候没必要用move

LC 98, LC 173, LC 236
都是典型算法，挑战是全部用iteration+stack完成，用了90分钟，感觉比较吃力，尤其是inorder-traversal的iteration写法又卡壳了，这是个需要印在心里的算法。

LC 98 的iteration+stack解：（这是这三题中比较对于我来讲新颖的写法，所以贴上来）

1. /**
   
2. * Definition for a binary tree node.
   
3. * struct TreeNode {
   
4. *     int val;
   
5. *     TreeNode *left;
   
6. *     TreeNode *right;
   
7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   
8. * };
   
9. */
   
10. class Solution {
    
11. public:
    
12.     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    
13.         /* 0. MISC */
    
14.         if(!root)return NULL;
    
15.         
    
16.         /* 1. prep */
    
17.         stack<TreeNode*> pStack = Path(root, p);
    
18.         stack<TreeNode*> qStack = Path(root, q);
    
19.         
    
20.         pStack = move(Reverse(pStack));
    
21.         qStack = move(Reverse(qStack));
    
22.         
    
23.         TreeNode * answer = NULL;
    
24.         
    
25.         /* 2. key algo */
    
26.         while(!pStack.empty() && !qStack.empty() && pStack.top() == qStack.top()){
    
27.             answer = pStack.top();
    
28.             pStack.pop();
    
29.             qStack.pop();
    
30.         }
    
31.         
    
32.         /* 3. answer */
    
33.         return answer;
    
34.     }
    
35.    
    
36.     stack<TreeNode*> Reverse(stack<TreeNode*> & stk){
    
37.         stack<TreeNode*> answer;
    
38.         while(!stk.empty()){
    
39.             answer.emplace(stk.top());
    
40.             stk.pop();
    
41.         }
    
42.         return answer;
    
43.     }
    
44.    
    
45.     stack<TreeNode*> Path(TreeNode* root, TreeNode* dst){
    
46.         /* 0. MISC */
    
47.         if(!root)return {};
    
48.         
    
49.         /* 1. prep */
    
50.         stack<TreeNode*> ansPath;
    
51.         ansPath.emplace(root);
    
52.         
    
53.         /* 2. key algo */
    
54.         while(!ansPath.empty()){
    
55.             TreeNode* node = ansPath.top();
    
56.             if(node == NULL){
    
57.                 ansPath.pop();
    
58.                 while(!ansPath.empty() && ansPath.top()->right == node){
    
59.                     node = ansPath.top();
    
60.                     ansPath.pop();
    
61.                 }
    
62.                 if(!ansPath.empty())
    
63.                     ansPath.emplace(ansPath.top()->right);
    
64.             }else{
    
65.                 if(node->val == dst->val)break;
    
66.                 ansPath.emplace(node->left);                     
    
67.             }                 
    
68.         }
    
69.         
    
70.         /* 3. answer */
    
71.         return ansPath;
    
72.     }
    
73. };

复制代码

LC 695. Max Area of Island
take away: 再做图bfs/dfs时，visited要在discover child的时候进行mark，不然的话，如果多个node指向一个child，这个child就会被多次推进queue/stack，造成计算错误或者重复运算。
码完用时28分钟，test但是没有检测出自己的错误（没有在discover child的时候mark as visited，导致重复推进stack造成重复count node）
花了8分钟想明白问题所在并debug

1. class Solution {
   
2. public:
   
3.     int maxAreaOfIsland(vector<vector<int>>& grid) {
   
4.         /* 0. MISC */
   
5.         if(grid.empty() || grid[0].empty())return 0;
   
6.         
   
7.         /* 1. prep */
   
8.         vector<vector<bool> > visited(grid.size(), vector<bool>(grid[0].size(), false));
   
9.         int answer = 0;
   
10.         
    
11.         /* 2. key algo */
    
12.         for(int i = 0; i < grid.size(); ++i){
    
13.             for(int j = 0; j < grid[0].size(); ++j){
    
14.                 if(grid[i][j]==0 || visited[i][j])continue;
    
15.                 answer = max(answer, Area(grid, &visited, i, j));
    
16.             }
    
17.         }
    
18.         
    
19.         /* 3. answer */
    
20.         return answer;
    
21.     }
    
22.    
    
23.     int Area(const vector<vector<int> > & grid, vector<vector<bool> > * visited, int i, int j){
    
24.         /* 0. MISC */
    
25.         
    
26.         /* 1. prep */
    
27.         stack<pair<int, int> > dfsStack;
    
28.         vector<pair<int, int> > directions = {
    
29.             pair<int, int>(0, 1),
    
30.             pair<int, int>(0, -1),
    
31.             pair<int, int>(1, 0),
    
32.             pair<int, int>(-1, 0)
    
33.         };
    
34.         int count = 0;
    
35.         dfsStack.emplace(i, j);
    
36.         (*visited)[i][j] = true;
    
37.         
    
38.         /* 2. key algo */
    
39.         while(!dfsStack.empty()){
    
40.             auto node = dfsStack.top();
    
41.             dfsStack.pop();
    
42.             ++count;
    
43.             for(auto dir: directions){
    
44.                 int childI = node.first + dir.first;
    
45.                 int childJ = node.second + dir.second;
    
46.                 if(InRange(grid, childI, childJ) &&
    
47.                    grid[childI][childJ] == 1 &&
    
48.                    (*visited)[childI][childJ] == false){
    
49.                     (*visited)[childI][childJ] = true;
    
50.                     dfsStack.emplace(childI, childJ);
    
51.                 }
    
52.             }
    
53.         }
    
54.         
    
55.         /* 3. answer */
    
56.         return count;
    
57.     }
    
58.    
    
59.     bool InRange(const vector<vector<int> > & grid, int i, int j){
    
60.         return i >= 0 && i < grid.size() && j >= 0 && j < grid[0].size();
    
61.     }
    
62. };

复制代码

LC 98. Validate Binary Search Tree

第三遍重写这道题，目标是把思路搞清晰。我把对代码的解答写在了comment里面
核心点是implicit branching and monotonically increasing stack

1. /**
   
2. * Definition for a binary tree node.
   
3. * struct TreeNode {
   
4. *     int val;
   
5. *     TreeNode *left;
   
6. *     TreeNode *right;
   
7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   
8. * };
   
9. */
   
10. class Solution {
    
11. public:
    
12.     bool isValidBST(TreeNode* root) {
    
13.         int prevVal;
    
14.         
    
15.         stack<TreeNode*> largerElements;
    
16.         TreeNode* current = root;
    
17.         
    
18.         bool started = false;
    
19.         
    
20.         while(!largerElements.empty() || current){
    
21.             /* the elements in the stack is monotonically increasing from bottom to top because of the way
    
22.                 we emplace the elements */
    
23.             
    
24.             /* at this point if the current is not NULL, that means the previous loop bottom has assigned a
    
25.                 right node of previous node, and that means this node is a starting point to search the next larger
    
26.                 element, so that we can to as left as we can in order to get it.
    
27.                
    
28.                 Otherwise if the current is NULL, that means the previous loop
    
29.                 bottom doesn't see a right pointer attached to the previous value, so we have to pop the top of our
    
30.                 monotically increasing stack in order to get the next larger value. (if the previous value doesn't have
    
31.                 a valid right child, that means it is the largest child. the only way to find a larger element is to get its right parent,
    
32.                 which by definition is stored in our monotonically increasing stack) */
    
33.             
    
34.             /* so the condition branching is implicit here in the line arrangement */
    
35.             
    
36.             /* for inorder traversal, backtracking stack is only used when there exists parent->left relationship because in this case the
    
37.                parent is larger than the child and yet is discovered before the child */
    
38.             
    
39.             while(current){
    
40.                 largerElements.emplace(current);
    
41.                 current = current->left;
    
42.             }
    
43.             
    
44.             current = largerElements.top();
    
45.             largerElements.pop();
    
46.             
    
47.             if(!started)started = true;
    
48.             else if(prevVal >= current->val)return false;
    
49.             prevVal = current->val;
    
50.             
    
51.             if(current->right)current = current->right;
    
52.             else current = NULL;
    
53.         }
    
54.         
    
55.         return true;
    
56.     }
    
57. };

复制代码

补充内容 (2018-11-4 23:24):
implicit branching by line arrangement

补充内容 (2018-11-4 23:25):
and loop bottom-top signaling communication