2008年3月14日星期五

baidu笔试mp3搜索问题 from smth

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

1.    假设一个mp3搜索引擎收录了2^24首歌曲,并记录了可收听这些歌曲的2^30条URL,但每首歌的URL不超过2^10个。系统会定期检查这些URL,如果一个URL不可用则不出现在搜索结果中。现在歌曲名和URL分别通过整型的SONG_ID和URL_ID唯一确定。对该系统有如下需求:
1)    通过SONG_ID搜索一首歌的URL_ID,给出URL_ID计数和列表
2)    给定一个SONG_ID,为其添加一个新的URL_ID
3)    添加一个新的SONG_ID
4)    给定一个URL_ID,将其置为不可用

限制条件:内存占用不超过1G,单个文件大小不超过2G,一个目录下的文件数不超过128个。

为获得最佳性能,请说明设计的数据结构、搜索算法,以及资源消耗。如果系统数据量扩大,该如何多机分布处理?
:================================================

内存不够存储这些url,所以将数据写入若干个文件中。

每一首歌曲对应的存储在文件中的信息格式为(url1, url2……)。

文件的总大小大约为2^24*2^10*4 =2^36 =64GB.根据SongID即可计算出在哪个文件的哪个位置,那么一个随机的查询操作耗时即是一次随机打开文件啊并执行seek操作读取数据的实际,大约是ms级别。

将每首歌曲的信息存入文件中,由于每首歌的url不超过2^10个,所以在文件中每首歌的存储结构是2^10个int数,每个int数字标识着一个url。-1表示url不存在。初始化时将文件中每个int数初始化为-1.
这样每个SongID对应的信息占用的空间为2^10*4=4KB,设每个文件大小1G,那么每个文件可存储2^18=256K个Song的信息。总共需要64个文件,把这些文件编号从0-63.

对于任意一个SongID,他所对应的url信息所在的文件编号是:SongID>>18,在文件中的位置是:(SongID&0x3FFFF)<<12.

另外内存中用一个2^24大小的short int型数组来保存每一首歌曲对应的url的个数,计数组名为urlCount[],初始化时值为-1,表示对应的Song_ID不存在。此数组占用空间2^25Byte=32MB;

url是否可用的信息用位图来标识。位图保存在内存中,占用的空间为2^30/8=2^27 Byte=128MB.


对所要求的操作:
:1)    通过SONG_ID搜索一首歌的URL_ID,给出URL_ID计数和列表
通过SONG_ID计算出文件号和对应在文件中的位置,从urlCount[]中读取url个数,读出所有的url,并对每个url_ID查询位图看是否可用,若可用,将此url加入返回列表。

:2)    给定一个SONG_ID,为其添加一个新的URL_ID
通过SONG_ID计算出文件号和对应在文件中的位置,设为start,在通过urlCount[]得到url个数,假设有n个url,那么将新的URL_ID写入文件的start+sizeof(int)*n处。修改urlCount[SONG_ID]的值。

:3)    添加一个新的SONG_ID
检查将对应的urlCount[SONG_ID],若为-1,则修改为0,若大于等于0,则表明改Song_ID已经存在。

:4)    给定一个URL_ID,将其置为不可用
修改url位图,标识URL_ID对应的位,表示为不可用。

没有评论: