百度08-9-24成都电子科技大学笔试题(第一套)

诸葛亮

008-9-24成都电子科技大学百度笔试题（第一套题）
一：编程题
现有一组共计N个固定的集合（N为万量级），每个集合有个从0开始递增的集合ID，每个集
合包含1~M个TERM（M为0~100的量级），希望设计一个程序能够持续对外服务，输入是一个
TERM数组，输出其中任意一个集合ID（如果该TERM数组包含该集合的所有TERM），如果找
不到输出-1。要求：
1， 时间复杂度最优，能够在短时间内对大量输入逐个输出
2， 实现具体的代码（可以是伪代码），其中常用的数据结构可以采用标准库。
3， 给出时间复杂度和空间复杂度。
TERM组合集合的文件格式举例：
TERM_1 空格 TERM_2
TERM_1 空格 TERM_3
TERM_1 空格 TERM_3 TERM_4
输入的为TERM数组（说明：TERM为一个词，可能是中文，固定字符串表示）
二：算法题
你现在有一个文件，文件中顺序存有N个记录，R1,R2,...,RN,这些记录不是有序的，但是
你知道一个整数M,这些记录满足R1
1,设计一个算法或编写一个程序，将文件中的记录排序为R1'取文件的次数为O(N),不限内存使用，
2,设计一个算法或编写一个程序，将文件中的记录排序为R1'写文件的次数为O(N)，空间复杂度为O(1)，(亦即，你使用的内存大小和M,N均无关。)
三：系统设计题
网络上所有的链接都可以用以下的三元素进行描述：
From_url（链接所在页面的URL）
to_url（链接所指向的URL）
anchor（链接在页面上所显示的内容）
现在假设所有的网页链接信息（from_url \ to_url \anchor）按from_url为轴都存储在M
个（M：1k以内）巨型数据库中：
1， 链接存储形式：from_url to_url anchor；
2， 一个from_url的所有的to_url都存储在同一个数据库中；
3， 假设每个数据库存储的数据量相同
4， 要求设计一个获取所有链接分发程序，将这些数据均匀分发到N个远程数据库中（N:1
00以内）要求做到：1所有to_url相同的链接需要分到同一个远程数据库，2所有to_url的
站点相同的需要分发到同一个远程数据库，3每个远程数据库获取的链接总数要尽量均匀，
4每台数据库完成时间尽量保持一致5，获取网页的速度尽量快（从数据库中）
信息。