Fwd: 如何做cc150算法题 zz

高频题：

http://blog.csdn.net/sushiplus/article/details/17596305

解题思路和答案：

http://hawstein.com/posts/ctci-solutions-contents.html

Coding前问好问题：

当我看cracking这书时，把注意力更多的放在了解题上，经常是一看到题目就提笔想解决办法，然后coding。这种做法，不论是在实际的解题过程中，还是在面试中都是不可取的，这也是导致我被拒的主要原因，我觉得。就目前我面过的而言，面试官想看的往往不是你多聪明，多快地想出解决办法，是否给出了最优解，而是想知道你解决问题的思路。当然能够给出最优解也很重要，但不能一开始就把重心放在这上面。我们平时上课写作业时，老师给的问题不会很模糊，也不会很复杂，需要的条件和假设也都会事先给你，往往不需要你考虑很多细节。但面试过程中，面试官问的问题往往很模糊。虽然模糊，但你真要立马coding也可以，不过coding时需要考虑到非常多问题，考虑的情况太多，会把程序复杂化，也很容易扰乱你的思路，应该没有几个面试官会喜欢这样的。为了能够很好的解决问题，需要你问一系列clarifying问题，把problem具体化，把那些需要知道的细节都理清楚，比如一个字符串多长，是不是null terminated的，有没有memory limit，等等。我想实际工作中解决问题的情况不比在学校时，对于任何给你的问题，都先搞清楚它的background，各种可能的影响因素，然后才能在这些给定的条件或假设下给出解决办法。不要害怕问问题，也不用担心问问题会让面试官觉得你不会做这题目。至于问什么样的问题就取决于问题本身了，尽可能地做细致地考虑。现在我看到问题会想一下有哪些unclear的地方，但考虑的只是一些可能影响到coding的细节，还是不够细致，问的问题也不够多。

现在看来，做cracking上的题目时，主要目的不是记住什么样的问题用什么样的解法，而是培养解题的思路，如前所说的，问那些clarifying question，该考虑那些因素，等等。拿到一道题，先读题，思考，然后发问，列出哪些问题需要clarify，然后想解决办法。cracking里每个问题的sample answer都值得好好读一下，不只是看代码，还要看下人家是如何思考如何发问的。我虽然做了不少题，但把重点都放在写代码上了，没有练练前期的思考发问

Coding：

等所有的疑问都clear之后，才开始写代码。写代码也挺重要，尽量不要出现bug。写代码的过程中还要和面试官交流，不能埋头在那些。不过边写代码边说有点难度，还会影响思路，比较好的办法是，写完一个block就说一下这个是干嘛的。写完code之后，不要马上和面试官说写完了，应该自己先复查一遍，找出可能的问题，修改之，然后再说完成。之后面试官可能会让你测一下代码，或者让你改进，或者改变问题后让你修改代码等等，得有心理准备，follow up的问题可能很刁钻。根据面的岗位不同，follow up的问题可能和特殊的岗位有关。比如ms时我面的testing职位，四个面试官都问了我testing的问题。不过不是单独给我问题让我test，而是基于之前写的code，做的设计等进行测试。如何测试可以看看cracking书上的testing章节。针对问题找比较好的解决方法和coding过程就取决于平时积累和临时准备了。网上有各种各样的面试题和面经，careercup，glassdoor，mitbbs。为了gg和ms的面试，除了做了cracking上的一些题，我还找了些面经里出现的题目看。

如何回答技术问题

1. 问好问题, 以缩小原问题的范围, 如数据类型是什么, 数量级有多大.尽量假设更多的条件

2. 设计算法时,需要考虑的问题

   • 空间和时间复杂度是多少?

   • 如果输入数据非常大会发生什么事情

   • 你的算法设计是否会导致一些副作用

   • 一定要考虑和利用题目本身提供的输入数据

3. 写出伪代码

4. 认真写出真实的代码

5. 测试你的代码

五种解决算法题的方法

1. 从示例数据推导出规律以及解题算法.

2. 模式匹配: 从题干,推导出相应的算法.

3. 将复杂的问题简化,抽象

4. 从简单/基本的情况, 反推导出复杂情况时的解决方法

5. 数据结构遍历和匹配, 通过题干的内容,遍历自己了解的数据结构,然后找到合适的一个以解决问题

Question

Data structure in question

Data structure in solution

Algorithm in solution

Coding


题目：非常关键，一个题目通常有一些相应的变形题目，同一个题目可能有不同的要求
。比如时间复杂度，空间复杂度的要求，比如recursive,
iterative的要求。而根据题目的变形与要求，可能会极大的影响到你能够采取的数据
结构和算法。


问题中的数据机构：问题中有可能带数据结构，有可能没有数据结构，有可能是可以自
定义数据结构


解决方案中的数据结构：可以是in-place的，也就是利用已有的数据结构，也可能是创
建新的数据结构。新的数据结构跟已有的数据结构没有必然的联系，而很多问题都是一
题多解，可能采取不同的数据结构。


算法：一般来说，当解决方案中的数据结构确定以后，算法也就确定了。同样，一旦解
决方案的算法确定，相应的数据结构也就确定了。这两个没有先后的关系，但解决方案
中的数据结构和算法具有非常紧密的联系。


代码：非常关键。代码就是解决方案的数据结构和算法的实现了。目前来看，题目，数
据结构和算法在面试中出现的类型比较固定，因此代码的好坏则是拉开面试者水平的一
个有效手段。这也是为什么F，G如此看中代码的质量了。我发现上面几点比较容易突击
，但是写代码的功力还是需要实打实的积累的。