百度面试题a。zz

百度面试题。

 

1.

·谈谈你对数据库中索引的理解

 

R1.

使用索引可快速访问数据库表中的特定信息。索引是对数据库表中一列或多列的值进行排序的一种结构，例如 employee 表的姓（lname）列。如果要按姓查找特定职员，与必须搜索表中的所有行相比，索引会帮助您更快地获得该信息。

 

建立索引的优点

1.大大加快数据的检索速度;

2.创建唯一性索引，保证数据库表中每一行数据的唯一性;

3.加速表和表之间的连接;

4.在使用分组和排序子句进行数据检索时，可以显著减少查询中分组和排序的时间。

 

索引的缺点

1.索引需要占物理空间。

2.当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，降低了数据的维护速度。

 

唯一索引

唯一索引是不允许其中任何两行具有相同索引值的索引。

当现有数据中存在重复的键值时，大多数数据库不允许将新创建的唯一索引与表一起保存。数据库还可能防止添加将在表中创建重复键值的新数据。例如，如果在 employee 表中职员的姓 (lname) 上创建了唯一索引，则任何两个员工都不能同姓。

 

主键索引

数据库表经常有一列或列组合，其值唯一标识表中的每一行。该列称为表的主键。

在数据库关系图中为表定义主键将自动创建主键索引，主键索引是唯一索引的特定类型。该索引要求主键中的每个值都唯一。当在查询中使用主键索引时，它还允许对数据的快速访问。

 

聚集索引

在聚集索引中，表中行的物理顺序与键值的逻辑（索引）顺序相同。一个表只能包含一个聚集索引。

如果某索引不是聚集索引，则表中行的物理顺序与键值的逻辑顺序不匹配。与非聚集索引相比，聚集索引通常提供更快的数据访问速度。

 

2.

现在普通关系数据库用得数据结构是什么类型的数据结构

 

3.

索引的优点和缺点

 

4.

session 和 cache 的区别是什么

 

R4.

Session 是单用户的会话状态。

 

当用户访问网站时，产生一个 SESSIONID。并存在于 COOKIES 中。每次向服务器请求时，发送这个 COOKIES ，再从服务器中检索是否有这个 SESSIONID 保存的数据。。。

 

而 CACHE ，则是服务器端的缓存，是所有用户都可以访问和共享的。

 

5.

如果有几千个 session，怎么提高效率

 

6.

session 是存储在什么地方，以什么形式存储的

 

R6.

session是存在服务器的内存中

每个会话对应一个sessionId

通过sessionId开区分是那个会话的session

 

7.

多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。如果说,前面的人比后面的人高(两人身高一样认为是合适的),那么我们就认为这两个人是一对“捣乱分子”,比如说,现在存在一个序列:

176, 178, 180, 170, 171

这些捣乱分子对为<176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>,

那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给出捣乱分子对的数目即可,不用具体的对)

 

要求：

输入:

为一个文件(in)，文件的每一行为一个序列。序列全为数字，数字间用”,”分隔。

输出：

为一个文件(out)，每行为一个数字，表示捣乱分子的对数。

 

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

 

限制：

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

 

 

9.

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

 

用户以ID形式表示，现给出好友列表数据的文本形式如下：

1 3,5,7,67,78,3332

2 567,890

31 1,66

14 567

78 10000

…

每行数据有两列，第一列为用户ID，第二列为其好友ID，不同ID间用”,”分隔，ID升序排列。列之间用”t”分隔。

 

 

要求：

请设计合适的索引数据结构，来完成以下查询：

给定用户A和B，查询A和B之间是否有这样的关系：B是A的二维好友（好友的好友）。

如上例中，10000为1的二维好友，因为78为1的好友，10000为78的好友。

 

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

 

限制：

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

 

10.

有关系模式：User（userId, userName）， Article（articleId, userId, title, content），Vote（articleId, score），User为用户关系，Article为用户发表的文章关系，Vote为文章得票关系，title为文章标题、score为得票数。

（1）用SQL语言查询所有没发表过文章的用户名；

（2）用SQL语言查询得票数大于100的所有文章标题，按得票数倒序排列；

（3）用SQL语言查询出发表文章数大于5，文章平均得票数大于100的用户名，按平均得票数倒序排列；

（4）设计这些表的主键、外键和索引，并指出上面三个查询所使用的索引。

（5）当用户数超过1000万，文章数超过1亿时，如何考虑存储及性能的改进和优化？

 

 

11.

每天论坛访问量300万左右，更新帖子10万左右。

请给出数据库表结构设计，并结合范式简要说明设计思路。

 

R11.

这是我看见的百度面试题，以前也在cdsn上面看见过类似的问题，没有仔细想就写了自己的见解和答案，很可惜我以前的想法是错误的；算是误人子弟阿，郁闷！因此我还是先把和几个朋友讨论的结果和自己的想法做一个总结，算是弥补我以前想法造成别人曲解的过错； 首先，我们先来分析一下这道面试题：用户名，email，主页，电话，联系地址，发帖标题，发帖内容，回复标题，回复内容。这些字段可以基本归为三类：

 

1、用户基本信息：用户名(UserName)，email(Email)，主页(HomePage)，电话(Tel)，联系地址(Address)；

2、发帖主题信息：发帖标题(Title)，发帖内容(Content)；

3、回复信息：回复标题(RTitle)，回复内容(RContent)；

 

以上一步有基本开发经验的人都知道，只是对基本的信息进行划分；相信将用户基本信息存放在一张表内不会有什么好讨论的，我创建一张表叫T_Users，并建立主键UserID，用户基本信息所需要存放的内容都放置在此表内；那么是应该把发帖主题和回复信息分别创建两张表存放数据呢还是应该存放在一张表内？字段内容还是比较接近的，因此从数据冗余的角度看，一张表和两张表在此方面的区别并不影响设计；假设按照大多数论坛的设计思路，将2、3设计成两个表T_Topics和T_Reverts后，再来分析看看是否合适这里的要求；

 

现在“每天论坛访问量300万左右，更新帖子10万左右”对这句话进行分析，才是这个面试题的关键所在。面试题显然要求在操作数据库的性能方面要有更高的要求。而对数据库的操作而言，检索数据的性能基本不会对数据造成很大的影响（精确查找的情况下），而对表与表之间的连接却会产生巨大的影响，特别在有巨量数据的表之间；而对数据库的连接也是相当消耗性能的操作（这在ADO.NET的教程中都多次提醒的）；因此对问题的定位基本可以确定：在显示和检索数据时，尽量减少数据库的连接以及表与表之间的连接；

 

解决问题的指导性原则找到了，那就来看看，从上面的设计中，有哪一些地方会产生我们提到的表与表之间的连接；（连接数据库的次数尽量减少到每打开一个页面只连接一次数据库就可以得到所有的数据）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这个字段来增加性能！

 

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

 

12.

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

 

R12.

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

遍历文件a，对每个url求取hash(url)%1000，然后根据所得值将url分别存储到1000个小文件（设为a0,a1,...a999）当中。这样每个小文件的大小约为300M。遍历文件b，采取和a相同的方法将url分别存储到1000个小文件(b0,b1....b999)中。这样处理后，所有可能相同的url都在对应的小文件(a0 vs b0, a1 vs b1....a999 vs b999)当中，不对应的小文件（比如a0 vs b99）不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。

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

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

 

13.

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

 

R13.

 

使用hash_map和链表。

首先定义一个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的大小，就知道有多少个兄弟单词了。

14.

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

 

R14.

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

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）的方法找出来即可。