http://www.voidcn.com/article/p-mcpeppez-bcg.html
1. https://leetcode.com/problems/patching-array/ 补丁数组
2. https://leetcode.com/problems/find-the-duplicate-number/ 找出重复元素
3. https://leetcode.com/problems/majority-element-ii/ 找出主元素 （O(n)）
4. https://leetcode.com/problems/lru-cache/ LRU Cache （链表）
5. https://leetcode.com/problems/sliding-window-maximum/ 滑动窗口-单调队列
6. https://leetcode.com/problems/largest-rectangle-in-histogram/（单调栈，可看）
7. https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/ 股票最大收益（动态规划）
8. https://leetcode.com/problems/distinct-subsequences/ 找不同序列（动态规划）
9. https://leetcode.com/problems/h-index/ H指数计算
10. https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/ 旋转有序数组中找最小元素
11. https://leetcode.com/tag/depth-first-search/ 深度优先搜索
在职刷题 + System Design + 面试准备的路上
Leetcode: 刷了关于interval的各种变形，发现这类问题很多公司都爱考，这类题目有很多，一天刷不完，明天继续.
目前理解是一种是需要维护一个list，先按start time排序，然后根据情况看是否需要再按end time排序. 然后依次遍历相邻时间片的首尾是否有overlapping.
第二是因为按照时间排序的有序数组，查找操作可以使用二分法，边界情况需要根据检查start time 还是end time来区别，大多是查找刚好overlapping的第一个点的位置
第三是可以利用TreeMap这个数据结构来简化操作，主要可以用在检查是否有overlapping和插入新的interval。对于合并和删除interval会比较复杂。
56. Merge Intervals(四刷)
57. Insert Intervals
435. Non-overlapping Intervals
729. My Calendar I
252.Meeting rooms
253.Meeting rooms II(四刷)
715.Range module
Leetcode: 其实Skyline问题也是interval的一种，只不过从一维变二维，求的是overlap的最高位。其他变形也可以是求overlap的最低位，此类问题需要多思考，变形非常多。
731. My Calendar II
759. Employee Free Time
807. Max Increase to Keep City Skyline
218. The Skyline Problem
11.Container With Most Water
397. Integer Replacement: DFS or 根据n-1或n+1的1bit数来确定选择，1越少越快完成
333. Largest BST Subtree: check if BST and count or record size of BST and lower and upper boundary for each node, use PostOrder traversal compare the value of parent with upper of left and lower of right and update till to the top root.
543. Diameter of Binary Tree: Postorder traversal, bottom-up get heights of left and right side for each node and record max
572. Subtree of Another Tree: similar with isSameTree or serialize two trees and find substring.
面经题：
1. Collatz Conjecture : Memoization
2. Implement Queue with limited size of array : Store List<Object> in last position of List<Object>
Leetcode: 今天按专题刷Union Find 和DFS是好朋友
482. License Key Formatting: Iterate over from end to beginning.
399. Evaluate Division: Union find or DFS
721. Accounts Merge: Union find or DFS
737. Sentence Similarity II: Union Find
959. Regions Cut By Slashes: DFS
339. Nested List Weight Sum: BFS
472. Concatenated Words: Recursion
73. Set Matrix Zeroes: record state in first row and column
490. The Maze: BFS
505. The Maze II: BFS
499. The Maze III: PriorityQueue
17. Round Prices: 每个数统一向下取整，然后判断其sum与原近似值sum差值多少来决定有多少数需要向上取整，然后根据小数部分排序，拥有较小的小数部分的数向下取整，其他的向上取整
18. Sliding game: BFS, 同时使用三个queue分别去记录当前的路径，当前空格点的位置，当前棋盘情况，使用hashset来check棋盘避免重复路径
29. Ten Wizards: Dijkstra解法，使用Priorityqueue每次pop出cost最小的点，为了记录path，用一个数组去记录到达过的点，在每个点中记录每个到达这个点的父节点，这样做既能从后往前把路径串起来也能通过判断该数组中某位置是否为空来判断此位置是否已经访问过来避免重复路径。
9 Maximum Number of Nights You Can Accommodate: DP
20 Find Case Combinations of a String: BFS
21 Menu Combination Sum: Sorted in order to pruning and DFS
22 K Edit Distance: Trie and DP. 如果按照edit distance做法去判断每一个太慢。建立trie能够使得相同的prefix只计算一次，使用DP记录每一层trie node与target的操作步数，可以简化为一维数组.
24 Minimum Cost with At Most K Stops: Dijkstra, 使用priorityqueue存储cost, stop和flight信息，每次pop出cost最小的，存入该flight可以到达的所有flight信息
25 String Pyramids Transition Matrix: Backtracking
26 Finding Ocean: DFS or BFS
27 Preference List: Typological sort
28 Minimum Vertices to Traverse Directed Graph: 每次把未访问过的点放入结果中，然后从这个入口遍历所能达到的点，都标记为visited，如果这个点能够到达结果中的点，就把结果中能到达的那个点除去而保留现在入口的这个点。以此往复，直到遍历完所有点，剩下的就是答案。
31 Guess Number: 17次：首先用1111判断一次，之后每次从2-5中为每一位选值需要4次，4*4+1=17。最优8次：1111,...,5555判断5次，然后为了确定第一位需要判断1或2次，即abbb,accc. 然后确定第2位需判断一次，第三为1次
Boggle Game: 首先为words建立Trie tree， 然后在board和Trie中开始DFS，以每个character为起点进行查找，每找到一个word，再从头开始第二个DFS继续查找其他word。这里的tricky是剪枝操作，我们需要把第二次DFS的visited不进行回溯，而只回溯list中添加的word。而只在第一个DFS才对visited进行回溯。Palindrome Pairs： HashMap存储每个word，然后对每个单词的每个position，分为前后两部分，判断一个部分是否是palindrome，判断另一个部分的reverse是否map中，如果在，且不是自身。就可以组成palindrome.Alien Dictionary: Typological sort 或者 DFS从当前点找到结尾，加入到result中，把这个path上的点都标为visited，再去找未visited的点，未visited的表明这个点是在之前的path的上游，所以一路走下去就能到达path的起始点，连在一起。这样就组成了from end to beginning. 然后我们reverse整个结果。Find Median In large file : 首先遍历一遍找出共有多少个单词，然后使用二分法和quick select，即设置上下边界，找多少个数小于上下边界的中间值，如果数量少去总共单词数的一半，就移动下边界，否则移动上边界。因为我们要找的第k大的点在多的那一侧。最终找到小于median的数量刚好为k即答案
cherry pick
140. Word Break II: DFS. 优化有两种：1.DP to check if the word breaks 2. Use memoization to save the previous results to prune duplicated branches.
341. Flatten Nested List Iterator: Stack
54. Spiral Matrix : 设置上下左右四个边界，记得在边界更改时，for loop的结束条件也要改变
152. Maximum Product Subarray: DP to record minimum and maximum array
53. Maximum Subarray: DP -> record the current and previous state
68. Text Justification: 1.计算每行的单词数(注意两个单词之前需要预留一个空格) 2.计算总共有多少个空格 3.平分空格到单词之前, 余数从左到右依次多加1个空格. 4. 最后一行，单词之前只有一个空格，单词之后补全空格.65. Valid Number: 分别考虑不相容情况, 1.有+-时，只能出现在第一个或者e之后; 2.有.时，之前没有. 和 e出现过; 3. 有e时，e的前后必须有number; 4.有数字时，则需要区别是.之前的number还是.之后的number。 这个时候我们可以这样：在遇到数字时，用两个boolean值都mark为true代表有数字。如果出现.且合法，则把.之后的mark为false. 最后只有两个boolean都为true，number才是valid的443. String Compression: Two pointers76. Minimum Window Substring：maintain a window with left and right pointers. Initialize the count with length of target and check each character in source.
53. Maximum Subarray 的followup, Size至少为2 : Size至少为2的意思就是必须至少有两个数相加，不管是否比之前小，那么我们就需要用当前的数去加之前相对更小的数，可能是之前的一个数，也可能是之前的数之和，所以还是需要一个一维数组存储当前的最大sum, 每次添加当前的值和另一个数时，另一个数取自之前的值和sum的较大值。150. Evaluate Reverse Polish Notation: Stack242. Valid Anagram : map
1. Collatz Conjecture: 因为求得是一个范围内最长的sequence，所以需要check从1到n每个数，我们可以使用cache来进行加速。
2.Implement Queue with limited size of array: 使用double linkedlist
29. Skiing: 这题首先需要clarify是否有环，没有的话可以使用typological sort，从start到end，走遍所有路线，更新每个点最大的score。使用hashmap来构建graph，记录cost，定义一个class表明每个点，记录每个点的reward和其parent，最后走完全程，返回end这个点的score即是答案，通过此点的parent向前逆序就能够找到整个路线。使用DFS或者BFS也是类似，需要不断更新每个点的score，记录最大的score和其parent。29. Ten Wizards： 使用Dijkstra 或者 DP都能够解决此问题。时间复杂度为O((E+V)logV) 如果使用Dijkstra, DP的话是O(n^2).
2. Implement Queue with limited size of array：方法二 ListNode with fixed size of array3. List of List Iterator: 方法一：col iterator and row iterator. 方法二：row index and col index.
4. Display page : Iterator, hashset and reachEnd. reachEnd为true时，添加重复元素，为false时不添加，counter满足时，reset hashset。iterator.hasNext为false时，reset iterator.Find target node from root and print path: recursively add left and right node and maintain a list.(pre order)
13. Water Drop: 有高墙和无高墙
16.Meeting time: 把start time 和end time 分离放入一个list中，并排序
30.Boggle Game: Trie + DFS. 先依次遍历找到一个word之后，再DFS去找其他不overlap的word。可以使用list来保存最长路径，最后可以返回list，也可以返回最大数字。
31.Lowest common ancestor of words: hashmap
Meeting room I
Meeting room II
Leetcode: 今天主要做的题是Trie + bucket sort或者 Trie + DP 或者 Trie + DFS.
745. Prefix and Suffix Search
692. Top K Frequent Words
347. Top K Frequent Elements
451. Sort Characters By Frequency
22 K Edit Distance
31. Max Profit with interval: DP of interval size
32. Skiing: Typological sort
29. Ten Wizards: Dijkstra
19 Maximum Number of Nights You Can Accommodate: DP
24 Minimum Cost with At Most K Stops: Dijkstra
此类型的题都是求graph的最大或者最小值，如果是求最小值可以使用Dijkstra，如果是最大值用BFS,如果没有环可以使用Typological sort. 打印路径的话可以使用在class里定义list去记录，也可以使用全局数组，在class里只需要定义parent，以此来追踪路径
系统设计：News Feed.
OOD: Parking System
https://github.com/allaboutjst/airbnb/blob/master/README.md
“Don't focus on goals but focus on systems/process. It is not about one single accomplishment, it is about a cycle of endless refinement and continuous improvement. It is your commitment to the process that will determine your progress. ”
问一个design时候的unittest 问题
1. https://leetcode.com/problems/patching-array/ 补丁数组
2. https://leetcode.com/problems/find-the-duplicate-number/ 找出重复元素
3. https://leetcode.com/problems/majority-element-ii/ 找出主元素 （O(n)）
4. https://leetcode.com/problems/lru-cache/ LRU Cache （链表）
5. https://leetcode.com/problems/sliding-window-maximum/ 滑动窗口-单调队列
6. https://leetcode.com/problems/largest-rectangle-in-histogram/（单调栈，可看）
7. https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/ 股票最大收益（动态规划）
8. https://leetcode.com/problems/distinct-subsequences/ 找不同序列（动态规划）
9. https://leetcode.com/problems/h-index/ H指数计算
10. https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/ 旋转有序数组中找最小元素
11. https://leetcode.com/tag/depth-first-search/ 深度优先搜索
在职刷题 + System Design + 面试准备的路上
Leetcode: 刷了关于interval的各种变形，发现这类问题很多公司都爱考，这类题目有很多，一天刷不完，明天继续.
目前理解是一种是需要维护一个list，先按start time排序，然后根据情况看是否需要再按end time排序. 然后依次遍历相邻时间片的首尾是否有overlapping.
第二是因为按照时间排序的有序数组，查找操作可以使用二分法，边界情况需要根据检查start time 还是end time来区别，大多是查找刚好overlapping的第一个点的位置
第三是可以利用TreeMap这个数据结构来简化操作，主要可以用在检查是否有overlapping和插入新的interval。对于合并和删除interval会比较复杂。
56. Merge Intervals(四刷)
57. Insert Intervals
435. Non-overlapping Intervals
729. My Calendar I
252.Meeting rooms
253.Meeting rooms II(四刷)
715.Range module
Leetcode: 其实Skyline问题也是interval的一种，只不过从一维变二维，求的是overlap的最高位。其他变形也可以是求overlap的最低位，此类问题需要多思考，变形非常多。
731. My Calendar II
759. Employee Free Time
807. Max Increase to Keep City Skyline
218. The Skyline Problem
11.Container With Most Water
397. Integer Replacement: DFS or 根据n-1或n+1的1bit数来确定选择，1越少越快完成
333. Largest BST Subtree: check if BST and count or record size of BST and lower and upper boundary for each node, use PostOrder traversal compare the value of parent with upper of left and lower of right and update till to the top root.
543. Diameter of Binary Tree: Postorder traversal, bottom-up get heights of left and right side for each node and record max
572. Subtree of Another Tree: similar with isSameTree or serialize two trees and find substring.
面经题：
1. Collatz Conjecture : Memoization
2. Implement Queue with limited size of array : Store List<Object> in last position of List<Object>
Leetcode: 今天按专题刷Union Find 和DFS是好朋友
482. License Key Formatting: Iterate over from end to beginning.
399. Evaluate Division: Union find or DFS
721. Accounts Merge: Union find or DFS
737. Sentence Similarity II: Union Find
959. Regions Cut By Slashes: DFS
339. Nested List Weight Sum: BFS
472. Concatenated Words: Recursion
73. Set Matrix Zeroes: record state in first row and column
490. The Maze: BFS
505. The Maze II: BFS
499. The Maze III: PriorityQueue
722. Remove Comments
11. Text Justification
12. Regular Expression
13. Water Drop
14. Hilbert Curve
15. Simulate Game
18. Sliding game: BFS, 同时使用三个queue分别去记录当前的路径，当前空格点的位置，当前棋盘情况，使用hashset来check棋盘避免重复路径
29. Ten Wizards: Dijkstra解法，使用Priorityqueue每次pop出cost最小的点，为了记录path，用一个数组去记录到达过的点，在每个点中记录每个到达这个点的父节点，这样做既能从后往前把路径串起来也能通过判断该数组中某位置是否为空来判断此位置是否已经访问过来避免重复路径。
9 Maximum Number of Nights You Can Accommodate: DP
20 Find Case Combinations of a String: BFS
21 Menu Combination Sum: Sorted in order to pruning and DFS
22 K Edit Distance: Trie and DP. 如果按照edit distance做法去判断每一个太慢。建立trie能够使得相同的prefix只计算一次，使用DP记录每一层trie node与target的操作步数，可以简化为一维数组.
24 Minimum Cost with At Most K Stops: Dijkstra, 使用priorityqueue存储cost, stop和flight信息，每次pop出cost最小的，存入该flight可以到达的所有flight信息
25 String Pyramids Transition Matrix: Backtracking
26 Finding Ocean: DFS or BFS
27 Preference List: Typological sort
28 Minimum Vertices to Traverse Directed Graph: 每次把未访问过的点放入结果中，然后从这个入口遍历所能达到的点，都标记为visited，如果这个点能够到达结果中的点，就把结果中能到达的那个点除去而保留现在入口的这个点。以此往复，直到遍历完所有点，剩下的就是答案。
31 Guess Number: 17次：首先用1111判断一次，之后每次从2-5中为每一位选值需要4次，4*4+1=17。最优8次：1111,...,5555判断5次，然后为了确定第一位需要判断1或2次，即abbb,accc. 然后确定第2位需判断一次，第三为1次
Boggle Game: 首先为words建立Trie tree， 然后在board和Trie中开始DFS，以每个character为起点进行查找，每找到一个word，再从头开始第二个DFS继续查找其他word。这里的tricky是剪枝操作，我们需要把第二次DFS的visited不进行回溯，而只回溯list中添加的word。而只在第一个DFS才对visited进行回溯。Palindrome Pairs： HashMap存储每个word，然后对每个单词的每个position，分为前后两部分，判断一个部分是否是palindrome，判断另一个部分的reverse是否map中，如果在，且不是自身。就可以组成palindrome.Alien Dictionary: Typological sort 或者 DFS从当前点找到结尾，加入到result中，把这个path上的点都标为visited，再去找未visited的点，未visited的表明这个点是在之前的path的上游，所以一路走下去就能到达path的起始点，连在一起。这样就组成了from end to beginning. 然后我们reverse整个结果。Find Median In large file : 首先遍历一遍找出共有多少个单词，然后使用二分法和quick select，即设置上下边界，找多少个数小于上下边界的中间值，如果数量少去总共单词数的一半，就移动下边界，否则移动上边界。因为我们要找的第k大的点在多的那一侧。最终找到小于median的数量刚好为k即答案
cherry pick
140. Word Break II: DFS. 优化有两种：1.DP to check if the word breaks 2. Use memoization to save the previous results to prune duplicated branches.
341. Flatten Nested List Iterator: Stack
54. Spiral Matrix : 设置上下左右四个边界，记得在边界更改时，for loop的结束条件也要改变
152. Maximum Product Subarray: DP to record minimum and maximum array
53. Maximum Subarray: DP -> record the current and previous state
68. Text Justification: 1.计算每行的单词数(注意两个单词之前需要预留一个空格) 2.计算总共有多少个空格 3.平分空格到单词之前, 余数从左到右依次多加1个空格. 4. 最后一行，单词之前只有一个空格，单词之后补全空格.65. Valid Number: 分别考虑不相容情况, 1.有+-时，只能出现在第一个或者e之后; 2.有.时，之前没有. 和 e出现过; 3. 有e时，e的前后必须有number; 4.有数字时，则需要区别是.之前的number还是.之后的number。 这个时候我们可以这样：在遇到数字时，用两个boolean值都mark为true代表有数字。如果出现.且合法，则把.之后的mark为false. 最后只有两个boolean都为true，number才是valid的443. String Compression: Two pointers76. Minimum Window Substring：maintain a window with left and right pointers. Initialize the count with length of target and check each character in source.
53. Maximum Subarray 的followup, Size至少为2 : Size至少为2的意思就是必须至少有两个数相加，不管是否比之前小，那么我们就需要用当前的数去加之前相对更小的数，可能是之前的一个数，也可能是之前的数之和，所以还是需要一个一维数组存储当前的最大sum, 每次添加当前的值和另一个数时，另一个数取自之前的值和sum的较大值。150. Evaluate Reverse Polish Notation: Stack242. Valid Anagram : map
1. Collatz Conjecture: 因为求得是一个范围内最长的sequence，所以需要check从1到n每个数，我们可以使用cache来进行加速。
2.Implement Queue with limited size of array: 使用double linkedlist
29. Skiing: 这题首先需要clarify是否有环，没有的话可以使用typological sort，从start到end，走遍所有路线，更新每个点最大的score。使用hashmap来构建graph，记录cost，定义一个class表明每个点，记录每个点的reward和其parent，最后走完全程，返回end这个点的score即是答案，通过此点的parent向前逆序就能够找到整个路线。使用DFS或者BFS也是类似，需要不断更新每个点的score，记录最大的score和其parent。29. Ten Wizards： 使用Dijkstra 或者 DP都能够解决此问题。时间复杂度为O((E+V)logV) 如果使用Dijkstra, DP的话是O(n^2).
2. Implement Queue with limited size of array：方法二 ListNode with fixed size of array3. List of List Iterator: 方法一：col iterator and row iterator. 方法二：row index and col index.
4. Display page : Iterator, hashset and reachEnd. reachEnd为true时，添加重复元素，为false时不添加，counter满足时，reset hashset。iterator.hasNext为false时，reset iterator.Find target node from root and print path: recursively add left and right node and maintain a list.(pre order)
13. Water Drop: 有高墙和无高墙
16.Meeting time: 把start time 和end time 分离放入一个list中，并排序
30.Boggle Game: Trie + DFS. 先依次遍历找到一个word之后，再DFS去找其他不overlap的word。可以使用list来保存最长路径，最后可以返回list，也可以返回最大数字。
31.Lowest common ancestor of words: hashmap
Meeting room I
Meeting room II
745. Prefix and Suffix Search
692. Top K Frequent Words
347. Top K Frequent Elements
451. Sort Characters By Frequency
22 K Edit Distance
31. Max Profit with interval: DP of interval size
32. Skiing: Typological sort
29. Ten Wizards: Dijkstra
19 Maximum Number of Nights You Can Accommodate: DP
24 Minimum Cost with At Most K Stops: Dijkstra
此类型的题都是求graph的最大或者最小值，如果是求最小值可以使用Dijkstra，如果是最大值用BFS,如果没有环可以使用Typological sort. 打印路径的话可以使用在class里定义list去记录，也可以使用全局数组，在class里只需要定义parent，以此来追踪路径
系统设计：News Feed.
OOD: Parking System
你说的很有道理，最近我面system design也感觉并不是那么顺手，特别是在一些细节的地方被面试官问卡住了也发生过
https://github.com/allaboutjst/airbnb/blob/master/README.md
15 Simulate Diplomacy
Input (army_name, location, action())
action() could be:
- move(new_location) then army_name to new_location, If there is an army at new_location, then company strength of two aramy:
- The army have higher strength stay at new_location, the lower army is disappeared.
- If two army have the same strength, both are disppeared.
- hold() stay at the same location
- support(army_name) supoort another army. The supported army have one more strength.
The army's strength are intialized as the same.
“Don't focus on goals but focus on systems/process. It is not about one single accomplishment, it is about a cycle of endless refinement and continuous improvement. It is your commitment to the process that will determine your progress. ”
问一个design时候的unittest 问题
| 有一个简单的design题，写一个走路的程序，一个5x5的棋盘, 物体有(x,y,方向)这些属性，move 向前，left/right旋转，place重置位置。 程序很简单 我写成了一个console 程序，while(cin, command) 来读命令。 关键是要求提供测试数据来证明程序是对的 - There must be a way to supply the application with input data. - Provide test data to exercise the application. - The application must run and you should provide sufficient evidence that your solution is complete by, as a minimum, indicating that it works correctly against the supplied test data - you may use external libraries or tools for building or testing purposes. Specifically, you may use unit testing libraries or build tools available for your chosen language 我估计他是让你写unit test. 我的问题是，Unittest里面就是 判断做了一个操作以后的位置是不是指定的位置，这个指定的位置肯定是hardcode的，不可能是按照逻辑算出来的， 因为操作本身是程序算出来的，期望位置也是算出来的话这比较就没有意义。 那如果是手写，怎么完全覆盖呢？ 5x5的位置有25个起始位置，操作组合无数种，我不可能每种情况都写个test case啊 |
