阿里实习生笔试归来
笔试安排在浙大的玉泉校区，时间是昨天晚上6:30~8:30，周六晚上，这个时间点不得不说给很多人带来了不便，不知道是出于什么考虑。很早就投了简历，安排是29号全国统一笔试，等到笔试前两天才收到短信，开始还惶惶的以为要刷人。
有几个同学分在了不同的教学楼，看来这次的规模真的很大。我所在的考场不大，共52个人，我就是51号，不过这个数字我还挺满意的，因为每个位置上放的编号卡片上有写这是51job组织的，51job，51号，不错，很有意义。
回到正题吧，考场中有两个监考，考试提供一张答题卡、一份7页的试卷、一张稿纸。感觉好久都没有体验这样正规的考试了，上一次还是2年前吧，这样的氛围让人觉得靠谱。2个小时的时间，7页的试卷，一共29道题目，分为单选20道，不定项选择4道，填空与问答题5道。当然最后第7页还有一道Java选做题，这像是阿里笔试题的一个传统似的，之前也是如此。我不搞Java，所以最后一题瞟了一眼，没有写，把时间都放在了前面。
单选
单选20道，涉及网络（1题，划分子网）、操作系统（1题，linux系统磁盘查看大小问题）、概率题（1题，生女孩问题）、逻辑题（2题，找假钱问题和市场客户问题），剩下的就是编程中的一些具体问题，包括快排的时间复杂度序、递归、二叉树度问题、栈的出栈顺序等。选几题觉得有些意义的题回忆一下吧。
第4题： C语言程序运行在32位操作系统上，x和z是int型，y是short型，x=127,y=-9. 执行z=x+y 之后，x,y,z各是多少（十六进制表示）？
计算机中整数是以补码形式存储的，正数的补码与原码相同，负数的补码等于原码取反(不包括符号位)+1
执行 z = x + y，x 和 y 运算前后不变，x为正数，所以x=0x0000007F。
y为short型-9，原码为1000 0000 0000 1001，最高位符号位为1表示负数，其补码为1111 1111 1111 0110 + 1 = 1111 1111 1111 0111 = 0xFFF7。所以 y=0xFFF7。
z = x+y = 127-9=118，补码表示为 z = 0x00000076
第8题：下面C++代码的输出是___？
[cpp]void fun(char *x)
{
x++;
*x = 'a';
}
int main()
{
char str[sizeof("hello")];
strcpy(str,"hello");
fun(str);
cout<<str;
return 0;
}[/cpp]
这一题的关键是sizeof(“hello”) 值是多少。”hello” 是一个字符串，系统会自动在后面添加一个’\0’，所以sizeof(“hello”) 等于6。后面的就好理解了。fun函数无非将第二个字符转换为a，所以程序的输出为hallo。
第16题：年轻人花80元买老板的原件160的物品，年轻人没有零钱，给了张100的，老板也没有零钱，就接过年轻人的100元去隔壁兑换了零钱，然后找给了年轻人20元。但是事后，隔壁过来说100元是假的，老板不得不赔给隔壁100元。请问，整个事件中，老板损失了多少钱？
不要被问题的花花绕的一大圈弄混了。抓住关键点：隔壁没有损失，老板的损失也就是年轻人赚到的钱。年轻人赚了65元的物品和20元的现金。所以老板损失65+20=85元。
第17题：2100 mod 7 = ?
找规律 21 mod 7 = 2; 22 mod 7 = 4; 23 mod 7 = 1; 24 mod 7 = 2; 25 mod 7 = 4 …
所以规律是：2-4-1 循环，所以 2100 mod 7 = 21 mod 7 = 2;
第11题： 给了一个含有递归的函数fun()，问在通常的机器上运行，fun(35)的运行时间大概是多少？
[cpp]int f(int x)
{
int s = x;
while(s-- > 0) s += fun(x);
return max(s,1);
}[/cpp]
可选项是几毫秒，几秒，几分种，几个小时。
这题我到时没有做出来，感觉应该是n!+(n-1)! … 的复杂度，就猜了一个几分钟。具体的，等我再想想。
第15题：给了一个有向图，求起点到终点的最大流量。（这题我还不太懂，待学习）
多选（21~24）
第21题是关于malloc和free的一些理解。判断下面的说法是否正确：
(1) 无法通过malloc(size_t)函数调用申请超过机器物理内存大小的内存块。
首先，通过查找资料[1，2]，得出结论：malloc() 分配的是虚拟内存，访问具体虚拟地址的时候，实际上会做虚拟内存和物理内存的映射，最终调用物理地址的内容。
所以我觉得可以通过malloc(size_t)申请超过机器物理内存大小的内存块，因为机器存在虚拟内存。(1) 错误。 【我不是太确定】
(2) 无法通过内存释放函数free(void*)直接将某块已经使用完的物理内存直接还给操作系统。
资料[3] 中提到：
其中brk区（确切名字我不知道）可以用系统调用brk动态增长或缩小，malloc/free动态分配的内存就在brk区，内存分配算法由C库函数实现，与操作系统无关。需要更多内存时，调用sbrk/brk增长brk区，malloc一般不对应一次brk，一次brk分配比较大的块，malloc在这里再分，free一般只是更新空闲块，不调用任何系统调用，就是说free释放的内存可能不归还给系统，直到进程退出时才释放。
free释放的内存不一定直接还给操作系统，可能要到进程结束才释放。但(2) 说free不能把它归还给操作系统，就不对了。所以，我认为(2)是错误的。
(3) 可以通过内存分配函数malloc(size_t)直接申请物理内存
通过前面两题的，可以直到malloc不能直接申请物理内存，它申请的是虚拟内存。所以我认为(3)是错误的。
填空和简答题 (25~29)
第25题是数据传输问题。给了一副画面的分辨率，画面的像素位深，每秒的传输帧数，然后已知蓝牙的最大带宽，问能不能通过蓝牙传输。
这题比较简单，简单算一下每秒传输的数据量，比较一下与蓝牙带宽的大小即可。
第26题：将N条长度为M的有序链表进行合并，合并以后的链表也保持有序，时间复杂度为____?
两两归并排序。
第一次，N/2 组，每组时间复杂度O(2M)，综合为 O(N/2 * 2M) = O(NM)
第二次，N/4 组，每组时间复杂度O(4M)，综合为 O(N/4 * 4M) = O(NM)
依次类推，共有logN （底为2）次。
故总的时间复杂度为：O(MNlogN)
第27题： ABCD四人要在夜里过桥，分别耗时1、2、5、10分钟，只有一个手电筒，并且同时最多两人一起过。请安排方案让四人都过，用时最短，给出方案。
这题，我当时没有想到好方法。以为满足贪心算法，就让A每次来回接送。共耗时19分钟。
但是，刚刚我搜free 和 malloc时，发现了已经有人把昨晚的题目都放出来了。同时也给了他的解答，速度真快，让我佩服！
他对于本题的答案是17，方法是：1、2先过，2留下1回来，5、10再过，2回来，1、2再过。
比我的要优。看来我这题悲剧了。
第28题：下列代码是实现有序整数数组的二分查找，请指出其中的bug。
[cpp]int binary_search(int *array, int length, int key)
{
int start = 0, end = length - 1;
while (end > start)
{
int middle = (start + end) / 2;
int tmp = array[middle];
if (tmp < key)
start = middle;
else if (tmp > key)
end = middle;
else
return middle;
}
return -1;
}[/cpp]
我认为这里面存在1个bug和2个可改进的地方。
1个bug: end > start 改为 end >= start。 前者会丢掉array长度为1，且array[0]就是要查找的元素的情况。
2个可改进：start = middle 改进为 start = middle +1 因为middle也是不可能的。同理 end = middle 改进为 end = middle -1.
第 29 题，跳跃链表，求时间复杂度。
完全不会。我就猜它和二叉排序树(nlogn)差不多，然后利用上概率p进行改进，所以猜它的时间复杂度为O(nplogpn)，完完全全是猜的啊。
-------------------------------------------------------------------------------------------------------------
总的来说，本次笔试，我对阿里的印象还不错，组织的正规，题目也有难度，有广度，有深度，有区分，像个搞技术的大公司的笔试题。对自己的答题，只能说能做的我都做了，确实自己存在一些知识点不知道，有待学习。
作者：JarvisChu
原文链接：阿里实习生笔试归来
版权声明：自由转载-非商用-非衍生-保持署名 | Creative Commons BY-NC-ND 3.0