2008-9-24百度笔考试题（第一套题） 一百分求解
2008-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<R2<...<RM以及RM+1<RM+2<...RN.
1,设计一个算法或编写一个程序，将文件中的记录排序为R1'<R2',<…<,RN',算法或程序读取文件的次数为O(N),不限内存使用，
2,设计一个算法或编写一个程序，将文件中的记录排序为R1'<R2'<...<RN',算法或程序读写文件的次数为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:100以内）要求做到：1所有to_url相同的链接需要分到同一个远程数据库，2所有to_url的站点相同的需要分发到同一个远程数据库，3每个远程数据库获取的链接总数要尽量均匀，4每台数据库完成时间尽量保持一致5，获取网页的速度尽量快（从数据库中）
------解决方案--------------------
第一题，应该是倒排索引的程序编程，你可以自己看一下，具体实施会比较复杂
第二题，没有内存要求，应该是优先度排序，所以保证每个文件读一遍就可以了，然后随便用个排序算法就可以了
第三题，我没时间看，希望有人帮你解答
------解决方案--------------------
第一个 可以用倒排索引，先根据Term建立倒排索引，然后检索
第二个 1、二路归并算法可以吧，空间复杂度O(N)，第二问，原地归并算法应该可以，复杂度O(1)
第三个 没想出来 等高手
------解决方案--------------------
第一题的解法：
1，建立倒排索引，格式如下：
termi,termi在ID集合中出现的顺序，按照集合ID从小到大排列，并记录每个集合的元素数目，即
term1,id3,10,id5,100,id 100,30…… 这种形式
2，查询的时候 根据输入的 term的集合，可以得出 有哪些倒排列表符合条件，然后将倒排列表合并，但是之前可以排除一些不可能符合的ID，比如说 查询得出的term的倒排列表个数 是10，但是你的集合ID 对应的集合的元素数目是100， 也就是这次查询的元素数目是肯定不会包括这个ID 的，
3，将合并后的倒排链表统计一下，找出第一个符合 ID的元素数目= term倒排列表的和的……
------解决方案--------------------
第二题的第一个问的解法：
根据M 读出文件，并将文件分成两个数组，这两个数组内部有序，然后将两个数组归并即可——这个就是归并排序的原理吧，符合题目要求的O(N)读入读出
------解决方案--------------------
第三题 是一个 map reduce的题目，就是将 每一个数据 影射成 key-value对 然后进行组装，主要考的就是这个吧——模拟 hadoop map reduce 的过程
------解决方案--------------------
第三题很简单啊,
用M台机器分别同时读M个数据库,对to_url字符串做hash : i = hash(str)/远程数据库个数
对于每条记录发送到远程第i个机器上.
由于M个数据库记录个数相似,所以几乎是同时完成的
一：编程题
现有一组共计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<R2<...<RM以及RM+1<RM+2<...RN.
1,设计一个算法或编写一个程序，将文件中的记录排序为R1'<R2',<…<,RN',算法或程序读取文件的次数为O(N),不限内存使用，
2,设计一个算法或编写一个程序，将文件中的记录排序为R1'<R2'<...<RN',算法或程序读写文件的次数为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:100以内）要求做到：1所有to_url相同的链接需要分到同一个远程数据库，2所有to_url的站点相同的需要分发到同一个远程数据库，3每个远程数据库获取的链接总数要尽量均匀，4每台数据库完成时间尽量保持一致5，获取网页的速度尽量快（从数据库中）
------解决方案--------------------
第一题，应该是倒排索引的程序编程，你可以自己看一下，具体实施会比较复杂
第二题，没有内存要求，应该是优先度排序，所以保证每个文件读一遍就可以了，然后随便用个排序算法就可以了
第三题，我没时间看，希望有人帮你解答
------解决方案--------------------
第一个 可以用倒排索引，先根据Term建立倒排索引，然后检索
第二个 1、二路归并算法可以吧，空间复杂度O(N)，第二问，原地归并算法应该可以，复杂度O(1)
第三个 没想出来 等高手
------解决方案--------------------
第一题的解法：
1，建立倒排索引，格式如下：
termi,termi在ID集合中出现的顺序，按照集合ID从小到大排列，并记录每个集合的元素数目，即
term1,id3,10,id5,100,id 100,30…… 这种形式
2，查询的时候 根据输入的 term的集合，可以得出 有哪些倒排列表符合条件，然后将倒排列表合并，但是之前可以排除一些不可能符合的ID，比如说 查询得出的term的倒排列表个数 是10，但是你的集合ID 对应的集合的元素数目是100， 也就是这次查询的元素数目是肯定不会包括这个ID 的，
3，将合并后的倒排链表统计一下，找出第一个符合 ID的元素数目= term倒排列表的和的……
------解决方案--------------------
第二题的第一个问的解法：
根据M 读出文件，并将文件分成两个数组，这两个数组内部有序，然后将两个数组归并即可——这个就是归并排序的原理吧，符合题目要求的O(N)读入读出
------解决方案--------------------
第三题 是一个 map reduce的题目，就是将 每一个数据 影射成 key-value对 然后进行组装，主要考的就是这个吧——模拟 hadoop map reduce 的过程
------解决方案--------------------
第三题很简单啊,
用M台机器分别同时读M个数据库,对to_url字符串做hash : i = hash(str)/远程数据库个数
对于每条记录发送到远程第i个机器上.
由于M个数据库记录个数相似,所以几乎是同时完成的