阿里实习生笔试归来

Mar 30, 2014

Life, Coding

笔试安排在浙大的玉泉校区，时间是昨天晚上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题原码和补码 #

第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题 sizeof 和指针 #

第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题 #

第16题：年轻人花80元买老板的原件160的物品，年轻人没有零钱，给了张100的，老板也没有零钱，就接过年轻人的100元去隔壁兑换了零钱，然后找给了年轻人20元。但是事后，隔壁过来说100元是假的，老板不得不赔给隔壁100元。请问，整个事件中，老板损失了多少钱？

不要被问题的花花绕的一大圈弄混了。抓住关键点：隔壁没有损失，老板的损失也就是年轻人赚到的钱。年轻人赚了65元的物品和20元的现金。所以老板损失65+20=85元。

第17题 #

第17题：2^100 mod 7 = ?

找规律 2^1 mod 7 = 2; 2^2 mod 7 = 4; 2^3 mod 7 = 1; 2^4 mod 7 = 2; 2^5 mod 7 = 4 …

所以规律是：2-4-1 循环，所以 2^100 mod 7 = 21 mod 7 = 2;

第11题 #

第11题：给了一个含有递归的函数fun()，问在通常的机器上运行，fun(35)的运行时间大概是多少？

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

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

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

第15题 #

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

多选（21~24） #

第21题 #

第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题 #

第25题是数据传输问题。给了一副画面的分辨率，画面的像素位深，每秒的传输帧数，然后已知蓝牙的最大带宽，问能不能通过蓝牙传输。

这题比较简单，简单算一下每秒传输的数据量，比较一下与蓝牙带宽的大小即可。

第26题 #

第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题 #

第27题： ABCD四人要在夜里过桥，分别耗时1、2、5、10分钟，只有一个手电筒，并且同时最多两人一起过。请安排方案让四人都过，用时最短，给出方案。

这题，我当时没有想到好方法。以为满足贪心算法，就让A每次来回接送。共耗时19分钟。

但是，刚刚我搜free 和 malloc时，发现了已经有人把昨晚的题目都放出来了。同时也给了他的解答，速度真快，让我佩服！

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

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

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

第28题 #

第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题 #

第29题，跳跃链表，求时间复杂度。

完全不会。我就猜它和二叉排序树(nlogn)差不多，然后利用上概率p进行改进，所以猜它的时间复杂度为O(nplogpn)，完完全全是猜的啊。

总的来说，本次笔试，我对阿里的印象还不错，组织的正规，题目也有难度，有广度，有深度，有区分，像个搞技术的大公司的笔试题。对自己的答题，只能说能做的我都做了，确实自己存在一些知识点不知道，有待学习。