【www.gbppp.com--题目解答】
2009百度笔试题Zz
一、编程题（30分）
输入：N（整数）
输入：数据文件A.txt，不超过6条记录，字符串长度不超过15个字节
文件格式如下：
字符串\\t数字\\n
说明：
每行为1条记录；字符串中不含有\\t。
数字描述的是该字符串的出现概率，小于等于100的整数。
多条记录的出现概率之和为100，如果A.txt不满足该条件，程序则退出；
如果文件格式错误，程序也退出。
要求：
编写一个程序，输入为N（正整数），读入文件A.txt，按照字符串出现概率随机
地输出字符串，输出N条记录
例如：
输入文件A.txt
abc\\t20
a\\t30
de\\t50
输入为：10
即 abc有20%的概率输出，a有30%的概率输出，de有50%的概率输出，输出10条记
录
以下为一次输出的结果,多次输出的结果可能不相同。
abc
a
de
de
abc
de
a
de
a
de
二、算法题（35分）
题目描述：
设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
程序输入：n个数
程序输出：联接成的多位数
例如：
n=2时，2个整数32，321连接成的最小整数为：32132，
n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355
[题目要求]
1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算
法。
2. 给出算法的时间空间复杂度。
3. 证明你的算法。（非常重要）
三、系统设计题（35分）
在一个有1000万用户的系统中，设计一个推送(feed)系统。以下是一些预定义概念:
1、用户：在这个系统中，每个用户用一个递增的unsigned int来表示user id(简写为uid)；则uid的范围是从1到1000万的正整数。
2、好友：用户之间可以形成好友关系，好友是双向的；比如说uid为3和uid为4的两个用户可以互为好友。每个用户好友的上限是500个；用户之间的好友关系可以被解除
3、活动：每个用户只能发文章；文章可以被作者删除，其他人不能删除非自己发表的文章；每篇文章通过一个blogid表示。
4、feed：我们希望，每个用户可以看到他所有好友的活动列表，在这个简化的系统中就是所有好友的文章更新列表。
5、访问量要求：所有feed访问量每天在1亿量级；所有的blogid增加量每天在百万量级。
题目：请在以上限制条件下，设计一个高效的feed访问系统。
要求：
1、能够尽快的返回每个用户的好友feed列表，每个用户可以最多保留1000条feed；feed的展现按照时间倒排序，最新的在最前面
2、用户删除某篇文章后，被推出去的feed需要及时消失。即每个用户看到的好友feed都是未被删除的
3、尽可能高效
2010百度校园招聘笔试题
一、简答题
1. 简述树的深度优先遍历及广度优先遍历及其非递归实现的特点；
2. 找出以下程序中的bug：
#include <stdio.h>
#include <stdlib.h>
struct Record{
int a;
int b;
};
int create(struct Record *p, int num)
{
p = new struct Record[num];
if (!p)
return -1;
else
return 0;
}
int Test()
{
struct Record *p = NULL;
int i;
int num;
printf("0x%08x\n", p);
scanf("Input record num:%d", &num);
if (create(p, num) < 0)
return -1;
printf("0x%08x\n", p);
for (i = 0; i < num; i++) {
p[i].a = 0;
p[i].b = 0;
}
return 0;
}
int main(void)
{
Test();
getchar();
return 0;
}
#include <stdio.h>
#include <stdlib.h>
struct Record
{
int a;
int b;
};
int create(struct Record *&p, int num)
{
p=NULL;
p = new struct Record[num];
if (!p)
return -1;
else【百度笔试题目】
return 0;
}
int Test()
{
struct Record *p = NULL;
int i;
int num;
printf("0x%08x\n", p);
printf("Input record num:"); scanf("%d",&num);
if (create(p, num) < 0)
return -1;
printf("0x%08x\n", p);
for (i = 0; i < num; i++) {
p[i].a = 0;
p[i].b = 0;
}
delete []p;
return 0;
}
int main(void)
{
Test();
getchar();
return 0;
}
3. 有一台Mini计算机，内存大小为1K，CPU主频为1M（CPU状态每秒改变10的6次方次），问在这台计算机上可运行并且确定可以终止的程序的最长运行时间是多少？
给出思路及推理过程（可以做任何假设）。
二、算法设计
1. 某大型项目由n个组件N1, N2„„Nn构成，每个组件都可以独立编译，但是某些组件的编译依赖于其它组件（即某些组件只能在其它组件编译完成后才能编译），设计算法给出统计过程。
#include <iostream>
#define MAXN 505
#define MAXM MAXN*MAXN
struct edge
{
int v;
edge *mNext;
};
int in[MAXN];
int n,m;
edge E[MAXM];
int en;
edge *first[MAXN];
int cnt[MAXN][MAXN];
void insert(int u,int v)
{
E[en].v=v;
E[en].mNext=first[u];
first[u]=&E[en++];
}
void topo()
{
for(int i=1;i<=n;i++)
for(int u=1;u<=n;u++)
{
if(in[u]==0)
{
in[u]=-1;
printf("%d ",u);
for(edge *e=first[u];e;e=e->mNext)
in[e->v]--;
break;
}
}
}
int main()
{
freopen("c:/a.txt","r",stdin);
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(first,NULL,sizeof(first));
memset(cnt,0,sizeof(cnt));
memset(in,0,sizeof(in));
int u,v;
en=0;
for(int i=0;i<m;i++)
{
scanf("%d%d",&u,&v);
if(cnt[u][v]==0)
{
cnt[u][v]=1;
insert(u,v);
in[v]++;
}
}
topo();
printf("\n");
}
return 0;
}
2. 完成函数：
int maxnumstr(char *inputstr, char *outputstr)
函数功能：找出inputstr中的最长连续数字串存储到outputstr里并返回长度，如调用maxnumstr("123abc1234a", outputstr)后返回4且outputstr中为"1234"。
#include <iostream>
#define MAXN 1000
int maxnumstr(char *inputstr, char *outputstr)
{
if(inputstr==NULL || outputstr==NULL)
throw "Error NULL params";
if(*inputstr=='\0')
{
1：堆和栈的区别，什么时候用堆什么时候用栈？
2：树的深度优先搜索算法
按照某种条件往前试探搜索，如果前进中遭到失败（正如老鼠钻迷宫老鼠遇到死胡同）则退回头另选通路继续搜索，直到找到条件的目标为止。
3：广度优先搜索算法
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Prim最小生成树算法采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位址，彻底地搜索整张图，直到找到结果为止。
4：树的非递归实现
5：数据库事务的四大特性【百度笔试题目】
原子性atomic、一致性consistency、分离性isolation、持久性durability
◎事务的原子性指的是，事务中包含的程序作为数据库的逻辑工作单位，它所做的对数据修改操作要么全部执行，要么完全不执行。这种特性称为原子性。
◎事务的一致性指的是在一个事务执行之前和执行之后数据库都必须处于一致性状态。 ◎分离性指并发的事务是相互隔离的。即一个事务内部的操作及正在操作的数据必须封锁起来，不被其它企图进行修改的事务看到。
◎持久性意味着当系统或介质发生故障时，确保已提交事务的更新不能丢失。即一旦一个事务提交，DBMS保证它对数据库中数据的改变应该是永久性的，耐得住任何系统故障。持久性通过数据库备份和恢复来保证。
6：ASCII码--十进制（对应关系）
0--48 9--57
A--65 Z--90
a--97 z—122
十进制：decimal，简称：DEC
7：算法与程序设计题
#include <iostream>
using namespace std;
//该函数实现返回一个以“\0”结束的字符串中最长的数字串的长度，
//并把该数字子串的首地址赋给outputstr
//不能使用任何库函数或已经存在的函数，如strlen。
//例如：在字符串“abc123abcdef12345abcdefgh123456789”中，
//把该字符串的首地址赋给inputstr，函数返回，
//outputstr指向字符串“”的首地址。
int maxContinuNum(const char *inputstr,const char *outputstr)
{
}
int max=0,count=0; while(*inputstr!='\0') //如果字符串没有到末尾，继续循环 { } if(*inputstr=='\0') //特殊情况，最长字符串在末尾 { } cout<<"返回最大数字子串的首地址对应的数字："<<*outputstr<<endl; return max; max=count; outputstr=inputstr-count; //返回最大数字子串的首地址对应的数字 if(*inputstr>=49 && *inputstr<=57) //如果在统计范围内 { } else //如果在统计范围外 { } inputstr++; if(count>max) { } else { } count=0; max=count; outputstr=inputstr-count; //返回最大数字子串的首地址对应的数字 count=0; count++;
int main()
{
}
int max; char *str="abc123abcdef12345abcdefgh123456789"; cout<<"字符串“abc123abcdef12345abcdefgh123456789”中最长的数字串的长度为："<<max<<endl; max=maxContinuNum(str,str);
8：New Coke的一项失败营销方略
始于可口可乐与百事可乐之争的。这是商业史上的著名案例，很多人曾经从不同角度分析这个案例。而在blink书中，两种可乐在做产品比较时采取了错误的“切片”方法。百事在最初攻击可口时，曾经通过在大街上随即抽取人员作双盲测试，并发现大多数人认为百事可乐更
好喝，以此为证据说明百事的优点。可口也作了同样的测试，惊恐的发现事实确实如此。于是他们断定可口可乐必须在产品上改进，经过大量的投入，一种新的New Coke发布出来了。New Coke在做同样的双盲测试时，更多人认为New Coke比Pepsi好喝。当时的CEO郭思达在发布时说，这是可口可乐有史以来做的最有把握的一件事。可是，事实是，New Coke迅速被消费者抵制，最后可口可乐不得不重新推出原来的可口可乐并完全摒弃New Coke。
这种双盲测试是一种错误的切片方法，因为在做这种试验时，用户对每种饮料都只喝一小口，而不是像正常时一次喝一瓶。而当用户只喝一小口饮料时，大多数人会更喜欢更甜的那一种——虽然当他们喝一整瓶的时候会有不同的看法。书中又举了更多例子说明，所谓的用户测试并不是一种能够让你相信的结果，因为用户测试会被很多不同的因素所影响，包括包装、饮用方法。
9：链表和数组的优缺点？
链表：链表是一块不连续的动态空间，长度可变；链表需要按顺序检索节点，效率低； 链表的优点是可以快速插入和删除节点，大小动态分配，长度不固定。
链表不存在越界问题。
数组：数组是一快连续的空间，声明时长度就需要固定。
数组的优点是速度快，数据操作直接使用偏移地址。
数组有越界问题。
2008-9-24 百度电子科技大学网络工程师笔试题(第五套笔试题)
第一大题，共6小题，每题5分，共30分
1:什么是保留IP地址,请列举?为什么规定保留IP地址?
保留IP地址：1个A类地址 10.*.*.*；16个B类地址 172.16.*.*---172.31.*.*
256个C类地址 192.168.0.*---192.168.255.*；保留IP地址不会在internet网上出现，用于企业网络，A企业可以用,B企业也可以使用！
2:IPv4和IPv6的地址分别是多少？
IPv4的地址是32位，IPv6的地址是64位。
3:什么是访问控制列表?它的执行流程?
访问控制列表（ALC）实际上就是一系列允许和拒绝匹配准则的集合。总的一句话就是数据包与ALC中的一旦出现的匹配情况，就执行相应的操作，而此时对此数据包的检测就到此为止了，后面不管出现多少不匹配的情况将不作检测。
4:802.1Q协议实现什么功能?和ISL有何区别
5:端口镜像,链路汇聚的功能是什么,请用你熟悉的交换机写出它们的命名。
6:linux下解释: ip rule add from 192.168.3.112/32 [tos 0x10] table 2 pref 1500
第二大题，30分
你现在有一个文件，文件中顺序存有N个记录，R1,R2,...,RN,这些记录不是有序的，但是你知道一个整数M,
这些记录满足R1<R2<...<RM以及RM+1<RM+2<...RN.
1,设计一个算法或编写一个程序，将文件中的记录排序为R1',R2',...,RN',算法或程序读取文件的次数为O(N),不限内存使用，
2,设计一个算法或编写一个程序，将文件中的记录排序为R1',R2',...,RN',算法或程序读写文件的次数为O(N)，空间复杂度
为O(1)，亦即，你使用的内存大小和M,N均无关。
第三大题，每小题20分，共40分
1：在某些情况下，网络中会出现路由环路，请根据你的理解，说明可能出现路由环路的原理，并以你最熟悉
的路由协议，说明该路由协议采取了哪些措施避免路由环路。
2：如果用户向你申述上百度主页很慢，你会从哪些方面取分析这个问题，如何高效的分析并判断故障根源所在？
第四套题的第三大题的第一个
现在需要对2000台机器升级某个软件？已经有这个软件的最新代码，
1：你会选择用什么工具自动升级该软件？请给出具体步骤或方法？
2：为了便于后期的运维，如果让你设计一套软件部署方案，你会怎么设计？
1、请实现两棵树是否相等的比较，相等返回，否则返回其他值，并说明算法复杂度。
数据结构为：
typedef struct_TreeNode{
char c;
TreeNode *leftchild;
TreeNode *rightchild;
}TreeNode;
函数接口为：int CompTree(TreeNode* tree1,TreeNode* tree2);
注：A、B两棵树相等当且仅当Root->c==RootB-->c,而且A和B的左右子树相等或者左右互换相等。
2、写一段程序，找出数组中第k大小的数，输出数所在的位置。例如{2，4，3，4，7}中，第一大的数是7，位置在4。第二大、第三大的数都是4，位置在1、3随便输出哪一个均可。
函数接口为：int find_orderk(const int* narry,const int n,const int k)
2'、已知一个字串由GBK汉字和ansi编码的数字字母混合组成，编写c语言函数实现从中去掉所有ansi编码的字母和数字(包括大小写),要求在原字串上返回结果。
函数接口为：int filter_ansi(char* gbk_string)
注：汉字的GBK编码范围是0x8140-0xFEFE
百度笔试题
1）此题10分
对任意输入的正整数N，编写C程序求N!的尾部连续0的个数，并指出计算复杂度。如：18！＝6402373705728000，尾部连续0的个数是3。
（不用考虑数值超出计算机整数界限的问题）
2）此题10分
编写一个C语言函数，要求输入一个url，输出该url是首页、目录页或者其他url
如下形式叫做首页：
militia.info/
/
/
/Reality/
请注意：
a） url有可能带http头也有可能不带
b）动态url（即含有"？"的url）的一律不算目录页，如：
/utility/mailit.php?l=/activity/details/3135/
/utility/mailit.php?l=/activity/details/2449/
另：如果你会linux，请用linux下的grep命令实现第2题的功能（附加5分）。
3）此题40分
如果必须从网页中区分出一部分"重要网页"（例如在10亿中选8亿），比其他网页更值得展现给用户，请提出一种方案。
4）此题40分
假设有10亿网页已经被我们存下来，并提供如下信息：网页全文（即网页的源码）、全文长度、网页正文（即网页中提取的主体文字）、
一、算法设计
1、设rand（s，t）返回[s,t]之间的随机小数，利用该函数在一个半径为R的圆内找随机n个点，并给出时间复杂度分析。 思路：这个使用数学中的极坐标来解决，先调用[s1，t1]随机产生一个数r，归一化后乘以半径，得到R*（r-s1）/（t1-s1），然后在调用[s2，t2]随机产生一个数a，归一化后得到角度：360*（a-s2）/（t2-s2）
2、为分析用户行为，系统常需存储用户的一些query，但因query非常多，故系统不能全存，设系统每天只存m个query，现设计一个算法，对用户请求的query进行随机选择m个，请给一个方案，使得每个query被抽中的概率相等，并分析之，注意：不到最后一刻，并不知用户的总请求量。
思路：如果用户查询的数量小于m，那么直接就存起来。如果用户查询的数量大于m，假设为m+i，那么在1-----m+i之间随机产生一个数，如果选择的是前面m条查询进行存取，那么概率为m/（m+i），如果选择的是后面i条记录中的查询，那么用这个记录来替换前面m条查询记录的概率为m/（m+i）*（1-1/m）=(m-1)/(m+i)，当查询记录量很大的时候，m/（m+i）== (m-1)/(m+i)，所以每个query被抽中的概率是相等的。
3、C++ STL中vector的相关问题： （1）、调用push_back时，其内部的内存分配是如何进行的？ （2）、调用clear时，内部是如何具体实现的？若想将其内存释放，该如何操作？ vector的工作原理是系统预先分配一块CAPACITY大小的空间，当插入的数据超过这个空间的时候，这块空间会让某种方式扩展，但是你删除数据的时候，它却不会缩小。 vector为了防止大量分配连续内存的开销，保持一块默认的尺寸的内存，clear只是清数据了，未清内存，因为vector的capacity容量未变化，系统维护一个的默认值。 有什么方法可以释放掉vector中占用的全部内存呢?
标准的解决方法如下 template < class T >
void ClearVector( vector< T >& vt ) { vector< T > vtTemp; veTemp.swap( vt ); } 事实上，vector根本就不管内存，它只是负责向内存管理框架acquire/release内存，内存管理框架如果发现内存不够了，就malloc，但是当vector释放资源的时候(比如destruct), stl根本就不调用free以减少内存，因为内存分配在stl的底层：stl假定如果你需要更多的资源就代表你以后也可能需要这么多资源(你的list, hashmap也是用这些内存)，所以就没必要不停地malloc/free。如果是这个逻辑的话这可能是个trade-off 一般的STL内存管理器allocator都是用内存池来管理内存的，所以某个容器申请内存或释放内存都只是影响到内存池的剩余内存量，而不是真的把内存归还给系统。这样做一是为了避免内存碎片，二是提高了内存申请和释放的效率——不用每次都在系统内存里寻找一番。
二、系统设计
正常用户端每分钟最多发一个请求至服务端，服务端需做一个异常客户端行为的过滤系统，设服务器在某一刻收到客户端A的一个请求，则1分钟内的客户端任何其它请求都需要被过滤，现知每一客户端都有一个IPv6地址可作为其ID，客户端个数太多，以至于无法全部放到单台服务器的内存hash表中，现需简单设计一个系统，使用支持高效的过滤，可使用多台机器，但要求使用的机器越少越好，请将关键的设计和思想用图表和代码表现出来。
三、求一个全排列函数： 如p([1,2,3])输出： [123]、[132]、[213]、[231]、[321]、[312] 求一个组合函数。
方法1：依次从字符串中取出一个字符作为最终排列的第一个字符，对剩余字符组成的字符串生成全排列，最终结果为取出的字符和剩余子串全排列的组合。 优点：该方法易于理解，但无法移除重复的排列，如：s="ABA"，会生成两个“AAB”。 方法2：利用交换的思想，具体见实例，但该方法不如方法1容易理解。 我们以三个字符abc为例来分析一下求字符串排列的过程。首先我们固定第一个字符a，求后面两个字符bc的排列。当两个字符bc的排列求好之后，我们把第一个字符a和后面的b交换，得到bac，接着我们固定第一个字符b，求后面两个字符ac的排列。现在是把c放到第一位置的时候了。记住前面我们已经把原先的第一个字符a和后面的b做了交换，为了保证这次c仍然是和原先处在第一位置的a交换，我们在拿c和第一个字符交换之前，先要把b和a交换回来。在交换b和a之后，再拿c和处在第一位置的a进行交换，得到cba。我们再次固定第一个字符c，求后面两个字符b、a的排列。 既然我们已经知道怎么求三个字符的排列，那么固定第一个字符之后求后面两个字符的排列，就是典型的递归思路了。 基于前面的分析，我们可以得到如下的参考代码： 如p([1,2,3])输出： [1]、[2]、[3]、[1,2]、[2,3]、[1,3]、[1,2,3] 这两问可以用伪代码。
北京 产品设计 笔试
纯文科背景，很简单的互联网产品经验，报百度纯粹是志趣所在。 笔试题与大家分享，如果是真心喜欢互联网行业的同学肯定觉得题目很简单。
1. 选一个你熟悉的百度产品，针对用户体验提出改进意见。
2. 设计一个在线音乐播放器的界面并说明设计思路。
3. 设计几个指标衡量百度图片所搜的用户体验。
4. 有一个手机通讯软件的添加好友界面，评述优点和确定，平提出建议。
5. 冰箱通常带有照明灯，请说明这一设计的必要性和适用场景。以及微波炉是否需要这一功能？为什么？
2013年百度商业业务分析笔试题
一、推理题
1、 根据已有信息判断正误
All people love running
Some people love cook（类似，记不清了）
Some people look like their masters
判断下面几句话正误
比如 all people loving run love cook
People love run look like their masters 等
2、 有2只红袜子、20只黄袜子，31只蓝袜子，问抽几只袜子，能确保抽到两只颜色一样的？
3、 有50个红球，50个蓝球，两个罐子，随机抽取一个罐子，随机抽取一个球放入罐子，问如何能让抽到红球的概率最大？（所有球的进入罐子）在这样的设计下，球数应该增多还是减少？
4、 象棋中，如果最后只剩下了将和帅，有多少种状态是没有结果的？
5、 推理题
8个将军射猎，其中一个人射中了鹿，但是国王让大家猜是谁射中的，8个人每人一句话，国王说只有三个人说的是对的，问谁射中了鹿？如果五个人说的是对的，那么是谁射中的？
6、 切金子问题
15cm长的金子，每天给工人1cm，三刀，如何切？若是16cm可以么？
7、 一个女生想找三高男，高个子、高收入、高学历，A、B、C、D只有一个满足要求，给了几个条件：
（1） A和B收入一样
（2） C和D身高情况相反
（3） 三个高个子，两个高收入，一个高学历（记不太清了，大概类似条件）
问谁是三高男？
二、选答题
1、 给出一个SNS网站推荐好友功能的策略设计。
2、 移动互联网与PC互联网的异同，在商业流量变现的角度看两者的优劣势，那么搜索推广如何？
3、 一个研究者对于广告页面绿色对点击率影响的统计，第一页和第二页都显示绿色会增加点击率，但综合统计显示没有明显关系，请问是为什么？采用什么统计方法进行分析？
4、 公交IC卡的一个问题，它不只是一个金融工具，也可以提供很多用户数据。从公交站、广告商等角度看广告的投放？（没仔细看。。）
【面经】
百度系统工程师（基础网络）北京
有点小惊讶，三次面试竟然全部都是电话面试。而且三次面试都是技术面试。但是个人觉得百度的网络岗位技术面试跟其他的公司很不一样。
1.百度重视基础知识，一些类似于传统的三次握手肯定是必问
2.百度重视应用，经常是给你一个拓扑，围绕着拓扑询问。从某个知识点出发，但是又不拘泥于这个知识点，遗憾的是这一部分掌握的不是很好
3.百度比较人性化，问你一些问题的时候会事先征求你的意见，例如问路由协议的话他会提前问你，你觉得那一块掌握的比较好。我觉得这一块我回答的挺不错的。
4.百度重视与面试者之间的互动。同百度的老师们沟通交流时很愉快的一件事情，因为不像
其他公司搞的那么严谨，你在回答问题的时候有很多机会可以跟老师们沟通交流。有些方向你想歪了，面试官会温馨的提醒你。总之有点类似于学生跟老师沟通交流某个问题时候的感觉啊。
百度上海，开发测试，三面归来
一面：
预定时间是22号下午四点。 我回去东一把数据结构，西一把算法，都不知道复习什么好了。 因为知道百度刷人刷得挺狠的，之前同学面试笔试北京百度的时候，不少都尘沙折戟了。 第二天，心情沉重的过去了，结果三点多就轮到我了。 面我的是个很阳光清爽的GG。 开始让我自我介绍，说说学校的情况，以及简历上的实验室项目和实习项目。 然后他询问了一些感兴趣的部分，以及一些项目的细节，这些不在话下。
总体说来，一面问的东西蛮多的，也蛮全面的，好像一个小时二十多分钟，时间挺长的。包括一些常用的linux命令、网络编程（估计因为项目涉及，所以就问了）、指针、数组指针、C++内存分配、函数压栈、数据库等等。 大部分是我擅长的东西，自我感觉前面答得还不错，但是我回去之后核查了几个问题，发现有个内联函数的问题答得不太精确，难怪那位GG后来又问我宏定义的问题，好在宏定义上面没有弄错，估计那位GG以为我记得稍微模糊了点，所以放了我一马。 后面写了几个代码，如果平时在学校认真学，应该都没问题，没有传说中的那么恐怖，当然，也不排除我运气问题。 第一个是输出1-100中所有的素数； 第二个是链表反转 第三个是Y链表 可能因为第二个代码写得不太好，指针指来指去，把自己绕晕了，然后就有点紧张，再加上当时屋子里有好几对面试的，周围一直嗡嗡的响，后来那位GG可能看出来了我的状态了，就提示了几下，终于搞定。然后，又补问了第三个问题。 以为自己没戏了，挂在链表上了，回来路上就开始各种伤心，觉得链表逆序，那么经典基础的东西怎么可以不会呢，特别的自责，连地铁都坐过好多站。 没想到，晚上收到二面通知：22号三点。 兴奋又感激，看来那位GG看我前面回答的不错的份上，给了我第二次机会。 于是我把指针重点复习了一下，顺带着看了看二叉树部分，还扫了几眼B树，B+树之类的。 又临时抱佛脚的在网上找了半天的面经，有今年的，也有往年的。
二面： 忐忑过去二面。 二面到楼上，面试官先让自我介绍，然后问是一面还是二面（当天好像也有一面的人）。 我如实回答是二面。然后，因为是侧面坐的关系（一面是面对面），我看见他在电脑上调出我的资料，于是就进入了二面的正题。 第一个是循环指针的问题，幸亏我之前复习过一点，阿弥陀佛！ 第二个问题是树的遍历问题，也过关了。 然后就让写代码，输出一颗树的所有邻居节点对。 貌似那位哥哥对我的数据结构设计还比较满意，看了下程序，问了几个问题，肯定了我的答案之后，又问有没有更好的，建议让用递归的过程。我想了一会，没想出来，于是说，递归因为会影响性能，所以平常能不用就不用，我一时可能想不出来。 然后就扯了会编程风格的问题，这题算勉强通过了吧。 然后，那位GG说，下面再来一个难点的吧。 题目大概意思是，有一个容器，容量为S，还有N个物品，体积是个随机值，为Wn=ran(i)。问怎样用最快的方式把容器正好装满。 我当时用了贪心算法 和0-1背包问题的大致思想解决的，然后那位哥哥就让我求其复杂度。 后来那位哥哥说，用B树的方式速度更快，就给我分析原因。 我如实回答，基本没有用过B树，只是对其有个大概的印象。 本来以为还有第三题，或者过不了关，谁知道下面那位GG忽然就问我手头有
本文来源：http://www.gbppp.com/jy/428967/
推荐访问:百度运营笔试题目 百度笔试面试题目