V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
paulw54jrn
V2EX  ›  问与答

阿里 2015 校招机考

  •  
  •   paulw54jrn · 2014-08-29 21:01:37 +08:00 · 3874 次点击
    这是一个创建于 3740 天前的主题,其中的信息可能已经有所发展或是发生改变。
    第一题:
    一个提供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:已经交卷,所以不用担心抄袭...
    20 条回复    2014-08-31 09:37:49 +08:00
    rock_cloud
        1
    rock_cloud  
       2014-08-29 21:09:57 +08:00
    第三题貌似不是LCS吧,LCS是可以不连续的,题目中要求是连续的
    liliang13
        2
    liliang13  
       2014-08-29 21:15:43 +08:00
    我居然错过了,天啊。。。。
    paulw54jrn
        3
    paulw54jrn  
    OP
       2014-08-29 21:18:32 +08:00
    @rock_cloud
    额..难道看错了.. 尴尬了..
    spacewander
        4
    spacewander  
       2014-08-29 21:23:09 +08:00
    @paulw54jrn 话说如果是连续的话难度会小很多……
    jamesxu
        5
    jamesxu  
       2014-08-29 21:35:45 +08:00
    楼主把题目都泄露了不怕人家不找你吗?
    Exin
        6
    Exin  
       2014-08-29 21:39:27 +08:00
    表示看不懂
    YouXia
        7
    YouXia  
       2014-08-29 21:50:05 +08:00   ❤️ 1
    第二题我看错题了,搞了一个优先队列,复杂度变高了。
    第三题,这个不是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
        8
    spacewander  
       2014-08-29 22:40:25 +08:00
    第一题,提到了“独立分开一个服务器,用CDN, memcache或redis做in-memory缓存,负载均匀”,不过没有楼主那么详细。
    第二题, 我是用的递归,找出min,max然后取差。不需要取绝对值吧。
    第三题,建n * m的表,像7楼那样爬格子。
    zts1993
        9
    zts1993  
       2014-08-29 23:41:03 +08:00
    泄题不好吧。。。。。。。
    zts1993
        10
    zts1993  
       2014-08-29 23:50:24 +08:00
    我觉得优化问题的第一步应该是分析瓶颈,然后针对不同的情况回答么?

    我没答题不知道具体情况
    shanks
        11
    shanks  
       2014-08-30 00:13:32 +08:00
    难道你们没签保密协议。。。

    不过这题量真少啊,看来对答案要求比较高,要考虑多方面的情况。。
    mudenng
        12
    mudenng  
       2014-08-30 00:20:30 +08:00 via iPhone
    这只是三道附加题,我觉得前40分钟的单选才是重点,很多逻辑推理和数学基础
    YouXia
        13
    YouXia  
       2014-08-30 00:21:56 +08:00   ❤️ 1
    @shanks

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

    还有20道选择题,特别难,考到了数学概率,分布式,计算机网络,操作系统,算法,Linux等等。
    xjx0524
        14
    xjx0524  
       2014-08-30 00:25:13 +08:00
    @YouXia 这次研发笔试的第二题和上一次笔试的附加题一样。。。魔盒那个
    Ransford
        15
    Ransford  
       2014-08-30 01:27:38 +08:00
    楼主~前40分钟20道选择,后80分钟3道附加题。 是这样吗????
    Wins0n
        16
    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
        17
    paulw54jrn  
    OP
       2014-08-30 11:11:01 +08:00
    @Ransford
    是的,只不过这次考试略坑爹.
    说好是中国时间9点,因为时差的关系,当地时间是11晚上才开始.
    我当地时间9点十多分随手刷新了一下页面,结果考试已经开始了. 考试时间只剩下20多分钟...
    rAYz
        18
    rAYz  
       2014-08-30 23:43:45 +08:00
    选择题不方便贴出来?
    tonyluj
        19
    tonyluj  
       2014-08-31 02:39:12 +08:00
    这是研发 还是 其他岗的?
    paulw54jrn
        20
    paulw54jrn  
    OP
       2014-08-31 09:37:49 +08:00
    @rAYz
    选择题略多,做的时候没有注意保存.
    不过相信网上别人会有保存的.

    @tonyluj
    申请的是系统工程师
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   941 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 22:23 · PVG 06:23 · LAX 14:23 · JFK 17:23
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.