2012年10月份，百度笔试题

一、简答题

1、列举几个常见的哈希算法，简述哈希算法的主要用途

http://blog.csdn.net/zxycode007/article/details/6999984

这篇文章介绍的很清楚了。

主要用途：查找关键字、文件校验、数字签名

2、描述OSI的7层架构，并指出HTTP、UDP、ARP协议在那一层？

应用层：为应用程序提供网络服务

表示层：确保不同应用信息的识别

会话层：建立数据传输通路

传输层：进行流量控制、分割数据包，以及定义一些传输协议

网络层：提供IP地址服务、进行IP到MAC地址的转化

数据链路层：确保帧的无差错传输

物理层：提供bit或者电压的处理

ARP属于网络层，UDP属于传输层、HTTP属于应用层

3、简述让一段C语言代码运行起来的代码要求和执行过程。

         编译，编译程序读取源程序（字符流），对之进行词法和语法的分析，将高级语言指令转换为功能等效的汇编代码，再由汇编程序转换为机器语言，并且按照操作系统对可执行文件格式的要求链接生成可执行程序。

编译的过程：源代码-->预处理-->编译-->优化-->汇编-->链接-->执行

         预处理：头文件（Include file）的插入， 宏 （Macro） 的解开，条件编译（Conditional compilation）的处理 。

         编译：编译器首先要检查代码的规范性、是否有语法错误等，以确定代码的实际要做的工作，在检查无误后，编译器把代码翻译成汇编语言。

         汇编：将汇编语言转换成机器语言。

         链接：将参与链接的对象文件合并成一个可执行文件。

         （http://lavasoft.blog.51cto.com/62575/187229）

二、算法与程序设计

1、 小杨拉来一车苹果进行包装，如果3个包一袋剩下2个，5个包一袋剩下3个，7个包一袋剩下2个，设计算法，求出N个符合条件的苹果个数。

思路：

1）N符合N%3 =2，N%5=3，N%7=2，可知(N-2)%3=0，(N-2)%7=0，(N-3)%5=0，

假设A=N-2，那么A%3=0，A%7=0，(A-1)%5=0，

所以，A是3与7的公倍数，且A-1的结尾是0或者5，

按照这个思路，就可以解题了。代码如下：

void printFitApples(int n){
       //设有N个苹果，A=N-2
       int A = 0;
       while(n >= 0){
           A += 21;
           if((A-1) % 10 == 0 ||(A-1) % 10 == 5){
              System.out.println(A+2);
              n--;
           }
       }
}           

2）如果要再优化的话，由于A每次是加21，因此，每次尾数增加1. 在尾数为1或6的时候，加上21*5=105，刚好会使得尾数为6或1，因此，每次进行 A+= 105，可以少做4/5次的运算。因此，符合的数字为23,23+105,23+2*105...23+n*105，故，直接使用公式23+n*105（n为自然数）就可以得到结果。（算法略）

2、 编写递归算法，查找字符串中相同字符连续出现的最大次数，例如：aaabbcc，最大连续重复数为3，abbc，最大连续重复数为2。

分析：对于字符串s,从位置d开始，到位置u结束（s[d,u]）首先取出中间的位置mid=(d+u)/2,那么最大值分成3种情况

1） 最大值位于s[d,mid-1]中

2） 最大值位于s[mid+1,u]中

3） 最大值包含第mid个数，例如aabbbbcc，mid=（0+7）/2=3，最大值范围是[2,5]，在第mid个数’b’的两边。需要对mid两边进行搜索以找出连续的字符个数。

按照这种方式进行递归查询，代码如下

//搜索[d,u]区域
    int getCountRecursion(char[] s, int d, int u){
       if(u <= d)
           return 1;
       int mid = (d+u)/2;
       int cLeft =getCountRecursion(s, d, mid-1);
       int cRight =getCountRecursion(s, mid+1, u);
       int cMid = 1,i = mid;
       //搜索cMid两边的字符
       while(--i>=d &&s[mid] == s[i] )
           cMid++;
       i= mid;
       while(++i<=u &&s[mid] == s[i] )
           cMid++;
      
       returnmax(max(cLeft,cRight),cMid);
}           

3、 见图

三、有一个数量大于100亿的整型数组，从小到大有序排列，现在该有序数组被分成若干字段，已知每段的数据个数不超过20个，但每个段内的数量不相同，且将每段内的数据重新进行打乱，得到一个新的数组。要求对得到的新的数组重新进行从小到大排序，求效率最高的算法，并给出时间复杂度分析。

         分析：100亿个数，整体已经排好序，但局部无序。若每个段都是固定的，那么，只需把每小段都进行排序即可，但每段的长度是不同的，又该如何分析？

         举个例子，原数组是：1,2,3,4,5,6,7,8,9,10,11,12,13,14,15

         每段数据不超过5进行打乱后（打乱的长度为5,3,4,3），数组为：

         2,5,3,4,1,7,8,6,11,9,12,10,14,15,13

         是一个整体有序，局部无序的数组。考虑到其限制：每段数据不超过5个，故数据位置的偏移量（偏离原来的位置）最多为4（乱序位置-原始位置，取绝对值），我们可以这么做

先对前5个排序，得到数组arr=1,2,3,4,5

再对6到10个数进行插入arr排序,得到arr=1,2,3,4,5,6,7,8,9,10

再对11到15个数进行插入arr排序，得到arr=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15

整个数组排序完成。

观察这个结果，假设第1到第5n个数已经有序为sort(5n)，那么我们要将5n+1到5n+5这5个数据添加到已排序的数组中，只需要进行插入排序，将这5个数添加进即可。由于分段的长度不超过5，所以第5n+1个数在插入的时候，最多只需要搜索到第5n-4个数就可以了，比较个数不会超过5次。又因为5n+1到5n+5是已经排好序的，所以，后面的数比较次数也不会超过5次（最多比较到前一个插入的位置）。因此，每加入5个数到已排序数组中，时间复杂度是O（5*5），

         假设长度为N，每段长不超过K。则每段插入的时间复杂度即为O（K*K）。

而对于以段为单位插入的操作，需要进行N/K次，所以，总的时间复杂度是O(K*K)*O(N/K)=O(NK)

回到原题由于每个段的长度不超过20，我们可以先以20为长度单位，从前到后，对每一小段进行插入前面的数组的插入排序，就能够完成。考虑到数组较长，无法全部存入内存，故无需对整个数组进行存储，只需要取要插入的段前面的那个数组就可以了（原因之前分析过）。可以在每排序完一定长度的数组时，进行存储并释放内存。

尝试过先对小段排序，再进行插入，发现耗费时间大概为直接插入的三倍，哎~画蛇添足。

代码如下，先打乱，再排序

public class SegmentSort {

	Random random = new Random();
	
	//以maxSegmentLen为最大长度，进行数组打乱
	void disorder(int[] arr, int maxSegmentLen){
		int ranInt = random.nextInt(maxSegmentLen);
		int i = 1;
		while(i+ranInt < arr.length){
			disorderSegment(arr, i, i+ranInt);
			i = i+ranInt+1;
			ranInt = random.nextInt(maxSegmentLen);
		}
	}
	
	//将arr[start,end]，进行打乱
	void disorderSegment(int[] arr,int start,int end){
		int len = end-start;
		for(int i = 1;i<len;i++){
			int r = random.nextInt(len);
			Tools.swap(arr,start+i,start+r);
		}
	}
	
	void sort(int[] arr, int maxSegmentLen){
//		可以预先对小段排序，但时间会耗费更长
//		for(int i=1;i<arr.length;i += maxSegmentLen)
//			Arrays.sort(arr,i,i+maxSegmentLen);
		
		for(int i=1;i<arr.length;i += maxSegmentLen)
			insertInto(arr, i, maxSegmentLen);
	}
	
	//将arr[sortedEnd,sortedEnd+maxSegmentLen)，
	//插入arr[0,sortedEnd)中进行插入排序
	void insertInto(int[] arr, int sortedEnd,int maxSegmentLen){
		int insertEnd = Math.min(arr.length, sortedEnd+maxSegmentLen);
		for(int i = sortedEnd;i<insertEnd;i++){
			int t = i;
			while(arr[t] < arr[t-1]){
				Tools.swap(arr, t, t-1);
				t--;
			}
		}
	}
	
	public static void main(String[] args) {
		int LEN = 1000;
		int SEGMENT_LEN = 22;
		int[] arr = new int[LEN+1];
		arr[0] = Integer.MIN_VALUE;	//arr[0]作为哨兵
		//初始化
		for(int i = 1;i<=LEN;i++){
			arr[i] = i;
		}
		SegmentSort segmentSort = new SegmentSort();
		segmentSort.disorder(arr, SEGMENT_LEN);
		
		segmentSort.sort(arr,SEGMENT_LEN);
//		用于验证排序是否正确
//		for(int i = 1;i<=LEN;i++)
//			if(arr[i] != i)
//				Tools.println("sort error! "+i); 
	}
}
           

原题：