2、提了一个问题：上千万条记录，统计出重复记录最多的前N条。

　　3、一个概率题：54张扑克牌，除去两张大小王剩下52张扑克牌。问红桃A和黑桃A同时被一个人拿到的概率是多少?

　　4、多个线程访问共享内存时因该怎么办?

　　5、在写程序遇到问题的时候，通常采用什么调试方法?

　　7、剩下就是随便聊聊，比如有缺点、期望工作的性质、职业规划等

　　/mianshiti 后，你看到了IT面试题的博客首页，那么这一切是如何发生的呢？

的教程中都多次提醒的）；因此对问题的定位基本可以确定：在显示和检索数据时，尽量减少数据库的连接以及表与表之间的连接；

解决问题的指导性原则找到了，那就来看看，从上面的设计中，有哪一些地方会产生我们提到的表与表之间的连接；（连接数据库的次数尽量减少到每打开一个页面只连接一次数据库就可以得到所有的数据）1、用户基本信息中的用户名在发帖主题列表以及打开一个主题查看回复内容时上面会有所显示，需要在T_Users和其他两张表进行连接；2、在打开一个主题查看回复内容时，需要在T_Topics和T_Reverts之间进行连接；其他应该是不需要产生表与表之间的连接；按照面试题来推测：T_Users的数据量应该在1万-10万之间，T_Topics应该在100-1000万之间，T_Reverts应该在1000万-1亿之间；从上面两类连接可以看出来，T_Users和T_Topics会在列表页面连接一次；T_Users、T_Topics和T_Reverts三张表会连接一次；

我说不上来第一种连接是否可以允许（至少在我开发的系统里面都是允许的），但是另外三张表连接是绝对不会允许的！特别是T_Topics和T_Reverts两表之间的连接会产生很大的性能损耗，因此需要避免这样的情况产生。那怎么样的设计可以避免T_Topics和T_Reverts两表之间的连接呢？前面已经进行了分析：可以考虑把发帖主题和回复信息存放在一张表（T_Infos）里面，看看是否可以解决这个问题；我们设计一个字段（Flag）来标记是主题还是回复的内容；设计一个字段（ParentID,主题此字段为ID值）来指定是哪一个特定主题的回复；在开打回复信息时，只需要按照所知道的主题ID，就可以检索到这个主题的内容以及所有的回复内容，上面指出的问题就可以解决！

为了性能，我们再一次对T_Users和T_Infos连接对性能的影响进行一下细致的分析，可以通过在T_Infos表内增加UserName字段来解决和它的连接，这样至少在显示时，性能能够得到保证；但是这样的设计因为UserName字段是冗余的，因此在用户修改UserName的时候就会产生同步数据的问题，这个需要程序来进行弥补，并是我们认为用户不会经常性的修改他的用户名这样的前提下；

因此这道面试题的答案应该是设计两张表，用户基本信息表T_Users和内容表T_Infos，这两张表的连接还是通过UserID，但是T_Infos中增加UserName这个字段来增加性能！

上面的面试题算是分析完了，但是从这道题目的分析中我们可以看出来，这样的设计是建立在“一个简单的论坛系统”这样的基础上的极端事例，在我们真实的世界中，不太会有很多的人喜欢这样简单的论坛，而且这样的论坛在扩展性方面会产生很大的限制；这算不算这道题目是应试教育的产物呢？而且在设计的时候不仅仅是为了适应现在系统的需求还需要提供将来新的要求的变化，因此在实际的开发过程中间并不推荐使用这道面试题的答案。

给你a、b两个文件，各存放50亿条url，每条url各占用64字节，内存限制是4G，让你找出a、b文件共同的url。

可以估计每个文件的大小为5G*64=300G，远大于4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

b999)当中，不对应的小文件（比如a0 vs b99）不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。

比如对于a0 vs b0，我们可以遍历a0，将其中的url存储到hash_map当中。然后遍历b0，如果url在hash_map中，则说明此url在a和b中同时存在，保存到文件中即可。

如果分成的小文件不均匀，导致有些小文件太大（比如大于2G），可以考虑将这些太大的小文件再按类似的方法分成小小文件即可。

给你一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b是a的兄弟单词。现在给你一个字典，用户输入一个单词，让你根据字典找出这个单词有多少个兄弟单词。 （这道题面试官说有O(1) 的解法，。。。。。）

首先定义一个key，使得兄弟单词有相同的key，不是兄弟的单词有不同的key。例如，将单词按字母从小到大重新排序后作为其key，比如bad的key为abd，good的key为dgoo。

使用链表将所有兄弟单词串在一起，hash_map的key为单词的key，value为链表的起始地址。

开始时，先遍历字典，将每个单词都按照key加入到对应的链表当中。当需要找兄弟单词时，只需求取这个单词的key，然后到hash_map中找到对应的链表即可。

这样创建hash_map时时间复杂度为O(n)，查找兄弟单词时时间复杂度是O(1)。

只要定义一个合适的特征码，然后用hash结构保存，就可以达到O(1)的解法。

比如：对单词aadb 定义特征码如下a2b1d1， dddabc的特征码是a1b1c1d3，以此类推（各位大侠可以设计更好的特征码）。

数据结构定义如：hash_map >,其中hash_map的key是特征码，value是兄弟单词集。首先扫描字典，将所有单词的特征码和相应单词集装入这个数据结构。

查找时，先计算出待查单词的特征码，然后搜索一下hash_map里相应set的大小，就知道有多少个兄弟单词了。

五桶球，一桶不正常，不知道球的重量和轻重关系，用天平称一次找出那桶不正常的球。

这个问题的解法如下（首先假定只要不把球从天平拿下来就还算一次，另外每个桶内的球是一样的）：

1）从1号和2号桶各拿一个，放上天平（1号左，2号右），如果平衡，说明这两桶球都是正常的，可以做为砝码。如果不平衡，那么1号和2号桶必有一个不正常，而其他3，4，5桶是正常的，可以作为砝码。

2）首先考虑1号2号桶不平衡的情况，这时从1号和3号桶再各拿一个球，放上天平（1号右，3号左），如果这时平衡了，说明1号桶是不正常的，如果还是不平衡，那么2号桶是不正常的。

3）如果第一步1号2号桶是平衡的，那么也好办，把3，4号桶各拿一个放上天平（3号左，4号右），这时如果还是平衡的，那么5号桶必然是不正常的。如果不平衡，说明不正常的就在3，4号桶之中。我们再用2）的方法找出来即可。

详细说明自己的解题思路，说明自己实现的一些关键点。
写出函数foo原代码，另外效率尽量高，并给出代码的复杂性分析。
al1和al2的长度不超过100万。而且同一个数组的区间可能出现重重叠。
使用的存储空间尽量小。

为一个文件(in)，文件的每一行为一个序列。序列全为数字，数字间用”,”分隔。
为一个文件(out)，每行为一个数字，表示捣乱分子的对数。

详细说明自己的解题思路，说明自己实现的一些关键点。并给出实现的代码 ，并分析时间复杂度。

输入每行的最大数字个数为100000个，数字最长为6位。程序无内存使用限制。

二、下面是两道选做题，请根据自己的情况选择其中的一道作答(WEB方向请答第4道，其他职位方向答第3道）。

考虑一个在线好友系统。系统为每个用户维护一个好友列表，列表限制最多可以有500个好友，好友必须是这个系统中的其它用户。好友关系是单向的，用户B是用户A的好友，但A不一定是B的好友。

用户以ID形式表示，现给出好友列表数据的文本形式如下：
每行数据有两列，第一列为用户ID，第二列为其好友ID，不同ID间用”,”分隔，ID升序排列。列之间用”t”分隔。

请设计合适的索引数据结构，来完成以下查询：
给定用户A和B，查询A和B之间是否有这样的关系：B是A的二维好友（好友的好友）。
如上例中，10000为1的二维好友，因为78为1的好友，10000为78的好友。

详细说明自己的解题思路，说明自己实现的一些关键点。并给出实现的伪代码实现建立索引过程和查询过程，并说明空间和时间复杂度。

用户数量不超过1000万，平均50个好友。

（1）用SQL语言查询所有没发表过文章的用户名；
（2）用SQL语言查询得票数大于100的所有文章标题，按得票数倒序排列；
（3）用SQL语言查询出发表文章数大于5，文章平均得票数大于100的用户名，按平均得票数倒序排列；
（4）设计这些表的主键、外键和索引，并指出上面三个查询所使用的索引。
（5）当用户数超过1000万，文章数超过1亿时，如何考虑存储及性能的改进和优化？

一、选择题：15分 共10题
1. 任何一个基于“比较”的内部排序的算法，若对6个元素进行排序，则在最坏情况下所需的比较次数至少为____。

2. 关系模型有三类完整性约束，定义外键实现的是 完整性.
A. 实体完整性 B. 参照完整性
C. 用户定义的完整性 D. 实体完整性、参照完整性和用户定义的完整性

4. 下面说法正确的是：
A. 根据gprof统计的程序运行时函数调用次数及执行时间，进行程序代码优化，这是amdahl定律的应用
B. 计算机网络设备的缓冲区是时间和空间局部性原理的应用
C. 局域网内的计算机发送数据包的数学模型遵循泊松分布
D. 分支预测使用先前运行时得到的配置文件，这是依据正态分布

6. 上下文无关文法是一种____。
A 左线性文法 B 右线性文法 C 正则文法 D 以上都不上

二、简答题：20分，共2题

请评价该监控程序的敏感性和正确性。

三、编程题：30分 共1题
注意：要求提供完整代码，如果可以编译运行酌情加分。

试设计程序：针对各个group(0-->9)，根据value字段排序，输出各组top 10的节点。（top10是从小到大，取后面的大值top10.）
要求：尽量减少计算复杂度、遍历次数，不允许大量的辅助内存

四、设计题：35分 共1题
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。

1. 设想网络上的一个发送者和64个接收者，发送者每秒有不超过128条的命令产生，每条命令包含一个512字节的头部command_head_t和至多4K字节的变长内容。command_head_t的结构如下：
int cmd_no; //该命令的命令号，唯一识别一个命令
发送者根据命令号将这些命令分别发送给接收者去处理，例如：发送者产生c1，c2，c3，c4命令，并设定将c1，c2命令发送到接收者r1和r2，将c2、c3，c4命令发送到r3。
接收者执行接收到的命令，并相应修改自己的状态。
现在的问题是：在尽可能多的考虑各种可能的意外情况下（包括但不限于网络故障、传输错误、程序崩溃、停电…），如何设计命令的存储、发送、接收的流程，以保证命令的：
1) 传输中的有序、无漏、无重复性
2) 整个过程中命令和数据的正确性
3) 多个同一类型的接收者（例如r1与r2）的状态可以在有限时间内趋于一致
最后，请针对你考虑到的意外情况，说明所采用的避免、解决或恢复方案。

三个警察和三个囚徒的过河问题
　　三个警察和三个囚徒共同旅行。一条河挡住了去路，河边有一条船，但是每次只能载2人。存在如下的危险：无论在河的哪边，当囚徒人数多于警察的人数时，将有警察被囚徒杀死。
　　问题：请问如何确定渡河方案，才能保证6人安全无损的过河。
　　警察囚徒过去，警察回来
　　囚徒囚徒过去，囚徒回来
　　警察警察过去，警察囚徒回来
　　警察警察过去，囚徒回来
　　囚徒囚徒过去，囚徒回来

1、给你一组离散的点集合S和一个坐标P，在S中找到一个点使其到给定点P的距离最短；（要求：不能求两个点之间的距离）

2、任意给定平面上n个点的坐标，要求你确定一个圆，将这个n个点平均分为两部分，其中一部分在圆的内部，另外一部分在圆的外部，这个圆不一定是唯一，只要输出其中一个圆的圆心和坐标就可以了。（要求：不能求两个点之间的距离）

为某图书馆开发在线浏览系统，使用户可以通过自定义的图书别名浏览相关联的图书  
内容。假设该图书馆有1000万注册用户，馆藏图书1000万部。在线浏览系统允许用户自  
定义分类名称，每个分类可以包含若干部书籍。用户可以添加、删除分类，修改分类的  
名称（同一用户不允许有名称相同的分类），可以在分类下添加、删除书籍，修改书籍  
的别名（同一分类下不允许有名称相同的别名）。现在设定每个用户最多可以自定义10  
0个分类，每个分类最多可以包含100部书籍。   
A、假定用数据库解决存储问题，请设计相关的数据表结构，并给出设计考虑。   
C、请根据题目A的结果，尝试分析一下当用户数目增长到1亿，馆藏图书达到10亿册，每  
天访问用户达到500万，平均每人有10次操作时，系统应当做哪些改进或优化。

该图书馆有1000万注册用户，馆藏图书1000万部。在线浏览系统允许用户自  
定义分类名称，每个分类可以包含若干部书籍。如书架名、书名号接下去为代码加上自己的代号就行。

要求按时间大小得到移动轨迹，同时把重复合并一下。

这是个相当难度的问题。大侠帮忙呀。急……