发布于 2014-09-26 08:20:01 | 482 次阅读 | 评论: 0 | 来源: 网友投递
百度(Baidu)中文搜索引擎
百度（Nasdaq简称：BIDU）是全球最大的中文搜索引擎，2000年1月由李彦宏、徐勇两人创立于北京中关村，致力于向人们提供“简单，可依赖”的信息获取方式。“百度”二字源于中国宋朝词人辛弃疾的《青玉案·元夕》词句“众里寻他千百度”，象征着百度对中文信息检索技术的执著追求。
一、 简答题（本题共30分）
1. 请简述Tcp-ip的3次握手以及4次挥手过程？并解释为何关闭连接需要4次挥手（10分）
2. 操作系统的内存管理淘汰算法有哪些，清了列出并简要说明？（10分）
3. 进行数据库设计时通常需要遵守哪些范式，请列出并说明？（10分）
二、 算法与程序设计题（本题共45分）
1. 寻找一个单向链表的中项，如果存在两个则返回前一个。请给出算法描述并给出代码实现（15分）
2. 在由N个正整数的集合S中，找出最大元素C，满足C=A + B，其中A,B都是集合S中元素，请给出算法描述，代码与时间复杂度分析（15分）
3. 使用堆栈（Stack）来模拟队列（FIFO）功能，要求数据必须存储在堆栈内部。需要实现enqueue（入队）。dequeue（出对）。isEmpty（判空）三个功能，并给出单元测试。（15分）
三、 系统设计题（本题共25 分）
手机推送服务设计，在各个手机端应用都需要一定的云控制能力，可以在某些情况下云端发送各种数据或者命令到手机端，例如发送一个强制升级的命令或者手机app 配置变换的数据包，以及发送一个信息给特定人群（某个地区）请设计一个以长链接为主的云端控制服务，为了聚焦主要问题，可以忽略掉低速手机网络（例如:2g 网络），手机终端等因素，用户登录的需求。服务需要承担定向、定量的推送需求，在设计中要尽量高的吞吐能力和容错能力。
需要完成
a) 基本的模块视图。
b) 链接管理主要设计思路。单台机器承担更多链接，但是链接多了后管理链接（链接中断，链接查找）都会出现性能瓶颈，请尝试给出思路。
c) 尝试给出提高容错能力（避免因为某台物理机器或者某个机器上的程序挂掉导致真个系统不可用）的思路。