百度校园招聘笔试题-2015年

一、简答题

1、请描述数据结构中栈和队列的差别，以及至少三种栈和队列的基本操作接口？（10分）

2、在面向对象设计中，什么是多态，说明一种C++中多太的实现方法，并编写一个简单的例子来说明多态？（10分）

3、请描述TCP协议中四次挥手的过程，以及TIME_WAIT状态产生的原因和存在的理由？（10分）

二、算法与程序设计题

1、使用 C/C++ 语言写一个函数，实现一篇文章中所有单词逆置，即第一个单词出现在文末，最后一个单词出现在第一个位置。要求不能用任何库函数和系统调用，且空间复杂度最小，函数原型是：char* reverse_word(char* str)。（15分）

2、一个序列有n个数：A[1], A[2], ..., A[n], 求出最长非降子序列的长度。

          例如序列：5，3，4，8，6，7

          输出：4 （最长非降子序列为3，4，6，7）（15分）

3、请设计一个有限状态机，用于提取一个C语言文件中的所有注释。（15分）

三、系统设计题（本题共25分）

考虑设计一个基于社交网络的游戏排名系统，需求如下：

       1. 用户能够看到其所有好友的游戏分数与排名（朋友圈内的所有人的排名）

       2. 用户能够看到自己在游戏服务器上的总排名数（如第9527名）

问题如下：

       1. 请设计游戏客户端与服务器分数和排名的交互、存储的方式与结构，描述如何实现分数的实时更新、排名的高效查询。

       2. 考虑如果在线用户超过1亿，请分析上述方案能否支持，如果支持请给出支持的理由；否则请给给出该井的方案和技术。