搜索引擎方向面试的两个难题
1.搜索的输入信息是字符串,统计300万输入信息中的最热门的前十条,每次输入的字符不超过255个字节,内存使用只有一G,请描述算法,写出程序(C语言),空间和时间复杂度.

2.国内的一些贴吧,如baidu,有几十万个主题,假设每个主题都有上亿个跟贴,怎样设计系统速度最好,请描述思想,写出算法(C语言),空间和时间复杂度.

[解决办法]
1.用hash统计各个输入出现的次数，自己处理冲突，可以用链表，全部输入空间不会超过1G，时间复杂度是O(n),然后扫描一遍hash表可以线性的求出前十名，时间复杂度也是O（n）
关键 在于hash函数以及 hash表大小的设置

2.第二题应该是个系统设计题吧，应该设计系统的数据结构和主要操作。
主题其实也可以用hash表来保存，或者用2叉平衡搜索树，至于跟贴可以用链式结构来保存帖子在磁盘文件中的位置。
第二题希望有牛人有更完善的答案
[解决办法]
第一用黑 ,cnt出次
11 struct data_s
12 {
13 char *key ;
14 int cnt ;
15 }
如果源文件, 可使用mmap映像.用不了1G物理存.
造需要48M存,
如sizeof(struct rb_tree) 度16, 3*16 = 48M
可一次性malloc(3*1024*1024* sizeof(struct rb_node))


[解决办法]
hash函数选择得好, hash表的确要好些,
但是300万数据不多,建表也很快, 在我的pc机上很快就出来了.

就第一题看来,只选最多的10个,该有更好的办法.


[解决办法]
这样是否要更好,
int keychar[256]
1. 以key第一个字符为索引,将数据分为256组.排序可以得到前10组的第一个字符.
2. 以第二个字符为索引,可以取得每一组的热门第二个字符
3. 根据一二步结果,得到100个指针数组, 排序得到最热门的前两个字符
4. 重复计算第3个,第4个.