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

EPI 9.3 Test A String Over "{,},(,),[,]" For Well-Formedness

库存还有2道，明天应该能发上进度

今天给一个门卫大叔话15分钟讲明白了二分查找，给另一个门卫大哥花30分钟讲了 Leetcode Edit Distance 的 二维DP解法，我讲明白了，他听懂了。对练习交流很有帮助，同时我对DP的理解也深了一些。

发图感觉太麻烦了，先休息一段时间，有时间了再继续发图

最近看到了Algorithm Design Manual 动态规划的章节，于是集中训练动态规划。最近三天在不看答案的情况下解决了12道动态规划的思路，其中有四道放在了一天里当作模拟onsite进行白板编程讲解，平均解题时间45分钟（写完码）。12道题中，快题（经典题目，变式）的话2~5分钟得出思路，慢题（没见过，状态转移方程相对复杂）大概需要2~3个小时，尝试多个方向之后才能得出思路，不过得解之后的感觉比直接看答案深刻太多了。

这本书貌似真的都是慢慢干货。一开始是美国人介绍给我的， 我买了JAVA版本的，但是好像在华人中热度不够？？

改做leetcode，按知识点tag刷，每个tag做8题，目标10月底完成70~120道medium和hard新题。

LC301 Clone Graph
/*
    Problem Metrics:
        1. Understand problem: at 3 min
        2. Get core concept: at 8 min
        3. Come up with algorithm draft: at 14 min
        4. Detailed example derivation: at 18 min
        5. AC solution: at 90 min            
*/

问题总结
    标准的图遍历题目，使用DFS和BFS都可以，我使用了两个BFS平行进行，一个遍历原图，一个更新新图。在从queue pop出来之后对新图更新edge和popped node的neighbors。如果见到visited node，则只在新图上加这个edge。加edge的方法使用一个hash table存旧图和新图一一对应的节点，因此新图的目标node可以直接搜到。时间复杂度O(V+E)，空间复杂度O(V) 不算答案本身，因为没存edge
    弱项：代码实现时间过长（72min）
    分析：通过编译用了27min，debug用了45min，debug加了一行，改了一行，是一个typo
    解决：要严格按照想好的算法流程走，最好在码之前写出pseudo code的细节。 debug时要一行一行过代码，不要想当然


补充内容 (2018-10-4 01:26):
更正：不是301，是133

103. Binary Tree Zigzag Level Order Traversal

1. Understand problem: at 1 min
2. Get core concept: at 3 min
3. Algorithm draft: at 11 min
4. Example derivation at 18 min
5. Code draft at 26 min
6. AC solution at 29 min

For level order traversal, remember to CLEAR the next level after assignment

这道题是我今天Bloomberg的on campus面试，我没有答好。原因在于思路没有捋顺就开始写了。解决方法是把解题步骤印到骨子里，一步一步扎实的做，以及要提高得解速度和码功，这都要靠练。

能否问下楼主大神白板是哪里买到的。。