阿里实习生笔试归来

笔试安排在浙大的玉泉校区,时间是昨天晚上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++代码的输出是___?

void fun(char *x)
{
	x++;
	*x = 'a';
}

int main()
{
	char str[sizeof("hello")];
	strcpy(str,"hello");
	fun(str);

	cout<<str;
	return 0;
}

这一题的关键是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)的运行时间大概是多少?  

int f(int x)
{
	int s = x;
	while(s-- > 0) s += fun(x);
	return max(s,1);
}

可选项是几毫秒,几秒,几分种,几个小时。

这题我到时没有做出来,感觉应该是n!+(n-1)! … 的复杂度,就猜了一个几分钟。具体的,等我再想想。

第15题:给了一个有向图,求起点到终点的最大流量。(这题我还不太懂,待学习

多选(21~24)

第21题是关于malloc和free的一些理解。判断下面的说法是否正确:

(1) 无法通过malloc(size_t)函数调用申请超过机器物理内存大小的内存块。

首先,通过查找资料[12],得出结论: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时,发现了已经有人把昨晚的题目都放出来了。同时也给了他的解答,速度真快,让我佩服!

2014.3.29 阿里巴巴 实习校招 笔试 题目及部分参考答案

他对于本题的答案是17,方法是:1、2先过,2留下1回来,5、10再过,2回来,1、2再过。

比我的要优。看来我这题悲剧了。

第28题:下列代码是实现有序整数数组的二分查找,请指出其中的bug。

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;
}

我认为这里面存在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

发表评论