百度网页搜索部

一、算法效率比较

      题目：针对数组A和数组B，两个数组的元素内容相同，不过数组A是已经排序的，数组B是乱序的，针对数组的中位数，存在以下两组程序，比较其效率并分析原因。       

1 2 3 4 5 6 7 8 9 10 11 12

int g; int main() {     g = 0;     for(int i = 0 ; i < n ; i++) {         if( A[i] > mid )            g++;     }     for(int i = 0 ; i < n ; i++) {         if(B[i] > mid )            g++;     } }

 

      当包含流水线技术的处理器处理分支指令时就会遇到一个问题，根据判定条件的真/假的不同，有可能会产生转跳，而这会打断流水线中指令的处理，因为处理器无法确定该指令的下一条指令，直到分支执行完毕。流水线越长，处理器等待的时间便越长，因为它必须等待分支指令处理完毕，才能确定下一条进入流水线的指令。

      这个题目之前在网上浏览到过，知道有序的数组的效率其实比无序的要高很多，但是原因实在想不出来。现在搜一下，原来是stackoverflow上面的经典问答呢，原因不是编译器动手脚，而是CPU动的手脚，CPU有一个叫分支预测的技术，是这个技术导致有序数组的效率很高。 CPU指令执行的过程是流水线，简单的分支预测方案是针对当前元素(实际是处理过元素的统计学规律)判断下一个元素的指令跳转方向，有序的话分支预测的准确率很高，无序的话分支预测技术就不生效了，无法提前装载指令进入流水线，这样就损耗了一定的CPU时间。

二、简单算法之求不同元素

      题目：一个数组中只有一个数字出现1次，其他数字出现两次。

      挺简单的题目，因为见过，所以就跳过了这个题目，所以元素异或即可。

三、DP题目

      题目：一个m*n得棋盘，每个格子中有一个数字，计算从左上角至右下角的最大路径和，每一步行只能够向右或者向下行走。

      ACM的时候做过，我只知道是DP，不过不是很理解，现在好好高一下。

         

      

1 2 3 4 5 6 7 8 9

先初始化二维数组S，用双重for循环，Arrays.fill方法只可初始化一维数组     s[0][0] = a[0][0];     for(int i=1; i<N; i++)         s[i][0] = a[i][0] + s[i-1][0];     for(int j=1; j<M; j++)         s[0][j] = a[0][j] + s[0][j-1];     for(int i=1; i<N; i++)         for(int j=1; j<M; j++)             s[i][j] += a[i][j] + Math.max(s[i-1][j],s[i][j-1]);

三、海量数据处理

      问题：两个URL文件，分别有20亿条记录，每个URL的项目大约1KB。文件中有重复的URL记录，如何去除重复？

      因为在一面的过程中了解到，有序的数组去除重复的时候能够得到快速的去重，所以就考虑到了首先排序，但是两个这么大的文件单机排序？外部排序，k路归并排序，然后面试官就顺势的问了我k路归并排序的知识，k路归并排序的时间估计，因为k路归并排序很多时间在磁盘的IO上面，所以我猜测可能磁盘的IO才是时间的平静，每个元素最终进出磁盘4次，所以我估计的方法是元素数量*4*磁盘IO平均时间。不知道这个方法对不对。

      多机的扩展，MapReduce程序应该可以完成，但是我对hadoop不是很了解（所以这个方法没有答）。自己想一下多机的扩展吧，当然也是分治，想想也可以多机k路归并排序，后来面试官引导我说可以不排序么？我才意识到原始问题只是为了去除重复，所以这里分治并且利用hash的方法应该能够达到很快速的算法（复习一下《大型网站架构》这本书）一致性simhash方法应该是解决这个问题的。

      我首先想到的是hash，因为前面见过如何求出访问最多的IP，就是对IP进行Hash，只不过不知道如何Hash而已，过两天专门搞海量数据的Hash处理。

      参考文献http://www.cnblogs.com/weixliu/p/3900633.html

四、象棋问题

      中国象棋中帅，将和一个将身边的士，输出其合理位置的方案。

      刚看到这个算法题目的时候还卡了一下，不过后来自己把棋盘编号为1,2,3,4,5,6,7,8,9之后豁然开朗~不过我的代码if，else比较多，3类情况枚举，后来在面试官的提示下进行条件合并，节省了很多的代码。 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

for(int s = 1 ; s <= 9;s++) {        for(int j = 1 ; j <= 9;j++) {             for(int jsb = 1; jsb <= 9;jsb += 2) {                            if( validposition(s,j,jsb))                             printf("%d,%d,%d",s,j,jsb);             }          } }    bool validposition(int s,int j,int jsb) {    //将和帅相对应，并且不是士兵挡在将的前面的情况？？？     if ( s%3 == j%3 && !( jsb % 3 == j % 3 && jsb < j ) )         return false;     return true; }