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

LC 449. Serialize and Deserialize BST

Problem Metric:
1. Understand problem at 2 min
2. Get core concept at 4 min
3. Algorithm draft (part 1) at 5 min
4. Detailed example derivation (part 1) at 9 min
5. Code draft & Debugged & AC solution (part 1) at 12 min
6. Algorithm draft (part 2) at 18 min
7. Detailed example derivation (part 2) at 27 min
8. Code draft (part 2) at 38 min
9. Code compile at 41 min
10. AC solution at 41 min

Take away: inclusive index partitioning is really clean and neat to handle, can be a usefully strategy for binary search
The whole procedure of preorderConstruct is about asking "where are my children???" using partitioning technique

标准遍历定义题目，这题的难点在对先序遍历的掌握和代码整洁

补充内容 (2018-10-9 02:07):
class 2

LC 329. Longest Increasing Path in a Matrix

Problem Metrics: (class 2)
1. Understand problem at 4 min
2. Get core concept  at 5 min
3. Algorithm draft at 9 min
4. Detailed example derivation at 15 min
5. Code draft 31 min
6. Code compile at 32 min
7. AC solution at 44 min

Runtime Error: reference binding to misaligned address 0x000000000021 for type 'value_type', which requires 4 byte alignment
Reason: read outside of the range of a vector. (this will actually cause random runtime error, so sometimes it may appear fine, other times not)

Take away: go through your index end case LINE BY LINE, don't forget that +1/-1/whatever you need

一道思路比较简单的DP题目，可是为啥我的代码这么慢呢？（C++， ~700ms, 5%），求大家帮忙看看！

    int longestIncreasingPath(vector<vector<int>>& matrix) {
        /* This is directed graph level order traversal in 3D by stacking up input matracies */
        
        /* Step 0: MISC */
        /* handle corner cases*/
        if(matrix.size() == 0 || matrix[0].size() == 0){
            return 0;
        }        
        
        /* Step 1: preparation */
        int currentLength = 0;
        unordered_set<int> currentLevel, nextLevel;
        for(int i = 0; i < matrix.size() * matrix[0].size(); ++i){
            currentLevel.emplace(i);
        }
        
        /* Step 2: 3D level-order traversal (key step) */
        while(!currentLevel.empty()){
            
            ++currentLength;     
            
            for(auto itr = currentLevel.begin(); itr != currentLevel.end(); ++itr){
                int code = *itr;
                pair<int, int> loc = move(Decode(matrix, code));
               
                int i = loc.first, j = loc.second;
                int val = matrix[i][j];
               
                if(i > 0){
                    if(matrix[i-1][j] > val){
                        nextLevel.emplace(Encode(matrix, i-1, j));
                    }
                }

                if(i < matrix.size() - 1){
                     if(matrix[i+1][j] > val){
                        nextLevel.emplace(Encode(matrix, i+1, j));
                    }                  
                }

                if(j > 0){
                     if(matrix[i][j-1] > val){
                        nextLevel.emplace(Encode(matrix, i, j-1));
                    }                  
                }

                if(j < matrix[0].size() - 1){
                    if(matrix[i][j+1] > val){
                        nextLevel.emplace(Encode(matrix, i, j+1));
                    }                    
                }

            }           
            
            currentLevel = move(nextLevel);
            nextLevel.clear();            
        }
        
        /* Step 3: generate and return answer */
        return currentLength;
    }
   
    int Encode(const vector<vector<int> > & matrix, int i, int j){
        return i * matrix[0].size() + j;
    }
   
    pair<int, int> Decode(const vector<vector<int> > & matrix, int code){
        return {code/matrix[0].size(), code%matrix[0].size()};
    }

LC 210. Course Schedule II （class 3）

Problem Metrics:
1. Understand problem at 3 min
2. Get core concept at 6 min
3. Algorithm draft at 11 min
4. Detailed example derivation at 34 min
5. Code draft at 46 min
6. Code compile at 48 min (TLE)
7. AC solution at 88 min (solved TLE and loop issue)

Take away:
1. The interative equivalent of child branching is pushing child into stack. This can cause some issues:
the top node (one of the child) of stack is already processed in the previous child's iteration, and therefore should be treated as cousin node (just throw it away and do nothing). If this case isn't handled, this node could jam the stack and cause the program to stall. In conclusion, all three cases for a top node (unvisited, on path, processed) should all be considered and handled.

2. A graph may have multiple sources, and a topological sort in this case should first collect all source nodes before proceeding. This could be done by adding a single source pointing to all other sources. However, this single source won't catch separate cycles because there are no source nodes (in-degree == 0) in pure cycles, so the cycle detection can be done by checking the size of the topological sorted array against the number of nodes. if the array size is smaller than the number of nodes, that means our single source doesn't cover some of of the nodes in the original graph, and these nodes can only be cycle nodes because they exist in a separate graph that can escape the search of single source node. (the single source node searches and add only to in-degree-0 nodes)

这是一道很典型的图题，考的是topological sort
我的问题出在对iterative stack graph DFS traversal 的细节掌握有问题，导致代码少处理了一个情况造成TLE。把这里TLE的case放回course schedule I，不出所料也是TLE，修正细节之后问题解决。对遍历模板的理解有所进步，感觉递归和迭代遍历的对应部分和区别部分理解的更加生动清晰了。

LC 787. Cheapest Flights Within K Stops

Problem Metrics:
1. Understand problem at 4 min
2. Get core concept at 15 min
3. Algorithm draft at 21 min
4. Detailed example derivation at 32 min
5. Code draft at 45 min
6. Code compiles at 48 min
7. AC solution at 49 min

Take away:
Graph can go together with dynammic programming

dijkstra is a flavored dynammic programming version of universal cost search, and similar ideas can be applied flexibly to a variety of graph search optimization problems, and level order traversal is SOOOOOOOO universal. It appears everywhere in graph.

这道题不简单，是Djikstra和BFS的混合，也可以理解为 BFS with Djikstra/Dynammic Programming flavor
第一眼看到的时候脑中冒出的就是Dijkstra，因为想法实在是太接近了，第一个算法模式是限制Dijkstra算法在0~k stops以内，然后从0跑到k，后来发现无需这样做，只需要跑一遍阉割版的Dijkstra就可以了，而且严格来讲不能算是Dijkstra，而是level order traversal and cost update，属于借助了Dijkstra概念的BFS（level order traversal）。Dijkstra的核心是universal cost search on weighted graph，把这个概念稍加变换，把侧重点从universal cost branch extension 改成level-order branch extension，然后保留cost update的部分，就完成了本题的算法，属实有趣。

还有一点，就是level order traversal的广泛运用。现在看来，level order是BFS的一个重要变体，其作用在于keep track of your distance，这一特质可以有很多用途，比如在这题中的搜索结束条件。


补充内容 (2018-10-10 00:47):
后来查了一下。。。我实现的算法是有学名的。。。叫做Bellman–Ford algorithm。。。早知道应该多看看书，就不用自己推了。。。

芥末黄 发表于 2018-10-8 11:55
看不到啊？

看不到啥？

LC 51 N-Queen

Problem Metrics:
1. Understand problem at 4 min
2. Get core concept at 6 min
3. Algorithm draft at 25 min
4. Detailed example derivation at 31 min
5. Code draft at 55 min
6. Code compile at 63 min
7. AC solution at 68 min

标准backtracking，这题就是考设计和syntax。
当然，permutation思路真的很赞，以后要试一试。

backtracking代码如下：
class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        /* Step 1: prep */
        vector<vector<string> > answerStore;
        vector<vector<int> > answerBuilder;
        
        /* Step 2: algorithm */
        answerBuilder.emplace_back(vector<int>(n, 0));
        PlaceQueenRecursion(&answerStore, &answerBuilder);
        
        /* Step 3: answer */
        return answerStore;
    }
   
    /* vector<vector<int> > answerBuilder val: 0~8 (use its binary representation) */
    void PlaceQueenRecursion(vector<vector<string> > * answerStore, vector<vector<int> > * answerBuilder){
        /* base case / ending case */
        
        if(answerBuilder->size() > (*answerBuilder)[0].size()){
            answerStore->emplace_back(BuildAnswer(*answerBuilder));
            return;
        }
        
        /* recursion */
        
        vector<int> *prevRow = &(answerBuilder->back());
        vector<int> thisRow(prevRow->size(), 0);
        
        /* first, construct the attack map */
        for(int i = 0; i < prevRow->size(); ++i){
            int attackState = (*prevRow)[i];
            if(attackState & 0b100){
                if(i > 0){
                    thisRow[i-1] |= 0b100;
                }
            }
            if(attackState & 0b010){
                thisRow[i] |= 0b010;
            }
            if(attackState & 0b001){
                if(i < thisRow.size()-1){
                    thisRow[i+1] |= 0b001;
                }
            }
        }
        
        for(int i = 0; i < thisRow.size(); ++i){
            if(thisRow[i] != 0)continue;
            
            /* change */
            thisRow[i] = 0b1111;
            answerBuilder->emplace_back(thisRow);
            
            /* branch */
            PlaceQueenRecursion(answerStore, answerBuilder);
            
            /* undo */
            thisRow[i] = 0;
            answerBuilder->pop_back();
        }
        
    }
   
    vector<string> BuildAnswer(const vector<vector<int> > & answerBuilder){
        vector<string> answer;
        for(int i = 1; i < answerBuilder.size(); ++i){
            string rowStr = "";
            for(int j = 0; j < answerBuilder[i].size(); ++j){
                if((answerBuilder[i][j] & 0b1000) != 0){
                    rowStr += 'Q';
                }else{
                    rowStr += '.';
                }
            }
            answer.emplace_back(move(rowStr));
        }        
        return answer;
    }
   
};

LC 426. Convert Binary Search Tree to Sorted Doubly Linked List

Problem Metrics:
1. Understand problem at 2 min
2. Get core concept at 4 min
3. Algorithm draft 16 min
4. Detailed example derivation at 26 min
5. Code draft at 34 min ( No compile error! )
6. AC solution at 35 min ( No runtime error! )

This is just an inorder traversal with a small tricky processing stage. Nothing special.

标准的考inorder traversal，用一个global pointer解决问题（pass pointer by pointer）

LC 315. Count of Smaller Numbers After Self (class 3)

Problem Metrics:
1. Understand Problem at 1 min
2. Get core concept at 12 min
3. Algorithm draft at 31 min
4. Detailed example derivation at 45 min
5. Code draft at 66 min
6. Code compile at 70 min
7. AC solution at 80 min

This can be solved using BST. just more fancy processing stages.

很有趣的leetcode hard，我写出的是BST解法，看过discuss之后还有发现还有binary segment tree, binary index tree, merge sort等解法，感觉像兔子洞一样，通向了很多地方，由此看来，知识点是要连接贯通的

Problem Metrics: (class 3.5)
1. Understand problem at 2 min
2. Get core concept at 14 min
3. Algorithm draft at 15 min
4. Detailed example derivation at 42 min (tired)
5. Code draft at 56 min
6. Code compile at 63 min
7. Gave up at 115 min
8. Changed to DP approach, AC in 52 min

递归解法尝试了2个小时，失败，放弃。改成了DP解法，花了52分钟码出来，行数不多，但是逻辑难度相对较大，是我目前做过的最难的一题。

C++ 代码如下（beat 100%）
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        /* 0 */
        if(n == 0)return {};
        
        /* 1 */
        vector<vector<TreeNode*> > collections(n + 1, vector<TreeNode*>());        

        /* 2 */
        generateTreeAux(n, &collections);
        
        /* 3 */
        return collections[n];
    }
   
    void generateTreeAux(int n, vector<vector<TreeNode*> > * collections){
        TreeNode * zeroNode = NULL;
        (*collections)[0].emplace_back(zeroNode);
        
        for(int i = 1; i <= n; ++i){            
            for(int j = 1; j <= i; ++j){
                int leftOffset = 0, leftN = j - 1;
                int rightOffset = j, rightN = i - j;
               
                for(auto leftRoot : (*collections)[leftN]){
                    for(auto rightRoot : (*collections)[rightN]){
                        TreeNode * root = new TreeNode(j);
                        root->left = OffsetTree(leftRoot, leftOffset);
                        root->right = OffsetTree(rightRoot, rightOffset);
                        (*collections)[i].emplace_back(root);                        
                    }
                }               
            }         
        }        
    }
   
    TreeNode* OffsetTree(TreeNode* root, int offset){
        if(!root)return NULL;
        TreeNode* offsetRoot = new TreeNode(root->val + offset);
        offsetRoot->left = OffsetTree(root->left, offset);
        offsetRoot->right = OffsetTree(root->right, offset);
        return offsetRoot;
    }
};

补充内容 (2018-10-11 06:11):
LC 95 Unique Binary Search Trees II   

LC 272 Closest Binary Search Tree Value II

Problem Metrics:
1. Understand problem at 3 min
2. Get key concept at 8 min
3. Algorithm draft at 10 min
4. Detailed example derivation at 18 min
5. Code draft 60 min
6. Code compile at 64 min
7. AC solution at 64 min (no runtime error!)

这是一道树题，知识点明确典型，难点在于代码整洁。我发现边写边大声说出来，并且让思考速度领先于打码速度，保持节奏，可以提高代码正确性。这个150行的代码在修改了几个syntax typo之后直接AC，没有出现runtime error

C++代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        /* universal cost bi-directional expansion, similar to the idea of Dijkstra, but simpler */
        /* optimal runtime can be O(k), currently I have an idea of O(k*logn)
           by reusing the path stack, we might be able to optimize the runtime to O(k) */
        
        /* Procedure:
            0. handle corner cases (k == 0)
            1. find the closest node to the number, record the path stack for further reuse.
            2. write two functions: PrevNode, NextNode --> these functions return the modified stack, with the target pointer on the top
        */

        /* 0. MISC */
        if(k == 0)return {};
        if(!root)return {};
        
        /* 1. prep */
        stack<TreeNode*> path;
        FindNode(root, target, &path);
        int value = path.top()->val;
        if(value > target){
            stack<TreeNode*> prevPath = path;
            PrevNode(&prevPath);
            if(!prevPath.empty()){
                int prevVal = prevPath.top()->val;   
                double diff1 = value - target, diff2 = target - prevVal;
                if(diff2 < diff1){
                    path = move(prevPath);
                }
            }   
        }else if(value < target){
            stack<TreeNode*> nextPath = path;
            NextNode(&nextPath);
            if(!nextPath.empty()){
                int nextVal = nextPath.top()->val;   
                double diff1 = target - value, diff2 = nextVal - target;
                if(diff2 < diff1){
                    path = move(nextPath);
                }
            }   
        } /* else: value == target, no change needed */
        
        
        stack<TreeNode*> biggerPath = path, smallerPath = move(path);
        
        vector<int> answer;        
        answer.emplace_back(biggerPath.top()->val);
        
        NextNode(&biggerPath); PrevNode(&smallerPath);
        
        /* 2. algorithm */
        while(answer.size() < k){
            
            bool goNext = false;
            
            if(smallerPath.empty()){
                goNext = true;
            }else if(biggerPath.empty()){
                goNext = false;
            }else{
                double nextDiff = abs(target - biggerPath.top()->val);
                double prevDiff = abs(target - smallerPath.top()->val);
               
                if(nextDiff < prevDiff){
                    goNext = true;

                }else{
                    goNext = false;
                }
            }
            
            if(goNext){
                answer.emplace_back(biggerPath.top()->val);
                NextNode(&biggerPath);
            }else{
                answer.emplace_back(smallerPath.top()->val);
                PrevNode(&smallerPath);
            }
        }        
        
        /* 3. answer */
        return answer;
    }
   
    void FindNode(TreeNode * root, double target, stack<TreeNode*> * path){
        TreeNode * current = root;
        while(current){
            path->emplace(current);
            if(target < current->val){
                current = current->left;
            }else if(target > current->val){
                current = current->right;
            }else{
                break;
            }
        }
    }
   
    void NextNode(stack<TreeNode*> * path){
        if(path->empty())return;
        TreeNode* current = path->top();
        if(!current)return;
        
        if(current->right){
            current = current->right;
            path->emplace(current);
            while(current->left){
                current = current->left;
                path->emplace(current);
            }
            return;
        }
        
        path->pop(); /* pop the current */
        while(!path->empty()){
            TreeNode * parent = path->top();
            if(parent->left == current){
                break;
            }
            current = parent;
            path->pop();
        }
    }
   
    void PrevNode(stack<TreeNode*> * path){
        if(path->empty())return;
        TreeNode* current = path->top();
        if(!current)return;
        
        if(current->left){
            current = current->left;
            path->emplace(current);
            while(current->right){
                current = current->right;
                path->emplace(current);
            }
            return;
        }
        
        path->pop(); /* pop the current */
        while(!path->empty()){
            TreeNode * parent = path->top();
            if(parent->right == current){
                break;
            }
            current = parent;
            path->pop();
        }        
    }
};