学院街：[763]香港中文大学计算机专业面试

暑假时，坐飞机大老远跑到深圳去面试香港中文大学，本来是信心满满的，到了外面之后才发现希望原本就是无所谓有无所谓无的。才真心体会到了什么叫差距。。。。 或许你觉得自己发过几篇论文，有丰厚的科研经历，貌似很牛叉，其实都没用，水论文大家都有。拼学校，拼不过他们;拼GPA，也没法跟他们比。拼ACM，就更不行了。。呵呵。。当然，如果你有top conference或者top journal，而且完全是自己做的，这个绝对牛。不服不行 叫了30多人过去，目前听说录取了不到2个，其中申请人包括港大、北大、上交的MS，浙大、中科大、哈工大、川大等等或者有顶级论文，或者有ACM相关经历，据说最后录取了一个GPA4.0的中科大的mm。相比而言，这次面试，我被鄙视的很彻底。。。。 中午吃过一餐丰盛的自助，同时在餐桌上跟这帮中大的老师聊了N多之后，下午开始了紧张的面试。(当然也有人是上午面完后直接走的) 全英文的面试，刚开始或许有些不习惯，但其实到头来，你发现自己不是被卡在英文上了，而是思维上。 自我介绍就不用多说了，基本上都问。。。。估计除非你经历特别牛，否则那帮老师基本上都不怎么鸟你。。。 第一题，简述二分查找。这个基本上大家都会。回答完之后，有个老师说，那如果是三分查找呢?? 这个题目我当时愣了半天，在黑板上写了个大O什么什么。那老师立马来了一句，we don't need big O, please give us the precise time complexity. 于是我愣了半天，硬是没想出来。那老师看我半天没想出来，直接来了一句：Then is the time complexity trisection search faster or slower than binary search? 我当时愣了半天，憋出来一句：that would be ... e.... slower....最后，他们也不着急，直到面试时间到了把你礼貌的请出去。 第二个题，怎样以10%的概率生成1,20%的概率生成2,30%的概率生成3,40%的概率生成4。当然这个题没什么好说的，基本上大家都会。 [cpp] view plaincopyrandom=rand()%10 if(random<1) return 1; if(random<3) return 2; if(random<6) return 3; if(random<9) return 4; 即可。。。 关于第一个题，我后来又想了一下，并跟同学交流了一下，发现好多人刚开始一听三分查找都冷一下。有些比较牛的同学会给出理智的分析，大部分都是在猜。 我想法是这样的：(大家可以交流一下) 三分查找的具体操作是： 首先在将目标数与1/3处的数进行比较，如果比其小，就在数组最小的1/3处继续查找; 如果比它大，就接着与2/3处的数比较，如果比它也小，说明在中间1/3处，在中间1/3处继续查找; 如果比2/3处的数还大，说明在最大的2/3处，在此部分继续查找。 如果写成递推关系的话: 1/3处的数字为a，2/3处数字为b，目标数字为s。 (1)T(n)=T(n/3)+1, if s (2)T(n)=T(n/3)+2, if a (3)T(n)=T(n/3)+2, if s>b (完成和a、b的比较之后才确定是在最大1/3部分。) 如果从粗略的角度去分析时间复杂度，二分查找树的高度为O(log2n)，所以时间复杂度也是O(log2n)，三分查找树的高度为O(log3n)，时间复杂度O(log3n)，看似是三分查找的平均时间复杂度低了。但这帮老师让我们分析精确的时间复杂度： 直观的角度去考虑，从2分查找每次比较1个数，3分查找每次比较2个数......n分查找每次比较n-1数，当变到n分查找时，也就成了顺序查找了，时间复杂度为O(n)。分析这个趋势，直观的感觉是平均情况下三分查找慢了。。。