香港中文大学面试（两道面试题）
暑假时，坐飞机大老远跑到深圳去面试香港中文大学，本来是信心满满的，到了外面之后才发现希望原本就是无所谓有无所谓无的。才真心体会到了什么叫差距。。。。
或许你觉得自己发过几篇论文，有丰厚的科研经历，貌似很牛叉，其实都没用，水论文大家都有。拼学校，拼不过他们；拼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。当然这个题没什么好说的，基本上大家都会。
进一步得到：
对二分查找:
只需比较5/3log3n和log2n的大小即可：
所以，平均情况下，三分查找的时间复杂度要大于二分查找。。。。。估计这才是那老师想要的。。。虽然不难，但是估计当场能想到这的不会很多的。。。
