笔试面试

百度笔经分享(一)

如下内容是一位网友参加百度笔试后,写下的笔经,希望能帮助后来人。
编程:

用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);

大家都在看