在工作中，我们总是会碰到各种各样的问题，可是你是如何解决的呢？碰到容易的，已经解决过类似的问题，那还好说，举一反三就好了，可是如果碰到一个新的、棘手的问题怎么办呢？
前天会山东老家，跟侄子聊天。侄子学习不好，在家里还不帮着干活，我就跟他说让他学着帮忙干点什么，其中一个就是让他学习看秤。跟他说了几次后，为了验证他是否学会了，我就给他出题，随便将秤拨到某个地方，让他认是几斤几两。有的时候，他就两眼瞪着撑杆不说话，我就着急，担心他不会。我就说说，刚才是怎么跟你说的，用手指出来哪是一斤，哪是两斤，两个点的距离相当于多少。。。他指着秤上的星点，一个一个的，说对了，出了几个题目，他都做对了，我很满意。联想到最近的面试，我发现我满意并不仅仅因为他说对了，而是他一下一下地指出来哪是一斤哪是二斤，哪是一两二两，这种方法会了，而且把它给说出来了，所以我觉得他掌握了方法，相信他其他的也都可以很容易认出来，所以我认为他真的会了，才高兴。想到最近的面试，我发现其实面试官希望看到的也是这样的一个过程，你是怎么做出来的，你的方法是什么，你的过程是怎样的，etc. 为什么这些很重要呢？因为面试时间很短，大家没法知道你是不是走运而把问题解决了，如果面试时因为走运而通过了，但平时工作中怎么不可能时时都有运气，如果不是总是有运气，那将来也就没法应付新的工作了，尤其面对新的领域时，更是如此。所以，面试中表达清楚你的方法，解答过程是非常重要的。
Problem Solving有很多种方法，不同的问题需要不同的方法，常见的方法比如：类比、分而治之等等，更多的可以看看http://en.wikipedia.org/wiki/Problem_solving。这些方法都是很高层次的描述，在SDE面试中真正需要用到的往往更多的是CS里的方法，比如递归、用栈、用队列、用分而治之等，往往需要我们不但能够灵活应用，而且能说明为什么要使用其中的某个方法，比如为什么用divide and conquer，为什么用递归，为什么要用栈而不是队列等等。除了这些具体的方案外，我们也需要说清楚我们的策略，比如我们要把这一部分数据按照某个特定顺序处理，并与其余部分分割，为了达成这样的目标，我可以选用加marker或者分别保存的方法，经过验证，只有一种方法可以用，那再说清楚怎么用；如果两种都可以用，那说明白Pros and Cons，然后选择一个，并实现之。。。。
概括来说，我们在解决一个problem时，总是要有个步骤，或者总纲一样的东西：
- 分析问题：分析问题一方面要clarify assumption[看What’s the assumption you are mading]，一方面要找到问题的特征，以便于用合适的思路寻找办法。
- 解决问题：找到办法后，还需要比较一下，然后选择合适的办法来解决它。
- 验证问题：测试一下，设计一些test case，验证一下，看System Thinking。
下面是《Cracking Coding Interview》给出的五种找到算法问题解法的方法，可以帮助我们分析问题：
1. EXAMPLIFY: Write out specific examples of the problem, and see if you can figure out a general rule
Example: Given a time, calculate the angle between the hour and minute hands
Approach: Start with an example like 3:27 We can draw a picture of a clock by selecting where the 3 hour hand is and where the 27 minute hand is
By playing around with these examples, we can develop a rule:
» Minute angle (from 12 o’clock): 360 * minutes / 60
» Hour angle (from 12 o’clock): 360 * (hour % 12) / 12 + 360 * (minutes / 60) * (1 / 12)
» Angle between hour and minute: (hour angle - minute angle) % 360
By simple arithmetic, this reduces to 30 * hours - 5 5 * minutes
2. PATTERN MATCHING: Consider what problems the algorithm is similar to, and figure out if you can modify the solution to develop an algorithm for this problem
Example: A sorted array has been rotated so that the elements might appear in the order 3 4 5 6 7 1 2 How would you find the minimum element?
Similar Problems:
» Find the minimum element in an array
» Find a particular element in an array (eg, binary search)
我们可以发现结果的区别性的特征，然后进行解答。比如说在某个二叉树中找到最长路径（不含折返路径）。分析其特征，如果某个节点在这个路径上，那该路径必然同时过其左孩子和右骇子，那我们就可以从跟节点开始一个个验证，直到找到那个节点为止。
3. SIMPLIFY & GENERALIZE: Change a constraint (data type, size, etc) to simplify the problem Then try to solve it Once you have an algorithm for the “simplified” problem, generalize the problem again
Example: A ransom note can be formed by cutting words out of a magazine to form a new sentence How would you figure out if a ransom note (string) can be formed from a given magazine (string)?
Simplification: Instead of solving the problem with words, solve it with characters That is, imagine we are cutting characters out of a magazine to form a ransom note
对于有多个变量的问题，我们是否可以考虑假设将某一个变量固定，然后考虑其他变量，是否就可以找到答案了呢？
4. BASE CASE AND BUILD: Solve the algorithm first for a base case (e g , just one element) Then, try to solve it for elements one and two, assuming that you have the answer for element one Then, try to solve it for elements one, two and three, assuming that you have the answer to ele-ments one and two
Example: Design an algorithm to print all permutations of a string For simplicity, assume all characters are unique
5. DATA STRUCTURE BRAINSTORM: This is hacky, but it often works Simply run through a list of data structures and try to apply each one
Example: Numbers are randomly generated and stored into an (expanding) array How would you keep track of the median?
这些方法会帮助我们找到解决问题法方法，但是这还是不够的，我们还要能够清晰地表达出推理的过程。
下面是《Cracking Coding Interview》给出的解答technical interview question的五步:
- Ask your interviewer questions to resolve ambiguity
- Design an Algorithm
- Write pseudo-code first, but make sure to tell your interviewer that you’re writing pseudo-code! Otherwise, he/she may think that you’re never planning to write “real” code, and many interviewers will hold that against you
- Write your code, not too slow and not too fast
- Test your code and carefullyfix any mistakes
除此之外，我还要说一下，如果我们碰到一个问题，但是我们自己心里做了一些分析以后，没有找到思路怎么办呢？ 这是很容易碰到的，首先不要慌，就把它当成日常工作中碰到问题那样，想办法来解决，当然前提是你已经问了足够多的assumption clarification的问题，已经彻底明白了问题的各个细节了。然后就当是跟面试官聊天，说说自己的想法，你理解的难点在什么地方等等，如果注定要fail，也要有风度一些！！！！