目前题目剩下的一部分需要一点数学推理，找规律的，就是那种知道了就知道了，没见过很难一下子想出来思路的题目，最近时间很紧，无暇顾及，现在总结剩下得常规和高频题目.
写总结受 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 至关重要！
No comments:
Post a Comment