百度技术研发笔试题目.docx
《百度技术研发笔试题目.docx》由会员分享，可在线阅读，更多相关《百度技术研发笔试题目.docx（12页珍藏版）》请在冰点文库上搜索。
XX技术研发笔试题目
XX技术研发笔试题目
/*XX面试题
*有一根27厘米细木杆，在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。
*木杆很细，不能同步通过一只蚂蚁。
开始时，蚂蚁头朝左还是朝右是任意，它们只会朝前走或调头，
*但不会后退。
当任意两只蚂蚁碰头时，两只蚂蚁会同步调头朝反方向走。
假设蚂蚁们每秒钟可以走一厘米距离。
*编写程序，求所有蚂蚁都离开木杆最小时间和最大时间。
*
*
*分析:
题目中蚂蚁只也许相遇在整数点,不可以相遇在其他点,例如3.5cm处之类,也就是可以让每只蚂蚁走1秒,然后
*查看与否有相遇即可.
*
*这样我程序实现思路就是,初始化5只蚂蚁,让每只蚂蚁走1秒,然后看与否有相遇,如果有则做相应解决.当每只蚂蚁都
*走出木杆时,我就记录当前时间.这样就可以得到当前状态状况下,需要多久可以走出木杆,然后遍历所有状态则可以得到所有也许.
*/
packageXX;
publicclassAnt{
/*
*step表达蚂蚁每一种单位时间所走长度
*/
privatefinalstaticintstep=1;
/*
*position表达蚂蚁所处初始位置
*/
privateintposition;
/*
*direction表达蚂蚁迈进方向，如果为1表达向27厘米方向走，如果为－1，则表达往0方向走。
*/
Privateintdirection=1;
/*
*此函数运营一次，表达蚂蚁迈进一种单位时间，如果已经走下木杆则会抛出异常
*/
publicvoidwalk（）{
if（isOut（））{
thrownewRuntimeException（"theantisout"）;
}
position=position+this.direction*step;
};
/**
*检查蚂蚁与否已经走出木杆，如果走出返回true
*
*/
publicbooleanisOut（）{
returnposition<=0||position>=27;
}
/**
*检查此蚂蚁与否已经遇到此外一只蚂蚁
*@paramant
*@return如果遇到返回true
*/
publicbooleanisEncounter（Antant）{
returnant.position==this.position;
}
/**
*变化蚂蚁迈进方向
*/
publicvoidchangeDistation（）{
direction=-1*direction;
}
/**
*构造函数,设立蚂蚁初始迈进方向,和初始位置
*@paramposition
*@paramdirection
*/
publicAnt（intposition，intdirection）{
this.position=position;
if（direction!
=1）{
this.direction=-1;//方向设立初始位置,例如为0时,也将其设立为1.这样可以以便背面解决
}else{
this.direction=1;
}
}
}
/////////////////////////////////////////////////////////
packageXX;
publicclassController{
publicstaticvoidmain（String[]args）{
inttime=0;
for（inti=0；i<32；i++）{
Ant[]antArray=getAntList（getPoistions（），getDirections（i））;
while（!
isAllOut（antArray））{
for（Antant：
antArray）{
if（!
ant.isOut（））{
ant.walk（）;
}
}
time++;
//查看与否有已经相遇Ant,如果有则更改其迈进方向
dealEncounter（antArray）;
}
System.out.println（time）;
//将时间归0,这样可以重新设立条件,再次得到所有走完所需要时间.
time=0;
}
}
/**
*这个函数算法很乱，但暂时能解决问题
*
*@paramlist
*/
publicstaticvoiddealEncounter（Ant[]antArray）{
intnum_ant=antArray.length;
for（intj=0；jfor（intk=j+1；kif（antArray[j].isEncounter（antArray[k]））{
antArray[j].changeDistation（）;
antArray[k].changeDistation（）;
}
}
}
}
/**
*由于有5只Ant，因此组合之后有32种组合.刚好用5位二进制来表达,如果为0则表达Ant往0方向走如果为1,则表达往27方向走
*
*注:
在通过Ant构造函数设立初始值时,通过过滤把0修改成了-1.
*/
publicstaticint[]getDirections（intseed）{
intresult[]=newint[5];
result[0]=seed%2;
result[1]=seed/2%2;
result[2]=seed/4%2;
result[3]=seed/8%2;
result[4]=seed/16%2;
System.out.println（"directionsis"+result[0]+"|"+result[1]+"|"
+result[2]+"|"+result[3]+"|"+result[4]）;
returnresult;
}
/**
*批量设立Ant初始位置,这样设立不是十分必要,可以直接在代码中设立
*
*@return
*/
publicstaticint[]getPoistions（）{
returnnewint[]{3，7，11，17，23};
}
/**
*获得设立好初始值5只Ant
*
*@parampositions
*@paramdirections
*@return
*/
publicstaticAnt[]getAntList（int[]positions，int[]directions）{
Antant3=newAnt（positions[0]，directions[0]）;
Antant7=newAnt（positions[1]，directions[1]）;
Antant11=newAnt（positions[2]，directions[2]）;
Antant17=newAnt（positions[3]，directions[3]）;
Antant23=newAnt（positions[4]，directions[4]）;
returnnewAnt[]{ant3，ant7，ant11，ant17，ant23};
}
/**
*判断与否所有Ant都已经走出了木杆,也就是设立退出条件
*
*@paramantArray
*@return
*/
publicstaticbooleanisAllOut（Ant[]antArray）{
for（Antant：
antArray）{
if（ant.isOut（）==false）{
returnfalse;
}
}
returntrue;
}
}
编程：
用C语言实现一种revert函数，它功能是将输入字符串在原串上倒序后返回。
2编程：
用C语言实现函数void*memmove（void*dest,constvoid*src,size_tn）。
memmove
函数功能是拷贝src所指内存内容前n个字节
到dest所指地址上。
3英文拼写纠错：
在顾客输入英文单词时，经常发生错误，咱们需要对其进行纠错。
假设已有一种包
含了对的英文单词词典，请你设计一种拼写纠错
程序。
（1）请描述你解决这个问题思路；
（2）请给出重要解决流程，算法，以及算法复杂度；
（3）请描述也许改进（改进方向如效果，性能等等，这是一种开放问题）。
4寻找热门查询：
搜索引擎会通过日记文献把顾客每次检索使用所有检索串都记录下来，每个查询串
长度为1-255字节。
假设当前有一千万个记录，
这些查询串重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个
。
一种查询串重复度越高，阐明查询它顾客越多，
也就是越热门。
请你记录最热门10个查询串，规定使用内存不能超过1G。
（1）请描述你解决这个问题思路；
（2）请给出重要解决流程，算法，以及算法复杂度。
5集合合并：
给定一种字符串集合，格式如：
{aaabbbccc}，{bbbddd}，{eeefff}，{ggg}，{dddhhh}
规定将其中交集不为空集合合并，规定合并完毕后集合之间无交集，例如上例应
输出
{aaabbbcccdddhhh}，{eeefff}，{ggg}
（1）请描述你解决这个问题思路；
（2）请给出重要解决流程，算法，以及算法复杂度
（3）请描述也许改进（改进方向如效果，性能等等，这是一种开放问题）。
////////////////////////////////1
1题
char*revert（char*str）
{
intn=strlen（str）;
inti=0;
charc;
for（i=0;i
{
c=str;
str=str[n-i];
str[n-i]=c;
}
returnstr;
}
///////////////////////////////////
2题
void*memmove（void*dest,constvoid*src,size_tn）
{
assert（（dest!
=0）&&（src!
=0））;
char*temp=（char*）dest;
char*ss=（char*）src;
inti=0;
for（;i{
*temp++=*ss++;
}
returntemp;
}
/////////////////////////////////////////////////
3题
（1）思路：
字典以字母键树组织，在顾客输入同步匹配
（2）
流程:
每输入一种字母：
沿字典树向下一层，
a）若可以顺利下行，则继续至结束，给出成果；
b）若该处不能匹配，纠错解决，给出拼写建议,继续至a）；
算法:
1.在字典中查找单词
字典采用27叉树组织,每个节点相应一种字母,查找就是一种字母
一种字母匹配.算法时间就是单词长度k.
2.纠错算法
状况:
当输入最后一种字母不能匹配时就提示出错,简化出错解决，动态提示
也许解决办法:
（a）当前字母前缺少了一种字母：
搜索树上两层到当前匹配作为建议；
（b）当前字母拼写错误：
当前字母键盘相邻作为提示；（只是简朴描述，可
以有更多）
依照分析字典特性和顾客单词已输入某些选取（a）,（b）解决
复杂性分析：
影响算法效率重要是字典实现与纠错解决
（a）字典实现已有成熟算法，改进不大，也不会成为瓶颈；
（b）纠错方略要简朴有效,如前述状况，是线性复杂度；
（3）改进
方略选取最是重要，可以采用记录学习办法改进。
//////////////////////////////////////////////
4题
（1）思路：
用哈希做
（2）
一方面逐次读入查询串，算哈希值，保存在内存数组中，同步记录频度
（注意值与日记项相应关系）
选出前十频度，取出相应日记串，简朴但是了。
哈希设计是核心。
//////////////////////////////////////////////////
5题
（1）思路：
先将集合按照大小排列后,优先考虑小集合与否与大集合有交集。
有
就合并，如果小集合与所有其她集合都没有交集，则独立。
独立集合在下一轮比
较中不用考虑。
这样就可以尽量减少字符串比较次数。
当所有集合都独立时候，
就终结。
（2）解决流程：
1.将集合按照大小排序，构成集合合并待解决列表
2.选取最小集合，找出与之有交集集合，
如果有，合并之；
如果无，则与其他集合是独立集合，从待解决列表中删除。
3.重复直到待解决列表为空
算法：
1。
将集合按照大小从小到大排序,构成待解决集合列表。
2。
取出待解决集合列表中最小集合，对于集合每个元素，依次在其她集合中搜索
与否有此元素存在：
1>若存在，则将此小集合与大集合合并，并依照大小插入相应位置。
转3
。
2>若不存在，则在该集合中取下一种元素。
如果无下一种元素，即所有元素
都不存在于其她集合。
则表白此集合独立，从待解决集合列表中删除。
并加入成果集
合列表。
转3。
3。
如果待解决集合列表不为空，转2。
如果待解决集合列表为空，成功退出，则成果集合列表就是最后输出。
算法复杂度分析：
假设集合个数为n，最大集合元素为m
排序时间复杂度可以达到n*log（n）
然后对于元素在其她集合中查找，最坏状况下为（n-1）*m
查找一种集合与否与其她集合有交集最坏状况是m*m*（n-1）
合并时间复杂度不会超过查找集合有交集最坏状况。
因此最后最坏时间复杂度为O（m*m*n*n）
需要阐明是：
此算法平均时间复杂度会很低，由于无论是查找还是合并，都是处
于最坏状况概率很小，并且排序后优先用最小集合伙为判断与否独立对象，优先
与最大集合进行比较，这些都最大回避了最坏状况。
（3）也许改进：
一方面可以实现将每个集合里面字符串按照字典序进行排列，这样就可以将查找以及
合并效率增高。
此外，也许采用恰当数据构造也可以将查找以及合并等操作效率得到提高。
升级会员 