BT的网易有道笔试

先是一堆选择题

然后一个基本编程题

1 给定n个整数,求对应的哈夫曼树的高度

整个笔试一多半时间花这个上面了，自己动手建堆，维护堆性质，唉，就差没写二进制了。等搞到完，发现后面还有两个更BT的

两个高级编程题

1 平面上n个节点求闭包

前两天刚看到算法导论上有讲这个的，可惜没看

2 给定数轴上的n个整数开区间，问最少删除多少个区间，使得剩余的开区间不相交

看到这题只有2分钟了，就知道好像算法导论上有。后来知道是活动选择问题，可以用greedy算法搞定

EMC笔试

EMC笔试3个小时，是我参加的最长时间的笔试了。题也很有趣，跨度很大。

先来一堆选择题，有数论，C,C++,操作系统，Java，逻辑，概率，网络，数据结构，算法，可谓包罗万象。可惜，其中12道与C,C++和Linux相关的题都不会。

列举几个题如下：

（1）2008～8002之间有多少个各位数字不同但能被3整除的数

（2）f(n)=50!*5^n,问n至少为多少，f(n)和f(n+1)的后面0的个数相同

（3）两个单链表，长度分别为m和n，求两个链表是否相交以及交点的算法的最小复杂度多少

（4）class A{}, sizeof(A)输出啥

（5）n个蓝球大小不同，对应有n个红球大小分别与篮球一样，要求将这2N个球红蓝配对，相同大小的配一对，相同球不可比较大小，要求在额外空间为O(1)的条件下，最佳的算法的平均复杂度。

（6）A和B头上各有一个正整数标签，两者相差1，相互只看到对方的标签，A和B希望能够猜测自己的标签，A说”我不知道自己的是几“， B说”我也不知道自己的“， A说”我知道自己的了“，B说”那我也知道了“， 问A和B头上的标签是多少。

（7）n!+2,n!+3,...,n!+n, 有几个质数

（8）RAID-3,RAID-4,RAID-5的问题

（9）关于如何将一个进程从前台变成后台
Ctrl-z 可以将前台进程挂起(suspend), 然后可以用bg jobid 让其到后台运行。
fg jobid :可以将一个后台进程放到前台。
job & 可以直接让job直接在后台运行。

（10）5个位置围成一个圈，每个位置可以任意放红求或蓝球，问没有两个红球相邻的概率是多少

（11）Java 垃圾收集的问题

（12）关于排序算法时间复杂度，空间复杂度以及是否稳定的叙述，问哪个不正确。

编程题（客观来说还算温柔，至少不管算法优劣，能搞出个算法）

1 输入一个单链表以及整数k，输出从链表末尾开始的倒数第k个节点

2 给定一个m*n的二维数组，要求用转圈的方式打印数组。就是以顺时针方向先打印最外圈的，然后再打印次外圈的。

3 平面上n个点，求距离最小的两个节点

    （考试前一天晚上瞄了一眼算法导论上这个例题，可惜没有细看，直接用了最笨的N平方算法，不过即使看会了，现场写NlogN的算法还是难度很大）

4 给定n个整数，任意取三个，求和的绝对值最小的三个数。

     直接穷举O(N^3)了，不知道有没有更好的方法

最后还有个写作题，考英文写作能力

总结：网易的要是没有见过原题能做完，那真是太牛了，不过都是算法导论的原题，唉，怪自己没好好看

EMC的题量好大，可惜C和C++栽个大跟斗，题目太多了。

算法导论是好东西，发现好多考题都是考例题了。

现在居然开始流行考计算几何的题目了。