腾讯实习生面试

面试官首先看了下简历，看我写熟习操作系统。首先问了malloc和free那到大题怎样答的。我提到了多是线程同步技术。假设有两个线程同时访问同享区域可能会出问题，C库应当具有线程安全性。貌似答得不对，面试官反问我这还要C++的智能指针等高级的线程同步技术来干吗。无语。
再问free如何通过传入的指针判断内存分配的大小，并进行释放。我说操作系统管理了1个待分配的内存链表，其中肯定包括所分区域的内存首地址和内存块的大小。通过传入的指针遍历这个链表就可以得到内存块的大小从而进行释放。然后面试官说不就结了，继续发问。
再问让我解释甚么是消息循环。我说是操作系统触发某个事件以后会给对应的进程发送消息，然落后程通过GETMESSAGE获得消息并进行处理。然后他说那你只是给单1进程发送消息，如果广播呢，操作系统采取甚么机制避免消息队列堆积，并且说操作系统预先不知道有多少进程在进行监听。没答上来。然后问我你要怎样实现，我说那必须知道有多少监听者，用这个全局变量进行减减，为0就从消息队列抛弃，他说这样也行吧。
然后继续问，进程有那几种通讯方式，怎样实现的。我说有管道，油槽，然后底层都是通过消息映照实现的。然后再问那线程通讯呢，我说在WINDOWS里进程是线程的容器，线程的通讯方式和进程方式相同。然后有事他出去了1会儿，等了10分钟。
回来以后就问我数据结构学的如何，我说1般。然后他说我们做几道题吧，然后就是开始：
1.给1个有序数组a[N]，然后随机切分成M个子序列，如何将这M个子序列重排序。我当时没闹明白，就说了用堆排。他说时间复杂度多少。我说（nlgn）。然后问有无更快的，我说看起来像归并排序。他说那是多少。我说nlgn。他说是吗？我想了1下nlgm。哦。那你写1下。
然后写了1段。发现我在写归并的算法就让我不要写了。看看大致思路，然后发现1些问题。想改不给我改了。然后问我有甚么善于的。想了1下没有说。然后看我简历里有ADABOOST算法的研究，就问了我原理。怎样训练的，卧槽早忘了好吗。看我不行又问了1下浮点转整数的原理，乘法除法变位移的方法。然后说你这样做有精度问题，有无查太高精度的方法。我说没有（这时候候已抓狂了）。
然后说那末我们继续做题。给出两个单链表判断是不是相交，第1次交点在哪里。这个看到过秒杀了。
然后在来1题，50E个IP如何找出出现次数最多的，内存1GB。我问1个IP多少大。他说IPV4。哦4B。算了1下需要20G我去神经啊。我说这内寄存不下，要用硬盘上吧。他说怎样用。我说分成20块，内寄存满了就倒到硬盘上。然后内存找不到就到硬盘上去找。他说怎样找。我想了1下难道是HASH？表示没用过不知道怎样操作。然后他说这个很简单的，你只要把IP通过HASH映照到文件然后在文件里遍历就好了。其实我想问怎样HASH映照，没实战过不敢讲啊。
然后说答得是还行，面试时间也很长了。回去等通知吧。感觉要跪，没底。