透露百度校园招聘笔试题
[攒RP系列]透露百度校园招聘笔试题
百度校园招聘在线笔试
1）15分
如下数据结构：
typedef struct TreeNode {
char c;
TreeNode *leftchild;
TreeNode *rightchild;
}
请实现两棵树是否相等的比较,相等返回0否则返回其它值.并说明你的算法复杂度
int CompTree(TreeNode* tree1, TreeNode* tree2);
注:A,B两棵树相等当且仅当RootA->c==RootB->c，而且A和B的左右子树对应相等或
者左右互换后相等．
2）15分
已知一个字串由GBK汉字和ansi编码的数字字母混合组成，编写C语言函数实现从中去掉所有
ansi编码的的数字和字母（包括大小写).要求在原字串上返回结果。
int filter_ansi(char* gbk_string);
注：汉字的GBK编码范围是0x8140 - 0xFEFE
3）30分
芯片测试：有2k块芯片，已知好芯片比坏芯片多．请设计算法从其中找出一片
好芯片，说明你所用的比较次数上限．
其中：好芯片和其它芯片比较时，能正确给出另一块芯片是好还是坏．
坏芯片和其它芯片比较时，会随机的给出好或是坏。
4）40分
请设计一个网页存储系统，能存储千万量级的网页。
要求：
1.支持按照URL为键值的随机添加，删除和修改网页
2.支持多个线程同时添加，修改和删除
3.支持多线程按照入库时间批量的获取网页，并尽可能的快
提示:设计应包括如下几方面:
1.网页的存储方式设计,即硬盘数据的组织形式
2.如何支持随机查找
3.如何优化批量检索
4.增删改查之间的同步和互斥,如何达到最大的并发.
系统限制和一些参考参数:
硬盘400G, 内存4G
硬盘的I/O比内存的I/O速度慢1000倍
硬盘的连续I/O比随机I/O快10倍
网页的平均长度为25K
附加：
请说明你的系统在亿到十亿规模的扩展方法．