电面

   上礼拜，百度那边打电话给我说是预约1110的电话面试时间，约的是下午4点半。
   今天3点20打过来，也好，早面完早结束。
    最先，让介绍自己。于是把本科和研究生的经历讲了一遍。
    第二，问根据我的经历，本科时的基础对研究生基本上没有什么帮助，于是我巴拉巴拉大堆，最后举个例子佐证，说数据结构的重要性，于是把当初实现链表快排给拎出来。然后他就问为什么会慢。我没讲明白。中间讲了下快排的思路，但是对时间复杂度还是不会算。
     第三，让我提个算法，求第k大的数，给了三个，1，排序，2，堆，3，快排思路的剪枝。让我算第三种的时间复杂度，我最开始说是nlgn，他说和快排一样啊，后来我改成logn.好像还是错的。
     第四，他见我说不出来上个的复杂度，说给我一个新的问题，如果求最大和最小两个数，有什么算法。我说就是从前往后遍历。时间复杂度是O(n),比较次数是2n.他让我优化下。想了很久，在给定的时间没有想出来。
     第五，他说有别的问题，于是没有纠结第四个问题。看简历上写了epoll和select，问两者区别。讲完了，好像还挺满意。
     第六，让我实现下tail命令。他问有没有用过，我说没有，他就大致讲了下这个命令的用途。最后让我说下思路。1.读文件，从前往后读，然后到指定的位置，显示。他问这个方法好不好。我说不好，会很慢。让我再想。中途，我和他讨论，说我想不出来，我能到达文件尾，但是不知道如何定位到倒数第几行。慢慢和他讨论，然后出来的方案是。2.定位到文件尾，然后从后往前找\n, 如果找到足够的，就停止，然后显示这之后的内容。
     他提示，说磁盘的速度怎样。于是我想到磁盘很慢，需要使用内存。我当时说的是共享内存，他接着问，那如果你有了共享内存，你要怎样使用这块内存呢。后来我放弃了。他说，我刚也提示了，磁盘和内存的速度真的差很多。如果你从后往前找的时候是读磁盘，按照你的方法，你待会显示的时候也需要再次从前往后读一次磁盘。而如果在第一次读磁盘的时候，就把读到的内容放如内存，那么显示的时候就不需要读磁盘了，这样我的方法就比你的方法快很多。
     他也说，这个只是他的想法，不是tail的实现方法。

     然后进入我问问题的时间。
     我说之前有到三面，但这次为什么还有面试。他说是全新的过程的，但是工作职位都一样的。
觉得，听到我进三面，会不让我继续面了吧，之前三面都不过的人。
      然后问了刚才我没有回答上的问题，就是求最大和最小两个数，如何减少对比次数。他说，是他看到的方法，就是先两两比较，这样最开始就是n/2的比较次数。然后小的部分进行比较，大的部分进行比较。这样比较次数能够降到3n/2。
    
     让我丢脸的上次的三面。三面的时候，我的状态也有关系。被那个面试官问的哑口无言，然后自己崩溃掉。其实现在想来他的问题都还能回答，只是自己心理承受能力有点太弱了。这个是大缺点。当时恨死自己这个样子。