百度笔试面试经验(一)

　　编程：

　　用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。

　　2 编程：

　　用C语言实现函数void * memmove(void *dest,const void *src,size_t n)。memmove函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。

　　3 英文拼写纠错：

　　在用户输入英文单词时，经常发生错误，我们需要对其进行纠错。假设已经有一个包含了正确英文单词的词典，请你设计一个拼写纠错的程序。

　　(1)请描述你解决这个问题的思路;

　　(2)请给出主要的处理流程，算法，以及算法的复杂度;

　　(3)请描述可能的改进(改进的方向如效果，性能等等，这是一个开放问题)。

　　4 寻找热门查询：

　　搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。

　　(1)请描述你解决这个问题的思路;

　　(2)请给出主要的处理流程，算法，以及算法的复杂度。

　　5 集合合并：

　　给定一个字符串的集合，格式如： {aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh} 要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出 {aaa bbb ccc ddd hhh}，{eee fff}， {ggg}

　　(1)请描述你解决这个问题的思路;

　　(2)请给出主要的处理流程，算法，以及算法的复杂度

　　(3)请描述可能的改进(改进的方向如效果，性能等等，这是一个开放问题)。

　　1 题

　　char *revert(char * str)

　　{

　　int n=strlen(str);

　　int i=0;

　　char c;

　　for(i=0;i {

　　c=str;

　　str=str[n-i];

　　str[n-i]=c;

　　}

　　return str;

　　}

　　2 题

　　void * memmove(void *dest,const void *src,size_t n)

　　{

　　assert((dest!=0)&&(src!=0));

　　char * temp=(char * )dest;

　　char * ss=(char * )src;

　　int i=0;

　　for(;i {

　　*temp =*ss ;

　　}

　　return temp;

　　}

　　3 题

　　(1)思路: 字典以字母键树组织，在用户输入同时匹配

　　(2) 流程:

　　每输入一个字母：

　　沿字典树向下一层，

　　a)若可以顺利下行，则继续至结束，给出结果;

　　b)若该处不能匹配，纠错处理，给出拼写建议,继续至a);

　　算法:

　　1.在字典中查找单词

　　字典采用27叉树组织,每个节点对应一个字母,查找就是一个字母

　　一个字母匹配.算法时间就是单词的长度k.

　　2.纠错算法

　　情况:当输入的最后一个字母不能匹配时就提示出错,简化出错处理，动态提示可能 处理方法:

　　(a)当前字母前缺少了一个字母：搜索树上两层到当前的匹配作为建议;

　　(b)当前字母拼写错误：当前字母的键盘相邻作为提示;(只是简单的描述，可 以有更多的)

　　根据分析字典特征和用户单词已输入部分选择(a),(b)处理

　　复杂性分析：影响算法的效率主要是字典的实现与纠错处理

　　(a)字典的实现已有成熟的算法，改进不大，也不会成为瓶颈;

　　(b)纠错策略要简单有效 ,如前述情况，是线性复杂度;