阿里巴巴2015年系统工程师笔试附加题目

作者：jefby
Email: jef199006@gmail.com


       终于做完阿里的系统工程师笔试题目，由于自己的失误，本来以为阿里云事业部的个人云（就是开发云路由，智能家居那部分的部门）应该是属于系统工程师，结果前几天才发现原来是自己投错岗位了，可是想改也已经改不了了！！哎，就先做做吧！！

说明：个人水平有限，做的题目肯定有bug，第一道题是不确定，第2,3道题目都验证过，可能效率不是特别高，欢迎高手拍砖指正！！
题目一：
A公司打算搭建一个Andriod App下载的Web站点，计划将目前常见的手机APP都放到这个网站上提供下载。因为业务开展初期下载量很小，技术部门就用了1台服务器，给服务器配置了一个公网IP对外进行服务。随着销售部门的推广到位，用户量和下载量呈指数级上载，要求技术部门马上进行改造。如果你是技术部门经理，你会怎么改造这个站点，以满足高负载的需求。
提示：短时间修改网站的代码不现实，其他方面的各种改造建议都可以，建议越多越好。
个人解答：
1.基于DNS的负载均衡方法，多个ip对应一个域名，均衡下载

2.使用硬件第四层交换技术
主要思想就是分流，将数据分配都不同的应用服务器上。根据包头信息和应用区间识别业务流，将整个区间段的业务流分配到合适的应用服务器。
就像虚拟IP一样，指向物理服务器。它传输的业务服从的协议多种多样，有HTTP、FTP、NFS、Telnet或其他协议。这些业务在物理服务器基础上，
需要复杂的载量平衡算法。在IP世界，业务类型由终端TCP或UDP端口地址来决定，在第四层交换中的应用区间则由源端和终端IP地址、TCP和UDP端口共同决定。
在硬件四层交换产品领域，有一些知名的产品可以选择，比如Alteon、F5等，这些产品很昂贵，但是物有所值，能够提供非常优秀的性能和很灵活的管理能力。

3.
在软件或者硬件四层交换的基础上搭建squid集群，这种思路在很多大型网站包括搜索引擎上被采用，这样的架构低成本、高性能还有很强的
扩张性，随时往架构里面增减节点都非常容易。

4.使用高速缓存技术，将下载最多的App放到高速缓存中。

5.反向代理负载均衡和高速缓存结合起来，让代理服务器将请求均匀转发给多台内部Web服务器之一上

6.基于NAT的负载均衡技术

7.半中心负载均衡方式
在半中心的负载均衡方式下，即当客户请求发送给负载均衡器的时候，中心负载均衡器将请求打包并发送给某个服务器，
而服务器的回应请求不再返回给中心负载均衡器，而是直接返回给客户，因此中心负载均衡器只负责接受并转发请求，其网络负担就较小了。

题目二：
写一个函数，输入一个二叉树，树中每个节点存放了一个整数值，函数返回这棵二叉树中相差最大的两个节点间的差值绝对值。请注意程序效率。
个人解答：
static int cnt = 0;
static int a[1001];

typedef struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
}TreeNode;

static void
InOrderTraverse_rec(TreeNode * root)
{
if(!root)
return;
else{
InOrderTraverse_rec(root->left);
a[cnt++]=root->val;
InOrderTraverse_rec(root->right);
}
}

int
compare (const void *elem1, const void *elem2 )
{
    return *(int*)elem1-*(int*)elem2;
}

unsigned int
max_tree(TreeNode* root,int(*cmp)(const void *elem1, const void *elem2 ))
{
    InOrderTraverse_rec(root);
    qsort(a,cnt,sizeof(int),cmp);
    return a[cnt-1]-a[0];
}
题目三：
给定一个query和一个text，均由小写字母组成。要求在text中找出以同样的顺序连续出现在query中的最长连续字母序列的长度。例如， query为“acbac”，text为“acaccbabb”，那么text中的“cba”为最长的连续出现在query中的字母序列，因此，返回结果应该为其长度3。请注意程序效率。
个人解答：
/* 最长公共子串 DP */
int dp[40][40];

int
LCS_dp(char * text,char * query)
{
int matextlen  = 0;
int textlen =0,querylen=0;

textlen= strlen(text);
querylen = strlen(query);

    for(int i = 0; i < textlen; ++i)
    {
        for(int j = 0; j < querylen; ++j)
        {
            if(text[i] == query[j])
            {
                if(i && j)
                    dp[i][j] = dp[i-1][j-1] + 1;
                if(i == 0 || j == 0)
                    dp[i][j] = 1;
                if(dp[i][j] > matextlen)
                    matextlen = dp[i][j];
            }
        }
    }
 
return matextlen;
}

chrome37 64bit install error

        今天看到了google官网上发布的chrome更新信息，据说是支持64位的稳定版，速度和效率都得到了很大的提升，所以好奇心驱使下试着卸载了32位，重装64位，但是安装后总是加载不了页面，连基本的设置插件页面都打不开，尴尬极了！最后实在没办法，就只好试着使用兼容模式运行，竟然可以，但是打不开优酷网站，太麻烦了！有解决方法？在plugins中已经设置启用adobe flash和google flash。

vim插件的安装和管理

今天晚上在一篇博客中看到有关安装vim插件的用法，心血来潮下自己在CentOS 6.5下试了下，走了一点点的弯路，就把步骤记录下来吧！！以便以后再次能迅速搭建环境！！
vim下vundle是一款管理插件的神器，能够管理众多的vim插件，安装方法如下：
#git clone https://github.com/gmarik/vundle.git ~/.vim/bundle/vundle
然后在/etc/vimrc中添加如下代码

set nocompatible "与vi不一致
filetype off
set rtp+=~/.vim/bundle/vundle/ "载入特定目录插件
"set rtp+=$HOME/.vim/bundle/vundle/ "Windows下
call vundle#rc()
"plugin 
"vimscripts账号下的项目直接填写名称即可
Bundle 'snipMate'
"其它需填写用户/资源名称
Bundle 'gmarik/vundle'
"非github上资源
Bundle 'git://git.wincent.com/command-t.git'
"indent
Bundle 'php.vim-html-enhanced'
"color
Bundle 'Lucius'
filetype plugin indent on

启用vundle，然后安装可以使用vundle管理的插件，例如powerline。

安装方法：

#cd ~/.vim/bundle/

#git clone https://github.com/Lokaltog/vim-powerline

在vimrc中添加如下代码：

set t_Co=256

Bundle 'vim-powerline'

set laststatus=2

let g:Powerline_colorscheme='solarized256'

重启vim，可看到如下图所示：

关于程序员开发环境配置的一点小看法

   前几天在Windows下写代码，使用的是UltraEdit 10.0，界面有点丑，有个师弟见了之后推荐我使用sublime软件试试，于是抱着好奇的心态下载并安装了sublime软件，我只能说好的编辑器能极大的提高程序员开发的积极性！！
   使用了几天之后，我是彻底喜欢上了这款编辑器，sublime最早是为Mac OSX开发的后来做了全平台适配，现在Windows、Linux也可以使用了，当然应该体验最好的是Mac OSX吧，Windows下需要安装cygwin之类的安装包，而Linux下虽然也可以安装sublime，并且自带有gcc编译器等，但是中文输入法是一个大难题，sublime默认不支持ibus输入法，所以就尴尬了，没有中文输入法是个让人很纠结的事情；而windows下虽然没有输入法的限制，但是默认的中文编码GBK是个bug，在默认使用utf-8的sublime下还是需要安装好package-control和convertToUTF-8包才可以较好的看到GB2312编码的中文注释等，当然也可以直接将文件另存为utf-8格式的，然后再使用sublime打开。
   而这更让我对Mac世界充满了向往，Mac下使用的默认编码是utf-8，而且是类Unix设计的操作系统，我想对于Linux开发者也是一个非常好的选择，而且界面设计的非常漂亮！！软件支持包众多！！

arm linux内核源码中关于何时开启MMU的思考

   今天再次阅读arm linux内核源码，看MMU启动部分发现了一个问题，就是在常规的__enable_mmu和__turn_mmu_on部分我没有找到真正使能MMU标志的代码，但是它到底是什么时候将MMU的最低位置1的呢？？怀着这个疑问我在google上搜索了好多，但是对于这个问题的解答都是模凌两可，说的特别含糊，千篇一律，不能让人信服。

__enable_mmu代码如下：

__enable_mmu:
#if defined(CONFIG_ALIGNMENT_TRAP) && __LINUX_ARM_ARCH__ < 6
orr r0, r0, #CR_A
#else
bic r0, r0, #CR_A
#endif
#ifdef CONFIG_CPU_DCACHE_DISABLE
bic r0, r0, #CR_C
#endif
#ifdef CONFIG_CPU_BPREDICT_DISABLE
bic r0, r0, #CR_Z
#endif
#ifdef CONFIG_CPU_ICACHE_DISABLE
bic r0, r0, #CR_I
#endif
#ifndef CONFIG_ARM_LPAE
mov r5, #(domain_val(DOMAIN_USER, DOMAIN_MANAGER) | \
domain_val(DOMAIN_KERNEL, DOMAIN_MANAGER) | \
domain_val(DOMAIN_TABLE, DOMAIN_MANAGER) | \
domain_val(DOMAIN_IO, DOMAIN_CLIENT))
mcr p15, 0, r5, c3, c0, 0 @ load domain access register
mcr p15, 0, r4, c2, c0, 0 @ load page table pointer
#endif
b __turn_mmu_on
ENDPROC(__enable_mmu)

__turn_mmu_on源码如下：
ENTRY(__turn_mmu_on)
mov r0, r0
instr_sync
mcr p15, 0, r0, c1, c0, 0 @ write control reg(启用MMU)
mrc p15, 0, r3, c0, c0, 0 @ read id reg
instr_sync
mov r3, r3
mov r3, r13 @r3中转入最后要跳入的虚拟地址
mov pc, r3 @跳转到__mmap_switched
__turn_mmu_on_end:

在__turn_mmu_on中将r0的值写入协处理CP15的C1寄存器中，但是r0的bit0什么时候被置位了呢？？__enable_mmu没有置位，那就肯定是在__enable_mmu之前，搜索代码找到了答案：

::arch/arm/mm/proc-v6.S

其实在__v6_setup中设置的，有一段代码如下：
adr r5,v6_crval @将v6_crval的实际运行地址加载到r5处
ldmia r5,{r5,r6}@将r5地址处的两个字内容保存到r5和r6处，根据v6_crval定义可知，值为clear和mmuset，mmmuset的最后一个比特值为1，也就是CR_M=1
orr r0,r0,r6 @在此处将设置r0的bit0为1。随后在__turn_mmu_on中将MMU的值写入CP15的C1寄存器，真正使能MMU。

v6_crval的定义如下：
.type v6_crval, #object
v6_crval: crval clear=0x01e0fb7f, mmuset=0x00c0387d, ucset=0x00c0187c
其中crval是定义的宏，根据配置CONFIG_MMU不同存放不同的值.
.macro crval, clear, mmuset, ucset
#ifdef CONFIG_MMU
 .word \clear
 .word \mmuset
#else
 .word \clear
 .word \ucset
#endif                                                                                                                  .endm  
至此就非常清楚了，在__v6_setup中设置了r0的bit0，然后调用__enable_mmu和__turn_mmu_on真正开启MMU。

关于积累和专注的想法

   今天偶然间在QQ群消息中知道我12年认识的一个同学获得了研究生电子设计大赛一等奖，感触良多。
   我和他交往不深，只是12年做FPGA比赛的时候认识的，我记得当时给我感触特别大的就是他会把他所做过的东西做一些总结，写成博文；而且更让我钦佩的是会定期做优化，会一点一点的做优化改进，而当时的我什么也没做过，没写过博客或者做过任何项目方面的总结，而他当时已经是chinaAET上的知名博主了，同样是做技术的，同样是一级学生，怎么差距这么大？？虽然我不是做硬件的，但是感觉看他的技术真的相当过硬，可以说是见过的同龄人里面最厉害的！
   下午抽空看了下他的比赛作品，更让我吃惊的是竟然是12年他们曾经做过的，不过和当时相比，作品的质量和技术得到了质的飞越，设计的硬件很精致，而且听说是由他自己设计的！我想象不出他是怎么一步一步、脚踏实地把他们当时比较粗糙的东西做优化，做精致；必定是痛苦蜕变的过程！而想想我，12~13年期间做的作品，比赛完后就再也没有看过，13~14年忙于老师的项目，项目做完还是没有做任何的总结和优化，做完也就完了！这才是我和他之间产生如此巨大差异的原因吧！！一个看到不足，然后总结经验，一点点的改进；另一个也看到不足，但是没有深刻总结，只是放弃！！去挖新的井！想起来我就是那成语里面说的那种反面教材吧！！！ ||_||
   我还很佩服一个人，他是我大学室友，朝夕相处增加了我们之间的了解，也让我更加佩服他，他和我一样是做软件开发的，不过他更偏重的是应用软件开发，经常会写一些很实用的小软件，然后慢慢改进他自己的代码，不断的总结优化，最后惊艳了似我这类屌丝！！
   向大神们学习！勤于总结，一点点改进优化，最终我要惊艳世人！！