阿里巴巴集团秋季校招笔试题和面试题答案(三)
第三部分 填空与问答(5题，共30分)
25. (4分)某无聊的程序员在玩Windows上的记事本程序，不用鼠标，每次可以按以下键或组合之一：A、Ctrl+A(全选)、Ctrl+C(拷贝)、Ctrl+V(粘贴)，那么在10次按键只能可以制造的最长文本长度为 。
26. (4分)若初始序列为gbfcdae，那么只会少需要 次两两交换，才能使该序列变为abcdefg。任给一个自由a--g这7个字母组成的排列，最坏的情况下需要至少 次两两交换，才能使序列变为abcdefg。
27. (5分)在某恶劣天气，若地图上S点到T点的交通网如下图所示，其中每条边表示一条双向通道，其上的数字为该通路可通行的概率，且该概率两两独立。求S到T的可通行概率 。
1/3
1/2
1/2
1/2
1/2
1/3
28. (8分)6度分离假说的含义是，世界上任何两个人要么是朋友，要么是朋友的朋友，或者更高阶的朋友的朋友(如朋友的朋友的朋友)，改论断中“朋友”一词出现的次数为两人之间的距离，那么该距离小于等于6。如果某SNS(如QQ、旺旺等)，有100万用户，其人际关系网咯符合以下两个假设：
1) 朋友关系是一种对称关系(如A和B是朋友，那么B和A也是朋友)
2) 符合2度分离假说
3) 第i个人拥有的朋友的个数为ni ，所有ni 中最大值为n
试估算n的最小值 。
29. (9分)某电子商务网站进行A、B两种推荐算法的效果对比测试，对用户的访问请求按照1:9的比例随机分配给A和B两种算法处理。产生推荐结果后，按照两种指标对比两种算法产生的结果好坏：第一种指标是CTRPV=该算法下用户的点击展现次数/该算法下所有的展现次数，第二种指标是CTRUV=该算法下有点击的用户数/该算法下所有的用户数。假定每个用户会对该推荐服务2次访问，如果A和B的CTRPV持平(假设为0.01)。那么CTRUV哪个大，大的比小的大百分之多少 。
第四部分：JAVA附加题(注，阿里有大量JAVA研发工程师需求;选作以下题目有机会增加该方向面试机会)
1.以下每个线程输出的结果是什么?(不用关注输出的顺序，只需写出输出的结果集即可)
public class TestThread{
public static vod main(String[] args){
// test1
Thread t1 = new Thread(){
@Override
public void run(){
try{
int i=0;
while(i++<100000000){
// nothing
}
System.out.println("A1");
}catch(Exception e){
System.out.println("B1");
}
};
};
t1.start();
t1.interrupt();
// test2
Thread t2 = new Thread(){
public void run(){
try{
Thread.sleep(5000);
System.out.println("A2");
}catch(Exception e){
System.out.println("B2");
}
};
};
t2.start();
// t2.interrupt(); //不确定是否有这句话
// test3
Thread t3 = new Thread(){
public void run(){
try{
Thread.sleep(50000);
System.out.println("A3");
}catch(Exception e){
System.out.println("B3");
}
};
};
t3.start();
t3.interrupt();
// test4
Thread t4 = new Thread(){
public void run(){
try{
Thread.sleep(50000);
System.out.println("A4");
}catch(Exception e){
System.out.println("B4");
}
};
};
t4.start();
t4.interrupt();
// test5
try{
t4.start();
System.out.println("A5");
}catch(){
System.out.println("B5");
}
}
}
2. 一个10亿条记录的文本文件，已按照关键字排好字存储，请设计方法，可以快速的从文件中查找指字关键字的记录。
【系统工程师】 附加题
1.在互联网时代系统的稳定性要求越来越高，为了提升系统的稳定性，高可用技术被广泛运用，请列举至少4中相关的技术解决硬件、系统或网络等层面的单点问题。
2.请描述一下TCP建立连接三次握手的过程。
3. 搜索引擎是很常用的web应用。大部分搜索引擎需要设计一个抓虫(Crawler)，从很多网站抓去网页，分析数据，供搜索引擎使用。
设想你来做一个搜索引擎的爬虫，需要抓去约一百万家网站的网页内容。
1) 请画出一个抓虫系统的架构图。
2) 重点说明你的爬虫需要如何优化来提升性能。
