发布于 2014-10-13 05:22:58 | 818 次阅读 | 评论: 0 | 来源: 网友投递
百度(Baidu)中文搜索引擎
百度（Nasdaq简称：BIDU）是全球最大的中文搜索引擎，2000年1月由李彦宏、徐勇两人创立于北京中关村，致力于向人们提供“简单，可依赖”的信息获取方式。“百度”二字源于中国宋朝词人辛弃疾的《青玉案·元夕》词句“众里寻他千百度”，象征着百度对中文信息检索技术的执著追求。
题1:C++/Java/Objective-C/C#语言是如何体现面向对象思想的。
不管什么面向对象语言，其面向对象思想就是通过面向对象特点：继承，封装，多态来实现面向对象设计（好像还有个抽象性，这里就不说了）。
在Java中：
继承性 Java通过继承实现代码复用。继承而得到的类称为子类，被继承的类称为父类。子类不能继承父类中访问权限为private的成员变量和方法。子类可以重写父类的方法，及命名与父类同名的成员变量。但Java不支持多重继承，即一个类从多个超类派生的能力。
封装性 java语言中，对象就是对一组变量和相关方法的封装，其中变量表明了对象的状态，方法表明了对象具有的行为。通过对象的封装，实现了模块化和信息隐藏。通过对类的成员施以一定的访问权限，实现了类中成员的信息隐藏。Java有四个不同的限定词：public，private，protected，default。
多态性 多态性体现在两个方面：由方法重载实现的静态多态性（编译时多态）和方法重写实现的动态多态性（运行时多态）。
对于C++来说，本人了解不多，我觉得它与Java在面向对象语法和概念上有很多相似的地方，然而Java是一种完全面向对象的语言，所有的东西都是在类中的，而C++中，全局变量、结构、枚举、联合等一些列源于C的概念仍然存在；同时其main方法也在所有的类之外。
至于C#和Objective-C本人没怎么接触，个人感觉主要思想都差不多，只是一些语法上的区别，重点在面向对象这四个字上，而不在与是什么语言。
题2：TCP协议主动连接和主动断开的过程。
若A为主动打开链接方，B为被动打开链接方。
主动连接过程：
B的TCP服务进程先创建传输控制块TCB，准备接受A的连接请求，然后B处于收听状态（Listen）；
A的TCP进程也是先创建传输控制块TCB，然后向B发出连接请求报文段，这时首部中的同步位SYN=1，同时选择一个初始序号seq=x。A进入同步已发送状态（SYN-Sent）。
B收到连接请求报文后，如果同意连接，则向A发送确认。在确认报文中把SYN和ACK都置1，确认号ack=x+1，同时也为自己选择一个初始序号seq=y。B进入同步收到状态（SYN-Rcvd）。
A收到B的确认后，还要向B给出确认。确认报文段的ACK置1，确认号ack=y+1,seq=x+1，这时连接建立。A进入已建立连接状态（Established）。
若B收到A的确认，B也进入已建立连接状态（Established）。
主动断开过程：
A发送连接释放报文，停止发送数据，报文首部FIN置1，序号seq=u，A进入终止等待1状态（FIN-Wait-1），等待B的确认。
B收到连接释放报文段后发出确认，确认号ack=u+1；seq=v，B进入关闭等待状态（CLOSE-Wait）。这之后B可能还会向A发送数据，但A不会向B发送数据。
A收到B的确认，进入终止等待2状态（FIN-Wait-2），等待B发出的连接释放报文。
若B已经没有向A发送数据，这时B发出连接释放报文使FIN=1，序号seq=w，确认号ack=u+1，B进入最后确认状态（LAST-ACK），等待A的确认。
A收到B的连接释放报文后必须发出确认，ACK置1，确认号ack=w+1，序号seq=u+1，进入时间等待状态（Time-Wait），A必须等待时间等待计数器设置的2MSL（最长报文段寿命）后A才进入到关闭（Close）状态。这时连接断开。
题3：const含义是什么，使用const有什么好处，同时解释下面五个表达式的含义。
const int a；
int *const a;
int const a;
const int *a;
int const *a const;
我觉得应该是在C或者C++中理解它，const是一个C语言的关键字，它限定一个变量不允许被改变。使用const在一定程度上可以提高程序的安全性和可靠性，另外，在观看别人代码的时候，清晰理解const所起的作用，对理解对方的程序也有一些帮助。
对于这五条语句我也是有点晕直接百度上来：
const int a; int const a; 这两个写法是等同的，表示a是一个int常量。
const int *a; 表示a是一个指针，可以任意指向int常量或者int变量，它总是把它所指向的目标当作一个int常量。也可以写成int const* a;含义相同。
int * const a; 表示a是一个指针常量，初始化的时候必须固定指向一个int变量，之后就不能再指向别的地方了。
int const * a const;这个写法没有，倒是可以写成int const * const a;表示a是一个指针常量，初始化的时候必须固定指向一个int常量或者int变量，之后就不能再指向别的地方了，它总是把它所指向的目标当作一个int常量。也可以写成const int* const a;含义相同。
算法设计题
题4：写出int strlen(const char *str)方法，要求方法中不能有局部或者全局变量。
当时看到不能定义变量，想了好久也没想到什么好办法，回来搜了下原来是要用递归，下面是参考代码：
int strlen(const char *str)
{
if(*str!='\0')
{
return 1 + strlen(++str);
}
else
{
return 0;
}
}
题5：题目大致意思是将一句英语句子调转顺序，但单词内字符顺序不变，例如：”The misson of Baidu is to provide the best way for people to find information.“
变为”information. find to people for way best the provide to is Baidu of misson The“，句子中的标点符号就当做单词的一部分，不区分开来。
我用C实现的，代码如下效率一般
#include<stdio.h>
#include<string.h>
int main()
{
int i,j,k,p,len,leni;
char temp,s[1000];
leni=0;
gets(s);
len=strlen(s);
for(i=0;i<(len/2);i++)//翻转整个字符串
{
temp=s[i];
s[i]=s[len-1-i];
s[len-1-i]=temp;
}
for(i=0;s[i]!='\0';)
{
for(j=i;(s[j]!=' ')&&(s[j]!='\0');j++)
leni++;
for(k=i,p=0;p<(leni/2);k++,p++)//翻转每个单词
{
temp=s[k];//k从i处每一步加一
s[k]=s[i+leni-1-p];//单次尾部指针从i+leni-1处每次减一
s[i+leni-1-p]=temp;
}
leni=0;
if(s[j]==' ')//跳过空格
i=j+1;
else if(s[j]=='\0')//判断是否结束
i=j;
}
puts(s);
}
题6：从100万个数里面找出10个最大的数。写出代码并分析复杂度。
这题直到最后还是没想出好办法，当然效率最低的办法就是一次次遍历，这样要算1000万次，明显不是好办法。
然后考虑分成多个线程计算，比如分成100组，每组1万个数，从每组中找出最大的10个，再从得到的1000个中找出最大的10个，这样大大提高了效率。
由于此题要写出代码，个人认为不是采用分组计算的方法，而是找出一种运算次数最少的方法，即时间复杂度最小。
试卷上我采用的是先构造一个10个数的数组并按照从小到大的顺序排列，然后所有的100万个数进行遍历，如果比数组的第一个数还要小则跳到下一个数，若比它大，则替换掉第一个元素，然后对数组进行排序，直到所有的数遍历完。这样整个时间复杂度最坏为100万*10log10。
网上的算法就是将上面的数组排序换成堆积排序，构建一个只有10个元素的堆，将根结点设为这10个数中最小的数，然后开始遍历数组，如果遇到的数根结点还小，直接跳过，遇到比根结点大的数，就替代根结点，然后对这个进行排序，保证堆头的特征。
希望各位大神指点，能给出更好的方案。
系统设计题
1：基于手机系统平台，设计一个IM多人实时语音聊天系统，包括手机端和Server端，请基于手机系统的一些特性，来设计这套IM系统。
2：请描述一下这套系统设计时需要考虑的关键性能指标有哪些。
3：如何保证实时语音的通话质量。
4：如何快速移植到多个手机系统平台（android和IOS）的方案。
5：请画出手机端程序的系统结构图。