面试剖析守望者成才网,在线教育,watchmen,C和指针,linux视频,面试视频 -

面试剖析

0 点赞 1 评论

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

312 次浏览 2014-09-24 12:08 显示评论

问题描述: 海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。查看更多>>

1 参考答案： 方案1： s 在每台电脑上求出TOP10，可以采用包含10个元素的堆完成（TOP10小，用最大堆，TOP10大，用最小堆）。比如求TOP10大，我们首先取前10个元素调整成最小堆，如果发现， ... zhouy 2014-10-17 14:36

0 点赞 1 评论

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

256 次浏览 2014-09-24 12:06 显示评论

问题描述: 海量日志数据，提取出某日访问百度次数最多的那个IP。查看更多>>

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

1

参考答案：

方法: 计数法
假设一天之内某个IP访问百度的次数不超过40亿次,则访问次数可以用unsigned表示.用数组统计出每个IP地址出现的次数,  即可得到访问次数最大的IP地址.
IP地址是32位的二进制数,所以共有N=2^32=4G个不同的IP地址, 创建一个unsigned count[N];的数组,即可统计出每个IP的访问次数,而sizeof(count) == 4G*4=16G, 远远超过了32位计算机所支持的内存大小,因此不能直接创建这个数组.下面采用划分法解决这个问题.
假设允许使用的内存是512M,  512M/4=128M 即512M内存可以统计128M个不同的IP地址的访问次数.而N/128M =4G/128M = 32 ,所以只要把IP地址划分成32个不同的区间,分别统计出每个区间中访问次数最大的IP, 然后就可以计算出所有IP地址中访问次数最大的IP了.
因为2^5=32, 所以可以把IP地址的最高5位作为区间编号, 剩下的27为作为区间内的值,建立32个临时文件,代表32个区间,把相同区间的IP地址保存到同一的临时文件中.
例如:
ip1=0x1f4e2342
ip1的高5位是id1  =  ip1 >>27 = 0x11 = 3
ip1的其余27位是value1  =  ip1 &0x07ffffff = 0x074e2342
所以把 value1 保存在tmp3文件中.
由id1和value1可以还原成ip1, 即 ip1 =(id1<<27)|value1
按照上面的方法可以得到32个临时文件,每个临时文件中的IP地址的取值范围属于[0-128M),因此可以统计出每个IP地址的访问次数.从而找到访问次数最大的IP地址
程序源码:
test.cpp是c++源码.
print?
#include <fstream>
#include <iostream>
#include <ctime>

using namespace std;
#define N 32          //临时文件数

#define ID(x)  (x>>27)                //x对应的文件编号
#define VALUE(x) (x&0x07ffffff)       //x在文件中保存的值
#define MAKE_IP(x,y)  ((x<<27)|y)    //由文件编号和值得到IP地址.

#define MEM_SIZE  128*1024*1024    //需分配内存的大小为 MEM_SIZE*sizeof(unsigned)

char* data_path="D:/test/ip.dat";       //ip数据

//产生n个随机IP地址
void make_data(const int& n)
{
ofstream out(data_path,ios::out|ios::binary);
srand((unsigned)(time(NULL)));
if (out)
{
      for (int i=0; i<n; ++i)
      {
         unsigned val=unsigned(rand());
         val = (val<<24)|val;             //产生unsigned类型的随机数

         out.write((char *)&val,sizeof (unsigned));
      }
}
}

//找到访问次数最大的ip地址
int main()
{
//make_data(100);    //
make_data(100000000);    //产生测试用的IP数据
fstream arr[N];

for (int i=0; i<N; ++i)                //创建N个临时文件
{
      char tmp_path[128];    //临时文件路径
      sprintf(tmp_path,"D:/test/tmp%d.dat",i);
      arr.open(tmp_path, ios::trunc|ios::in|ios::out|ios::binary);  //打开第i个文件

      if( !arr)
      {
         cout<<"open file"<<i<<"error"<<endl;
      }
}

ifstream infile(data_path,ios::in|ios::binary); //读入测试用的IP数据
unsigned data;

while(infile.read((char*)(&data), sizeof(data)))
{
      unsigned val=VALUE(data);
      int key=ID(data);
      arr[ID(data)].write((char*)(&val), sizeof(val));          //保存到临时文件件中
}

for(unsigned i=0; i<N; ++i)
{
      arr.seekg(0);
}
unsigned max_ip = 0; //出现次数最多的ip地址
unsigned max_times = 0;    //最大只出现的次数

//分配512M内存,用于统计每个数出现的次数
unsigned *count = new unsigned[MEM_SIZE];

for (unsigned i=0; i<N; ++i)
{
      memset(count, 0, sizeof(unsigned)*MEM_SIZE);

      //统计每个临时文件件中不同数字出现的次数
      unsigned data;
      while(arr.read((char*)(&data), sizeof(unsigned)))
      {
         ++count[data];
      }

      //找出出现次数最多的IP地址
      for(unsigned j=0; j<MEM_SIZE; ++j)
      {
         if(max_times<count[j])
         {
            max_times = count[j];
            max_ip = MAKE_IP(i,j);       // 恢复成原ip地址.
         }
      }
}
delete[] count;
unsigned char *result=(unsigned char *)(&max_ip);
printf("出现次数最多的IP为:%d.%d.%d.%d,共出现%d次",
      result[0], result[1], result[2], result[3], max_times);
}

zhouy

2014-10-17 14:41

0 点赞 1 评论

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

286 次浏览 2014-09-24 12:05    显示评论

问题描述: 有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。查看更多>>

1

参考答案:

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

方法二：类 ...

zhouy
2014-10-17 14:42

1

参考答案:

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

方法二：类似第1题方法二，但用的是Bloom Filter的变化SBF（Spectral Bloom Filter）

Bloom Filter的变种:
CBF（Counting Bloom Filter）通常采用固定的4bit的counter来记录出现频次，可以保证极小溢出概率，CBF使用counter只为了实现元素删除。
SBF（Spectral Bloom Filter）若想要支持元素的出现频率查询，4位远远不够，这就需要动态大小的counter

Bloom Filter介绍：
Bloom Filter概念和原理
Counting Bloom Filter
Spectral Bloom Filter

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？查看更多>>

1

参考答案:

分析：
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

1

参考答案:

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

50亿url = 5G*64 Byte

整理方法如下：
方法一：
分别扫描A,B文件，根据hash(url)%k值将url划分到不同的k个文件中，如a1，a2,....ak;b1，b2，...bk，（保存时可以把hash值也保存进去，避免以后重复计算) 对每一个hash段的两个文件，如a1，b1, 读取a1到一个HashSet中，再将b1投入，用链表保持hash值有冲突且url相等的url。

分割的文件数k: k> 5G*64/4G/2 = 160
当然该方法需要更多的磁盘空间

方法二：
使用Bloom filter。假设布隆过滤器的错误率为0.01，则位数组大小m约为输入元素个数n的13倍，此时需要的哈希函数k约为8个。（Google黑板报中介绍其用来存储垃圾邮件地址）

n = 5G
m = 5G * 13 = 65G = 650亿即需要650亿个bit位才能达到错误率0.01
而我们拥有的内存可容纳bit位个数：4G * 8bit = 32G bit = 320亿，按此实现错误率大于0.01。

方法三：
使用索引。想想，可以讲A存入数据库表并建立主键和索引，再将B读入插入数据库表，若报错则是重复的url。

zhouy

2014-10-17 14:43

0 点赞 0 评论

【守望者名企笔试题目】2014哈尔滨阿里巴巴笔试题

212 次浏览 2014-09-24 11:47

问题描述: 1. 单选题　　1. 假设把整数关键码K散列到N个槽列表，以下哪些散列函数是好的散列函数　　A: h(K)=K/N;　　B: h(K)=1;　　C: h(K)=K mod N;　　D: h(K)=(K+rand(N)) mod N, rand(N)返回0到N-1的整数　　2. 下面排序 ... 查看更多>>

0 点赞 0 评论

【守望者名企笔试题目】百度2014校园招聘深度学习算法研发工程师笔试题

962 次浏览 2014-09-24 11:35

问题描述: 一、简答题　　1.深度神经网络目前有哪些成功的应用?简述原因。(10分)　　2.列举不同进程共享数据的方式(至少三种)。(10分)　　3.对于N个样本，每个样本为D维向量，采用欧式距离使用KNN做类预测。(10分)　　1).给出 ... 查看更多>>

0 点赞 0 评论

[守望者算法]消除球

154 次浏览 2014-09-24 11:24

问题描述: 给一列球，球的颜色可以不同，如果k个连续的球的颜色是一样的，那么我们可以把他们消去，得到的分数为 k*k，求如何消去得到的分数最高。查看更多>>

0 点赞 0 评论

[守望者算法]滑雪

246 次浏览 2014-09-24 11:22

问题描述: 一个哥们喜欢滑雪，为了获得刺激感，他跑到一个山头滑雪，想找到一个最长的路径滑下来。现在给一个M*N的矩阵，矩阵上每个点是这个点的高度，找到一条最长路，可以上下左右走，这条路上的高度应该是递减的。 ... 查看更多>>

0 点赞 0 评论

[守望者算法]大牛合唱

206 次浏览 2014-09-24 11:22

问题描述: 给出一个数轴，一些位置有牛，每头牛一个位置xi,以及一个听力值vi。当两头牛交谈时，需要的声音为距离*max(vi,vj). 问所有牛两两交谈的声音总和查看更多>>

0 点赞 0 评论

[守望者算法 ]均富卡

231 次浏览 2014-09-24 11:22

问题描述: 有两个无序序列a,b，长度都为n, 序列元素的值任意整数。通过交换a,b中的元素，使与之间的差最小。（微软面试）查看更多>>

0 点赞 0 评论

[守望者算法]最长凹子序列

177 次浏览 2014-09-24 11:21

问题描述: 从数组中去掉尽可能少的数，使得这个数组是先递减之后递增的。查看更多>>

0 点赞 0 评论

[守望者算法]特殊遍历要求

161 次浏览 2014-09-24 11:21

问题描述: 给一棵树的所有节点标号为数字1~n，使得任意数字标号相邻的两个节点树上距离不超过3。查看更多>>

0 点赞 0 评论

[守望者算法 ]越扫越黄

228 次浏览 2014-09-24 11:20

问题描述: 一个n*n的网格图，每一格是白色和黄色任意一种颜色，你点击一个格子的时候，这个格子和它上下左右四周的格子都变色（黄-白或者白-黄），现在给你一个初始的图，问你1.能否 2. 最少需要点多少次使这个图的颜色变成 ... 查看更多>>

0 点赞 0 评论

[守望者算法 ]石头与树

174 次浏览 2014-09-24 11:20

问题描述: 有一棵树，有一些石头，依次把石头放在树叶上，如果一个节点的叶子节点全有一个石头了，就可以把它们的石头去掉，并把其中的一个石头放在这个节点上，而这个结点就相当于一个叶子节点了，去掉的石头可以再用，问直到 ... 查看更多>>

0 点赞 0 评论

[守望者算法树]最矮的二叉搜索树

188 次浏览 2014-09-24 11:20

问题描述: 给一个排好序的数组，生成一个最矮的二叉搜索树。 Follow up: 如果数组里面有重复，并且重复的数只能放在左子树里，如何生成最矮的二叉搜索树。查看更多>>

		自动登录	找回密码
密码			立即注册

面试剖析

推荐阅读