登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

银河里的星星

落在人间

 
 
 

日志

 
 

面试题目-大数据量专题  

2009-09-29 12:59:26|  分类: 算法与acm |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1. 给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL。 

2. 有10个文件,每个文件1G, 每个文件的每一行都存放的是用户的query,每个文件的query都可能重复。要你按照query的频度排序
 
3. 有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16个字节,内存限制大小是1M。返回频数最高的100个词

4.海量日志数据,提取出某日访问百度次数最多的那个IP。

5.2.5亿个整数中找出不重复的整数,内存空间不足以容纳这2.5亿个整数。

6.海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。

7.怎么在海量数据中找出重复次数最多的一个

8.上千万or亿数据(有重复),统计其中出现次数最多的前N个数据。

统计可以用hash,二叉数,trie树。对统计结果用堆求出现的前n大数据。增加点限制可以提高效率,比如 出现次数>数据总数/N的一定是在前N个之内

9.1000万字符串,其中有些是相同的(重复),需要把重复的全部去掉,保留没有重复的字符串。请问怎么设计和实现?

10.一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前十个词。请给出思想,给时间复杂度分析。

11.一个文本文件,也是找出前十个最经常出现的词,但这次文件比较长,说是上亿行或者十亿行,总之无法一次读入内存,问最优解。

12.有10个文件,每个文件1G, 每个文件的每一行都存放的是用户的query,每个文件的query都可能重复要按照query的频度排序

13.100w个数中找最大的前100个数

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

15.一共有N个机器,每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。
如何找到N^2个数的中数(median)?

转载及引用请注明作者:phylips@bmy
  评论这张
 
阅读(4484)| 评论(0)

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018