现在的位置: 首页 > 综合 > 正文

设计MP3搜索引擎 设计MP3搜索引擎

2017年11月02日 ⁄ 综合 ⁄ 共 1409字 ⁄ 字号 评论关闭

设计MP3搜索引擎

分类: 数据结构与算法 笔试面试题 213人阅读 评论(0) 收藏 举报

(百度)假设一个 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 个。

分析:

SONG_ID和URL_ID都从0开始。

一首歌曲的最大URL列表的大小:2^10 * 4 = 2^12 Byte = 4 KB

一个文件最多容纳歌曲数目:2G / 4KB = 2*2^30 / 2^12 = 2^19

最少文件数目:2^24 / 2^19 = 2^5 = 32

解答:1、文件系统

文件以二进制格式存储数据,以FILE_ID唯一确定,从0开始。

一个文件容纳歌曲数目为SONG_COUNT = 2^18,需要的文件数目为FILE_COUNT = 64。

文件存储的信息分为两部分:在文件头部存储歌曲信息:歌曲ID,能收听该歌曲的URL数目,URL列表在文件中的偏移量,即:SONG_ID,URL_COUNT,URL_OFFSET。一首歌曲占用SONG_INFO_SIZE = 12Byte,所有歌曲占用即文件头部大小为SONG_COUNT*SONG_INFO_SIZE。下一部分对于每一首歌曲,按顺序存储其URL列表,一首歌曲的URL列表占用SONG_URL_SIZE = 4KB,所有歌曲占用SONG_COUNT*SONG_URL_SIZE。

所有的歌曲无论存在与否,都写入文件,预先占用空间。若歌曲不存在,其SONG_ID设置为-1,其余数据未定义。

给定一首歌曲的SONG_ID,确定它的位置:存储它的文件FILE_ID = SONG_ID / SONG_COUNT,在文件中的偏移量是FILE_OFFSET= SONG_ID % SONG_COUNT * SONG_INFO_SIZE。

再用另外一个文件存储所有的URL是否可用,一个URL对应一个bit,1为可用,0为不可用,占用2^30bit。

2、主系统

采用缓存方案,用户查询时,先从缓存中查找,若找到,直接返回,若找不到,从文件中查找,并读取到缓存中。

用户查询系统,分层:一是接入层,接收用户查询请求,将请求存到请求队列,从响应队列取出响应,发送给用户;二是业务逻辑层,从请求队列读取请求,调用缓存系统的方法得到歌曲数据,处理,将响应存到响应队列。接入层需要管理大量Socket,windows平台使用IO完成端口,Linux平台使用epoll。在多核平台,业务逻辑层可使用线程池。

缓存系统,使用哈希表存储歌曲信息,以SONG_ID为键,URL列表为值,保持2^10首歌曲信息。缓存系统负责,从文件中读取歌曲信息和URL信息,将改变了的歌曲信息或URL信息存回文件,以老化算法定期清理最近最少访问的歌曲。

给定一个 SONG_ID,为其添加一个新的 URL_ID,二叉查找新URL应该在的位置,可能需要将该位置以后的URL_ID集体后移。

抱歉!评论已关闭.