一面：
给你一棵二叉树，如何判断它是否是完全二叉树？ 最开始我连完全二叉树的定义都忘了，面试官提醒我之后我才明白是啥。。汗。我当时回答的是先把它转化成数组的形式存储（就是2*n存左孩子，2*n+1存右孩子的存法)，然后循环判断一下是不是所有的结点都是在数组的前m个位置。
给你一个数组，求它的一个子串，使该子串的和最大。 这是典型的最大子串和问题，我直接就说这是个经典的动态规划问题：令F[m]表示以第m个数为结尾的所有子串中和最大的子串的子串和。则若F[m-1]>0,则F[m]=F[m-1]+a[m],若F[m-1]<0，则F[m]=a[m]。求出所有F[m]中最大的一个就行了。
vector是如何实现的？ 这个简单到爆了，我寥寥几句说完了。
C++里，虚函数是如何实现的？ 我一听就明白想说的是vptr和vtable,直接说：如果一个对象含有一个以上虚函数，则它的对象中有一个vptr，指向该对象所属类型的虚拟函数地址表（vtable)，这样，就能根据一个对象的实际类型来确定要执行的函数地址了。
C++里动态申请一个数组是用的int *p=new int[10]类型的方法，而销毁时，则是用delete [] p ，请问，delete时，没有指明销毁空间有多大，它是如何知道要delete的数组是多大的？如果你来设计C++,你会如何来实现？ 这个我之前确实没思考过，我想了会儿，说可能是new时在前面多申请出几个字节，用来存该申请出区域的大小。这样，返回的p可能不是申请出的首地址，delete时，用p往前几个字节，就能知道数组有多大了。后来网上查了查，似乎确实是用差不多的方法实现的。
给你一个随机数发生器，它有p的概率生成0，1-p的概率生成1，现在让你设计一个随机数发生器，有1/2的概率生成0，1/2的概率生成1. 这个想了好一会儿没想出来好方法。后来面试结束后，让大二大三的想，他们找到了个方法：用给出的随机发生器，随机生成两次数字，由于先1后0和先0后1的概论是相同的，都是p(1-p)的概率，所以，如果先1后0，就输出1，如果先0后1，就输出0.如果同1或者同0，就重复试验，直接两次生成的数不相同为止。
给你一棵树，并给你两个结点，如何求它们的最近公共祖先？ 我一听最近公共祖先（LCA问题)，直接说能用tarjan算法来算，然后他又让我说明具体怎么算，我想了好一会儿才想清楚具体的过程。说完才意识到他现在只是问求一次最近公共祖先如何求，我又说，如果只求一次的话只需要简单的一次搜索就可以了。。而求多次的话，每次都搜索太慢，可以用上面说的tarjan算法或者用一次搜索先转化成+-1RMQ问题来求解。
请详细说明如何使用socket。 这个我以前我用C语言和C#都写过socket程序，所以对这个很是熟悉，又是直接说了一通。
TCP和UDP的区别是什么？ 我说TCP是面向连接的，UDP是无连接的。
请详述TCP的三次握手的过程 这个我当时确实不会，就直接说没了解过。
关于虚拟内存管理，说说你的看法。 这个，我当时不太了解，不过猜测和cache管理比较类似，然后就按cache管理答了些东西，后来看看，大致还算比较靠谱。
你有什么问题想要问的没有？ 这个说是问题也可以算是个问题吧，我就随便扯一点点，然后帮同学问问一个同学为什么还没接到电面通知，他说他会帮我问问的。
然后，面试完和面试官闲谈了谈，谈到我在大连理工参加的大连赛区的ACM比赛，面试官似乎之前在大连理工上过学，他说似乎大连赛区这个比赛的申办和他还有些关系…
二面： 先是在去往面试地点的路上，电梯里，聊了聊ACM相关的东西，他问我现在中国有几个赛区，我说五个，他说“现在这么多赛区啊”，看样子他以前也参加过ACM。面试开始后，他最开始先是让我自己讲一下我写的OJ系统的工作原理，我扯了一堆linux系统调用之类的东西，然后，他似乎感觉不错，开始一直问我算法方面的题目。 第一道题是让我在纸上写一个什么函数，现在忘记到底是啥函数了，反正不太难，不过在纸上写代码确实有些郁闷。 第二个题是给了一个链表结构，让我写个代码使这个链表中的相邻的元素两两进行交换，比如1 2 3 4
5 交换成2 1 4 3 5，最后剩余的元素不再交换。就这么个简单的程序，我竟然写了好一会儿，写错了n次才终于写对。当时感觉到自己真是弱爆了。 第三道题说的是有m个数，其中部分数能分到集合一里，部分数能分到集合二里，部分数可以分到集合一也可以分到集合二，现在给你集合一的容量和集合二的容量，如何划分这些数（可以分到一个集合中或者不放入任何一个集合），让两个集合中数的和最大。我刚开始把容量理解成是放进这个集合中的数的和不能超过这个定值，当时想了一会儿没想好具体怎么去搞。后来他准备去引导我把这题搞出来，在他引导我的时候，我才明白原来他说的容量是指放入的数的个数，我立刻说这题能用贪心算法来做，就是从大数到小数排序，用三个变量a,b,c分别表示集合一剩余容量，集合二剩余容量，和总剩余容量，然后从大到小对这些数一个一个进行处理，如果待处理的数只能放到集合一中，则让集合一剩余容量减少，总剩余容量减少，如果只能放到集合二中，则让集合二剩余容量减少，总剩余容量减少，如果既可放到一也可放到二，则只让总剩余容量减少。如果某个数只能放到集合一（或二）中，而集合一（或二）的剩余容量已为0，则该数不放入任一集合，当总剩余容量为0时算法停止。
第四道题说的是连连看游戏，说是给你一个连连看的初始状态，现在让你判断某两个位置的物品是否能够消除。 我想了一会儿，说可以先横着枚举，从两个物品都往横方向发一条直线，枚举这两条直线上由该物品可直接到达的点，看看这两条直线上这些点有没有横坐标相同并且中间没有阻挡直接到达的情况，如果有，则证明可以消去，如果没有则不可消去。但是我也知道这个方法似乎很慢。主要就慢在判断两个点是否没有阻挡直接可达上。然后，我又说要不行的话先预处理存下所有的点之间的连通状态。他让我算一下空间复杂度，我一算，似乎需要的额外空间很大，然后我又想到可以利用存前n项和的方法，也就是说，先把有物品的地方标记为1，没有物品的地方标记为0，利用部分和的方法求出每一列的前n项和存到一个对应的数组里，（同样也求出每一行的前n项和存到另一数组里），然后利用f[m-1]-f[n]就可以得到第n+1项到第m-1项的和，如果它们为0，则表明中间没有阻挡，如果不为0，则表明有阻挡，则这里每次判断的复杂度从O(n)转化成了O(1)，然后面试官又说，你这样是可以很快了，但是，你消除元素之后，如何去更新你的数组？我一想这样的话消除元素之后，更新数组又成O(n)的复杂度了。不过瞬间我就想起了这样求和并需要更新，明显插点问线型的树状数组可以搞，于是，我立马说可以用树状数组进行插线问点。面试官愣了下，问我什么是树状数组。。我汗了一下，然后，意识到他搞竞赛时可能树状数组还不流行。。于是解释了一下原理，然后说可以实现插点问线。然后面试官才说“哦，知道了，也就是说和线段树类似嘛”，我说“嗯，不过比线段树写起来简单多了”，然后面试官说好了，面试结束了，问我有什么问题要问没有，我开始变聪明了，问了问面试结果什么时候出来，面试官直接说，“你二面已经通过了，不过今天有点晚了，不能直接三面了，可能明天或者下周会安排你进行三面”，我又帮另一同学问了问内推的事，他说他也不清楚，于是二面就结束了。
三面： 面试官先让自我介绍，这个我还算有点准备，不过感觉面试官听得很不仔细，边看电脑边听的样子，于是，心里有些慌，感觉自己想说的面试官没听进去。。 不过，我还是把想说的都说了说，说了自己许多优点。然后面试官和我聊了会儿之后，开始问我题目，只问了一道题： 现在给你N个点，给你一个函数能算出任意两个点之间的距离，现在要把这N个点中距离最近的两个点合并成一个点（合并之后点的坐标也给你一个现成的函数能算出来），然后，继续这样操作，让你找一个方法，能尽可能高效的把这N个点合并成一个点。如果给你M台计算机，你该如何利用多台计算机加快这个过程。
这题不多说了，我当时答得沾了个边，但是答得不是很好，反正我说的是用极小堆和标记数组搞来搞，后来下来一想当时答得有些扯淡。现在想好了一个方法，不过说起来比较难描述，不多说了。 他又问我能过去实习不，我想了想说应该可以吧。 他又问我有什么想问的或者想说的没有，我本来想给他说说OJ，后来发现他对OJ也很熟悉（估计又是一搞过ACM的），然后我就没啥可说的了，然后我还和二面时一样问什么时候能出结果，面试官又爽快地说我三面已经过了。
于是，就这样拿到了offer.