![中国人才网](http://static.cnrencai.com/img/cn_logo2.jpg"){kind=logo}
答案是我自己做的，可能存在bug，欢迎讨论。
百度2010实习生招聘笔试题
A卷(共三道大题)
【请先阅读卷首的试卷说明，在A、B卷选择一套试卷作答，同时作答试卷无效】
第一题、简答题
1. 简要说明树的深度优先、广度优先遍历算法，及非递归实现的特点。
[cpp] view plaincopy //基本思路：用栈模拟递归过程
#include
#include
using namespace std;
struct Node
{
Node *left;
Node *right;
int value;
};
void iterator_bsf(Node *root)
{
stack
while(root || !stack.empty())
{
if(root)
{
cout << root->value << " ";
stack.push(root);
root = root->left;
}else{
root = stack.top()->right;
stack.pop();
}
}
}
2. 在处理磁盘数据时，需要首先将其读入内存才能进行处理。如果要读取的数据已经在内存中，则可以直接访问内存。通常来说内存是有限的，因此要读取新的数据时必须覆盖内存中一部分原有的数据。假设现在有n块同样大小的数据，内存一共可以容纳m块数据。现在给出一系列对这些数据的读取请求，要求它们必须按照给定的顺序被读取，同时要求读取磁盘的次数尽可能地少。请简述一个策略满足这样的要求。
[plain] view plaincopy 这里考察了数据库的相关知识
可以采用这样的策略：
1.对每个在内存中的数据块加一个标签，表明其最后被使用的时间。
2.每次要读数据时，如果该数据块在内存中，则直接从内存中读取该数据块，并更新该数据块的时间标签，如果该数据块不在内存中，则如果内存还有空间，就从数据库中读取该数据块，加入时间标签，如果内存没有空间，则从从数据库中读取该数据块，加入时间标签，并覆盖掉时间标签最早的那个内存块。
第二题、算法与程序设计
1.百度全体员工玩分组游戏，前面五分钟大家分头找队友，并将每个人找到的队友信息汇报给主持人，如果A和B是队友，B和C是队友，那么A和C也是队友;接着主持人不断地随机抽取两个人，希望判断二者是否为队友。请设计一个计算机程序辅助主持人判断两个人是否为队友，说明程序的关键算法，不需要代码实现。
例如：
<小明，小王>，<小军，小王>，<小丽，小李>是队友，那么小军和小明是队友，小军和小丽不是队友。
[plain] view plaincopy 思路来自： com123cc (感谢com123cc)
1.建立图模型开销太大，当然也可以，然后用深度优先找出所有的连通分支，当给定量个点(两个名字)，则查询这两个点是否在同一个连通分支中即可。
2.使用并查集：
1)将有好友关系(具有传递性)的所有元素看做等价类，放入一个集合中
2)当给定量个点(两个名字)，则查询这两个点是否在同一个集合中即可。
[cpp] view plaincopy //基本思路：并查集
#include
using namespace std;
const int N = 100;
int father[N];
void init(int n)
{
for(int i = 1; i <= n; i++)
father[i] = i;
}
int getfather(int v)
{
if(father[v] == v)
return v;
return getfather(father[v]);
}
void merge(int x, int y)
{
x = getfather(x);
y = getfather(y);
father[x] = y;
}
bool judge(int x,int y)
{
x = getfather(x);
y = getfather(y);
return x == y;
}
int main()
{
int n;
cin >> n;
init(n);
int x,y;
while(1)
{
cin >> x >> y;
if(x == 0)
break;
merge(x,y);
}
while(1)
{
cin >> x >> y;
cout << judge(x,y) << endl;
}
}
2.给定以下二叉树:
struct node_t
{
node_t *left, *right;
int value;
};
要求编写函数 node_t* foo(node_t *node, unsigned int m, unsigned int k);
输出以 node 为根的二叉树第 m 层的第 k 个节点值.
(level, k 均从 0 开始计数)
注意：
1) 此树不是完全二叉树;
2) 所谓的第K个节点，是本层中从左到右的第K个节点
[cpp] view plaincopy node_t* foo(node_t *node, unsigned int m, unsigned int k)
{
queue
if(node)
q.push(node);
while(!q.empty() && k)
{
queue
while(!q.empty())
{
temque.push(q.front());
q.pop();
}
while(!temque.empty())
{
node_t *tem = temque.front();
temque.pop();
if(tem->left)
q.push(tem->left);
if(tem->right)
q.push(tem->right);
}
k--;
}
if(k > 0)
return NULL;
while(!q.empty() && m)
{
q.pop();
m--;
}
if(m > 0)
return NULL;
return q.front();
}
第三题、系统设计题
百度打算开发一个投票系统，它提供创建、查看、参与和管理投票功能。用户创建一个投票时，有如下信息可知：创建者、标题、各选项内容、截止时间、可投票数。另外，该投票是否对所有用户可见继承于创建者的个性设置。查看一个投票时，除了显示上述信息外，还需要显示每个选项的投票数。在截止时间之前，用户可以参与投票。管理投票功能为创建者提供删除一个投票和调整进行中投票截止时间的功能。
预计该投票系统会很受用户欢迎，每天可望创建超过1万个投票。每天浏览次数达数百万，并且有约一百万人次参与投票。经验还表明，用户更喜欢新近的内容。
实习生小A针对上述需求，打算用数据库来实现这个投票系统，他给出了数据库的表设计如下：
user_info：
|
uid |
name |
… |
visible |
|
1 |
“Alex Wang” |
… |
1 (all) |
|
2 |
“Jeff Li” |
… |
0 (self) |
vote_info：
|
vid |
uid |
title |
options |
counts |
close_time |
max |
visible |
|
1 |
1 |
“Do you like Lady Gaga?” |
“Yes; No; Who?” |
“4; 2; 1” |
1339071276 |
1 |
1 |
|
2 |
1 |
“Who’s the best forward?” |
“Messi; Ronaldo; Droba; Millito” |
“912; 654; 400; 301” |
1339076234 |
1 |
1 |
(红色为主键)
问题：
1、小A的设计存在什么问题，如何改善?
2、如果想增加一个功能，即每个用户对每个投票只能投一次。如何设计?
3、系统运行了较长一段时间之后，用户反馈使用中速度变慢。请分析可能的原因，并提出解决办法。
4、请完整给出新系统下各功能的实现流程。涉及数据库查询的，请给出SQL语句。
B卷(共三道大题)
【请先阅读卷首的试卷说明，在A、B卷选择一套试卷作答，同时作答试卷无效】
第一题、算法和程序设计题
1、请编写函数foo(int x, int y, int n)计算：随机生成x个大小为[1,y]的正整数，它们的和为n的概率是多少?语言仅限于PHP、C/C++、Java中的一种。
2、设计函数，输入为一个字符串，里边包含中文、英文、数字等字符，编码为GBK。中文字符的编码规则假定为：双字节组成，高字节大于0x80，低字节任意。
a) 用常用语言(c/c++/php/java)编写函数，实现功能为：按顺序提取输入文本中的中文字符，形成新的文本串返回调用者。
b) 如果调用者有时希望得到输入串的全中文内容，有时希望得到英文内容，那么该函数应如何设计。
c) 如果调用者希望获取输入串中包含中文、英文、数字这三种字符中的一种或多种的需求不定时，函数应如何设计。
3、有一个图书馆系统，含有Book和BookMaster两个类。Book可以用来设置书的属性(如title)，BookMaster每天做的事情就是根据上级的要求重设设定某些书的title，以增加借阅
者的注意力，让更多的人对书有新的兴趣。
有一天，上级需要BookMaster在setTitle的操作之前都要在日志中记录一条log。但不幸的是由于一些很特别的原因，没有办法去修改Book类，无法在Book类的setTitle()方法
中增加记录log的操作。更不幸的是上级不信任BookMaster自己的统计结果，使BookMaster不能在做setTitle()之前自己做log记录。
请问如何做才能达到目标，请写出必要的实现代码。
相关类定义如下：
public interfaceBook {
public voidsetTitle(String title);
public StringgetTitle();
}
public classBookException extends Exception {
publicBookException() {
}
}
public classBookImpl implements Book {
private Stringtitle;
public voidsetTitle(String title) {
this.title =title;
}
public StringgetTitle() {
returnthis.title;
}
}
public classBookMaster {
public staticvoid main(String[] args) {
Book book =new BookImpl();
out.println("set a book’s title today"); //不能添加这行语句，因为上级不信任BookMaster自己的统计结果
book.setTitle("I feel good.");
out.println(book.getTitle());
}
}
注：题目中所提供类的定义为Java实现，但您可以根据您的喜好自由选择其它语言完成题目要求。
第二题、简答题
1、网站如何维护用户的登录状态?百度知道、百度贴吧、百度百科三个网站域名不同，但同在.baidu.com主域下，它们之间如何共享用户登录状态?如果两个网站域名也不在一个主域下，例如www.baidu.com和www.qiyi.com，那么要如何共享用户登录状态?
要求：请尽量提供多种方案并分析各种方案的优劣。
2、在炎炎夏日，你十分口渴，想要买一瓶冰汽水，商店中有三瓶汽水供你选择(如ABC)，其中只有一瓶是冰过的。当你选定了其中的某一瓶后(设为A)，店员摸了下剩余两瓶中的一瓶(设为B)，并告诉你B不是冰的，此时你会将你的选择变更为剩余的那瓶嘛(C)?请详述你的理由?
3、TCP服务器在启动时，需要经过socket、bind、listen和accept四个步骤。
一个单进程的服务器的伪代码如下：
01. listen_fd =socket(TCP);
02. bind(listen_fd,my_addr);
03.listen(listen_fd, backlog);
04.
05. while(true)
06. {
07. client_fd = accept(listen_fd);
08. read(client_fd, request);
09. response = process(request);
10. write(client_fd, response);
11. close(client_fd);
12. }
某客户端的伪代码如下：
13. fd =connect(server_addr);
14. write(fd,request);
15. read(fd,response);
16.display(response);
17. close(fd);
假设服务器在04行执行了sleep(1000000)：
问题1：请简介服务器四个步骤的意义或作用是什么?
问题2：当1个客户端访问该服务器时，客户端执行到哪行会失败?会发生阻塞吗?为什么?
问题3：当50个客户端从50台机器几乎同时访问该服务器时，各个客户端的反应有差别吗?为什么?(注：忽略防火墙因素)
第三题、系统设计题
1、假设系统里有很多模板文件，每个模板文件都有一个唯一的文件名，其内容是一个长字符串，其中包含很多通过$...$方式标记起来的模板变量，如：
my name is $spname$,i’m $spage$ years old ...
其中spname,spage就是我们所谓的模板变量，请设计一个简单高效的模板解析系统，要求上游模块向该系统提供一个模板文件名和一个模板变量值字典时，
系统能够返回经过模板变量解析后的文本内容，例如：
假设模板文件A.tpl的内容为：
my name is $spname$,i’m $spage$ years old ...
提供的模板变量值字典dict为：
array(’spname’ =>’robin928’, ’spage’ => ’29’)，
则解析后的文本内容应该为：
my name is robin928,i’m 29 years old ...
(访问字典时可以通过dict[’spname’]访问到模板变量spname的参数值)
2、目前最流行的, 被称为微革命的互联网应用Twitter中, 人民可以在Twitter中互相关注, 被关注的人发出的每一条微型博客(一般都在140字以内), 都会被关注他的人看到. 而一个人可能被几万,几十万, 甚至上百万的人关注; 当然, 理论上, 一个人也可以关注几万,几十万,甚至上百万的人.
1) 请设计出这样的一个系统,并详细说明你的设计.
2) 请指出你设计中的缺点, 并给出改进后的设计.
3) 请评述你的最终设计的优点和缺点.
· 您可先离线完成所有答案，再把整份答案内容剪贴到这里;所有内容都将以.txt文件格式保存。
· 如果您长时间未进行任何操作，答题页面可能会超时失效;若失效请重新登录，以防止提交失败。
· 请务必在笔试时间结束前提交您的答案，以保证我们能及时处理。
· 答案一旦提交成功，则您的笔试结束，您将不能继续提交答案。
答题区(请在下边文本区域填写答案)
答案附件:(500K以内，可以为doc,zip,pdf,jpg文件)
?2009 Baidu 使用百度前必读
B卷
第一题、算法和程序设计题
2(a)读取中文
public static String getChinese(String src)throws UnsupportedEncodingException {
Stringdesc="";
for(int i = 0; i < src.length(); i++) {
charch=src.charAt(i);
byte[]buf=(ch+"").getBytes("GBK");
if(buf.length>1){
desc+=ch;
}
}
returndesc;
}
2(b)读取中文或英文
public class GetPart {
publicstatic final int CHINESE=1;
publicstatic final int ENGLISH=2;
/**
* @param src
* @param type 当type为CHINESE,得到中文,当type为ENGLISH时,得到英文
* @return
* @throws UnsupportedEncodingException
*/
publicstatic String getPart(String src,int type)throws UnsupportedEncodingException{
if(type==CHINESE){
returndoGetChinese(src);
}elseif(type==ENGLISH){
returndoGetEnglish(src);
}else{
thrownew IllegalArgumentException("参数type应该为1,2,3");
}
}
privatestatic String doGetEnglish(String src) throws UnsupportedEncodingException {
Stringdesc="";
for(int i = 0; i < src.length(); i++) {
charch=src.charAt(i);
byte[]buf=(ch+"").getBytes("GBK");
if(buf.length==1&& Character.isLetter(ch)){
desc+=ch;
}
}
returndesc;
}
privatestatic String doGetChinese(String src) throws UnsupportedEncodingException {
Stringdesc="";
for(int i = 0; i < src.length(); i++) {
charch=src.charAt(i);
byte[]buf=(ch+"").getBytes("GBK");
if(buf.length>1){
desc+=ch;
}
}
returndesc;
}
publicstatic void main(String[] args) throws UnsupportedEncodingException {
System.out.println(getPart("123你好ok",ENGLISH));
}
}
2(c)可以同时读取任意的文本
public class GetPart {
publicstatic final int CHINESE=0x1;
publicstatic final int ENGLISH=0x2;
publicstatic final int DIGIT=0x4;
/**
* @param src
* @param type 当type为CHINESE,得到中文,当type为ENGLISH时,得到英文
* @return
* @throws UnsupportedEncodingException
*/
publicstatic Result getPart(String src,int type)throws UnsupportedEncodingException{
Resultresult=new Result();
if((type& CHINESE) == CHINESE){
result.setChinese(doGetChinese(src));
}
if((type& ENGLISH) == ENGLISH){
result.setEnglish(doGetEnglish(src));
}
if((type& DIGIT) == DIGIT){
result.setDigit(doGetDigit(src));
}
returnresult;
}
privatestatic String doGetDigit(String src) throws UnsupportedEncodingException {
Stringdesc="";
for(int i = 0; i < src.length(); i++) {
charch=src.charAt(i);
byte[]buf=(ch+"").getBytes("GBK");
if(buf.length==1&& Character.isDigit(ch)){
desc+=ch;
}
}
returndesc;
}
privatestatic String doGetEnglish(String src) throws UnsupportedEncodingException {
Stringdesc="";
for(int i = 0; i < src.length(); i++) {
charch=src.charAt(i);
byte[]buf=(ch+"").getBytes("GBK");
if(buf.length==1&& Character.isLetter(ch)){
desc+=ch;
}
}
returndesc;
}
privatestatic String doGetChinese(String src) throws UnsupportedEncodingException {
Stringdesc="";
for(int i = 0; i < src.length(); i++) {
charch=src.charAt(i);
byte[]buf=(ch+"").getBytes("GBK");
if(buf.length>1){
desc+=ch;
}
}
returndesc;
}
publicstatic void main(String[] args) throws UnsupportedEncodingException {
Resultresult=getPart("123你好ok",CHINESE|ENGLISH|DIGIT);
System.out.println(result.getChinese());
System.out.println(result.getEnglish());
System.out.println(result.getDigit());
}
}
public class Result {
privateString chinese;
privateString english;
privateString digit;
publicResult() {
}
publicString getChinese() {
returnchinese;
}
publicvoid setChinese(String chinese) {
this.chinese= chinese;
}
publicString getEnglish() {
returnenglish;
}
publicvoid setEnglish(String english) {
this.english= english;
}
publicString getDigit() {
returndigit;
}
publicvoid setDigit(String digit) {
this.digit= digit;
}
}
3.
答:很多方法能解决这个问题.第一:用动态代理为Book生成个代理.
第二:用设计模式的代理设计模式完成.
第三:用spring的aop.
这里我们选用设计模式的方式:
class BookProxy implements Book{
privateBook target;
publicBookProxy(Book target) {
this.target= target;
}
publicString getTitle() {
returntarget.getTitle();
}
publicvoid setTitle(String title) {
System.out.println("seta book’s title today");//增加的日志信息
target.setTitle(title);
}
}
class BookMaster {
publicstatic void main(String[] args) {
Bookbook = new BookImpl();
book=newBookProxy(book);
book.setTitle("Ifeel good.");
}
}
第二题、简答题
1。网站如何维护用户的登录状态
答:有以下几种方式:
(1):如果在同一域下,可以用cookie共享方式实现.
在服务器把cookie信息写到response时,需要加密.
当服务器读取cookie时,需要解密.
(2)如果在不同的域,可用一个服务器群集来存放用户的登录信息.
当需要session信息,直接到服务器群集去取得.
2。在炎炎夏日，你十分口渴，想要买一瓶冰汽水此时你会将你的选择变更为剩余的那瓶嘛(C)?请详述你的理由?
答:若A已经是冰的，那就不用选择C;若A不是冰的，并且店员已经确认B不是冰的，所以只有C是冰的。
3。
问题1：请简介服务器四个步骤的意义或作用是什么?
答:socket是建立套接字.
bind是让建立的套接字指定到具体的网络接口(如果一个机器有多个网络接口)和
端口号.
listen:监听客户端的请求
accept:如果有请求到来,accept返回一个客户端套接字.此时可以通信了.
问题3：当50个客户端从50台机器几乎同时访问该服务器时，各个客户端的反应有差别吗?为什么?(注：忽略防火墙因素)
答:有差别,因为没有用多个线程或者多进程技术,那么50个请求会放在操作系统的队列里面.
每一次只能处理一个请求,1,2，...,50等待时间各不相同.也许后面的会因为超时重传.
建议换成多线程技术来处理,也可以用非阻塞IO来处理.那么用户的体验没有那么差.
第三题、系统设计题
1。模板解析
答:因为模板文件的内容比较长,不能用正则表达式,这样的效率很低.
因为模板变量有明确的标志${}.那么一遍全文查找就可以了.遇到${,就开始记录便利,
遇到}就读取了变量var,那么查字典dict['var'],就能得到其值,然后填充在里面.
特别需要说明:字典用散列表建立,这样效率很高.
伪代码:
public class TemplateUtil {
/**字典*/
privatefinal static Map
static{
//初始化字典
}
/**
* 替换模板变量
* @param source
* @return
*/
publicstatic String replace(String source){
StringBuffersb=new StringBuffer();
for(int i = 0; i < source.length(); i++) {
charch=source.charAt(i);
if(ch=='$'&&(i+1)
i+=2;
Stringvar="";
while(i
var+=source.charAt(i);
i++;
}
sb.append(dict.get(var));
}else{
sb.append(ch);
}
}
returnsb.toString();
}
}
2。设计Twitter
答:
(1)设计.
这个系统中有两张重要数据库表:account,attention_account(当然还有其他的表)
account是用户表,而attention_account记录关注用户的用户列表.比如张三有李四和王五关注,
account(id,name,password)
attention_account(id,attention_id)--id为用户id,比如zhangsan,而attention_id为关注id用户的用户id,比如lisi
每个用户都可以订阅自己感兴趣的用户,
当某个用户每发布一篇文章时,都通知关注他的用户.
这是典型的发布订阅模式.
(2)缺点:发布订阅本来是一种比较好的解决方式,但是用户必须登录到Twitter系统才能看到自己感兴趣的信息.
所以在(1)中如果采取B/s模式的话,用户很难实时的看到自己感兴趣的信息.所以如果可以,建议在提供B/s模式的同时,
也提供一个可选的GUI客户端,当用户每次登录操作系统的时候,自动启动GUI客户端.这样实时性更好.
(3)评价:这个系统的优点是采用发布订阅方式,能够在用户发布信息的时候及时通知对其感兴趣的用户.难点是如何让用户实时的读取自己感兴趣的文章.