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

207. Course Schedule

Problem Metrics:
1. Understand Problem at 3 min
2. Get Core Concept at 9 min
3. Algorithm Draft at 12 min
4. Detailed example derivation at 38 min
5. Code draft at 58 min
6. AC solution 60 min

Note:
C++ map discard const qualifier problem, don't use [ ], use find()->second

本题是一个标准DFS题目，我所遇到的难点在于理解题意和抽象题目模型。本题核心抽象模型就是在图里找环，有环则代表出现dead lock，要return false
我在stack implementation of DFS的细节实施上面卡顿了一段时间，用了20多分钟才把思路理清楚，不过这一次理清之后stack DFS的思路就清晰了很多。
总的来讲stack DFS需要一个stack记当前路径，一个map(或array)记node状态（unvisited, discovered, processed），核心细节在于状态更新的时机，期初所有node都是unvisited, unvisited->discovred应该在pre-order时做，discovered->processed应该在post-order时做。所以这里的parent node既要可以在pre-order时被更新，也要可以在post-order时被更新，所以在所有children走完之前这个parent一直还应该待在stack里（right below all its children）

写完code draft之后有一个错误，即忘记return，其它还有一个编译错误如上述，以及2个typo，解决编译问题之后代码直接AC

LC199. Binary Tree Right Side View
Problem Metrics:
        1. Understand problem at 1 min
        2. Get core concept at 1 min
        3. Algorithm draft at 4 min
        4. Detailed example derivation 9 min
        5. Code draft at 13 min
        6. AC solution at 14 min

For any container with "node" (trees, linked lists, graphs), remember to handle the NULL case.

这道题的核心是level order traversal. 在level order traversal的模板算法下，把processing改为view from right side （visit vector.back() ）即可。树图的解题窍门是在脑中具象化，转换成图像后，算法都应该比较直接的。

要记得在码一开始就handle NULL case，不然会出现runtime error

LC 102. Binary Tree Level Order Traversal
道理同上一题，一遍AC

题目总结第一步，按AC时间分级
第一遍见到的新题目，分级如下
class 0: 15分钟内AC
class 1: 30分钟内AC
class 2: 60分钟内AC
class 3: 没能在60分钟内AC

大木虫 发表于 2018-10-3 23:48
题目总结第一步，按AC时间分级
第一遍见到的新题目，分级如下
class 0: 15分钟内AC

class 4: 借助答案AC或放弃AC

rocketdive 发表于 2018-10-3 15:42
能否问下楼主大神白板是哪里买到的。。

amazon                     

LC 301. Remove Invalid Parentheses (class 4)
Problem Metrics:
1. Understand problem at 5 min
2. Get core concept. Looked at solution idea at 30 min (only get general direction, no detialed instruction needed) seems like I must use brute force search
3. Algorithm draft at 50 min
4. Detailed example derivation 58 min
5. Code draft at 104 min
6. Code compiled at 108 min
7. AC solution at 116 min

This is hardcore backtracking.

这题写起来十分酸爽，一开始完全没有思路，后来瞄了一眼答案发现大家的基本方法是DFS (backtracking)，所以我就写了自己的DFS解法，在思路明了之后1小时之内写了230行代码（带comment），编译问题基本都是小typo，编译之后修改了一个小的逻辑错误之后AC通过。感觉自己的代码可读性没问题，但是太特么长了，当场白板的话不可能写完。以及，我还有几个可以提速的pruning logic没有用上，不过既然AC了，就先懒一懒。

这题的我解法的时间复杂度是 O(n*2^n)，空间复杂度也是(n*2^n), 存答案用

take away:
见到所谓 “return all possible...”一般就要做backtracking，先把暴力解写出来，不要寄希望于多项式解
一定要把复杂问题拆分成一个个小function才能防止在后期手忙脚乱



补充内容 (2018-10-4 03:21):
把pruning logic加上之后，成功beat 100%

200. Number of Islands  (老题，class 3)

mark as visited before push can make BFS much faster. If you only mark the node after you pop it out, it can be really slow. The reason is as following:
suppose node A and node B both have child C, when we explore node A, we find unvisited child C and push it into the queue. Later when we explore node B, we discover C again and push it since C is not explored yet (and therefore not marked visited). If we mark node C before we push it into queue, we will push it when we explore A and won't do it again when we explore B. This "pre-push" optimization can be applied when there are multiple nodes connecting to a child node.

Problem Metrics:
1. Understand problem at 1 min
2. Get core concept at 2 min (BFS/DFS for connected components in undirected graph)
3. Algorithm Draft at 6 min
4. Detailed example derivation 10 min
5. Code draft at 29 min
6. Code compile at 35 min
6. AC solution at 38 min

The branches of BFS should be independent of each other, don't use "else if", use "if" instead.
Remember to get the logic right according to problem (how is a valid node defined)
Get your parameter types consistent.

从时间分析上来看，这道题的主要难点是代码整洁度，作为标准的BFS/DFS题目，思路和概念是非常明确的，需要保证各种index的+1-1没有搞错，以及各种type要统一，五个月前写过一遍120行代码的解，今天的解是90行，还有待提高。

备注：用DFS再做一遍

LC 695 Max Area of Island (class 2)

Problem Metrics
1. Understand problem at 1 min
2. Core concept at 2 min
3. Algorithm draft at 3 min
4. Detailed example derivation at 4 min
5. Code draft at 15 min
6. Code compile at 20 min
7. AC solution at 26 min

Compile error: expected primary-expression before ‘int’
remember to remove the type cast for function call parameters.

Remember to initialize your integer to zero

标准题型，核心是DFS/BFS图遍历， processing是area+1

补充内容 (2018-10-5 05:28):
花了5秒钟把queue替换成stack，直接变成DFS解

楼主觉得书本值得购买吗？会过简单或者过难吗？对比起leetcode的discussion有什么优势？