阿里巴巴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;
}