垃圾回收站

发信人: bbinn (明天的明天), 信区: Algorithm
标 题: 百度试题 mp3搜索问题
发信站: 水木社区 (Wed Jul 25 18:03:14 2007), 站内

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 个。

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

–
- 不谈金钱,不谈妇女,不谈琐事

※ 来源:·水木社区 newsmth.net·[FROM: 218.249.22.*]

[本篇全文] [回复文章] [本篇作者：forcey] [回信给作者] [进入讨论区] [返回顶部]2发信人: forcey (爱到无可救药), 信区: Algorithm
标 题: Re: 百度试题 mp3搜索问题
发信站: 水木社区 (Wed Jul 25 18:11:24 2007), 站内

每个SONG_ID对应一个文本文件，文件里面每行一个URL_ID
这样前3个需求都很容易满足

然后把SONG_ID写成24位二进制，每6位一组分成4组，建立4级目录结构
这样限制条件也满足了

【 在 bbinn (明天的明天) 的大作中提到: 】
: 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，将其置为不可用
内存里放个bitset就解决了
: 限制条件：内存占用不超过 1G，单个文件大小不超过 2G，一个目录下的文件数不超过 128 个。
: 为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？

–
Only two things are infinite, the universe and human stupidity,
and I am not sure about the former.

– Albert Einstein

※ 修改:·forcey 于 Jul 25 18:11:43 修改本文·[FROM: 202.106.180.*]
※ 来源:·水木社区 newsmth.net·[FROM: 202.106.180.*]

[本篇全文] [回复文章] [本篇作者：godking] [回信给作者] [进入讨论区] [返回顶部]3发信人: godking (岁月如梭), 信区: Algorithm
标 题: Re: 百度试题 mp3搜索问题
发信站: 水木社区 (Wed Jul 25 18:27:45 2007), 站内

SONG_ID都放入内存,
SONG_ID对应的URL_ID列表节点分两种类型,
类型1小的放入内存,大的对应文件,文件偏移
是否有效,用bit域表示

【 在 bbinn (明天的明天) 的大作中提到: 】
: 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
: ……………….

–

※ 来源:·水木社区 newsmth.net·[FROM: 202.106.180.*]

[本篇全文] [回复文章] [本篇作者：bbinn] [回信给作者] [进入讨论区] [返回顶部]4发信人: bbinn (明天的明天), 信区: Algorithm
标 题: Re: 百度试题 mp3搜索问题
发信站: 水木社区 (Wed Jul 25 21:00:48 2007), 站内

太牛了！

【 在 forcey (爱到无可救药) 的大作中提到: 】
: 标 题: Re: 百度试题 mp3搜索问题
: 发信站: 水木社区 (Wed Jul 25 18:11:24 2007), 站内
:
: 每个SONG_ID对应一个文本文件，文件里面每行一个URL_ID
: 这样前3个需求都很容易满足
:
: 然后把SONG_ID写成24位二进制，每6位一组分成4组，建立4级目录结构
: 这样限制条件也满足了
:
: 【 在 bbinn (明天的明天) 的大作中提到: 】
: : 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，将其置为不可用
: 内存里放个bitset就解决了
: : 限制条件：内存占用不超过 1G，单个文件大小不超过 2G，一个目录下的文件数不超过 128 个。
: : 为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？
:
:
: –
: Only two things are infinite, the universe and human stupidity,
: and I am not sure about the former.
:
: — Albert Einstein
:
:
: ※ 修改:·forcey 于 Jul 25 18:11:43 修改本文·[FROM: 202.106.180.*]
: ※ 来源:·水木社区 newsmth.net·[FROM: 202.106.180.*]

–
- 不谈金钱,不谈妇女,不谈琐事

※ 来源:·水木社区 newsmth.net·[FROM: 211.99.222.*]

[本篇全文] [回复文章] [本篇作者：SeeKee] [回信给作者] [进入讨论区] [返回顶部]5发信人: SeeKee (寻找梦起飞的地方), 信区: Algorithm
标 题: Re: 百度试题 mp3搜索问题
发信站: 水木社区 (Wed Jul 25 21:25:40 2007), 站内

太多io操作了。

【 在 bbinn (明天的明天) 的大作中提到: 】
: 太牛了！

–

※ 来源:·水木社区 newsmth.net·[FROM: 61.148.100.*]

[本篇全文] [回复文章] [本篇作者：forcey] [回信给作者] [进入讨论区] [返回顶部]6发信人: forcey (爱到无可救药), 信区: Algorithm
标 题: Re: 百度试题 mp3搜索问题
发信站: 水木社区 (Wed Jul 25 21:30:08 2007), 站内

系统会自动把剩下的内存用来缓存频繁访问的文件的

如果按照楼上某位兄弟的做法，把小列表放内存把大列表放硬盘，
不能保证小列表都是频繁访问的列表

【 在 SeeKee (寻找梦起飞的地方) 的大作中提到: 】
: 太多io操作了。