4/3/16
### google onsite系列：走迷宫 http://pastebin.com/1FzVetG8
原题：matrix迷宫最短路径的扩展，假设小球在确定一个方向后一直走直到碰到障碍物或者到了迷宫的边界才会停下来。只有当小球最终停在出口位置才算走出迷宫，计算最少需要几步走出迷宫。

思路：简单的迷宫最短路径用bfs来遍历。这题的考点是如何把小球的行走方式转换为bfs遍历中离散的“下一步”。这里想象在x或者y轴上障碍物和边界组成的线段，所有段里的点都有两个方向上的2个next。所有对于任何一个非障碍物点，其next一共有4个：x和y轴上段的边界。预处理的方法就是一行行和一列列scan，同时更新线段中所有点的两个边界。有了预处理的表以后，只需要用可计算步数的bfs即可。

基本算法：

- 预处理在一个方向上要两层loop，比如x轴，outer loop逐行，inner loop逐列。因为左右两个出口，所以只有遇到障碍或者右边界才处理所有当前线段内的点（多一层循环），最后更新left进入下一个线段。
- bfs：层次化的bfs也需要两层loop，outer loop表示处理完一层，inner loop处理同层的所有点。这样每次inner loop结束就可以increment step。

思路明确了，写code的时候还是犯了不少错误。

- x方向和y方向处理的不同：x方向扫的时候，用left和right表示当前边界。而y方向扫的时候，用up和down作为当前边界。因为matrix中的点都是按row-major的方式存储的为一个int。无论横向还是纵向预处理，都是用row index*列数+column index这个公式。所以两种处理的边界点的计算code中不是直接替换left和up，right和down的（看code就明白了）
- reset left/right/up/down：因为是逐行/列扫描，在处理下一行/列的时候要reset left/right/up/down。开始错误的只在两层循环外初始化这些变量。

3/30/16 Wed
### Merge two/k Sorted List
要点：除了brute force，还有三种方法：

- PriorityQueue：这个就一个个list node push到q里，q的size是k，所有每次某个node出q，把下一个（如果存在）也push进来。
- 递归：先做左右两边，然后递归回来正确的位置merge
- iteration: 要点就是step len作outer loop，inner loop以step为步长X2循环两两merge
- 2、3都是保证在数组相应的有效位置存相应的list

brute force的time complexity是O(n*k*k)：如果依次merge，那么总的time为n+2n+3n+...+kn，而上面三种方法都是O(n*k*lgk)

3/29/16 Tue

- : 通过merge intervals和insert intervals两道题讲解interval的基本属性和操作
    - 2个interval A和B之间有相交和不相交，同时每种有A和B各在前面2种情况，共有4种情况
    - insert intervals: 比较中心是待insert的interval和当前的interval，merge intervals比较中心是前后两个intervals
    - 为什么merge intervals只有一个条件分支？因为比较的intervals之间前后顺序已经定了，只有相交或者不相交中的各1种情况。如果不相交就不需要merge，所以不考虑
    - 为什么insert intervals有三个条件分支？假设insert interval为A，当前待处理interval为B，不变量是所有已处理的interval都是和A没有相交的。如果与当前interval B也没有相交，如果A在前，那么直接插入并结束。如果B在前，继续保持不变量并继续。如果有相交，可以merge A和B作为新的insert interval A’
        - 注意最后在loop外面插入insert interval：任何中间的插入都会提前返回
    - insert intervals: 环？http://fisherlei.blogspot.com/2012/12/leetcode-insert-interval.html: no need to think further

3/26/16 Sat
### LRU Cache
这是一道leetcode的难题，这种题往往是算法结构很复杂，涉及一个或多个考点算法和数据结构的组合，同时又有很多corner cases要考虑。所以一定要找到合适memorize的结构，这样很容易推导出整个题目的解。否则会不断的记了忘忘了记。

这题分成大面上有两个考点，一个是LRU算法本身，另一个是hash table和doubly list的操作。LRU算法围绕两个接口get() and put()。这题的internal data structure之所以是hash table和list的结合是因为接口支持基于key的操作，而进出则是基于顺序，所以hash table用来支持key query，而list可以跟踪访问顺序。用到doubly list是因为其支持list上单node的reference的所有操作，不需要同时保存prev或者next的reference。
high-level操作

- get()：从hash table查询key value返回值，同时移动key对应的node到队列头
- put()：考虑两种情况：key已经在cache中存在或者不存在。
    - 如果存在，与get的操作类似。
    - 如果不存在，因为LRU cache的capacity有限，进一步考虑是否当前cache中的key已经等于当前capacity
        - 如果等于，需要删除list的最后node，然后插入新的到hash table和队头
        - 如果小于，直接插入新的到hash table和队头

low-level细节

- 根据high-level算法，无论是更新存在的key或者加入新key，对list只有两个基本操作removeNode()和addNodeToHead()，核心都是更新prev和next reference。无论是删除还是添加，都有可能对队头node，所以需要一个dummy node作为sentinel head
- corner cases：对于删除操作，一般的操作是更新next node的prev，所以对于tail，其next node为null，需要忽略这步。类似，对于添加到队头操作，需要更新当前队头node的prev，所以如果是空list，也要忽略这步。

3/25/16
### MHT
[先说有向图，再说无向图]
leetcode有三道题用到topological sort: course schedule I/II, minimum height tree(MHT)。course schedule是directed graph而MHT是undirected graph。

Course Schedule

- input: 边的List，因为要bfs/dfs的过程要沿着每一个结点的neighbors populate，所以要转化为adjacent matrix或者adjacent list的表示
- output: I是判断是否可以topological sort（即graph没有环），II要求输出排序的课程
- dfs的方法
    - idea：每一条dfs的路径都是一段partial order，两个目标：构建多有partial order的路径，判断是否有环
    - curRec：当前的partial order路径，res：结果队列，根据topological order，最底层排在头，所以当前node在dfs recursion之后近结果队列
    - 环的判断：对于directed graph，不能用visited来判断环，比如下图的例子。visited数组的作用是排除多余的dfs搜索。环只能发生在同一dfs搜索路径下，所以通过curRec set来track。同时function的return会populate back到顶层
    - 搜索的起点可能是一条完整连通路径的任何一点，从这点开始，可以覆盖到底，因此路径上的其他node都是在topological sequence靠后的位置，所以在结果里也是后入q的。同时由于visited数组，可以排除重复进res的情况
- bfs的方法
    - 基本：用q来maintain层级，最终q中元素的顺序就是排序顺序
    - indegree数组来保存每个结点当前的入度，初始可以通过遍历adjacent list得到
    - 从所有入度为0的结点开始，如果其neighbor的入度-1==0，说明是下一层的结点，入q。这样一层层遍历直到没有下一层产生。
    - loop invariant：只需要排序不需要结果返回最后一层的结点，可以用!q.isEmpty()，而每个iteration只出队列一个结点。如果已知当前为无环图，也可以存一个待处理node的set: nodes，当neighbor进q后从nodes里去掉

MHT
对于undirected graph，更新indegree要同时更新边的两个结点，indegree为1即为leaf。注意如果是孤立结点，入度可以为0，所以初始化的检测条件是indegree<=1
因为要返回树的根（可能是一个也可能是两个），即bfs的最后一层，需要用逐层的方式做bfs，这里用到两个q：q：全是indegree<=1的, bfs当前层，qnext:  bfs的下一层

3/23/16
### Coins in a Line, Flip Game, Nim Game
都是一类题，基本思路都是game AI里的minimax方法。基本方法网上很多，这里说说如何记住minimax算法结构。本质上是recursion，一般的recursion只需要每层做一次选择，但是对于minimax，因为一回合是两个player的决策，所以需要两个选择，然后再递归到下一层。recursion function的返回值优化特定player的value（一般是先手，这里假设player 1）。当player 1选择时，其一定选择几种可能的最大值，同理，当player 2选择时，其一定选择使player 1的value最小的选项。注意因为recursion function返回player 1的最优值，只有player 1的选择时累加value
递归的end condition是胜负结果都能直接一步得到，这样最优解也可以直接得到。

naive的递归存在大量重复计算，因为多条选择路径可以到达某一个subgame。可以用memoization or dp来优化。memoization比较简单：每次产生了subgame的最优解就存起来，每次进入递归检查是否解已经存在，如果存在就可以直接返回。dp的本质是用iteration来重构recursion的路径，然后沿着路径一步步（bottom up）求解subgame。

EDIT: 7/19/16:

- dp/recursion的方式和是不是game无关，和game本身的规则有关：flip game不累加值，只需要一个boolean就可以。coin in a line II是从一个方向上选取，所以1d dp，而coin in a line III是两个方向，所以是2d dp
- flip game II: 。
    - https://repl.it/CeES
    - https://repl.it/CeES/1 (find version)
    - 错误点：
        - minmax game中递归的优化条件是相反的，这题应该是对手False相当于当前True
        - 注意minmax的memorization，一遍可以同时存两个值（对手的值）来speed up
        - 注意find的用法，并且找到i并不会移动i，所以要i+=1
- https://repl.it/Cr9y (I)

EDIT: 9/21/16:

- coins in a line I/II/III: check above 1.
- recursion的返回和dp[left][right]表示什么？假设game是[left,right]，那么player 1最多能得到多少
- II: 只pick一边，
    - 注意别计算player 2 pick的值，只min
    - 从右向左做dp目的是取值的index相同，其实无所谓，注意dp的init要从右边开始，也就是从最后取的开始
- III:
    - player 1可以向左取，也可以右取，而player 2也是，player 2取min，player 1取max。
    - <1即可为特殊情况，<2也可情况，都能直接算出来。

3/20/16
这两天开始重温leetcode经典题，发现再回过头来看很多问题都会有新的心得体会，leetcode的题真是要多过几遍才能融会贯通

### Symmetric Tree Problem
这题是道easy题 （曾经linkedin电面时候秒过），但是如果没想清楚只背下题很快就会忘了。下面是题解的code (java)

- 基本的思路是递归配对。之所以可以用递归的方法是因为镜面对称的二叉树任意配对的node的left和right children是镜面对称的。这个条件可以作为invariant对整个树遍历。递归的基点是当前层两个已经配对的node，recurive function要以两个node的左右children作为参数
- 对于两个node的比较一共有4种情况，both not null, both null, only left null, only right null. 只有前两种case才有可能true (都不为null还要比较value)
- 递归里还是递归外？当前两个待比较node在递归里，只有两个node都不为null。才找对称点blindly进下一层

几乎完全一样code结构的还有Same Tree，不过因为两棵树，递归好想多了

### Binary Tree Level Order Traversal
基本题中的基本，这题的衍生题leetcode上就有一坨（比如臭名昭著的word laddar II），用bfs很直观，也可以用dfs。另外注意bfs有至少三种方式：2个queue，用一个queue+2个counter，一个queue+delimiter。曾经在亚麻的面试中被要求搞了三种。dfs看似效率不高，但是时间复杂度实际和bfs是一样的（O(n)）。也要会，目测有衍生题会考这个点（隐约记得看过一个狗家的面经上有）

注意现在要求做到bug-free，有巨量的问题是有关循环的边界case是不是要额外处理。以2 counters的bfs为例，code里采用了前置循环，就是说起始值在循环外初始化（cur=1，root node入queue）。queue不为空，继续遍历当前层同时将下一层入queue。每一步出queue后检查是否当前层已经遍历结束来重置counter

### Binary Tree Zigzag Level Order Traversal
算法结构类似level order traversal，根据题意下一层和当前层的遍历顺序是相反的，所以在展开阶段要顺序push下一层到stack里，这样下一层出栈的顺序就反过来了。另外，展开当前node是左到右还是右到左是每层交替的，所以要用一个变量来track。
错误点

- reverse是如何定的？因为reverse决定的是push的顺序。所以当前层如果是从左到右访问，那么下一层是从右向左（reverse），但是出stack的方向是反的，综上，reverse是False
- 这题因为是stack，所以不能用2层公用一个stack counting的方法做level traversal，必须用两个stack

### Maximum Depth of Binary Tree
简单一题，但是递归结构可以用在很多Binary Tree的题目上（比如LCA）：递归左右子树，然后比较左右返回结果取一返回

### Construct Binary Tree from Preorder and Inorder Traversal
### Construct Binary Tree from Inorder and Postorder Traversal
这两道题都是一个思路，比较tricky。以preorder/inorder为例，对于preorder遍历，一个子树对应一个连续的子数组，而首个元素就是root。问题就变成如何在子数组中进一步确定左右子树的边界，这样就可以进一步递归构建左右子树。inorder的序列可以用来找到边界：具体来说，因为无论是inorder还是preorder，子树都是数组中连续的元素，inorder的左右子树的分界点在root，这样如果能找到root的index，就能确定左子树的大小，进而确定在preorder序列里左子树的大小。这就是为什么我们要提前做invert index来存储value到index的map。而offset是用来跟踪当前在inorder序列里的左边界。

EDIT: 5/3/16
题做多了就会发现这题的code结构和Kth Largest Element in an Array O(n)很像，除了要两边都要recursion而不是一边以外。

- 通过长度计算index，总是有反向计算公式来验证作为intuition
- offset的意义：因为offset是当前范围在inorder序列里的左边界，注意在preorder和postorder的右子树递归都是offset+m+1：加上m个左子树结点和1个当前root。

3/11/16
最近一起刷题的朋友让我总结下现在公司常考的topological sort题，本人在google，facebook和linkedin的面试中都曾经遇到过类似题目。topological sort可以在directed or undirected graph上做，两种图上略有差异。方法上说基本上就是dfs或者bfs，具体到实现上还是有些细节要考虑（由于刷题人口大增，现在湾区公司的面试已经开始要求上机写bug-free的code了）。打算在这个系列的讲解中以leetcode上topological sort相关题目作为讲解依据，侧重如何吃透题目的细节差异。基本的topological sort方法，google上很容易搜到。 dfs方法的依据就是图上的关联结点之间是单线的，如果 course schedule I/II (details first) MHT (next) =>