两道笔试题帮忙求解,在线等,谢谢

gbl777 2006-04-14 10:03:15
1. 寻找热门查询:
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串

的长度为1-255字节。假设目前有一千万个记录,
这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个

。一个查询串的重复度越高,说明查询它的用户越多,
也就是越热门。请你统计最热门的10个查询串,要求使用的内存不能超过1G。
(1)请描述你解决这个问题的思路;
(2)请给出主要的处理流程,算法,以及算法的复杂度。


2.集合合并:
给定一个字符串的集合,格式如:
{aaa bbb ccc}, {bbb ddd},{eee fff},{ggg},{ddd hhh}
要求将其中交集不为空的集合合并,要求合并完成后的集合之间无交集,例如上例应

输出
{aaa bbb ccc ddd hhh},{eee fff}, {ggg}
(1)请描述你解决这个问题的思路;
(2)请给出主要的处理流程,算法,以及算法的复杂度
(3)请描述可能的改进(改进的方向如效果,性能等等,这是一个开放问题)。
...全文
342 5 打赏 收藏 转发到动态 举报
AI 作业
写回复
用AI写文章
5 条回复
切换为时间正序
请发表友善的回复…
发表回复
chenhu_doc 2006-04-15
  • 打赏
  • 举报
回复
哈哈,进来学习。
jixingzhong 2006-04-15
  • 打赏
  • 举报
回复
第二个看你的集合是怎么保存的 ...

采用全排列思想,
两个两个集合判断,
有交集的则合并 ...

重复至任意集合的交集为空后输出结果即可 ~
gbl777 2006-04-14
  • 打赏
  • 举报
回复
非常感谢sharpdew(风刃)
?
第一题已经有思路了,第二题具体怎么用哈希呢,再给点提示好吗
xiaosong8584 2006-04-14
  • 打赏
  • 举报
回复
我是来看贴的
sharpdew 2006-04-14
  • 打赏
  • 举报
回复
既然你重贴,我也重贴一下吧^_^:
1. 最近时有公司出这种从几百万词条中找出频率最大的前几条或者重复的条目的问题。
对于这种问题实际上并不需要太多所谓的搜索专业知识,想想数据库是怎么实现或者数据结构中关于词典索引的章节就不难知道,这些题目的解决办法不外乎,采用二种数据结构:
树(二叉树,Trie树和B树)和哈希表。对于300万词条来说,构建一个开地址哈希肯定用不了1G内存,如果还不放心,就构建一棵Trie树,如果还怕内存不够就构建B+树进行多级索引。至于复杂度分析,稍微回忆一下你的数据结构书吧。
稍微补充一下,为啥要用B+树就是为了解决内存中不能载入全部数据的时候用来分级载入数据,这样可以充分利用内存的换入换出来解决海量数据操作的问题。这和操作系统的文件系统设计以及数据库实现原理是相似的。

2. 又是字符串,而且是无重复字符串问题,那么你应该立即想到构建Trie树了吧,不错,不过这次用哈希更简单。

70,023

社区成员

发帖
与我相关
我的任务
社区描述
C语言相关问题讨论
社区管理员
  • C语言
  • 花神庙码农
  • 架构师李肯
加入社区
  • 近7日
  • 近30日
  • 至今
社区公告
暂无公告

试试用AI创作助手写篇文章吧