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

同问楼主关于epi的看法。这本书网上不少人推荐过（但是生活中没见过朋友在用）。

简单看了sample和目录之后，我觉得这本书看起来有点像是leetcode 精选tag题加上作者关于这些题的解法。

请问楼主看了这本书之后觉得怎么样呢？为什么会说这本书（相比lc）“系统”呢？

gongchen 发表于 2018-10-4 23:24
同问楼主关于epi的看法。这本书网上不少人推荐过（但是生活中没见过朋友在用）。

简单看了sample和目录 ...

我觉得这本书很好。

系统 在于
各种不同解法 从最容易想到的  到比较难的 对于 各种情况的讨论也很到位

值得看一下

爱丽丝和鲍勃 发表于 2018-10-5 15:37
我觉得这本书很好。

系统 在于

有版主大人背书

这35刀看来是捂不住了哈哈哈

Problem Metrics: (class 2)
1. Understand problem at 1 min
2. Get core concept at 3 min
3. Algorithm draft at 8 min
4. Detailed example derivation at 12 min
5. Code draft at 22 min
6. Code compile at 24 min
7. AC solution at 28 min

Compile errors: typos

Runtime errors: memory limit exceeded
        Reason: didn't queue pushing condition properly. should put the procedure in the "if" statement

标准DFS/BFS题目，和数岛一样，核心是无向图找SCC，adjacency matrix的使用，以及用bit vector 记visited。易错点是push 进queue时容易判断出错导致memory exceeded


补充内容 (2018-10-5 23:54):
LC 547. Friend Circles

超级赞，这本书真的值得好好研读。祝楼主早日拿到心仪的offer！

gongchen 发表于 2018-10-5 15:24
同问楼主关于epi的看法。这本书网上不少人推荐过（但是生活中没见过朋友在用）。

简单看了sample和目录 ...

系统的意思是以相对较少的题量掌握不同类型的思路框架以及知识点之间的贯通，在这个标准下，有一个功力深厚的作者领路是更加有效的。

LC010 Regular Expression Matching

Problem Metrics:
1. Understand problem at 4 min
2. Get core concept at 10 min
3. Algorithm draft at 30 min
4. Detailed example derivation at 33 min
5. Code draft at 62 min
6. Code compile at 66 min (Runtime Error: load of null pointer of type '_Bit_type') vector 读过界了
7. AC solution at 68 min

This is a tough one

这是一道典型的DP题目，难点是要把题目逻辑转换成DP逻辑，实现方式是挑一个example详细的手写一遍，在过程中把DP逻辑写下来供码时参考



补充内容 (2018-10-6 22:26):
可以进一步优化把空间复杂度N^2降到N

补充内容 (2018-10-6 22:26):
beat 100% 哈哈哈哈哈哈！

补充内容 (2018-10-6 22:27):
Class 3

补充内容 (2018-10-6 22:29):
这是一道二维DP，与普通二维DP不同的是这题的DP内环如果根据是否为‘*’进行分类讨论会更加容易写，逻辑更清晰

93. Restore IP Addresses

Problem Metrics:
1. Understand problem at 2 min
2. Get core concept at 4 min
3. Algorithm draft 10 min
4. Detailed example derivation at 14 min
5. Code draft at 43 min
6. Code comiple at 46 min
7. AC solution at 61 min

Ordinary backtracking problem. Sticking to backtracking template is particularly helpful. DETAIL MATTERS. Use a set to store answer (remove duplicates).

Previously my answer is more than needed. It turns out that it's becuase I didn't use all the digits. Take away: always do a sanity check before adding an answer into the set.

Also, when your thing doesn't return correct answers, go back to the problem definition and find where you apply it wrong.

标准backtracking题目，这类题目的主要难点是把题目规则读清楚，这样才能写对递归判定的细节，我就是在一开始的时候加index的时候多了1，导致无法返回正确结果。以及，要把所有答案放到一个set里面去重复，然后在推到vector里面return。最后一点，在把一个answer放到set里之前最好对这个结果再做一遍sanity check，不要完全依赖自己的递归逻辑必然会返回valid answer.

补充内容 (2018-10-7 00:08):
class 3

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

Take away(important): putting all sanity checks as base cases can save a lot of lines!

Need to make sure your for loop index is correct

Runs super slow, weird (~700ms)

标准DFS backtracking题，我发现把所有所谓边界判定和条件判定统统放在一开始有助于大量减少行数，这个很有帮助。（虽然说多了一层function call，不过依靠现在编译器的优化应该不会有太大速度区别）

不过有一个问题，就是我的程序跑得很慢（~700ms, 5%）我查了半天不知道哪里的问题。代码如下，请大家帮忙看看。

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        /* Start at each location, do a backtracking search */
        /* Each backtracking seach keeps track of its own resource */
        
        if(word == "")return true;
        if(board.size() == 0 || board[0].size() == 0)return false;
        
        for(int i = 0; i < board.size(); ++i){
            for(int j = 0; j < board[0].size(); ++j){
                vector<vector<bool> > visited(board.size(), vector<bool>(board[0].size(), false));
                bool wordExists = ExistRecursion(board, word, &visited, 0, i, j);
                if(wordExists)return true;
            }
        }
        return false;
    }
   
    /* I need a tracker index and a visited tracker */
    bool ExistRecursion(const vector<vector<char> > & board, const string & word, vector<vector<bool> > * visited, int index, int i, int j){
        if(i < 0 || i >= board.size() || j < 0 || j >= board[0].size())return false;
        if(board[i][j] != word[index])return false;
        if((*visited)[i][j] == true)return false;
        if(index == word.size()-1) return true;

        (*visited)[i][j] = true;
        
        bool find = false;
        if(!find)find = ExistRecursion(board, word, visited, index+1, i-1, j);
        if(!find)find = ExistRecursion(board, word, visited, index+1, i+1, j);
        if(!find)find = ExistRecursion(board, word, visited, index+1, i, j-1);
        if(!find)find = ExistRecursion(board, word, visited, index+1, i, j+1);
        
        (*visited)[i][j] = false;
        
        return find;
    }
};


补充内容 (2018-10-7 03:36):
LC 79. Word Search (class 2)

LC 543. Diameter of Binary Tree (class 1)

Problem Metrics:
1. Understand problem at 1 min
2. Get core concept at 4 min
3. Algorithm draft at 8 min
4. Detailed example derivation at 10 min
5. Code draft at 14 min
6. AC solution (one time AC, no compile/runtime error)  at 16 min

Ordinary tree problem. Use post-order traversal to collect and update information

标准树题，使用post-order解决，标准模板处理，有一点写法问题就是这题我既return又update parameter，有些混乱