【一路走来】北大数字媒体所保研面经

作者：gnuhpc
出处：http://www.cnblogs.com/gnuhpc/

九月份自己的一个日记，在这分享给各位：
其实说是面试，实际上是笔试+面试+上机，比较麻烦，在北大整整呆了一天，刚刚从北大赶回来。赶紧记录下~说是面经，就是受虐过程。。。
北大的数字媒体所是做AVS的，也就是中国具有自主知识产权的视频信源编码。AVS其实现在处境非常不好，行业内的人都知道AVS这个标准政府的政策现在 已经不再有所倾斜了，而且这个标准较之TD来讲更加尴尬，现在做这个其实是比较没有前景的。报的原因归结为随便二字。为以后的面试积累经验。换句话说，去 受虐。
先和老师发了几封邮件说了说自己的情况，然后就是漫长的等待，据说有人和导师打过电话，我是没有。后来得到回复说我已经过了简历关可以参加面试了，还告知 要复习数字媒体技术基础这门课。我的专业是没有这门课的，但是还是硬着头皮把北大的这门课件下载下来看了三天，而且这就是所有我准备的,但是这个还基本没 有考。。。
今天上午八点半到的北大，带了应有的证书和复印件，可就是忘了带身份证，还好今天没有查，下次一定要记得~由一个师兄领着进入北大(因为现在北大还处于奥 运状态)。进去一看，大概有二十人左右吧，相当壮观，在点名的时候我撩了一眼名单中的学校，清华的两个，浙大的两个，西电成电各一个，北交的两个，北科的 三个，北邮的四个，其他的记不清了。主考老师先说了下流程，先有两个半小时的笔试，中间穿插有面试，下午是上机和其余人的面试，一共博士硕士加起来要4 个，而且还有五个人左右在外地，下次面试赶过来。。。。
笔试由三部分构成。
第一部分是基础知识部分，我一看基本就是不会，总结起来有这几项知识：高数、概率、智力。前两项忘得差不多，智力题就一个还是答得上来，就是答错了。。。。
第一个说的是独立与不相关的关系，相关性是指两个随机变量之间的线性关系，不相关只是说明它们之间不具有线性关系，但是可以有别的关系，所以不一定相互独 立。如果两个随机变量独立，就是说它们之间没有任何关系，自然也不会有线性关系，所以它们不相关。反过来说如果两个随机变量相关，也就是说它们之间有线性 关系，自然不独立。总结起来就是独立一定不相关，不相关不一定独立。这个答出来了。
第二题说的是拉格朗日中值定理的内容和作用，根本就是不记得是什么东西，回来一翻，发现大一天天利用它做高数题。。。学习还是会忘记的，温故而知新，这是 真理。。。内容就不说了，作用是以中值定理为基础，应用导数判断函数上升，下降，取极值，凹形，凸形和拐点等项的重要性态。从而能把握住函数图象的各种几 何特征。在极值问题上也有重要的实际应用。
第三题是简述矩阵的逆，秩和特征向量和特征值的关系，直接空白。其实对于关系存在非零解向量，则称为的一个特征值，相应的非零解向量称为属于特征值的特征向量。不过这是回来翻书才知道的。
第四题是说要知道正态分布的那个参量的物理意义。。。凡接触过概率的对正态分布应该都不陌生，这是在统计学中是最基本、最重要的一种分布。应用于误差的概 念中，由高斯最初发现的。它的物理意义与其应用从下面典型示例中很容易就可以理解：你对一个常数a（如一物体的质量）进行了非常细致的（如准确到10万分 之一克），非常多次的观测（如10万次），那么每次得到的结果都不完全相同。其测量值会在真正值附近摆动。居中的最多。大于它小于它的机会要随着距离的加 大而迅速减少。这是也是回来查的，其实当时脑子有点进水，想想高考分数的分布是正态的究竟是什么意义不就行了。。。
第五题是说贝叶斯公式及其由来，亲爱的，我弄成了条件概率，其实再多写一步就是Bayes了。。。唉，还是基础不好。。。至于由来我不知道，但是查到一个 文档觉得蛮不错的，尤其对于学习经济的同学们：http://wiki.mbalib.com/wiki/%E8%B4%9D%E5%8F%B6%E6 %96%AF%E5%85%AC%E5%BC%8F。
第六题是说一个人整月看到外星人的概率是91%,那么半个月看到外星人的概率是多少? 看完我就觉得我是罗纳尔多了。。。当然其实比较简单，但是我没有做出来，令半个月看到外星人的概率是p;
=> 1-(1-p)*(1-p)=91%
=> p=0.7
简单吧，可在场上我就想不起来。。。
第七题是说有A，B,C,D四个要从同一方向过独木桥，这四人有一个手电筒，且一次只能有两个人同时过桥，过桥时必须用手电筒，A单独过桥的时间是1分 钟，B是2分钟，C是5分钟，D是10分钟，问四个人过桥用的最短时间是多少？我这道题特别明白思路是这样的，反正ABCD四人都要过去，所以至少 1+2+5+10=18分钟，然后每次让回来最快的人来回就是最短的，共计18+ 3=21分钟。貌似还是有道理，但是其实是错的，应为
A、B先过：用2分钟
A回：用1分钟
C、D过：10分钟
B回：2分钟
A、B过：2分钟
共用2+1+10+4=17分钟。
其实这是考察图论知识，殊不知我图论就是混的。。。有空可以看看
http://blog.programfan.com/article.asp?id=25057这个里边讲的，话说这个算法我下星期还要考试呢。。。
计算机设计部分是有九道题：
第一题是数据存储是高位在前还是低位在前，用移位就行了，比较简单。
第 二题是判断一个链表中是否有环，我是用的系统调用方法设置了一个timer等溢出中断，一般cs的学生是不会从硬件和OS底层考虑的，他们的典型做法如 http://www.cppblog.com/humanchao/archive/2008/04/17/47357.aspx所述。
第三题是广度优先和深度优先生成树，对不起，当时就没讲也就没学。。。
第四题是Huffman编码，唉，终于出现自己专业的了。。。
第五题是前序遍历和中序遍历然后求二叉树，当年不知道做过多少这样的题目，亲爱的雅静在课上也讲过，但是年代久远统统忘怀。。。。
第 六题是记不太清了，但是基本上是说一个文件中有n个小于10000000的正整数，现要求对所有这n个数字进行排序，考虑到性能，要求一次性将这个文件的 n个数字读入内存进行排序，但计算机的内存只有2M，请出一个方案，在保证不会消耗掉所有内存的情况下，以什么方式将这n个数字放进内存并且排序。
回来搜了一下，仅有一个台湾人给了个算法：
分段(桶)排序，然後合並。
1、依據內存大小，設定段大小，及每個段對應一個小文件(只有2M的系統應該沒有內存映射文件可用)。
2、按段排序，記錄特征值。如：最大值，最小值，每隔1000個取一個特征值等方法為加速段合並運算做准備。
3、按重組先後的重要性排序段
4、按段信息一個個重組段。
5、合並段，輸出結果到文件中。
在事先不知道數據特征的情況下，哈希函數無法做得合理，哈希法會更慢。
我也是没怎么看懂。。。
第七题是存在一个单链表，目前就一个当前结点的指针，问如何删除该结点。然后我就玩命的想怎么得到上一个结点的内存地址，原来只要把当前结点往后的所有 值都赋给上一个结点，删除最后一个结点便能实现了，这题的关键不是地址的传递，而是链表内值的前移。。。这道题凸显自己智商成问题。。。。
第八题是翻译名词，知道的都写上了，不知道的一个没写。
第九道记不清楚了，应该是做出来了。
第三部分是语言运用，写让改病句。。。然后是英语翻译。。。后来是写一篇千字以上的非专业书评。。。这些我倒是在行。。。。
笔试我总结就是平时基础知识一定要温故知新，否则很容易忘掉或搞混的，其实这些都不是什么难的，当年考试没有一个不是高分（除了概率），而且还是要好好 了解这个实验室的研究内容，从中提取到它可能考察的基础知识是什么，找人问问相关学长也是很重要。还有就是多上网看面试题，因为这些题目我一Google 基本都是什么Google、华为、微软、中移动还有中行（怎么中行还面试这些。不解。。。）。全当玩智力游戏了。
中午管了顿饭，饭倒是很好，但就是用叉子吃盒饭。。。真是无语。。。果然不同，北大就是不一样。。。
下 午朦胧中被叫进去面试，进去先做了五分钟PPT自我陈述，还不错，第一个问题就是是否选择读博，答案是我的人生规划只把硕士列为我在校学习的最后阶段。后 来导师问了几个问题，我注意到他基本是针对我报名时做的自我陈述word文档来问的，问了些信息论的基本问题，答的还可以，后来又问我工程的一般流程，这 个最在行~有个老师说你想知道你基础知识得了多少分吗？我心里立刻认定我就是欠他十两银子，以这样的态度连忙连声道歉，说一定补上。。。后来还有一个老师 问到了一个概率问题，说一个检测某种兴奋剂的试剂，让一千个人服用这种兴奋剂，最后用试剂检测发现999个人被检出呈阳性，问这个检测是不是有效的？我必 须回答不完全有效。然后告诉他，那我再给一千个没有服用的让他检测可能会有误报的。“正确！但是这体现了什么概率思想呢？”。。。我麻了。。。。怎么又是 概率。。。我成绩单上赫然写着概率与数理统计78分，很低的。。。最后一个老师问我知道你工程经历多，但是我问你在你想象中拿到一个理论课题是怎样展开的 呢？我说了说，老师还看样子比较满意。最后老师说你说你口语好那就跟我们读段英文，这个没有问题，绝对标准~
面试总结就是心理状态不错，比较顺利，但是基础知识薄弱还是个软肋。。。看到一个北科的哥们哭着走出面试场，我觉得至少在面试上我的言辞和沟通还是很得体的。这就是进步~
上机不难，但是做的不好，平时依赖manual极为厉害（没办法，不想记东西），到了上手却不能查的时候就十分郁闷了，归根到底还是自己练得少，这是个必须解决的问题。不过现在C语言的功底与暑假前已有很大进步，看了《C和指针》这本书，相当不错~
出来后就去找北大的陆胤兄玩。她一直在为做鸟巢志愿者，也是很辛苦的。一起聊聊天，吃食堂，感觉很不错，老同学真是很好的，也是希望她不要压力太大（北大变态的人很多），身体第一~
就说这么多了。经历最重要，这是我北邮大哥说的，我相信。