`
wangleide414
  • 浏览: 606549 次
  • 性别: Icon_minigender_1
  • 来自: 西安
社区版块
存档分类
最新评论

百度面试 01

 
阅读更多

 

百度技术研发笔试题目

 

 

/*百度面试题

 * 有一根27厘米的细木杆,在第3厘米、7厘米、11厘米、17厘米、23厘米这五个位置上各有一只蚂蚁。

 * 木杆很细,不能同时通过一只蚂蚁。开始 时,蚂蚁的头朝左还是朝右是任意的,它们只会朝前走或调头,

 * 但不会后退。当任意两只蚂蚁碰头时,两只蚂蚁会同时调头朝反方向走。假设蚂蚁们每秒钟可以走一厘米的距离。

 * 编写程序,求所有蚂蚁都离开木杆 的最小时间和最大时间。

 * 

 * 

 * 分析:题目中的蚂蚁只可能相遇在整数点,不可以相遇在其它点,比如3.5cm处之类的,也就是可以让每只蚂蚁走 1,然后

 * 查看是否有相遇的即可.

 * 

 * 这样我的程序实现思路就是,初始化5只蚂蚁,让每只蚂蚁走1,然后看是否有相遇的,如果有则做相应处理.当每只蚂蚁都

 * 走出木杆时,我就记录当前时间.这样就可以得到当前状态情况下,需要多久可以走出木杆,然后遍历所有状态则可以得到所胡

 * 可能.

 */

 

package baidu;

 

public class Ant {

 /*

  * step 表示蚂蚁每一个单位时间所走的长度

  */

 private final static int step = 1;

 

 /*

  * position表示蚂蚁所处的初始位置

  */

 private int position;

 

 /*

  * direction表示蚂蚁的前进方向,如果为1表示向27厘米的方向走, 如果为-1,则表示往0的方向走。

  */

 private int direction = 1;

 

 /*

  * 此函数运行一次,表示蚂蚁前进一个单位时间,如果已经走下木杆则会抛出异常

  */

 public void walk() {

  if (isOut()) {

   throw new RuntimeException("the ant is out");

  }

  position = position + this.direction * step;

 };

 

 

 /**

  * 检查蚂蚁是否已经走出木杆,如果走出返回true

  *

  */

 

 public boolean isOut() {

  return position <= 0 || position >= 27;

 }

 

 /**

  * 检查此蚂蚁是否已经遇到另外一只蚂蚁

  * @param ant

  * @return 如果遇到返回true

  */

 public boolean isEncounter(Ant ant) {

  return ant.position == this.position;

 }

 

 /**

  * 改变蚂蚁的前进方向

  */

 public void changeDistation() {

  direction = -1 * direction;

 }

 

 

 /**

  * 构造函数,设置蚂蚁的初始前进方向,和初始位置

  * @param position

  * @param direction

  */

 public Ant(int position, int direction) {

  this.position = position;

  if (direction != 1) {

   this.direction = -1;//方向设置初始位置,比如为0,也将其设置为1.这样可以方便后面的处理

  } else {

   this.direction = 1;

  }

 }

 

}

 

 

 

/////////////////////////////////////////////////////////

 

 

package baidu;

 

public class Controller {

 

 public static void main(String[] args) {

 

  int time = 0;

  for (int i = 0; i < 32; i++) {

   Ant[] antArray = getAntList(getPoistions(), getDirections(i));

   while (!isAllOut(antArray)) {

    for (Ant ant : antArray) {

     if (!ant.isOut()) {

      ant.walk();

     }

    }

    time++;

    // 查看是否有已经相遇的Ant,如果有则更改其前进方向

    dealEncounter(antArray);

   }

   System.out.println(time);

 

   // 将时间归0,这样可以重新设置条件,再次得到全部走完所需要的时间.

   time = 0;

  }

 

 }

 

 /**

  * 这个函数的算法很乱,但暂时能解决问题

  * 

  * @param list

  */

 public static void dealEncounter(Ant[] antArray) {

 

  int num_ant = antArray.length;

  for (int j = 0; j < num_ant; j++) {

   for (int k = j + 1; k < num_ant; k++) {

    if (antArray[j].isEncounter(antArray[k])) {

     antArray[j].changeDistation();

     antArray[k].changeDistation();

    }

   }

  }

 

 }

 

 /**

  * 因为有5Ant,所以组合之后有32种组合.刚好用5位二进制来表示,如果为0则表示Ant0的方向走 如果为1,则表示往27的方向走

  * 

  * :在通过Ant的构造函数设置初始值时,通过过滤把0修改成了-1.

  */

 public static int[] getDirections(int seed) {

  int result[] = new int[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("directions is " + result[0] + "|" + result[1] + "|"

    + result[2] + "|" + result[3] + "|" + result[4]);

 

  return result;

 

 }

 

 /**

  * 批量设置Ant的初始位置,这样设置不是十分必要,可以直接在代码中设置

  * 

  * @return

  */

 public static int[] getPoistions() {

  return new int[] { 3, 7, 11, 17, 23 };

 }

 

 /**

  * 取得设置好初始值的5Ant

  * 

  * @param positions

  * @param directions

  * @return

  */

 public static Ant[] getAntList(int[] positions, int[] directions) {

  Ant ant3 = new Ant(positions[0], directions[0]);

  Ant ant7 = new Ant(positions[1], directions[1]);

  Ant ant11 = new Ant(positions[2], directions[2]);

  Ant ant17 = new Ant(positions[3], directions[3]);

  Ant ant23 = new Ant(positions[4], directions[4]);

 

  return new Ant[] { ant3, ant7, ant11, ant17, ant23 };

 }

 

 /**

  * 判断是否所有的Ant都已经走出了木杆,也就是设置退出条件

  * 

  * @param antArray

  * @return

  */

 public static boolean isAllOut(Ant[] antArray) {

  for (Ant ant : antArray) {

   if (ant.isOut() == false) {

    return false;

   }

  }

  return true;

 }

}

 

 

 

 

 

 

 

 

 

编程: 
用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
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<N;I++)
{
*temp++=*ss++;
}
return temp;
}

/////////////////////////////////////////////////
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)可能的改进:
首先可以实现将每个集合里面的字符串按照字典序进行排列,这样就可以将查找以及
合并的效率增高。
另外,可能采取恰当的数据结构也可以将查找以及合并等操作的效率得到提高。

 

分享到:
评论

相关推荐

    百度面试题大收集算法

    【知识点详解】 ...以上各个知识点涵盖了算法、数据结构、操作系统、网络、数学和概率等多个IT领域,都是程序员在面试中可能会遇到的问题。理解和掌握这些知识点对于提升编程技能和解决实际问题具有重要意义。

    百度面试题集锦

    ### 百度面试题解析:求最短操作路径 #### 题目背景 题目来源于一份整理的百度面试题集,该题集被认为是一个很好的资源,对于正在寻找工作的求职者来说具有较高的参考价值。 #### 题目描述 题目要求实现一个函数,...

    2011年整理的百度笔试面试题集

    本文主要从百度概况、百度历史、百度主营业务和品牌、百度文化与价值观等几个方面,对百度进行了详细介绍。 百度概况部分,首先介绍了百度的创始人李彦宏和徐勇,他们于2000年在北京中关村创立了百度公司。百度的...

    百度持续交付项目组面试题

    ### 百度持续交付项目组面试题解析 #### 计算机基础 ##### 数据结构、算法 **代码实现快速排序** 快速排序是一种高效的排序算法,采用分治法策略来把一个序列分为较小和较大的两个子序列,然后递归地排序两个子...

    java面试题精讲视频MP4Java面试题01.面试的整体流程

    java面试题精讲视频MP4Java面试题01.面试的整体流程提取方式是百度网盘分享地址

    最新Java面试题视频网盘,Java面试题84集、java面试专属及面试必问课程

    java面试题01.面试的整体流程.mp4 │ Java面试题02.java的垮平台原理.mp4 │ Java面试题03.搭建一个java的开发环境.mp4 │ Java面试题04.java中int占几个字节.mp4 │ Java面试题05.java面向对象的特征.mp4 │ Java...

    Java全能学习面试手册——互联网企业面试真题.zip

    01 java面试——北京-百度-Java中级.pdf 02 java面试——北京-京东-Java中级.pdf 03 java面试——广州-唯品会-Java大数据开发工程师.pdf 04 java面试——杭州-阿里云-Java中级.pdf 05 java面试——杭州-蚂蚁金服-...

    企业公司软件测试面试笔试题集合 软件测试面试题

    01_企业面试试卷(综合).doc 01_企业面试试卷(综合)_参考答案.doc 04_企业面试试卷(测试基础).doc 04_企业面试试卷(测试基础)_参考答案.doc 500强公司面试的经典正确与错误回答对比!!! 看看你的弱点.doc ...

    JAVA开发高级工程师面试全集资料

    【2018年百度招聘】百度客户端产品设计师___产品经理___一面面经 JavaGuide-master 【2018年谷歌8招聘】腾讯产品笔试策划+经验 java面试题.rar 华为校园招聘笔试面试题合集.rar 牛客网剑指offer编程题.docx 01_笔记...

    互联网Java工程师面试突击教程.zip

    【互联网Java工程师面试突击教程】 本教程针对互联网Java工程师的面试需求,旨在帮助求职者全面了解和掌握Java技术栈的核心知识,以便在激烈的面试竞争中脱颖而出。Java作为一门广泛应用于互联网行业的编程语言,其...

    Java全能学习面试手册——阿里开发手册全套.zip

    Java全能学习面试手册——阿里开发手册全套.zip 01 阿里巴巴Java开发手册1.0.0(公开版).pdf 02 阿里巴巴Java开发手册1.1.0(正式版).pdf 03 阿里巴巴Java开发手册1.2.0(升级版).pdf 04 阿里巴巴Java开发手册...

    JAVAAndroid面试题讲解视频

    资源名称:JAVA Android面试题讲解视频资源目录:【】2012黑马程序员01_面试题【】2012黑马程序员02_面试题【】2012黑马程序员03_面试题【】2012黑马程序员04_面试题【】225ce844c6c817e9614d8f17ea70a640【】...

    2023年最新总结,阿里,腾讯,百度,美团,头条等技术面试题目,以及答案,专家出题人分析汇总

    常见面试问题及答案 ***************************************************************************** 01.阿里篇 02.华为篇 03.百度篇 04.腾讯篇 05.美团篇 06.头条篇 07.滴滴篇 08.京东篇 09.MySQL篇 10.Redis篇 ...

    JAVA面试全集资料开发高级工程师

    【2018年百度招聘】百度客户端产品设计师___产品经理___一面面经 JavaGuide-master 【2018年谷歌8招聘】腾讯产品笔试策划+经验 java面试题.rar 华为校园招聘笔试面试题合集.rar 牛客网剑指offer编程题.docx 01_笔记 ...

    大厂学院高阶班java并发编程面试视频资料(6.95G)

    01_前言.mp4 44.96M 02_线程的start方法.mp4 68.78M 03_进程线程管程.mp4 54.58M 04_用户线程和守护线程.mp4 26.81M 05_对Future的改进.mp4 114.57M 06_CompletableFuture.mp4 44.98M 07_CompletableFuture四...

    mysql高级视频教程百度云(2019).txt

    MySQL高级 MySQL高级_思维导图.pdf 63.MySQL高级_主从复制.avi 62.MySQL高级_行锁总结.avi 61.MySQL高级_如何锁定一行.avi 60.MySQL高级_间隙锁危害.avi ... 59.MySQL高级_索引... 01.MySQL高级_课程简介.avi

    2021互联网大厂Java架构师面试题突击视频教程

    上百节课详细讲解,需要的小伙伴自行百度网盘下载,链接见附件,永久有效。 课程介绍: 01_先来看一个互联网java工程师的招聘JD 02_互联网Java工程师面试突击训练课程第一季的内容说明 03_关于互联网Java工程师面试...

    2024最新Java从入门到精通 视频教程下载百度 下载 是3.zip

    因为太大存入百度云盘, 因为,描述字数有限制 下面目录只是部分 阶段01: Java语言基础(JDK17) 阶段02: MySQL数据库技术 阶段03: Web开发与实战 阶段04: Web框架核心技术 阶段05:项目—:权限管理系统 阶段06:...

    最新笔试面试常用算法收集打包

    2009/10/01 18:52 540,464 最长重复子串问题.mht 2009/10/03 16:28 86,677 最长重复字串 搜索墙.mht 2009/12/24 13:14 &lt;DIR&gt; 百度算法 2009/09/27 15:08 114,176 笔试题笔记.doc 2009/09/27 15:08 15,084,743 计算机...

    最新升级版Web全栈开发架构师就业班视频教程 全栈技术+自动化测试+算法+项目+面试

    ├─百度小姐姐-面试.mp4 (12)\12.微信公众号开发;目录中文件数:2个 ├─1.微信公众号开发.mp4 ├─2.对接公众号服务器端接口.mp4 (13)\13.前端安全;目录中文件数:2个 ├─1.网络安全-常见的web攻击.mp4 ├─2.

Global site tag (gtag.js) - Google Analytics