Information Retrieval Blog

是百度的一道题

寻找热门查询： 搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串 的长度为1-255字节。假设目前有一千万个记录， 这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个 。一个查询串的重复度越高，说明查询它的用户越多， 也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。 （1）请描述你解决这个问题的思路； （2）请给出主要的处理流程，算法，以及算法的复杂度。

2006年04月24日 15:31:00

求职应聘:百度网上笔试题

　　1 编程：

　　用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。

　　2 编程：

　　用C语言实现函数void * memmove(void *dest,const void *src,size_t n)。memmove

　　函数的功能是拷贝src所指的内存内容前n个字节

　　到dest所指的地址上。

　　3 英文拼写纠错：

　　在用户输入英文单词时，经常发生错误，我们需要对其进行纠错。假设已经有一个包

　　含了正确英文单词的词典，请你设计一个拼写纠错的程序。

　　(1)请描述你解决这个问题的思路；

　　(2)请给出主要的处理流程，算法，以及算法的复杂度；

　　(3)请描述可能的改进(改进的方向如效果，性能等等，这是一个开放问题)。

　　4 寻找热门查询：

　　搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串

　　的长度为1-255字节。假设目前有一千万个记录，

　　这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个

　　。一个查询串的重复度越高，说明查询它的用户越多，

　　也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。

　　(1)请描述你解决这个问题的思路；

　　(2)请给出主要的处理流程，算法，以及算法的复杂度。

　　5 集合合并：

　　给定一个字符串的集合，格式如：

　　{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}

　　要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应

　　输出

　　{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}

　　(1)请描述你解决这个问题的思路；

　　(2)请给出主要的处理流程，算法，以及算法的复杂度

　　(3)请描述可能的改进(改进的方向如效果，性能等等，这是一个开放问题)。

Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=675148

mp3搜索引擎题目讨论

2007-12-20 11:48

题目是：“假设一个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_ID3) 添加一个新的SONG_ID4) 给定一个URL_ID，将其置为不可用

限制条件：内存占用不超过1G，单个文件大小不超过2G，一个目录下的文件数不超过128个。为获得最佳性能，请说明设计的数据结构、搜索算法，以及资源消耗。如果系统数据量扩大，该如何多机分布处理？