找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索

面试剖析

1 点赞 1 评论

【守望者 海量数据】最大间隙问题

507 次浏览    2014-09-24 12:10    显示评论
问题描述: 给定n个实数,求着n个实数在实轴上向量2个数之间的最大差值,要求线性的时间算法。 查看更多>>
思路:

方案1:最先想到的方法就是先对这n个数据进行排序,然后一遍扫描即可确定相邻的最大间隙。但该方法不能满足线性时间的要求。故采取如下方法:

s> 找到n个数据中最大和最小数据ma ...
zhouy
2014-10-17 14:33

0 点赞 2 评论

【守望者 海量数据】海量数据中验证数据是否存在?

390 次浏览    2014-09-24 14:34    显示评论
问题描述: 腾讯经典面试题:给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中? 查看更多>>
参考思路:

速度相当的快,应该是在小于o(n)的时间内就可以解决问题。但是rand()产生的随机数范围有限制,可以想想其他办法产生随机数。可以看到,所用到的内存很小,而且程序反应速度也很快。这种方法 ...
zhouy
2014-10-17 14:35

0 点赞 1 评论

【守望者 海量数据】海量数据的top10问题

312 次浏览    2014-09-24 12:08    显示评论
问题描述: 海量数据分布在100台电脑中,想个办法高效统计出这批数据的TOP10。 查看更多>>
参考答案:

方案1:

s 在每台电脑上求出TOP10,可以采用包含10个元素的堆完成(TOP10小,用最大堆,TOP10大,用最小堆)。比如求TOP10大,我们首先取前10个元素调整成最小堆,如果发现, ...
zhouy
2014-10-17 14:36

0 点赞 1 评论

【守望者 海量数据】海量日志数据,提取出某日访问百度次数最多的那个IP。

256 次浏览    2014-09-24 12:06    显示评论
问题描述: 海量日志数据,提取出某日访问百度次数最多的那个IP。 查看更多>>
参考答案:

方法: 计数法
    假设一天之内某个IP访问百度的次数不超过40亿次,则访问次数可以用unsigned表示.用数组统计出每个IP地址出现的次数,  即可得到访问次数最大的IP ...
zhouy
2014-10-17 14:41

0 点赞 1 评论

【守望者 海量数据】海量数据query的频度排序。

286 次浏览    2014-09-24 12:05    显示评论
问题描述: 有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。要求你按照query的频度排序。 查看更多>>
参考答案:

方法一:类似第1题方法一,扫描所有文件,使用hash将query重新散到不同文件中,这样相同的query一定在同一个文件中。
对每个小文件进行计数。最后归并结果。

方法二:类 ...
zhouy
2014-10-17 14:42

0 点赞 1 评论

【守望者 海量数据】海量数据中找出重复的url。

301 次浏览    2014-09-24 12:03    显示评论
问题描述: 给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url? 查看更多>>
参考答案:

分析:
1MB = 2^20 = 10^6 = 100万
1GB = 2^30 = 10^9 = 1亿

50亿url = 5G*64 Byte

整理方法如下:
方法一:
分别扫描A,B文件,根据ha ...
zhouy
2014-10-17 14:43

0 点赞 1 评论

[守望者 算法面试题] 海量短信中找重复的前10条

1884 次浏览    2014-09-23 13:33    显示评论
问题描述: 有一千万条短信,有重复,以文本文件的形式保存,一行一条,有重复。请用5分钟时间,找出重复出现最多的前10条。 查看更多>>
思路:

方法1:可以用哈希表的方法对1千万条分成若干组进行边扫描边建散列表。第一次扫描,取首字节,尾字节,中间随便两字节作为hash Code,插入到hash table中。并记录其地址和信息长度和重复次数,1 ...
zhouy
2014-10-17 14:55

推荐阅读

[守望者   java初中级视频]22_javaNIO,AIO编程
[守望者 java初中级视频]22_javaNIO,
内容简介:本课程介绍阻塞,非阻塞,同步和异步的基本概念,介绍javaNIO,AIO
[守望者 算法视频]01_数据存储(链表与数组)
[守望者 算法视频]01_数据存储(链表与
本章重点介绍数据的在计算机的存储方式 :连续存储(数组)与链式存储,同时
【守望者 观点】智能路由和Wi-Fi探针是一对好基友
【守望者 观点】智能路由和Wi-Fi探针是
智能路由与Wifi探针可以收集用户行为,同时可以收集用户MAC地址,还可以跟踪
【守望者 游戏项目】基于cocos2d-x的跑酷游戏项目教程
【守望者 游戏项目】基于cocos2d-x的跑
Cocos2d-x跑酷游戏项目教程Cocos2d-x跑酷游戏项目教程cocos2d-x特性cocos2
【守望者 linux项目】mini WEB服务器设计
【守望者 linux项目】mini WEB服务器设
以下是曾经Watchmen一个朋友学习网络编程时设计的一个简单的MiniWEB服务器。
【守望者 linux项目】linux下的FTP服务器与客户端,作者 灯下野狐 ...
【守望者 linux项目】linux下的FTP服务
本项目是一个完整的FTP服务器及FTP客户端设计示例,对于需要学习网络编程项目
【解读】什么样性格的人会被夸性格好
【解读】什么样性格的人会被夸性格好
守望者:性格决定命令。好的性格意识着给别人面子,能接受别人装逼,而且以上
[守望者 linux视频]01_开发工具与开发平台
[守望者 linux视频]01_开发工具与开发
本课主要介绍gcc,gdb等系列开发工具,开始编写程序之旅。要求理解Linux开发平
[守望者 算法视频]08_数据查找_hash算法
[守望者 算法视频]08_数据查找_hash算
守望者:普通逐个查找O(n),组织方式可以无序的数组或者普通链表。已经排序的
【观点】闲聊阿里“996",全集团ALL IN无线策略及加班之意义 ...
【观点】闲聊阿里“996",全集团ALL IN
守望者:几乎的所有的员工都不喜欢8小时之外的工作,而几乎所有的老板都期望