中午吃饭的时候上次的GG打电话过来要求面试，简单协调后定在下午2:00.
以下流水账：
1. 自我介绍一下（<1min搞定）
2. 问了一下科研工作里面关于Cache的一些研究，具体怎么做，性能提升等
3. 数据结构：反转单链表
4. 如何判定链表存在环（如下图所示）
我就说用visited标记一下结点，然后顺序访问，当遇到visited=true的结点就说明有环了。
又问如果不让你在结点上做修改呢？我说可以在外部维护映射表啊（好像有点无语），这题就这么PASS了。
后来查了一下可以用双迭代器实现，一个步长为1，另一个步长为2，如果过程中相遇则说明有环。
下面是威武的算法
5. 如何求得两个字符串的距离？
距离的定义：将字符串A通过若干步原子操作变为字符串B，所需要的最小操作步数称为两个字符串的距离。
原子操作包括：
添加：在字符串的任意位置加入一个任意字符
删除：删除字符串任意位置的一个字符
修改：将字符串任意位置的一个字符替换为任意一个字符
我给了一个基于LCS的算法，具体方法就是用LCS把A/B分别切分为N+1份（LCS长度为N），分别计算这N+1份对应的距离，最后相加即可。
后来才知道这题是标准的动态规划，所以我的做法是非主流。
让我证明我算法的正确性。沉默了一会我表示无法证明正确性，但对面也表示举不出反例证明我的算法有错误。
顺便又问了怎么用动态规划做LCS，我很实诚地说我忘了（这是真的）。
然后在引导下成功地得出了用动态规划求解距离的方法。
6. 一个数组（乱序）中，除了一个数x外，其他所有数都是成对出现的（比如2有2个，3有2个，4有2个…），如何找出这个x？
很直观地用计数统计做，被否定（数组非常大，无法放进内存）。
后来告诉我可以用异或做，将整个数组中的数进行异或，成对的数异或过都是0，最后的结果就是这个x.
然后让我在这个的基础上解决有2个数个数为1的情况下，如何找出这2个数？（即除了x,y外，其他数都是成对出现的）
我马上又傻了，不过得出一个结论就是这个数组异或之后的结果不为0（因为结果等于x^y=z，而x!=y，所以z不为0）
又让他引导了一下，既然z不为0，那么z中至少有1位二进制位是1，那么取这一位二进制数为z'.
显然x&z'与y&z'中有一个为0，一个不为0.
那么可以用z'做mask，将整个数组中的数与z'逐个取&，将结果等于0的加入序列1，不等于0的加入序列2.
显然成对的数不会被分开，而x,y必将分别进入序列1,2.
剩下的和之前的一样，只需要分别对序列1,2整体取异或，得到的结果就是x,y了。
面试到此结束。
让我回去思考思考如果再复杂一点，当这样的数有3个的时候如何找出？
对面问我还有什么问题，我就问了个最常见的：你们平时的工作是什么？
做了简要介绍，大概就是广告投放，广告初筛结果的rank.
然后我要求他们不管结果如何，都给我反馈，即使我表现不佳没有通过面试。
对面马上安慰我说你放心，你今天表现很好，马上会有二面。
听了以后比较放心了，客套过后挂机。
更多请关注：http://www.cnblogs.com/mdyang/archive/2011/05/04/2036587.html