30 家 IT 名企历年笔试面试题集合，（ 1 月 9 日更新）

先送上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

sleeperqp

2015-01-09 16:01:09 +08:00

//内存
//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。