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

LC 120. Triangle

Problem Metrics:
1. Understand Problem at 3 min
2. Get key concept at 8 min
3. Algorithm draft & detailed example derivation at 8 min
4. Code draft, compile, run 26 min (no errors)

新题，典型DP，标准解法，一遍过，需要更快，有点像level order traversal

请问和cc150比怎么样？

aabaa 发表于 2018-10-14 00:35
请问和cc150比怎么样？

我没有看过CC150

10/2到止今天一共20天，完成了70道LC新题，其中有6题是easy，有5题看过答案提示，最长代码AC时间119分钟，平均代码AC时间40分钟，总码量大概在3500行左右。休息3天，然后继续。

进入白板准备阶段，准备方式如下：
白板mock码题（题目出自Leetcode）
然后把白板码打入LC OJ run，记录compile error & runtime error
总结反思
预计每天3题，每题1~2小时

LC430 Flatten a Multilevel Doubly Linked List
白板复盘：
确认思路为DFS，第一个25分钟首先试图用stack解，但是发现要存的信息过于复杂，stack需要存4个node（head, childHead, childTail, tail）
过于复杂，遂放弃，改用recursion，使用function call stack来存node信息
take away：当recursion 层信息比较复杂时，用recursion不用stack会好写一些。

10分钟手写recursion解，发现代码其实很简洁。
take away: 想清楚思路的代码通常会比预想的简洁，所以先想清楚

3分钟过完testcase

这是一道做过的题，在人来人往的教室楼道白板进行训练会有一些别扭，不过这正是需要训练的心理素质，而且确实感到了和独自练习时的不同。需要继续这样的训练，在有人的地方，在声音嘈杂的地方训练。

从白板上抄下来的代码如下：（红色字体为修改或添加的部分）
    Node* flatten(Node* head) {
        FlattenRecursion(head);
        return head;
    }

    void FlattenRecursion(Node* head){
        Node* current = head;
        while(current){
            if(current->child){
                Node* child = current->child;
                FlattenRecursion(child);
                Node* childTail = Tail(child);
                current->child = NULL;
                childTail->next = current->next;
               
                current->next = child;
                child->prev = current;
                current = childTail->next;
               
                if(childTail->next)childTail->next->prev=childTail;
            }else current = current->next;
        }
    }  
   
    Node* Tail(Node* head){
        while(head && head->next)
            head = head->next;
        return head;
    }


补充内容 (2018-10-30 00:19):
从白板上直接抄到Leetcode OJ上面，红色字体为达到AC时在OJ上做的修改

补充内容 (2018-10-30 00:21):
take away：当recursion 层信息比较复杂时，用recursion不用stack会好写一些。
take away: 想清楚思路的代码通常会比预想的简洁，所以先想清楚
take away: 这是一道做过的题，在有人有声环境训练可训练心理素质

212. Word Search II
白板复盘:
确认思路为backtracking，吸取上次教训，不用stack，用recursion
27分钟写完代码，上OJ跑的时候有一些runtime error，修正详见代码

take away:  使用pointer reference的时候要记得统一syntax，不要这里用pointer，那里又不用pointer
take away: 双层逻辑的backtracking中两层（起始层和递归层）都要写清楚branching和housekeeping

从白板上抄下来的代码如下：（红色字体为修改或添加的部分）：
class Solution {
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        /* 0. MISC */
        
        /* 1. prep */
        unordered_set<string> dict;
        for(string word : words){
            dict.emplace(word);
        }
        unordered_set<string> ansStore;
        vector<vector<bool> > visited
            (board.size(), vector<bool>(board[0].size(), false) );
        string word = "";        
        
        unordered_set<string> prefixTable;
        for(int i = 0; i < words.size(); ++i){
            string prefix;
            for(int j = 0; j < words[i].size(); ++j){
                prefix += words[i][j];
                prefixTable.emplace(prefix);
            }
        }
        
        
        /* 2. key algorithm */
        for(int i = 0; i < board.size(); ++i){
            for(int j = 0; j < board[0].size(); ++j){
                visited[i][j] = true; word += board[i][j];
                WordSearchRec(board, dict, prefixTable, &ansStore, &visited, &word, i, j);
                visited[i][j] = false; word.pop_back();
            }
        }        
        
        /* 3. answer */
        vector<string> answer;
        for(auto itr = ansStore.begin(); itr != ansStore.end(); ++itr){
            answer.emplace_back(move(*itr));
        }
        return answer;
    }
   
    void WordSearchRec(const vector<vector<char> > & board,
                  unordered_set<string> &dict,
                  unordered_set<string> &prefixTable,
                  unordered_set<string> * ansStore,
                  vector<vector<bool> > * visited,
                  string * word, int i_, int j_){
        if(dict.find(*word) != dict.end()){
            ansStore->emplace(*word);
        }
        
        if(prefixTable.find(*word) == prefixTable.end()){
            return;
        }
        
        vector<pair<int, int> > directions = {pair<int, int>(0, -1),
                                              pair<int, int>(0, 1),
                                              pair<int, int>(-1, 0),
                                              pair<int, int>(1, 0)};
        
        for(auto dir : directions){
            int i = i_ + dir.first, j = j_ + dir.second;
            if(!InRange(i, j, board))continue;
            if((*visited)[i][j])continue;
            
            (*visited)[i][j] = true; (*word) += board[i][j];
            WordSearchRec(board, dict, prefixTable, ansStore, visited, word, i, j);
            (*visited)[i][j] = false; word->pop_back();
        }
    }
   
    bool InRange(int i, int j, const vector<vector<char> > &board){
        return i >= 0 && i < board.size() && j >= 0 && j < board[i].size();
    }
};

补充内容 (2018-10-30 23:41):
take away:  使用pointer reference的时候要记得统一syntax，不要这里用pointer，那里又不用pointer
take away: 双层逻辑的backtracking中两层（起始层和递归层）都要写清楚branching和housekeeping

补充内容 (2018-10-30 23:41):
倒数第二行InRange() function 最后一个assertion是 j < board[i].size()

补充内容 (2018-10-30 23:42):
好像显示不出来：board【i】.size()

LC 297. Serialize and Deserialize Binary Tree
高频题，我试图用iteration+stack写Deserizalize但是失败了，因为post-order iterative traversal实在是太麻烦，所以放弃了。整体用时45分钟

take away: 对于我个人来说，recursion写起来比iteration+stack更容易一些，所以能用recursion尽量recursion，虽然iteration在memory allocation上面有优势，但是上白板写起来容易出错。可以作为follow up讨论。当然，典型题目还是要把iteration+stack做熟练的（graph BFS/DFS 带visited marker那种，虽然也带post-order processing，但是有visited marker作为帮助会减少一些pointer检查，所以会好写一些）

/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        
        /* 0. MISC */
        
        /* 1. prep */
        stack<TreeNode*> dfsStack;
        dfsStack.emplace(root);
        string answer;

        /* 2. key algo */
        while(dfsStack.size() > 0){
            TreeNode* node = dfsStack.top();
            dfsStack.pop();
            if(!node)answer += "N ";
            else{
                answer += to_string(node->val) + " ";
                dfsStack.emplace(node->right);
                dfsStack.emplace(node->left);
            }
        }
        
        /* 3. answer */
        return answer;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int i = 0;
        return DeserializeRec(data, &i);
    }
   
    TreeNode* DeserializeRec(const string & data, int* i){
        /* 0. MISC */
        if(*i == data.length())return NULL;
        
        /* 1. prep */
        int end = data.find(" ", *i);
        string valStr = data.substr(*i, end - *i);
        *i = end + 1;
        if(valStr == "N")return NULL;
        
        /* 2. key algo */
        TreeNode* node = new TreeNode(stoi(valStr));
        node->left = DeserializeRec(data, i);
        node->right = DeserializeRec(data, i);
        
        /* 3. answer */
        return node;
    }
   
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

补充内容 (2018-10-31 23:08):
想到了一个相对折中的iteration+stack方法（deserialize），就是在stack中记录这个node是不是已经有了left。如果没有left，则接left，如果有了left，则接right，然后pop掉

LC 230. Kth Smallest Element in a BST
有一个细节没有注意到，就是在loop tail handling的时候。
take away: loop tail handling 需要和loop内部的operation逻辑保持一致，或者需要仔细检查，如果这个loop所修改的global在以后还会被用到的话（这种情况下最好保持内部和外部处理逻辑统一）。

/**
* 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:
    int kthSmallest(TreeNode* root, int k) {
        /* 0. MISC */
        if(!root){
            throw;
        }
        
        /* 1. prep */
        TreeNode* current = root;
        stack<TreeNode*> path;
        while(current->left){
            path.emplace(current);
            current = current->left;
        }
        
        /* 2. key algo */
        while(--k > 0){
            current = Next(current, &path);
            cout << current ->val << endl;
            if(!current)throw;
        }
        
        /* 3. answer */
        return current->val;        
    }
   
    TreeNode* Next(TreeNode* current, stack<TreeNode*> * path){
        /* 0. MISC */
        if(!current)return NULL;
        
        /* 1. prep */
        
        /* 2. key algo */
        if(current->right){
            path->emplace(current);
            current = current->right;
            while(current->left){
                path->emplace(current);
                current = current->left;
            }
        }else{
            while(!path->empty() && path->top()->right==current){
                current = path->top();
                path->pop();
            }
            if(!path->empty()){
                current = path->top();
                path->pop();
            }
            else current = NULL;
        }
        
        /* 3. answer */
        return current;
    }
};

LC 113. Path Sum II
跟上一题犯了类似的错误，tail case(也就是这里的base case)没有像generic case那样正确的handle。同样，由于这里的变量在处理完一个basecase之后还要继续被使用，所以当handle完tail case之后需要对变量进行与generic case一样的统一处理，在这里的意思是要记得pop_back()，或者不要提前return。

/**
* 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<vector<int>> pathSum(TreeNode* root, int sum) {
        /* 0. MISC */
        if(!root)return {};
        
        /* 1. prep */
        vector<vector<int> > ansStore;
        vector<int> path;
        
        /* 2. key algo */
        PathSumRec(root, &ansStore, &path, 0, sum);
        
        /* 3. answer */
        return ansStore;
        
    }
   
    void PathSumRec(TreeNode* node, vector<vector<int> > * ansStore, vector<int> * path, int currentSum, int target){
        if(!node)return;
        path->emplace_back(node->val);
        currentSum += node->val;
        
        if(currentSum == target && !node->left && !node->right){
            ansStore->emplace_back(*path); return; /* should not return here */
        }
        
        PathSumRec(node->left, ansStore, path, currentSum, target);
        PathSumRec(node->right, ansStore, path, currentSum, target);
        
        path->pop_back();
    }
};