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，

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

[java] view plaincopyprint?

1. "font-size:18px;">void printFitApples(int n){  
2.        //设有N个苹果，A=N-2  
3.        int A = 0;  
4.        while(n >= 0){  
5.            A += 21;  
6.            if((A-1) % 10 == 0 ||(A-1) % 10 == 5){  
7.               System.out.println(A+2);  
8.               n--;  
9.            }  
10.        }  
11. }  

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两边进行搜索以找出连续的字符个数。

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

 

[java] view plaincopyprint?

1. "font-size:18px;">    //搜索[d,u]区域  
2.     int getCountRecursion(char[] s, int d, int u){  
3.        if(u <= d)  
4.            return 1;  
5.        int mid = (d+u)/2;  
6.        int cLeft =getCountRecursion(s, d, mid-1);  
7.        int cRight =getCountRecursion(s, mid+1, u);  
8.        int cMid = 1,i = mid;  
9.        //搜索cMid两边的字符  
10.        while(--i>=d &&s[mid] == s[i] )  
11.            cMid++;  
12.        i= mid;  
13.        while(++i<=u &&s[mid] == s[i] )  
14.            cMid++;  
15.         
16.        returnmax(max(cLeft,cRight),cMid);  
17. }  

 

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为长度单位，从前到后，对每一小段进行插入前面的数组的插入排序，就能够完成。考虑到数组较长，无法全部存入内存，故无需对整个数组进行存储，只需要取要插入的段前面的那个数组就可以了（原因之前分析过）。可以在每排序完一定长度的数组时，进行存储并释放内存。

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

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

[java] view plaincopyprint?

1. public class SegmentSort {  
2.   
3.     Random random = new Random();  
4.       
5.     //以maxSegmentLen为最大长度，进行数组打乱  
6.     void disorder(int[] arr, int maxSegmentLen){  
7.         int ranInt = random.nextInt(maxSegmentLen);  
8.         int i = 1;  
9.         while(i+ranInt < arr.length){  
10.             disorderSegment(arr, i, i+ranInt);  
11.             i = i+ranInt+1;  
12.             ranInt = random.nextInt(maxSegmentLen);  
13.         }  
14.     }  
15.       
16.     //将arr[start,end]，进行打乱  
17.     void disorderSegment(int[] arr,int start,int end){  
18.         int len = end-start;  
19.         for(int i = 1;i
20.             int r = random.nextInt(len);  
21.             Tools.swap(arr,start+i,start+r);  
22.         }  
23.     }  
24.       
25.     void sort(int[] arr, int maxSegmentLen){  
26. //      可以预先对小段排序，但时间会耗费更长  
27. //      for(int i=1;i  
28. //          Arrays.sort(arr,i,i+maxSegmentLen);  
29.           
30.         for(int i=1;i
31.             insertInto(arr, i, maxSegmentLen);  
32.     }  
33.       
34.     //将arr[sortedEnd,sortedEnd+maxSegmentLen)，  
35.     //插入arr[0,sortedEnd)中进行插入排序  
36.     void insertInto(int[] arr, int sortedEnd,int maxSegmentLen){  
37.         int insertEnd = Math.min(arr.length, sortedEnd+maxSegmentLen);  
38.         for(int i = sortedEnd;i
39.             int t = i;  
40.             while(arr[t] < arr[t-1]){  
41.                 Tools.swap(arr, t, t-1);  
42.                 t--;  
43.             }  
44.         }  
45.     }  
46.       
47.     public static void main(String[] args) {  
48.         int LEN = 1000;  
49.         int SEGMENT_LEN = 22;  
50.         int[] arr = new int[LEN+1];  
51.         arr[0] = Integer.MIN_VALUE; //arr[0]作为哨兵  
52.         //初始化  
53.         for(int i = 1;i<=LEN;i++){  
54.             arr[i] = i;  
55.         }  
56.         SegmentSort segmentSort = new SegmentSort();  
57.         segmentSort.disorder(arr, SEGMENT_LEN);  
58.           
59.         segmentSort.sort(arr,SEGMENT_LEN);  
60. //      用于验证排序是否正确  
61. //      for(int i = 1;i<=LEN;i++)  
62. //          if(arr[i] != i)  
63. //              Tools.println("sort error! "+i);   
64.     }  
65. }