链家，一面卒

链家面经：一面跪

远程

关于远程笔试，只记得两道题，详见：

现场笔试 && 一面

首先进行一个小时的笔试。一面的主要内容就是讨论笔试题，然后聊了一些简历上的东西。面试官人很和蔼，沟通起来不累。笔试题如下：

1、有一个数组包含1000w个整数，给定一个整数n，在数组中找到所有ai和bi，使得ai+bi=n，写出代码。

首先想到了暴力法，时间复杂度是O(n^2)，然后使用了一个桶排序优化暴力。其实能不能优化心里也不清楚，感觉可以就写上了。

补充：感谢 @zssasa

Two Sum问题：http://blog.csdn.net/u010429424/article/details/77648989

2、二叉树，找到两个节点的最近公共父节点，写出代码。

由于题目没有给出二叉树的输入形式，因此根据以往的做题经验，如果二叉树以数组的形式给出，则直接用公式就能计算出父节点。比如二叉树【1，2，3，4，5】，则4、5的父节点下标为(3-1)/2 = 1和(4-1)/2 = 1。

如果二叉树以树的形式给出，分两种情况考虑，如果二叉树节点中有指向父节点的指针，则可以通过这个指针很方便地找到公共父节点。如果二叉树中没有指向父节点的指针，则先通过dfs找到根节点到4、5节点的路径：1、2、4和1、2、5，路径使用链表存储，然后从4、5向前找到第一次出现的公共节点。

但是面试官说，通过遍历树会有更好的方法。

补充：通过后续遍历，可以解决这个问题：https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/discuss/

3、一个袋中有n个球，球上面有标号，标号可以相同也可以不同。如果袋中球的编号之和大于编号之积，则叫做幸运袋，反之就是不幸运的。比如【1、3】1+3 > 1* 3就是幸运的；【2、3】，2+3 < 2 * 3就是不幸运的。现在给出一个有n个球的袋子，可以去掉m个球使得剩余的球构成幸运袋，问能够成的幸运袋的个数，写出代码。

没有思路，笨啊

4、通过IP怎么查找到城市。给出一组IP地址和对应的城市名，问使用怎样的数据结构，能够找到城市，写出代码。

第一个思路使用Trie树来存储IP，叶子节点对应城市。但看到题目的函数输入是整型的ip，瞬间感觉也可以用Hash来做，key是ip，value是对应的城市。因为不知道怎样把ip转换成int，被面试官鄙视了。。。。（当时说ip本质上也是用二进制来表示的，因此可以通过位运算转换成int）

补充：Ip转long  http://www.mkyong.com/java/java-convert-ip-address-to-decimal-number/

5、编辑器的undo撤销，redo恢复怎样实现，写出代码。

看到这道题的第一反应就是Git。但是不懂git的数据结构，只能装模作样地设计了一个双向链表。这样，通过指针的改变就能很快地前移和后退。结构又被面试官鄙视了~

（补充：后来听同学讲可以用两个栈来实现，参考：http://blog.csdn.net/cb0912cn/article/details/444393）

聊简历时，因为简历上写了一个图像处理方向的项目，面试官对这个项目发问较多。感觉自己回答的思路还算清晰。之前准备的Java基础知识都没有被问到，可能在这个时候面试官就已经把我pass了吧。

欢迎大神补充，自己太菜，回头总结一下，再接再厉 :-)， 注：侵必删