中国人民大学
中国人民大学是我的重要目标，所以我在申请季准备期间总结了一下人大信息学院的往年面经，信息都来自互联网。
面试经验
机试
2019年题：
- 斐波那契数列，真真正正的简单题，随便写了一个记忆化递归就能AC了，几分钟搞定。
- 高精度进制转换，但是只需要2~10进制互转。
2018年题：
-
提供了48个数据，格式为 2018.06.23 Russia-England ，输入的为一个国家的名字，输入所有该国家的比赛时间及对手，我认为这个题主要数据的处理，十分耽误时间，其实考察的就是简单的字符串比较。
-
输入一个二位数组，内容是# *，输出一共有多少个*组成的邻居团体以及最大的一个邻居团体有多少个*（*的相邻的8个位置都算是他的邻居）格式大概如下
######*##*# ###*##****# ####***#**# #****##***#考察也就是DFS或者BFS算法。
笔试
2019年题：只有编程题。
-
用三种不同的循环语句实现strncpy函数。
-
二叉链表倒序输出，自己给出数据结构，但是规定不能有指向双亲的指针。写出完整程序。
-
读取一个文件，文件里面有一排数字，然后按照题目要求的排序方式排序并输出，需要写出完整程序。题目的排序方式：原：1 3 2 4 1 3 2 → 排后：1 1 3 3 2 2 4 。（就是把出现过的数字都放在一起，但是不改变出现的整体顺序。时间久远，印象中是这样的排序方式，如有错漏，欢迎小伙伴们指正）。第三题有一大堆小问题，包括分析算法的时空复杂度，数据量大的时候是否仍然可行，等等。
2018年题：概念题+编程题
-
笔试考的是编程语言，切记一定要将C、C++、JAVA看一遍，特别是三者有一些共有的问题。因为程序设计笔试占80分，所以一定要重视笔试，这直接决定了你会不会录取。
-
前面两道题是问答题，主要是编程语言的内容：
- static在C、C++、java内的使用场景和作用。
- 多态性在C++、Java内都有哪些体现，两种语言任选一种作答。
-
后面两道题是编程题，手写代码。
- 完全平方数 输出所有四位数，是某一个数的完全平方数，并且格式为aabb，前两位相等，后两位相等。
- 题目大意是给你一个文件的路径，该文件内是一篇英语文章，你需要读出该文件内的词频最高的前K个单词，具体要求有很多，比如不能使用STL（笔试题均不能使用STL），我记得有好多要求，但是我想不起来了，抱歉，最后还需要分析你的代码的时空复杂度。知道前K个单词后，若你知道单词在每个段落的分布，你该如何向读者推荐哪个段落。
-
总结来看，考察的是C语言的文件操作（这个考点连续考了两年，务必重视），字符串的操作，复杂度分析。
-
算法题是找出形式是aabb的完全平方数，算法要求只能有一重循环，不能有循环嵌套。这题可以用数学分析简化，或者先算完全平方数再判断aabb的方法。
-
设计题是计算一篇文章中做出现频率最高的前k个单词，要考虑无效词(an this that这种)，还问根据结果怎么找出文章的代表段落。具体有有记不清楚了，有好几要求以及小问。我最后一点不太想做了，就简答的写了用字典树的做法以及用hashmap+数组维护前K个数的思想。不让使用STL。
面试
另外面试会问的3个英文问题一般有：自我介绍、介绍一下你的家乡或者你的学校。
2019年专硕面试：
-
英文群面：自由抢答式发言，但发过言后就不抢了，每人都要说话。话题都是关于计算机方面的开放式问题。Eg. In the era of big data, what do you think about the storage and transmission of data? 10个人，假设每个人每个话题只说2分钟内容，那每个话题就要20分钟，所以这一场直接花了40分钟，虽然平均下来自己说不了多少，但是神经还是紧绷的有没有…… 通过这一场其实很能看出同学们的实力，有的英文流利侃侃而谈，有的口语能力有待提高。
-
中文群面：按序号依次发言，先是自我介绍。静观各路大佬无形装b，表面笑嘻嘻，实则心戚戚……在10个大佬中做那个最吸引老师眼球的仔，并不是那么容易~ 自我介绍完毕了，也会有自由抢答式发言，我们组问到的问题是你觉得本科和研究生的课程有什么区别，以及你对这些课程的认识。都是开放式问题。
-
英文单面：自我介绍+简短英文问题，英文问题好像都是关于学校和生活的。整体大约3分钟。
-
中文单面：主要针对群面中你的发言提问（评委给每个同学发言都做了记录哦），每个老师都会问一些感兴趣的问题，涉及的比较全面，要对做过的竞赛和项目了如指掌才行。大约5分钟。
2019学硕面试：
-
英文群面：按序号依次发言，先是自我介绍，大佬们开始秀了，有位老哥那个英文背的贼溜（其实我觉着主要是说清楚，不要用太生僻的词）。然后就是，问问题，第一个问题：咳咳，同学你为啥选我们学校啊？（此时不舔更待何时....捂脸）。后面记不清楚了，有同学直博被问将一个科学家故事，他讲了李彦宏被泼水，（他说刚看完知乎，只记得这个，笑skr人.....）,其他实在不记得喽。
-
中文单面：学硕是递简历，所以简历一定要做好，个人建议项目和科研占据简历一半的位置，越详细越好，这样才是你做的嘛。老师基本是捡着简历来问，此外问了我卷积神经网络的理解（菜鸡复习过，表面一本正经，内心笑开了花，再次捂脸）。好像没有听说问专业课。
2018直博面试
-
我报考的是直博，英语面试和综合面试是一批老师，硕士有部分是分开面试。英语面试最重要的还是自我介绍，自我介绍不要说废话，我就是犯了这个毛病，因为时间紧张，我刚说完自己的基本情况，就被打断，老师让我说一下项目和课程情况，所以基本情况过后，一定要准备一下自己的项目和课程的一些情况。除此之外可以准备一下家乡、学校的英语介绍，以防万一。
-
接下来，中文内容需要详细说一下自己的项目或者论文，尽量让自己掌握主动权，多说但是不要说废话，说自己的工作和收获，一定不要夸大，可能会被怼，一旦被怼就应该会凉。我遇到的还有专业问题，最最最最最重要的莫过于数据结构，数据结构一定要多复习几遍，对于重要的内容，一定要上手实现，这样也有助于机试。我被问到的是DFS、BFS的伪码实现。DFS是递归实现，BFS需要借助于队列实现。
考研复试
-
英语笔试，第一道题目是翻译，是与目前生物数据库技术等相关的内容，生词不太多，也不是很长。
-
谈谈为什么来人大，想在这里学些什么，以及研究生的计划。
-
第一道是线性表逆转，用链表存储，递归与非递归方法实现，平时都用非递归，这个递归的方法确实有点想不太到，另外还要实现链表的建立和空间释放。
-
第二道就是用非递归的方法求树高和一条最长路径（即结点序号），当时自己用的是先序遍历和栈实现的，注意continue在if中的使用就是之后的判断语句都不执行，又到循环开始进行下一次的循环，后面和别人讨论，发现层次遍历也是可以的，用一个数组专门存储树高，像根节点树高1，它的左右子树就树高2，这样用队列实现了层次遍历之后，树高也同样得到了，其中一条路径也可以相应得到，两道题一共一个半小时。
复旦大学
上个学期申请季联系了复旦大学DAS Lab的一位老师，研究方向是并行计算。老师留了一道题目检测一下我是否适合做系统方向的研究。一开始看到题目是懵逼的，然后不懂就查嘛，于是逐渐搞清楚了题目要我做什么。使用perf_event_open进行测量的题目放弃了（其实也是题目的重难点），因为实在无法调用成功，我猜测的原因是我用了虚拟机。
如果大家有啥问题可以一起交流讨论，毕竟我只是一只菜鸡。
性能测量小作业
我们在计算机组成原理中已经学到，近几十年来，CPU速度提升远远快于内存，两者的速度差距越来越明显，因此高速的cache被设计在两者之间，充当一个中间的桥梁。但是cache的大小有限，不同的访存方式对程序性能有很大的影响。
- 对比四种访存方式sequential read、sequential write、random read、random write的性能。
- 尝试用perf_event_open [1] 测量上述四种访存方式的last level cache miss的情况。
- 尝试说明上述访存方式导致性能差异的原因。
[1] https://www.man7.org/linux/man-pages/man2/perf_event_open.2.html
1. 性能对比
该题要求对比顺序读写和随机读写四种操作的性能，可以编写一个C语言程序大规模重复运行上述操作，测量其运行时间及其他指标以反映处理器在处理这四种操作时的效率高低。
我们知道，数组的数据在主存中连续存放，那么顺着数组的存放方式（对于二维数组就是一行一行地进行）进行读写就是顺序读写，而无视数组数据的存放规则进行读写（对于二维数组可以一列一列地读写）就是随机读写。故可以编写如下C语言程序，命令行参数1～4分别表示顺序顺序读写和随机读写。
#include <stdio.h>
#include <string.h>
#define MAX 10000
int a[MAX][MAX];
int main(int argc, char **args) {
if(argc != 2) printf("Please enter 1~4.\n");
else {
int temp = 1024;
if(strcmp(args[1], "1") == 0) {
//sequential read
for(int i = 0; i < MAX; ++i) {
for(int j = 0; j < MAX; ++j) {
temp = a[i][j];
}
}
}
else if(strcmp(args[1], "2") == 0) {
//sequential write
for(int i = 0; i < MAX; ++i) {
for(int j = 0; j < MAX; ++j) {
a[i][j] = temp;
}
}
}
else if(strcmp(args[1], "3") == 0) {
//random read
for(int i = 0; i < MAX; ++i) {
for(int j = 0; j < MAX; ++j) {
temp = a[j][i];
}
}
}
else if(strcmp(args[1], "4") == 0) {
//random write
for(int i = 0; i < MAX; ++i) {
for(int j = 0; j < MAX; ++j) {
a[j][i] = temp;
}
}
}
else printf("Please enter 1~4.\n");
}
return 0;
}在Ubuntu虚拟机（分配了一个处理器内核）中编译上述程序并使用perf工具进行四次测量，得到的实验结果如下所示。对比发现顺序读(1)比随机读(3)所消耗的时间明显短，顺序写(2)比随机写(4)所消耗的时间明显短。
zilize@ubuntu:~/Documents$ perf stat ./rw 1
Performance counter stats for './rw 1':
247.33 msec task-clock # 0.993 CPUs utilized
11 context-switches # 0.044 K/sec
0 cpu-migrations # 0.000 K/sec
97,701 page-faults # 0.395 M/sec
<not supported> cycles
<not supported> instructions
<not supported> branches
<not supported> branch-misses
0.248986000 seconds time elapsed
0.207527000 seconds user
0.039909000 seconds sys
zilize@ubuntu:~/Documents$ perf stat ./rw 2
Performance counter stats for './rw 2':
322.80 msec task-clock # 0.994 CPUs utilized
17 context-switches # 0.053 K/sec
0 cpu-migrations # 0.000 K/sec
97,701 page-faults # 0.303 M/sec
<not supported> cycles
<not supported> instructions
<not supported> branches
<not supported> branch-misses
0.324707237 seconds time elapsed
0.197794000 seconds user
0.125135000 seconds sys
zilize@ubuntu:~/Documents$ perf stat ./rw 3
Performance counter stats for './rw 3':
827.85 msec task-clock # 0.992 CPUs utilized
41 context-switches # 0.050 K/sec
0 cpu-migrations # 0.000 K/sec
97,701 page-faults # 0.118 M/sec
<not supported> cycles
<not supported> instructions
<not supported> branches
<not supported> branch-misses
0.834865327 seconds time elapsed
0.760600000 seconds user
0.067344000 seconds sys
zilize@ubuntu:~/Documents$ perf stat ./rw 4
Performance counter stats for './rw 4':
988.89 msec task-clock # 0.993 CPUs utilized
32 context-switches # 0.032 K/sec
0 cpu-migrations # 0.000 K/sec
97,701 page-faults # 0.099 M/sec
<not supported> cycles
<not supported> instructions
<not supported> branches
<not supported> branch-misses
0.995373536 seconds time elapsed
0.853336000 seconds user
0.135576000 seconds sys
进一步考虑代码中选择的语句是否能够准确代表顺序读写和随机读写。我所使用的代表读操作的程序分别为：
temp = a[i][j]和temp = a[j][i]
代表写操作的程序分别为：
a[i][j] = temp和a[j][i] = temp
如果将前两句分别改为a[i][j]和a[j][i]，测量发现二者消耗的时间基本一样。初步推测是由于语句不具备实际意义，在编译优化时被干掉了。如何验证这一点？只需在程序中将a[i][j]或a[j][i]注释掉即可，测量发现该语句是否存在，对于程序运行时间基本没有影响。
后面两句除了向主存数组区中写入数据，还包含了从temp变量中读取数据的动作，这是否会对结果有较大影响呢？将temp改为立即数1024进行测量，发现与改动之前没有明显区别。初步推测temp变量一直处在Cache中，读取速度极高，所以对实验结果影响不大。
由上述分析可知，我所编写的程序中：
- 写操作包含两件事情：读取
temp数据，写入到数组存储区。前者的影响可以忽略。 - 读操作包含两件事情：读取数组数据，写入到
temp变量。后者的影响暂时未知。
所以上述实验结果可以进行纵向比较（即同为读操作，或者同为写操作进行比较），而不可进行横向的定量比较（即顺序读写之间的比较，或者随机读写之间的比较）。但是可以进行横向的定性比较，因为写操作中“写入到数据存储区”消耗的时间大于读操作（读数组数据、写temp变量二者之和），即便去掉写入temp变量消耗的时间，二者定性的大小关系依然不变。
要注意的是，这里提到的时间都应该是相似条件下平均意义上的消耗时间。
总之，在本例中可以得到四种操作的消耗时间顺序（倒过来就是性能顺序）：
随机写 > 随机读 >> 顺序写 > 顺序读
2. 使用系统调用测量Cache Miss
该题放弃
放弃的过程：
- 在Ubuntu虚拟机上无法调通参考页面上测量
instructions的示例程序。 - 尝试使用
perf命令直接测量cache-misses或者L1-dcache-load-misses，发现前者不支持（not supported）、后者测量值总为0。 - 在Stack Overflow上发现同样遇到测量值为0的案例，发现他不使用VMware之后测量值正常。从而推测可能是虚拟机导致无法读取硬件数据，毕竟VMware是运行在用户态的应用程序。
- 考虑到服务器厂商的服务器操作系统“可能”运行在裸机上，故在Vultr租赁centOS系统的服务器。
- 使用云端服务器安装了perf后命令行运行
perf list发现仍然不支持监测硬件事件（Hardware Event）。 - 推测原因是：云端服务器仍然是虚拟化的产物。
- 剩下唯一的方式就是将自己的电脑改为双系统。
- 考虑到最近个人电脑十分重要，不敢改，遂放弃。
3. 原因分析
仍可以推测测量结果为随机读写的cache-misses（按参考页面的说法：cache-misses通常意味着last level cache misses）远大于顺序读写，这导致了随机读写的性能远低于顺序读写。
为什么呢？
Cache的规模是十分有限的，速度也是极高的。对于顺序读写来说，每次访问内存时系统会将连续的一整块数据读入Cache，之后绝大部分对于数组的读取，都只需到较近的Cache进行读取，无需访存。毕竟Cache的更新规则就是按照程序的局部性原理来设计的。
对于随机读写来说，当数组达到一定规模时，一个数据块无法装入数组一行的数据，导致每次读取数组数据时都需要从更高级（离处理器更远故而更慢）的Cache乃至主存读取数据，CPU需要等待数据的回调，所以性能被大大制约。
因此我们在编写或优化程序时需要注意遵循比较自然的规则（符合时空局部性原理），这样才能利用好Cache，提高程序的运行效率。
Comments | NOTHING