面试官感觉就不是很想面试...虽然面的也一般。

四十五分钟。

爬虫

代码题

有n个素数a[n]从大到小排序，这些数可以组成（n-1）*n个分数，例如 a[1]/a[2]，给出一个k，问第k大的分数是多少。

想了一个用cnt[n]数组代表第i个元素当分母的时候分子的指针位置，然后从小到大找到第k个，复杂度O（nk）。面试官说可以优化，我就说把那个数组用大小为n的堆维护一下，找到最小的可以直接弹出，复杂度O（nlogk），面试官还是不满意。然后口胡了一种优化方案，面试官没听懂。

凉凉。想不到k怎么优化。

update：想了一想好像只要二分目标值，最后找最接近二分出来的答案的那个分数就可以了。二分目标值，统计小于这个值的数有多少个，如果大于k，那么就左移，如果小于k，那么就右移。统计的话应该是需要二分的，所以是个O（nlogn）的复杂度，加上二分就是O（nlognlogn），最后找到最接近的答案的时候也是一个二分的过程，需要O（nlogn）。所以最后总的是个O（nlognlogn）的复杂度，不知道面试官会不会满不满意。

进程和线程区别

进程的通信方式

MySQL隔离级别

TCP三次握手

MySQL索引