这是一个创建于 3593 天前的主题，其中的信息可能已经有所发展或是发生改变。
先送上30家IT名企历年笔试面试题集合，请转发分享给身边的码农吧。
http://weibo.com/2165760972/BEpE59YSp
我们做了一个专门面向IT互联网行业程序员的求职笔试面试备考的题库网站
牛客网 http://www.nowcoder.com?from=v2ex
本月我们会在论坛持续发贴，每天放出1-3道题目，欢迎大家跟帖解答，最先正确解答出来的朋友将会获得话费充值、笔记本等礼物。获奖的朋友名单会在第二天公布。
今日题目，来自百度
注意：请尽可能详细描述你的数据结构、系统架构、设计思路等。建议多写一些伪代码或者流程说明。
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 个。
为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何
多机分布处理
这个题目是我们挑战活动的百元难题之一，在牛客网的回答被采纳为系统推荐就可获得100奖金
来自http://www.nowcoder.com/questionTerminal/d3516831b19c4c608704280d31c4785d?from=v2ex
更多难题现金求解
http://www.nowcoder.com/activity/challenge?from=v2ex
 |
1
xcv58 2015-01-09 11:13:34 +08:00
这种读多写少的很适合 mongodb ，但百度的题目 就不答了。
|
 |
2
december 2015-01-09 11:47:49 +08:00  1
既然都允许使用社交账号登陆了。干嘛还非得让用户再填写邮箱呢。
|
 |
3
egrcc 2015-01-09 11:52:25 +08:00
您这是。。天天发呀
|
 |
6
sleeperqp 2015-01-09 16:01:09 +08:00 1
//内存
//SONG的主要数据结构 struct SONG_NODE{ int song_id; list<int>buffer; //缓存为8个URL_ID; string file; } //这里假设失效URL较少(╭(╯^╰)╮ 不然大部分失效了你还搜什么) //根据URL_ID即可该URL知道是否失效 map<int,bool>IsNotaURL //文件为SONG的URL列表 //SONG的URL列表 //这个比较多变 SONG_ID:{URL_ID,...URL_ID} //或者使用一些压缩编码比如VB编码等。 2) 给定一个 SONG_ID，为其添加一个新的 URL_ID 根据SONG_ID往其buffer中添加URL_ID 若buffer已满 则先将buffer与SONG的URL列表文件进行合并。 否则添加URL_ID进buffer 3) 添加一个新的 SONG_ID new SONG_NODE，初始化一下。 4) 给定一个 URL_ID，将其置为不可用 在IsURL中设置即可,IsNotaURL(URL_ID) = true; 1) 通过 SONG_ID 搜索一首歌的 URL_ID，给出 URL_ID 计数和列表 给定URL_ID,读入URL的URL列表,并结合buffer与IsNotaURL输出URL列表，统计URL_ID计数即可 细节问题: 1.题目要求为1G内存，所以buffer大致能用2^30/2^24=2^6 除去一些别的大概能给2^5即8个URL_ID 2.buffer与SONG合并: 首先是通过SONG_ID的查找SONG的URL列表问题:通过SONG_ID映射比如SONG_ID%128找到SONG所在文件 然后读取信息，合并，在文件中定位写回。 其次使用压缩编码进行节省空间，VB编码等都可以。这样就不会超过单文件2G的要求了。(只要不把URL_ID都写入一个文件基本就不会超过这个限制) 3.定时更新:定时将列表,buffer,IsNotaURL合并更新。 数据量增大: 一个方法是:通过SONG_ID(这里可能使用long long类型),通过SONG_ID的映射关系(如mod128)将SONG_ID处理对应到相关的机器上。 PS:这里数据量增大应该是可以加大内存了,╭(╯^╰)╮终于可以加大buffer。 |
 |
7
zhangchioulin 2015-01-09 17:16:17 +08:00
@sleeperqp 看不懂您的回答（哭）看来我离磨练还太少。。。
|
|
10
sleeperqp 2015-01-09 22:19:06 +08:00
@zhangchioulin 别= = 应该是我没写好吧- -
|
 |
11
mingyun 2015-01-11 16:13:33 +08:00
面试能真正用上吗
|
Select Language