当前位置:爱博仁人力资源官网 >> 职业指导 >> 笔试指导:2007百度校园招聘笔试题(解答答案)

笔试指导:2007百度校园招聘笔试题(解答答案)

2009-04-09 10:28:00  来源:爱博仁人力资源信息中心  作者:未知  浏览46次 

Baidu面试笔试题 解答答案

专家回答:

第一题
   简评
   百度的主要业务是搜索,搜索的基本原理如下
  1.编写爬虫程序到互联网上抓取网页海量的网页。
  2.将抓取来的网页通过抽取,以一定的格式保存在能快速检索的文件系统中。
  3.把用户输入的字符串进行拆分成关键字去文件系统中查询并返回结果。
  由以上3点可见,字符串的分析,抽取在搜索引擎中的地位是何等重要。
  因此,百度的笔试面试题中,出现这样的题就变得理所当然了。

百度面试笔试题-2007百度校园招聘笔试题 解答答案
IT面试题-最全最新IT面试题集合
金山笔试题(2007年10月)
腾讯c/c++笔试题

C语言面试题-华为C语言面试题
CC++面试题集(最全的CC++试题集和答案)(续)
C++面试题集(最全的CC++试题集和答案)
IT外企c语言面试题-外企C语言笔试题
据说是阿尔卡特(中国)的CC++面试题目
华为笔试题 - 华为C/C++笔试题
金山笔试题-金山C++笔试题
Kingsoft金山笔试题- Kingsoft金山公司C/C++面试笔试题

Java面试题集-Java面试题,J2EE面试题集
J2EE面试题集(附答案)
Java常见面试题集--面试题全面综合(一)
Java常见面试题集--面试题全面综合(二)
Java面试题集(欢迎大家踊跃提供)

  以下是该题的java实现,代码如下:

import java.net.*;
import java.io.*;
import java.util.*;

/** * @author tzy * 在j2sdk1.4.2下测试通过 */

public class FileNameStat{
  private String srcPath;//要统计的文件路径
  private Map statMap;//用于统计的map
 
  public FileNameStat(String srcPath)
  {
     this.srcPath=srcPath;
     statMap=new TreeMap();
  }
 
  /*获得要统计的URL的文件名*/
  public String getFileName(String urlString)
  {
     URL url=null;
     String filePath=null;
     String fileName=null;
     try
     {
       url=new URL(urlString);
       filePath=url.getPath();
       int index=0;
       if ((index=filePath.lastIndexOf(\"/\"))!=-1)
       {
       fileName=filePath.substring(index+1);
       }
       else
       {
         fileName=\"\";
       }
     }
     catch(MalformedURLException e)
     {
     }
     return fileName;
  }
 
  /*统计指定文件名的个数*/
  public void stat(String filename)
  {
     Integer count=null;
     if(statMap.get(filename)!=null)
     {
       count=(Integer)statMap.get(filename);
       count=new Integer(count.intValue()+1);
     }
     else
     {
       count=new Integer(1);
     }
     statMap.put(filename,count);
  }
 
  /*统计的主方法*/
  public void start() throws FileNotFoundException,IOException
  {
     BufferedReader bfin=new BufferedReader(new FileReader(this.srcPath));
     String temp=null;
     while((temp=bfin.readLine())!=null)
     {
       stat(getFileName(temp));
     }
  }
 
  /*输出统计结果*/
  public void result()
  {
     Iterator it=statMap.entrySet().iterator();
     while(it.hasNext())
     {
       Map.Entry entry=(Map.Entry)(it.next());
       System.out.println((entry.getKey().equals(\"\")?\"空文件名\":entry.getKey()) + \"的个数是\" + entry.getValue());
     }
  }
 
  public static void main(String[] args) throws Exception
  {
     FileNameStat fns=new FileNameStat(\"src.txt\");//指定成待统计文件
     fns.start();
     fns.result();
  }
}


  第二题

  简评:

  这道题也与百度的业务有关,百度现在除了搜索外,还有贴吧,知道,博客等重要产品。  同时也在积极的探索社区化,包括前不久宣布进军电子商务领域,搜索之外的这些产品,其主要功能的实现主要是对数据库的操作。  因此,想进入百度,也需要对数据库有一定的认识。   实现思路及数据库设计:  1,该论坛主要有两个实体对象,用户和帖子;对于帖子对象,有一个问题:回复的帖子是否应该跟主题帖子存放在同一个表里?

  考虑到每天更新10万帖子,说明帖子数比较多,为了方便主题的呈现,我一般都把主题贴和回帖分别放在不同的表中,把主题贴和回帖分开可以提高查询效率(300万的访问量每天)。

  2,按照1中的思路,该论坛由两个对象(用户和帖子)变成三个实体对象,分别是用户,主题帖子,回复帖子;

  3,上述三个对象存在三个关系,分别是:

  用户--主题帖,一个用户可以发0个或多个帖子,一个帖子对应一个用户(一对多关系),

  主题帖--回复帖:一个主题有0个或多个回复帖子,一个回复帖子对应一个主题(一对多关系);

  用户--回复贴:一个用户可以回0个或多个帖,一个帖子对应一个用户(一对多关系)。

  还存在对回复贴的回复,这个考虑用fatherId来表示。

  4,由于三个关系 “用户--主题帖,主题帖--回复帖,用户--回复贴” 都是一对多关系,根据表设计一般原则,可以将这两个关系独立建立表,也可以不另外建表而将一对多的关系体现在实体表中;然而,表间的连接查询是非常耗资源的,所以应尽量减少表间连接,那么对三个关系不应该分别建表,而是把用户的id作为主题表和回帖表的外键,把主题贴id作为回帖表的外键。

  5,鉴于以上考虑,该论坛的三个表如下所示

  表名:t_user_info (用户信息表)

字段名   类型  缺省值  中文含义  约束   备注 
id   Int    用户编号   PRI  Auto_increment
Name   Varchar(30)     用户名    
Email   Varchar(50)        
Phone   Varchar(30)          
Addr  Varchar(200)        


  其他字段略,根据需要添加  表名:main_content_info (主题帖信息表)

字段名  类型   缺省值  中文含义  约束  备注
id  Int    贴编号  PRI  Auto_increment
Title  Varchar(200)    发帖标题    
Content  Text    发帖内容    
UserID   Int     用户编号    外键


  其他字段略,根据需要添加


  表名:sub_content_info (回复贴信息表)

字段名 类型   缺省值  中文含义 约束  备注 
id   Int    贴编号  PRI  Auto_increment
Title  Varchar(200)    发帖标题    
Content   Text    发帖内容    
UserID  Int    用户编号    外键
FatherID  Int    父编号    
MainID  Int    主题帖编号    外键


  其他字段略,根据需要添加

  6,符合范式分析:

  上述表中每个字段不可再分,首先满足1NF;

  然后数据库表中的每个实例或行都是可以被惟一地区分(id),不存在部分依赖,因此满足2NF;

  t_user_info (用户信息表)和main_content_info (主题帖信息表)不存在任何传递依赖,至少属于BCNF;

  但是sub_content_info (回复贴信息表)不满足3NF,因为存在如下传递依赖:id-->FatherID,FatherID-->MainID。

  范式并不是越高越好,sub_content_info表只满足2NF却更有效率,也是当今论坛较主流的设计。

  第三题

  简评:

  如何对海量数据进行快速检索,这是搜索引擎的必需考虑的问题。这又涉及到数据结构和算法。  因此,要想进入百度,就必须熟悉一些基本的算法和数据结构。   思路及解决方案如下:

  1: 设计用TRIE树实现关键词到其对应id的快速词典查找

  TRIE树的每一个节点为一个包含256个元素的数组,同时指针指向其下一级节点

  节点定义如下:

struct trienode
{
  int   id;
  struct trienode *child[256];
}TRIENODE;


  如果TRIE树的某个节点的指针为NULL,说明从跟节点到当前节点的路径构成文件B中的一个关键词,

  在其节点的id保存该关键词的id;如果指针不为NULL,则id对应为0或者一个无穷大的整数,标志从根节点

  到当前节点的路径不是一个完整的关键词。

  将关键词转化为二进制无符号char型数组,即对于汉字等双字节字符视为两个无符号char型整数,

  每个元素的取值范围在0到255之间。

 

  2:生成文件b的TRIE树

  步骤1:依次读取文件b的每一行,对每一行执行步骤2到步骤5

  步骤2:读取关键词id和关键词,令为key

  步骤3:依次读取key的每一个字符,对每一个字符,执行步骤4;

  步骤4:如果该字符对应的指针为NULL,则创建其儿子节点;

  步骤5:为当前节点的对应字符id置为关键词id

  3:根据A文件生成C文件

  步骤1:依次读取文件A的每一行,对每一行执行步骤2到步骤5

  步骤2:分别获取当前行关键词、ip地址和时间

  步骤3:令关键词key=c1c2...cm,对c1到cm每个字符,执行步骤4

  步骤4:获取根节点的第c1个元素指针,转移到节点node1,

  根据node1的第c2个元素指针,转移到node2...

  根据nodem的第cm个元素,获取关键词的id

  步骤5:往文件c中写入一行数据,格式为关键词的id、ip地址和时间

  4:复杂度分析

  生成文件B的TRIE树过程时间复杂度为O(n*m),其中n为文件b行数,m为文件b关键词的最大长度。TRIE的空间复杂度为O(n*m),n和m含义同上,但由于实际应用中关键词之间可能会有很多前缀相同现象,所以实际耗费空间并不会很高。

  生成C文件的时间复杂度同样为O(n*m),n为文件a行数,m为文件a关键词的最大长度,因为有了TRIE树之后,给定一个关键词获得其id的时间复杂度为关键词长度。生成C文件的过程除了TRIE树空间外基本不需要太多额外的空间,空间复杂度为O(1),由于系统有1G的可用内存,TRIE占用的空间在几十兆到200M之间(与关键词集合有关),因此本方法完全可行。

 

 

 

责任编辑:wangling
标签:
爱博仁人力资源官网版权与免责声明:
1、本网转载其他媒体,目的在于传递信息,并不代表赞同其观点和对其真实性负责,本网不承担此类稿件侵权行为的连带责任。
2、如本网所转载稿件涉及版权等问题,请著作权或版权拥有机构致电或来函与本网联系,本网将在第一时间处理妥当。如有侵犯您的名誉权或其他权利,亦请及时通知本网。本网在审慎确认后,将即刻予以删除。
3、本网原创文章未经本网允许,私自转载者本网保留追究其版权责任的权利,转载请注明来源:爱博仁人力资源官网:http://www.abler.cn。
发表评论
网友评论仅供其表达个人看法,并不表明爱博仁人力资源官网同意其观点或证实其描述。

用户名: 密码: 验证码: 验证码


  • 发表评论须知:
  • 一、所发文章必须遵守《互联网电子公告服务管理规定》;
  • 二、严禁发布供求代理信息、公司介绍、产品信息等广告宣传信息;
  • 三、严禁恶意重复发帖;
  • 四、严禁对个人、实体、民族、国家等进行漫骂、污蔑、诽谤。
  • 频道推荐

    精彩推荐

    乞丐的觉醒:当改变自己时 一切都在改变 当你改变自己时,你会发现一切都改变了。 曾经有一个卖花的小姑娘在卖完大部分的花之后,发现天色己晚,所以决定早点回家。…[详细]

    房地产业新职业:验房师 10月27日,据中国房地产业协会消息,中国就业培训技术指导中心、中国房地产业协会正式启动《验房师国家职业标准》编制。 “…[详细]

    一位职场老前辈厉害总结的心得 如果这篇文章没有分享给你,那是我的错。 如果这篇文章分享给你了,你却没有读,继续走弯路的你不要怪我。 如果你看了这篇文章…[详细]

    在不冒犯对方的情况下 优雅地结束对话 您一定有过这样的经验,正当您在会议上与某人交谈,却从中意识到对话结束了!虽然你们都还在为延续对话而做出贡献,但却只是在运…[详细]

    厘清职场4种病症,3条界线,找到职场共感 拿不出成果的职场,常常欠缺的一个部分—那就是“共感”。 首先,我们将在这边一次公开,没有共感的职场中常常可以看到的4种病症…[详细]

    最新信息

    乞丐的觉醒:当改变自己时 一切都在改变当你改变自己时,你会发现一切都改变了。 曾经有一个卖花的小姑娘在卖完大部分的花之后,发现天色己晚,所以决定早点回家。…[详细]

    ·职业百科:系统交付工程师
    ·职业百科:仪器仪表工程师
    ·做人做事,顺序很重要
    ·凡事提前五分钟
    ·和领导出差,该聊点啥?
    ·闹离职的员工没走,不吭声的员工突然离职
    ·李佳琦一夜赚6亿,背后的高学历团队扎心……
    ·提升自己职业技能的方式,增加工作机会,提高成功的概率
    ·职场“名媛”

    关于我们 | 付款方式 | 会员协议 | 联系我们 | 合作代理 | 广告服务 | 隐私声明 | 法律声明 | 服务条款 | 友情链接 | 会员价格

    版权所有 舟山爱博仁人力资源咨询有限公司
    地址:浙江省舟山市定海区人民北路100号三楼(301)
    客服:0580-2086078 电话:0580-2526078 传真:0580-2262078