阿里 2015 校招机考

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3739 天前的主题，其中的信息可能已经有所发展或是发生改变。

第一题:
一个提供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:已经交卷,所以不用担心抄袭...

数据库

Server

Web

20 条回复 • 2014-08-31 09:37:49 +08:00

rock_cloud

2014-08-29 21:09:57 +08:00

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

liliang13

2014-08-29 21:15:43 +08:00

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

paulw54jrn

2014-08-29 21:18:32 +08:00

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

spacewander

2014-08-29 21:23:09 +08:00

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

jamesxu

2014-08-29 21:35:45 +08:00

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

Exin

2014-08-29 21:39:27 +08:00

表示看不懂

YouXia

2014-08-29 21:50:05 +08:00

第二题我看错题了，搞了一个优先队列，复杂度变高了。
第三题，这个不是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

2014-08-29 22:40:25 +08:00

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

zts1993

2014-08-29 23:41:03 +08:00

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

zts1993

2014-08-29 23:50:24 +08:00

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

我没答题不知道具体情况

shanks

2014-08-30 00:13:32 +08:00

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

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

mudenng

2014-08-30 00:20:30 +08:00 via iPhone

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

YouXia

2014-08-30 00:21:56 +08:00

@shanks

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

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

xjx0524

2014-08-30 00:25:13 +08:00

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

Ransford

2014-08-30 01:27:38 +08:00

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

Wins0n

2014-08-30 10:08:45 +08:00

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

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

paulw54jrn

2014-08-30 11:11:01 +08:00

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

rAYz

2014-08-30 23:43:45 +08:00

选择题不方便贴出来？

tonyluj

2014-08-31 02:39:12 +08:00

这是研发还是其他岗的？

paulw54jrn

2014-08-31 09:37:49 +08:00

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

@tonyluj
申请的是系统工程师