[Interview] Techinical Code Interview 流程总结

面试经验也积累一些了，近期学不进去就写写总结。

Technical Interview除了题目是否作对，感觉其他的也非常重要，思路和communication.

• Communication. 贯穿面试，体现沟通交流能力
• Thought. 思路，体现problem - solving 的能力
• Coding. 编程能力, 是否能将solution转换成program. 

所以整个面试结果三部分组成: 

感觉真的是综合考察，很多题目哪怕作对了，都会挂，还有一些题目虽然没有bug free，但是经过提示修正，或者思路对了，有一些小bug，也可以过，这点感触很深。

找了一份材料，是完整的code interview的过程，应该是palantir家给面试者的，我觉得是很科学的，应该用这个套路，这种思维去不断强化，达到快速反应的能力，这是绝对是综合能力的养成。

对于刷题，越发感觉不能麻木的刷，一道题目是否真正领会思想，举一反三很重要，单靠数量，记题一点用没有，题目蕴含的思想是最重要的，我得反思，重新来过。

Before you start coding

• Make sure you understand the problem. Don’t hesitate to ask questions. Specifically, if any of the problem requirements seem loosely defined or otherwise unclear, ask your interviewer to make things more concrete. There is no penalty for asking for clarifications, and you don’t want to miss a key requirement or proceed on unfounded assumptions.

题目没弄明白绝对是大忌啊，记得之前说Amazon面试，面试时候不确认题目扣10%还是多少来着。

我这两天接连犯这个错误，Symmetric Difference，还有找零钱方案数or所有方案 都没完全确认就开始动手了，还有个大忌，不要想当然这是Leetcode或者CC150的题目，往上套，很多时候没读清楚，其实不是个题目，一定注意。

• Work through simple examples. This can be useful both before you begin and after you’ve finished coding. Working through simple examples before coding can give you additional clarity on the nature of the problem — it may help you notice additional cases or patterns in the problem that you would otherwise have missed had you been thinking more abstractly.

如果没弄明白题目的话，实例最清晰明了，而且会帮助考虑一些corner case. 即便是弄明白了，自己也可以写一个例子跟面试官确认一些，这样也不浪费时间，而且看着这个写代码也会高效一点，不过注意，这些simple example 有时候会导致我们忽略一些corner case. 总之要多注意

• Make a plan. Be wary of jumping into code without thinking about your program’s high-level structure. You don’t have to work out every last detail (this can be difficult for more meaty problems), but you should give the matter sufficient thought. Without proper planning, you may be forced to waste your limited time reworking significant parts of your program.

对一道题目，很多时候多种解法，这步主要跟面试官描述下自己要怎么做，感觉没太多经验的或者一般的面试官就会让你直接写，一些有经验的面试官会先问问你时间复杂度之类的，确认一些solution有没有问题，或者是不是他想要的，这里能给最优解就给最优解。

• Choose a language. At Palantir, we don’t care what languages you know as long as you have a firm grasp on the fundamentals (decomposition, object-oriented design, etc.). That said, you need to be able to communicate with your interviewer, so choose something that both of you can understand. In general, it’s easier for us if you use Java or C++, but we’ll try to accommodate other languages. If all else fails, devise your own pseudo-code. Just make sure it’s precise (i.e. not hand-wavy) and internally consistent, and explain your choices as you go.

While you’re coding

• Think out loud. Explain your thought process to your interviewer as you code. This helps you more fully communicate your solution, and gives your interviewer an opportunity to correct misconceptions or otherwise provide high-level guidance.

我自己的做法一般是在动手前先把solution 说清楚，coding过程中尽量集中精神少沟通，不过也碰到一些情况确实需要沟通，比如一些invalid parameter的return值，还有其他的一些编程中遇到的问题，该问的就问，觉得无所谓的可以说自己假设这里应该怎么弄，也OK。

• Break the problem down and define abstractions. One crucial skill we look for is the ability to handle complexity by breaking problems into manageable sub-problems. For anything non-trivial, you’ll want to avoid writing one giant, monolithic function. Feel free to define helper functions, helper classes, and other abstractions to reach a working solution. You can leverage design patterns or other programming idioms as well. Ideally, your solution will be well-factored and as a result easy to read, understand, and prove correct.

程序一定要简洁明了，该拆分的就拆分，这种尤其体现在ListNode这类题目，经常需要多个helper function.

• Delay the implementation of your helper functions. (this serves a corollary to the previous point) Write out the signature, and make sure you understand the contract your helper will enforce, but don’t implement it right away. This serves a number of purposes: (1) it shows that you’re familiar with abstractions (by treating the method as an API); (2) it allows you to maintain momentum towards the overall solution; (3) it results in fewer context-switches for your brain (you can reason about each level of the call stack separately); and (4) your interviewer may grant you the implementation for free, if he or she considers it trivial.

有些题目，需要swap()， 或者List getLength(), 直接写出来函数名用就好了，因为简单明了，最后再补充helper function，时间紧的时候不写的都没关系，无所谓的. 一般都是些简单功能抽取出来

• Don’t get caught up in trivialities. At Palantir we are much more interested in your general problem solving and coding abilities than your recall of library function names or obscure language syntax. If you can’t remember exactly how to do something in your chosen language, make something up and just explain to your interviewer that you would look up the specifics in the documentation. Likewise, if you utilize an abstraction or programming idiom which admits a trivial implementation, don’t be afraid to just write out the interface and omit the implementation so you can concentrate on more important aspects of the problem (e.g., “I’m going to use a circular buffer here with the following interface without writing out the full implementation”).

碰到过这种问题，比如 invalid input， throw new IllegalArgumentException("invalid input"). 当时记不住这个Exception名字了，其实无所谓的，还有file 做input，读文件的一些函数，当然了，对于常见的编程问题，不应该有记不住的，但是真是忘记了，不必纠结。

Once you have a solution

• Think about edge cases. Naturally, you should strive for a solution that’s correct in all observable aspects. Sometimes there will be a flaw in the core logic of your solution, but more often your only bugs will be in how you handle edge cases. (This is true of real-world engineering as well.) Make sure your solution works on all edge cases you can think of. One way you can search for edge-case bugs is to…

在test case之前，养成写完code 检查的习惯，初步检查完大体逻辑没问题，自觉写test case. 这个需要锻炼和积累，不同题目有很多不同类型case，比如字符串的space，int处理的Integer.MAX_VALUE等，编程时候也要注意的到。

• Step through your code. One of the best ways to check your work is to simulate how your code executes against a sample input. Take one of your earlier examples and make sure your code produces the right result. Huge caveat here: when mentally simulating how your code behaves, your brain will be tempted to project what it wants to happen rather than what actually says happen. Fight this tendency by being as literal as possible. For example, if you’re calculating a string index with code like str.length()-suffix.length(), don’t just assume you know where that index will land; actually do the math and make sure the value is what you were hoping for.

定式思维很可怕，我有好几次代码写的出问题了，比如while  list.add(A[i]) 忘记++，还有listNode 忘记next，跑test case时候还全然不知，因为思维已经模式化了，认定他会++，但是代码确没写。按文中提到的，一定要fight this tendency才可以！很关键，否则过一遍的效果微乎其微，别想当然。

• Explain the shortcuts you took. If you skipped things for reasons of expedience that you would otherwise do in a “real world” scenario, please let us know what you did and why. For example, “If I were writing this for production use, I would check an invariant here.” Since whiteboard coding is an artificial environment, this gives us a sense for how you’ll treat code once you’re actually on the job.

很多不太professional的地方，要有合理解释。

另外补几点

1. 写完代码后Refactor 尽量体现出来，别只是说说，就想symmetric difference那个，在后面聊天的时候，要改动代码，因为已经清楚哪里有问题了，一定要改，不要只是留在那里，因为interviewer 是要要代码copy下来保留凭证的，也就是说，会有第三个人来看这份代码，显然我们没机会跟第三人解释！能refacor多少就refactor，代码写漂亮了。

2. 面试官指出bug的时候，一定要修改所有地方，记得又一次用int[] 设置Integer.MAX_VALUE做flag, 后来不用了， 这块初始化的代码没删掉（这块在class代码块中，不在method里面），我想的是我把逻辑已经改好了，我理解你意思并且改正了，你也知道我懂了，那个就放着吧，等你继续说别的。但是实际上是，他没办法容忍，或者说他可能也在帮我，因为这个代码要给别人看。 所以即便你知道了并且改正了一处，他也知道你懂了，沟通没问题了，你还是要改相关的地方。

3. 所有沟通的原则，就是，不要犟嘴，人家说啥你答应啥，有个题涉及两个数组问我time complexity，我说O(m + n), 其实就是O(n). 印度小哥问我为啥不是O(n).... 后来我俩沟通一下才说没问题，OK。可能他开始以为我不知道这是O(n).... 要让面试官尽可能的爽。

最后说说，其实公司要什么样的人，自己很清楚，是不是够聪明，面对未知有没有解决问题的能力，是不是很和善，容易沟通，还有基本的编程能力，既然我们都懂，就不应该回避一些点，应该直面这些能力的缺失，去不断提升，不断完善，我觉得自己在很多方面真的是有待提高，很多时候面试慌张，都是因为这些，还有我所谓的盲点，知道哪块不行，早TM干啥去了，非得面试前才去学么。总之，刷题容易，贯通不易，切刷且珍惜吧，对自己说句加油。

LeetCode Summary(3) -- Two Pointers

这个的分类是完全按照Peking2的分法， 解决的题目非常大，Two Pointer 只是一种思想，实际的情况不一定是完全的Two Pointers，有很多衍生。

总体来说，这部分题目思路上难度都不大，感觉就Sliding Window 难一些，拿到题目以后基本上可以快速反应，但是编程上细节很多，尤其是linked List 容易错，思路都搞定了，其他就通过练习来搞定！


题目数据结构: Array, String,  LinkedList.
解题技巧: Two Pointer, Three Pointer,  Index, Sliding Window


Two Pointers 三种类型

1. 两个Pointer 从start, end 往中间走: 主要是 Array的题目。

在Array的问题里面，Two Pointer 解决的问题主要是 O(n^2) 的Brute Force的效率问题，下面的题目Brute Force 都能做，但是这不是考点， LeetCode 上这类题目一定Two Pointer 才能AC.

• Two Sum
• 3Sum
• 3Sum closest
• 4Sum
• Sort Colors
• Container With Most Water
• Trapping Rain Water
• Binary Search (See Summary 1) O(n) -> O(log(n))

1. Two Sum
Two pointers 的方法要注意，数组是没有sorted的， Two Pointer 一定要用在sorted 数组上，复制数组不能直接用 引用，必须new 新的出来，用Arrays.arraycopy 复制内容. HashMap的方法记住，存的是Key 是 numbers[i], value 是index

2. 3Sum
跟Two Sum 的不同就是，1.多了一个元素，2.有重复，3. 结果不唯一，结束条件不同。 这样需要套一层循环，固定住第一个数，剩下的 i+1 到 n - 1的部分，套用two Sum的方法。这道题去重很重要，在于 i, start, end 坐标移动时候的重复值的skip

3. 3Sum closest
找close to target 的值，需要维护一个minValue 使得 Math.abs(sum - target)，因为假设有一个solution，所以不用管duplicates, 3Sum是要找所有的duplicate，自然要去重。

4. 4Sum
跟3Sum一样, 需要在i, j, start, end 除去重

5. Sort Colors
只走一遍，需要two pointer，redIndex 之前都是 0， blueIndex 之后都是2， 偏离A, 根据不同情况交换，1的时候i++.
挺有意思的

6. Container With Most Water
这个题目的一些特性使得我们可以用Two Pointer，容量取决于Math.min(height[i], height[j]). 
每次移动height 短得那个pointer，就一定不会skip最大值, 极端情况就是在在边界的时候最大，移动以后, j-i变小，面积也变小。

7 .Trapping Rain Water
对于每点，都需要计算window, [leftMost, rightMost], 当前的water = Min(leftMost, rightMost) - A[i]. 
优化一下，计算maxLeft[] 和maxRight[]. 在计算maxRight同时可以直接计算结果了，不必再用一个loop

2. 两个Pointer 从头往后走，快慢指针. 这是绝大多数Linked List题目设计的操作。Array 中也有部分题目利用这种思想，一般叫Sliding Window，解决一些跟序列有关的问题。

• Implement strStr()
• Minimum Window String
• Longest Substring without Repeating Characters
• Substring with Concatenation of All Words
• 
  
• Remove Duplicates from Sorted Array
• Remove Duplicates from Sorted Array II
• Remove Element
• 
  
• Remove Duplicates from Sorted List
• Remove Duplicates from Sorted List II
• Remove Nth Node From End of Test
• Reverse Linked List II
• Rotate List
• Swap Nodes in Paris

第一小部分除了strStr都是Sliding Window, 第二小部分是Array 的去重问题，都是有size 维护指定元素，另一个index 去遍历，第三小部分是典型的LinkedList Two Pointer的操作. 

1. Implement strStr()
注意 i < haystack.length() - needle.length() + 1. 一定别忘了+1.
O(m*n) m,n 为haystack, needle 长度

2. Minimum Window String
同样是Sliding Window, 主要是需要处理好什么时候包含所有T中字符，这里用count 和 HashMap的组合来控制. 
添加时候移动window右边，满足后，移动窗口左边直到不满足条件.
不同的地方是，window中包含不在dict中的字符，所以才构成了上述的解决方法。 

3. Longest Substring without Repeating Characters
需要一个leftBound 和i一起维护一个Sliding window, 
在用一个Hashset 来判断 下一个字符是否是重复字符, 比 遍历window中字符快的多
重点在于控制i遇到重复字符时候 窗口左端的移动


4. Substring with Concatenation of All Words
之前用permutation + strStr的思路超时. 等下再不这个题，跟 longest substring 差不多


5. Remove Duplicates from Sorted Array
in place.  定义size 指向不重复的最后一个，每次从A[i] 和 A[size] 比较，重复，就continue. 然后就A[++size] = A[i]

6. Remove Duplicates from Sorted Array II
需要跳过相同的，并且存储了两次以上得点，跟I基本一样，加了条件 size!=0 && A[size] == A[size - 1]

7. Remove Element
跟Remove Duplicates from Sorted Array 一样，区别是，因为elem 可能出现在 index = 0 的位子，而且每次A[i] 是跟
elem 比较而不是 A[size], 所以A[size++] = A[i]

8. Remove Duplicates from Sorted List
以后固定都用 current = head, runner = head.next while(runner != null)
每次在定义runner的时候都考虑是runner = head还是next，还有终止条件是current !=null or current.next != null. 
以后都是用runner 快一步，runner != null.

9. Remove Duplicates from Sorted List II -- dummy Node
特殊性在于找到duplicate, 不能直接move forward, 因为如果move了下次不知道这是不是duplicate了，所以要用while一次性全部删除


10. Remove Nth Node From End of Test --  dummy Node
N可以能等于List length, head可能被删除。p2 走n 步，然后p1,p2一起走 p2 走到头是 length - n, p1正好下一个点是Nth. 

11. Reverse Linked List II  dummy Node
in place. in one pass.
这个题目记得分段考虑，(1- m-1), (m,n) (n+1, end) part 主要是中间reverse part，需要标记prem，m, n, postn Node. reverse 从 m+1开始，因为是独立的部分，到时候还要拼接，没必要从m开始然后连上preMNode. 实际操作几点为postnNode.

12. Rotate List dummy Node
跟removeNth 差不多，找到以后nth node, rotate 即可，这道题目test case n > length. 所以要先得到length,再取余.

13. Swap Nodes in Paris
跟 reverse m,n 题目差不多, 需要一个lastNode 记录pre位，然后直接swap head, head.next. 不用把head 提到dummy 位. lastNode 一开始在dummy处.

3. 两个Pointer 控制两个不同的数组或者链表，一般出现在Merge相关的题目上

• Add Binary
• Add Two Numbers
• Multiply Strings
• 
  
• Merge Sorted Array
• Merge Two Sorted Lists
• Partition List

第一小部分都是String类型的计算题，binary的，还有 +，*. 第二小部分全是merge题.


1. Add Binary
跟merge的感觉一样，短的先结束，然后长得， 为了方便，如果a < b. 交换，让a 最长，最后都加完之后，记得判断carry > 0

2. Add Two Numbers
因为是list，不能判断长度，merge以后只能 判断 l1 != null  l2 !=null. 跟Add Binary 基本是一样的

3. Multiply Strings
比 Add Binary, Add Two Numbers 明显复杂一些，每次product计算需要考虑当前位置的值，因为当前值由两次计算加成. 还要记得最后trim 前面的无用的0.

3. Merge Sorted Array
注意到最后，如果 n > 0，要把B的再复制过来，m > 0 则不用，因为A前面已经sorted了

4. Merge Two Sorted Lists dummyNode
唯一要记得就是比较时候要，l1.val <= l2.val 小心漏掉 = 的情况

6. Partition List
根据value 不同，分到两个List中，这样可以保证preserve original order，然后merge一下，注意right.next = null 最后要，否则可能有相连. 

LeetCode Summary(2) -- Permutation and Combination

Permutation and Combination 题目很多, 算是基本题型，幸好大部分程序的框架都很类似，根据题目修改一些条件判断就可以了，答案需要统一化，这类题目没有任何理由不bug free，理解了之后 逻辑应该非常清晰，代码难度也不大.
这类题目实质就是DFS + BackTracking. 对于这两种思想的理解非常有帮助.


基本的Permutation & Combination 题目 7 道

• Permutation
• Permutation II 
• Subset
• Subset II
• Combination
• CombinationSum 
• CombinationSum II

应用场景题目9道

• Letter Combination of PhoneNumber
• Palindrome Partitioning
• Restore IP Address
• Path Sum II
• Sum Root to Leaf
• N-Queens I
• N-Queens II
• Work Break II
• Substring with Concatenation of All Words

Combination Sum Codes

     public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {  
         Arrays.sort(candidates);  
         ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();  
         ArrayList<Integer> list = new ArrayList<Integer>();  
   
         combinationSumHelper(result, list, candidates, target, 0);  
         return result;  
     }  
   
     private void combinationSumHelper(ArrayList<ArrayList<Integer>> result,   
             ArrayList<Integer> list, int[] candidates, int target, int position) {  
           
         int sum = 0;  
         for (int x: list) {  
             sum += x;   
         }  
           
         if (sum == target) {  
             result.add(new ArrayList<Integer>(list));  
             return;  
         }  
   
         if (sum < target) {  
             for (int i = position; i < candidates.length; i++) {  
                 list.add(candidates[i]);  
                 combinationSumHelper(result, list, candidates, target, i);  
                 list.remove(list.size() - 1);  
             }  
         }  
     }  

程序注意事项.

考虑

• 满足的条件使result.add(new ArrayList<E>(list)), 一定new 新的，否则添加list的引用无效
• for loop 中，有哪些element需要跳过，
• 递归的的条件是什么，传入i or i+1 等等， 这里编程注意，我老写着就写成position + 1了 

特性: 

1. Subset,  Combination, Combination Sum 的每道题目都要求 non - descending order，所以一定是要先Arrays.sort(S) 一下.  递归过程中要保证所取元素升序，需要position 来标记起始位， Permutation 不用，每次都从0开始

2. Permutation, Subset, Combination Sum. 都有duplicate 的follow up 题目, 面试很可能会连着问

1. Permutation
添加条件，list.size() == num.length. 够了才添加，每次取值都是从0开始取, 所以不需要position，i start from 0, 另外不允许重复出现，所以 list.contains(num[i]) 要continue

2. Permutation II 
多了duplicate的条件，之前的list.contains(num[i]) 显然不能用了，需要 boolean[] visited 来标记每个节点是否访问过，如果duplicate元素，第二个在第一个没用之前，不能用, 跳过的条件是，
visited[i] == true || (i != 0 && num[i] == num[i - 1] && visited[i - 1] == false)

3. Subset
和combination，permutation不同的是，添加到result的条件没有了，此时也不能return，subset必须用升序，来保证subset的唯一，所以先排序，每次添加的数字一定是大于第一个数字，递归时候需要 i+1. 

4. Subset II
多了duplicates的条件，和permutation II 差不多，需要skip掉 i != position && num[i] == num[i - 1]的element, 添加时候每次都是 i = position. 不用管duplicate，主要是回溯过程中，要考虑重复值的问题.

5. Combination
没什么特别，input 给的是n，记得从 1开始就好，别写成0了。

6. CombinationSum 
可以重复加一个element，所以每次递归，传入i，下次还从 candidate[i] 上取

7. CombinationSum II

每个element只能使用1次，迭代条件是 i + 1， 
同时多了duplicate的条件,  跟subset II 一样，skip掉 i != position && num[i] == num[i - 1].


场景题目

1. Letter Combination of PhoneNumber

一定要用递归思想，每次都是不同的group里选值, 所以每次调用的group都不同，建立 digits，每次调用的index， char[][] 的对应关系

index = Character.getNumericValue(digits.charAt(sb.length())); ---> 映射到 char[index] 

2. Palindrome Partitioning
很多分字符串的题目都是 combination 的，还有切割问题

这题非常考验对backtracking的理解，先分 prefix = str.substring(position, i +1)
新切割的时候， i = position，回溯的时候，i++，也就是interval变成2，3…回溯的过程中让interval 变大，这样可以控制所有的切割，只要判断prefix isPanlindrome即可，当切割到最后一位，position == s.length() 保存结果 
[a, a, b, b, a, a] --> [a, a, b, b, aa] -> [a,a, bb, a,a] --> [a, a, bb, aa]

3. Restore IP Address
IP 每个段得判断，得用long 防止12位的int溢出， 要判断 string 开头为0，length != 1的case
终止条件  list.size() == 4 && position == s.length() 跟Palindrome Partition 这个题目差不多，就是条件的变化

4. Path Sum II
主要是终止条件的判断, 对于一般节点，3种情况
1. root.left == null || root.right == null.  sum == 0  return  只有这种我们添加 到result
2. root.left == null || root.right == null.  sum != 0  return
3. root left, right 有一个不为空，不为空得递归到1.2 两种情况，另一种递归到 root == null. return. 
树跟int[] 没什么不同, 只是算完left，回溯到parent, 再算一遍右边.
helper(result, list, root.left, sum);  --> helper(result, list, root.right, sum)

5. Sum Root to Leaf
跟Path Sum II 基本一样，但是条件不能简单的归结为root == null 时候return，sum += value. 
因为这样的话，left，right 会各计算一次，还是按照path sum II的结构写

6. N-Queens I
本质是个排列问题，因为Queen的位置不一定是升序的，所以不需要position来标记。
skip的地方，需要查看isValid(cols, col) , 也就是插入 这个 col，原来的cols能不能valid, 不能就continue，
剩下的都是编程问题

7. N-Queens II
为了简便，写的和N-Queen一模一样，省掉了drawChessBoard. 返回result的size即可

8. Work Break II
这道题目直接用类似 Palindrome Partitioning的方式, 会Time Limit Exceeded, 原因是中间切割的过程有大量的重复计算，需要一个一维的数组来标记 (i+1, n-1) 有没有结果，DP问题。

9. Substring with Concatenation of All Words

还在超时中，没搞定

LeetCode Summary(1) -- Binary Search

Binary Search  题目

Binary Search 题目相对高频，因为套路固定，必须一次写对，几道题目大同小异。
相比于O(n) 的search，Binary Search O(log(n)) 搞定.

• Search Insert Position
• Search a 2D Matrix
• Search for a Range
• Search in Rotated Sorted Array
• Search in Rotated Sorted Array II
• Median of Two Sorted Array

下面这几道题目用的Binary Search 思想，但不是标准的Binary Search. 

• Divide Two Integers
• Pow(x, n)
• Sqrt(x)

Source Code

 public int search(int[] A, int target) {  
         if (A == null || A.length == 0) {  
             return -1;  
         }  
           
         int start, end, mid;  
         start = 0;  
         end = A.length - 1;  
    
         while (start + 1 < end) {  
             mid = start + (end - start) / 2;  
             if (target == A[mid]) {  
                 return mid;  
             } else if (target < A[mid]) {  
                 end = mid;  
             } else {  
                 start = mid;  
             }  
         }  
    
         if (target == A[start]) {  
             return start;  
         }  
    
         if (target == A[end]) {  
             return end;  
         }  
           
         return -1;  
     }  

• start + 1 < end
• mid = start + (end - start) / 2;
• A[start], A[end] 的判断别漏

每个题目需要关注的是

• target 和 A[mid] 的判断条件，以及对应的动作
• 最后的结果处理，整合

1. Search Insert Position

这题目主要处理corner case. [1,3,5,6], 2 → 1, [1,3,5,6], 7 → 4,[1,3,5,6], 0 → 0

最后在处理结果时候，除了 start, end 还要考虑是不是 target > A[end], target < A[start]. 

其实这5中情况可以和套路中 start，end 判断合并(每次写好代码记得看看能不能简化)

target <= A[start] -->  start;   target > A[end] --> end + 1;   else --> end;

2. Search a 2D Matrix

这题其实跟 search in int[] 一样， start = 0， end = m * n -1; 主要是mid 取值的处理，

element = matrix[mid / n][mid % n]

3. Search for a Range
这题很好，要走两边，先取leftBound，再取rightBound. 

代码上的处理: 

a.取leftBound 时候, target == A[mid] --> end = mid;  像个window 一样左移，这样即便是取到了duplicate的右边，最后一样能取到最左边的那个 target. 

因为一定是end 或者start 的一个，所以 在边界处理的时候会给 bound[0] 赋值，

b. 取rightBound 一样，只是 start = mid; 最后要先判断 target == A[end]. 因为test cast[2, 2] 2.

c. 第一次可能找不到target，记得直接return [-1, -1] 省下第二遍，第二遍如果进行，一定有值

4. Search in Rotated Sorted Array
Binary Search 一定要在Sorted 的部分进行，所以要先判断连续空间

A[start] < A[mid] (start, mid) 连续，判断 target >= A[start] && target < A[mid]

A[mid] < A[end] (mid, end) 连续,  同理

5. Search in Rotated Sorted Array II
与I 不同的是, 多了一种情况 A[mid] = A[start], 但是因为很多case，不能轻易用

A[start] <= A[mid]. 这样保证不了 (start, end) 连续，所以此时，start++, skip 掉useless节点

case [1, 3, 1, 1, 1] 3

6. Median of Two Sorted Array
TODO:
这题O(log(m+n)) 的方法我还没细琢磨明白.



1. Divide Two Integers
限制了操作类型，Can't use *, /, %. Could use +, -, <<,  >>.  正负号不用管，都弄成正得，用变量记录下来正负，结果时候加上就行.  要用long 代替int，防止overflow

用bit 比较方便，用a - b的最大倍数 (b << shift) <= a. 

result += 1 << (shift - 1); a -= (b <<(shift - 1)); 

2. Pow(x, n)
Recursive + Binary Search. 

求Pow(x, n)，先求Pow(x, n/2)，注意n % 2 == 0? 这样递归往下走,  用Binary Search 比每次* x 快的多得多。注意n < 0 以及 n = Integer.MIN_VALUE的case

3. Sqrt(x)
先理解题意，不能整开方的，比如83， sqrt 是 9. 都是int，别傻不拉几以为不能算呢.
从start = 0, end = x / 2 + 1. 来算, 最基本的Binary Search，但是要注意 mid * mid overflow，所以这里都是 mid == x / mid 来比较，即便是不考虑溢出，这样也是有好处的，比如说 83/ 9 == 9,
如果用 *, 不相等.

LeetCode Summary(0) -- Introduction

写一点总结分享一下，也能帮助我多积累一下。我感觉平时贪的太多了，必须定期总结才能巩固啊。

目前题目剩下的一部分需要一点数学推理，找规律的，就是那种知道了就知道了，没见过很难一下子想出来思路的题目，最近时间很紧，无暇顾及，现在总结剩下得常规和高频题目. 

写总结受 peking2的启发，看到他的总结很有意义，还有小美女的总结。两个人的原文我附在这里

peking2: http://blog.sina.com.cn/s/blog_b9285de20101gs7f.html

喵酱 Meow: http://jane4532.blogspot.com/2013/06/zz-from-peking2.html

很多内容会借鉴peking2的，除了第一篇外，尽量都干货，而且会一直更新这几篇总结的文章，比如碰到有类似解法或者规律的，我会持续补充。因为没那么多时间，写的比较随性，有时间会来重构。

有时间的话，我想把整个准备的过程都写一写，除了刷题这部分，还有OOD, design pattern, Big data, System Design等其他方面，现在感觉非常零散，很难有效组织，感觉总结非常有用。

我会按同类题 或者 专题来总结，先列个目录

1. Arrays and String

2. Linked List

3. Stack and Queue

4. Tree(DFS, Divide&Conquer, BFS)

5. Graph

1. Binary Search and nlog(n) Sorting

2. Permutation & Combination

3. Two Pointers  

4. Bit Manipulation. Number operation (Integer overflow 等问题的一类)

5. Dynamic Programming

面试题由这几部分组成

1. Question  读懂题目是最最关键的！

a. Data Structure

一般情况下都会有数据结构, 都是基本的, 也有些题目没有要求. 

b. Time Complexity

很多题目限定了时间复杂度，比如Median of Two Sorted Array. 限定O(log(m+n)). 这种在一定程度上决定了算法，比如这个题目，一定是Binary Search，而不能merge into new Array，then Binary Search， 这样则 O(m+n) + O(log(m+n)) -> O(m+n).

c. Space Complexity 

Set Matrix Zeros,  O(m*n) 来记录0位可以，O(m+n) 一行一列也可以，但是这道题目终极要求是constant solution, 就要考虑用已有空间(第一行，第一列) 来做标志位，跟Time Complexity 一样，Space Complexity的要求对我们一样是提示。

2.  Solution

a. Data Structure

in place. 比如 Set Matrix Zeros，要求利用已有的数据结构。可能采用新的数据结构，比如Inorder Traversal, Valid Parentheses 用到了stack.  Level-order Traversal 用了queue 一样，需要快速反应.  stack & queue 那节会总结应用题目。

b. Algorithm

Solution中的算法和数据结构关系非常紧密，互相决定。

3. Coding

a. 编码风格

很多小细节，我觉得我代码没问题. intent, 操作符两边空格，花括号空格等等。

Google 代码风格 http://google-styleguide.googlecode.com/svn/trunk/javaguide.html

b. 编码能力

这是最关键的一块，每个人写出来代码都不一样，也是日积月累的过程。

选择逻辑较清晰的方式写，有些太取巧的尽量少用. 比如Two Sum用 HashMap的O(1) 方法

• 注意input判断，if (num == null || num.length == 0) { return null;}
• 多条件下，注意if else 的条件整合，使代码清晰，比如Search Insert Position.
• 循环的边界

争取做到bug free

4. Test Case

写完代码，检查一下没问题以后，写test case. Test case 写也很注意，不要觉得肯定没问题，想当然的忽略掉corner case， 这些要写出来，这是给面试官看的。

• 正常的 Corner Case，比如num 为空， 或者num.length == 1. 就 root一个节点
• 正常的 Case
• 极端的 Case, 比如 pow(x, n)   n = Integer.MIN_VALUE

很多corner case 是影响代码逻辑块的，不要写重复无用的case， 减分项，没有test 能力.

做题思路总结:

1. 拿到一道题目后，首先应该读清楚题目，有时候题目非常晦涩，不容易读懂，一定不能模棱两可就开始写，面试中这是扣分项，double check 题目，不好懂的，让interviewer 举 例子，用例子理解题目相对来说会轻松不少。

2. 确定大体的数据结构和算法，跟面试官简述大体思路，做过的题目相信思路上没什么问题， 只是具体细节需要再考虑，没做过的说下大体的，然后就开始写，一遍写一遍考虑，前面写的过程中没必要跟interviewer扯淡，集中精神写。

3. 会的题目，写好以后，写test case 测试，有时间再加备注，完整阐述。 不会的，讲思路，讲卡在哪里，communication 至关重要！