阿里 2015 校招机考

[paulw54jrn]

第一题:
一个提供Android APK下载的站点,原采用单台服务器,该服务器有一公网IP. 后业务量增加,短时间内修改代码不现实,如何应对指数增长的用户量?

答:
0> 静态文件分离,把apk放到一个专门的web server中. 同时该web server使用不同域名.
1> 静态文件web server做cdn.
2> 公网ip绑定到负载均衡器上, 用round robin方式轮询web server.
3> 负载均衡器连接一个专门做缓存的server (memcache/varnish), 缓存不命中再连接web server.
4> 数据库和web server分离. 数据库可用多库并联, 可用 master-master 或者 master-slave 的方式连接. 提高并发的同时提高健壮性.
5> 数据库打到瓶颈时可分表, 继续提高并发.
6> 如果数据库数据量不是太大,可以把redis作为主数据库(数据全部in memory),同时把传统的rdbms作为备用数据库.若使用了DAO的话,可以减少代码的修改量.

第二题:
找出二叉树中节点最大的差值,注意性能.

代码大意:
用栈模拟递归,做中序遍历,找出二叉树中的maxVal和minVal,返回abs(maxVal-minVal)

第三题:
解决一个本质上是个最长公共序列(LCS)问题,注意性能.

代码:
用动态规划做,代码就不贴了.


---------------------------
个人没有做过高并发应用,第一题纯属纸上谈兵,请问大家有什么看法?

PS:已经交卷,所以不用担心抄袭...

[rock_cloud]

第三题貌似不是LCS吧，LCS是可以不连续的，题目中要求是连续的

[liliang13]

我居然错过了，天啊。。。。

[paulw54jrn]

@rock_cloud
额..难道看错了.. 尴尬了..

[spacewander]

@paulw54jrn 话说如果是连续的话难度会小很多……

[jamesxu]

楼主把题目都泄露了不怕人家不找你吗？

[Exin]

表示看不懂

[YouXia]

第二题我看错题了，搞了一个优先队列，复杂度变高了。
第三题，这个不是LCS啊，
for i = 1 - > len(p)
for j = 1 -> len(q)
dp[i][j] = dp[i-1][j-1] + 1 (if p[i] == q[j])

[spacewander]

第一题，提到了“独立分开一个服务器，用CDN， memcache或redis做in-memory缓存，负载均匀”，不过没有楼主那么详细。
第二题， 我是用的递归，找出min，max然后取差。不需要取绝对值吧。
第三题，建n * m的表，像7楼那样爬格子。

[zts1993]

泄题不好吧。。。。。。。

[zts1993]

我觉得优化问题的第一步应该是分析瓶颈，然后针对不同的情况回答么？

我没答题不知道具体情况

[shanks]

难道你们没签保密协议。。。

不过这题量真少啊，看来对答案要求比较高，要考虑多方面的情况。。

[mudenng]

这只是三道附加题，我觉得前40分钟的单选才是重点，很多逻辑推理和数学基础

[YouXia]

@shanks

这个是全国统一的，不需要啥保密协议，每年题目都不一样，不会对公平性造成影响的。

还有20道选择题，特别难，考到了数学概率，分布式，计算机网络，操作系统，算法，Linux等等。

[xjx0524]

@YouXia 这次研发笔试的第二题和上一次笔试的附加题一样。。。魔盒那个

[Ransford]

楼主~前40分钟20道选择，后80分钟3道附加题。 是这样吗？？？？

[Wins0n]

第三题算Longest Common Substring，和Longest Common Subsequence稍微不一样一点。用DP的话，时间复杂度O(N*M)，空间可以用滚动数组优化到O(M)。
我看了下网上的解决方案，大部分都用后缀数组，当然这其中很多人可能只是直接套用的模板了。
题目测试可以看这里： http://acm.hdu.edu.cn/showproblem.php?pid=1403

高并发完全没研究，看了下别人贴的其他题目，感觉略变态。

[paulw54jrn]

@Ransford
是的,只不过这次考试略坑爹.
说好是中国时间9点,因为时差的关系,当地时间是11晚上才开始.
我当地时间9点十多分随手刷新了一下页面,结果考试已经开始了. 考试时间只剩下20多分钟...

[rAYz]

选择题不方便贴出来？

[tonyluj]

这是研发 还是 其他岗的？

[paulw54jrn]

@rAYz
选择题略多,做的时候没有注意保存.
不过相信网上别人会有保存的.

@tonyluj
申请的是系统工程师