百度1

╰+攻爆jí腚メ 2022-04-10 08:38 311阅读 0赞

备注：转载于 [http://blog.csdn.net/ustc\_dylan/article/details/5451227][http_blog.csdn.net_ustc_dylan_article_details_5451227]

百度面试题，仅提供一些参考。

1 完成函数  
size\_t foo(unsigned int \*a1, size\_t al1, unsigned int\* a2, size\_t al2)  
其中a1和a2都为无符号数组，al1和al2为数组的长度，数组的长度为偶数。  
无符号数组由一对数字区间组成。 如下例：  
a1 为 0,1,3,6,10,20  
a2 为 0,1,20,50,4,5  
则 a1表示以下区间\[0,1\] \[3,6\] \[10,20\]  
a2表示以下区间\[0,1\] \[20,50\] \[4,5\]  
则a1,a2的重叠部分为\[0,1\] \[4,5\]，其长度为2  
函数foo要求返回重叠区间的长度。上例中为2.  
  
要求：  
详细说明自己的解题思路，说明自己实现的 一些关键点。  
写出函数foo原代码，另外效率尽量高，并给出代码的复杂性分析。  
限制：  
al1和al2的长度不超过100万。而且 同一个数组的区间可能出现重重叠。  
如a1可能为 0,5, 4,8, 9,100, 70,80  
使用的存储空间尽量小。

解题方法：先对两个数组的区间进行排序，排序规则以区间的第一个数为键，然后将一个数组构建二叉排序树，将另一个数组中的区间一次在二叉排序树中查找。 时间复杂度（nlogn） 。

有人提出了log(+n)的复杂度，就是将两个数组排序，排序规则如上，然后对两个数组进行归并，归并出的结果即为所得。

2 多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。如果说,前面的人比后面的人高(两人身高一样认为是合适的),那么我们就认 为这两个人是一对“捣乱分子”,比如说,现在存在一个序列:  
176, 178, 180, 170, 171  
这些捣乱分子对 为<176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>,  
那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给 出捣乱分子对的数目即可,不用具体的对)  
  
要求：  
输入:  
为一个文件(in)，文件的每一行为一个序列。序列全为数字，数字 间用”,”分隔。  
输出：  
为一个文件(out)，每行为一个数字，表示捣乱分子的对数。  
  
详细说明自己的解题思路，说明自己 实现的一些关键点。并给出实现的代码 ，并分析时间复杂度。  
  
限制：  
输入每行的最大数字个数为100000个，数字最长为6位。程 序无内存使用限制。

基本思路：将整个数列划分成多个递增序列，然后从第二个序列开始，对其中的每个数字与前面的序列比较，时间复杂度为  
二、下面是两道选做题，请根据自己的情况选择其中的一道作答(WEB方向请答第4道，其他职位方向答第3 道）。  
  
3  
考虑一个在线好友系统。系统为每个用户维护一个好友列表，列表限制最多可以有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个好友。  
  
4  
有 关系模式：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亿时，如何考虑存储及性能的改进和优化？

转自：[http://www.cnblogs.com/cswolf/archive/2010/09/10/2267163.html][http_www.cnblogs.com_cswolf_archive_2010_09_10_2267163.html]

[http_blog.csdn.net_ustc_dylan_article_details_5451227]: http://blog.csdn.net/ustc_dylan/article/details/5451227
[http_www.cnblogs.com_cswolf_archive_2010_09_10_2267163.html]: http://www.cnblogs.com/cswolf/archive/2010/09/10/2267163.html