百度笔试题及答案.doc

-教育精选-
第一题     简答题
1． 多线程和多进程模式有什么区别？在用两种模型开发服务程序时，分别有什么优缺点？采用长连接和短连接模式有什么区别？分别有什么优缺点？采用同步和异步模式有什么区别？分别有什么优缺点。
（1）启动进程的时候，操作系统会为进程分配资源，其中最主要的资源是内存空间，因为程序是在内存中运行的。在进程中，有些程序流程块是可以乱序执行的，并且这个代码块可以同时被多次执行。实际上，这样的代码块就是线程体。线程是进程中乱序执行的代码流程。当多个线程同时运行的时候，这样的执行模式成为并发执行。
对于一个进程中的多个线程来说，多个线程共享进程的内存块，当有新的线程产生的时候，操作系统不分配新的内存，而是让新线程共享原有的进程块的内存。因此，线程间的通信很容易，速度也很快。不同的进程因为处于不同的内存块，因此进程之间的通信相对困难。线程切换快，但实现稍复杂。进程易实现，较稳定，但性能与线程相比较差。
（2）所谓长连接，指在一个TCP连接上可以连续发送多个数据包，在TCP连接保持期间，如果没有数据包发送，需要双方发检测包以维持此连接，一般需要自己做在线维持。
短连接是指通信双方有数据交互时，就建立一个TCP连接，数据发送完成后，则断开此TCP连接，一般银行都使用短连接。

长连接多用于操作频繁，点对点的通讯，而且连接数不能太多情况，。每个TCP连接都需要三步握手，这需要时间，如果每个操作都是先连接，再操作的话那么处理速度会降低很多，所以每个操作完后都不断开，次处理时直接发送数据包就OK了，不用建立TCP连接。而像WEB网站的http服务一般都用短链接，因为长连接对于服务端来说会耗费一定的资源，而像WEB网站这么频繁的成千上万甚至上亿客户端的连接用短连接会更省一些资源，如果用长连接，而且同时有成千上万的用户，如果每个用户都占用一个连接的话，那可想而知吧。所以并发量大，但每个用户无需频繁操作情况下需用短连好。 

（3）同步:调用方调用一个程序,等待返回,然后再继续下面的程序处理 
异步: 调用方调用一个程序,不等待返回,继续执行下面的程序。
1)异步通信简单，双方时钟可允许一定误差。同步通信较复杂，双方时钟的允许误差较小。
2)通信效率：异步通信低，同步通信高。

2．请写出以下程序的运行结果，并解释导致这样运行结果的关键性原因。
 #include <iostream>
using std::cout;
class P
{
public:
virtual void print()
{
cout << "P";
}
};
class Q: public P
{
public:
virtual void print()
{
cout << "Q";
}
};
int main()
{
P * p = new P;
Q * q = static_cast <Q *> (p);

q->print();
         delete p;
cout << endl;

         q = new Q;
         p = q;
         q->print();
         p->print();
         cout << endl;

         p = new (q) P;
         q->print();
         p->print();
         cout << endl;

         p->~P();
         delete q;
         return 0;
}
P
QQ
PP

第二题 算法与程序设计题
1．给定如下的n*n的数字矩阵，每行从左到右是严格递增， 每列的数据也是严格递增
1 2 3
3 5 6
4 8 9
现在要求设计一个算法， 给定一个数k 判断出k是否在这个矩阵中。 描述算法并且给出时间复杂度（不考虑载入矩阵的消耗）
算法思想：
沿着对角线查找，获得i,使得k位于a[i][i]与a[i+1][i+1]之间。
k只可能存在于a[i][i]对应的右上角矩阵 和a[i+1][i+1]对应的左下角矩阵。
使用递归法继续查找即可。
时间复杂度 O(n)
int searchK(int int_arr[][],int n,int startlow,int startclm,int k)
{
int lefttemp=0;
int downtemp=0;
int i=0;
while(int_arr[startlow+i][startclm+i]<k||i<n)
i++;
if (i==n)
return 0;
else if(arr[i][i]==k)
reuturn 1;
else
return searchK(int_arr,n,startlow,startclm+i,k)+searchK(int_arr,n,startlow+i,startclm,k);
}
2．设 一个64位整型n,各个bit位是1的个数为a个. 比如7, 2进制就是 111,  所以a为3。
现在给出m个数, 求各个a的值。要求代码实现。
 #include <iostream>
#include<vector>
using namespace std;

int count(long long v)
{
int num=0;
while(v)
{
v &=(v-1); //执行效率为V中1的个数，时间复杂度比通过除操作、位操作比较高出很多
num++;
}
return num;
}

void main()
{
vector<long long> arr;
long long i;
cout<<"输入需要计算的数，Ctrl+z 停止" <<endl;
while(cin>>i)
{ //输入随机个数的数，使用Ctrl+z 停止，之后回车键继续。
arr.push_back(i);
};
for(vector<long long>::size_type idx=0;idx!=arr.size();++idx)
{
int n=count(arr[idx]);
cout<<n<<"\n";
}

}

第三题 系统设计题
实现一个简化的搜索提示系统。给定一个包含了用户query的日志文件，对于输入的任意一个字符串s，输出以s为前缀的在日志中出现频率最高的前10条query。
由于是分布式系统，假设至少有26台机器，每个机器存储以26个字母开头的query日志文件（如机器1存的是a字母开头的，机器2存的是以b字母开头的……）
每个机器上维护着一张哈希表，对于每条query, 在哈希表表中存放其地址（哈希地址为链式的），并对其进行排序，按频率由高到低进行排序。
当用户进行搜索时，可以很快定位到某台机器，并根据哈希表，返回出现频率最高的前10条query。

提示：
1、可以预处理日志
2、假设query不超过10亿条，每个query不超过50字节。
3、考虑在大查询量的情况下如何实现分布式服务

可编辑