1）给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？!
解决方法
将100G分成100份，将每个ip映射到相应文件中 ip_if=ip%100
找出每个文件中的出现次数最多的一个ip
再将100份里找出来的最多的一个放入一个哈希表中进行比较找出最大值
2）与上题条件相同，如何找到top K的IP？如何直接⽤用Linux系统命令实现？
解决方法
将100G分成100份，将每个ip映射到相应文件中 ip_if=ip%100
找出每个文件中的出现次数最多的k个ip
再将100份里找出来的最多的k个放入一个哈希表中进行比较找出最大的k 个
3）给定100亿个整数，设计算法找到只出现一次的整数!
将100亿个数分拆成1000份文件，再将每份文件里使用位图，并用两位bit表示数字出现的次数，00存出现0次的数，01存放出现1次的数，10存放出现多次的数，11舍弃，再将1000份中出现一次的数全部合并到一个文件里存放即可
4）给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集!
将第一个文件里的数用哈希映射到1000个文件中，将第二个文件用同样的哈希映射到另1000个文件中，然后比较每个哈希映射相同的文件即可
5）1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数!
将100亿个数分拆成1000份文件，再将每份文件里使用位图，并用两位bit表示数字出现的次数，00存出现0次的数，01存放出现1次的数，10存放出现2次的数，11舍弃，再将1000份中出现次数不超过二的数全部合并到一个文件里存放即可
6）给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？
算法和近似算法!
精确算法：
将两个文件分别存入相同哈希算法的1000个哈希桶（共两千个）文件，再在每个文件找出相同的query
近似算法：
利用布隆过滤器进行比较
7）如何扩展BloomFilter使得它支持删除元素的操作？!
将bloomfilter中每一位扩展成一个技术为，例如00表示无，01表示1，当没删除一个，计数器减1，直到减为0为止
8）如何扩展BloomFilter使得它支持计数操作？!
同上题思路
9）给上千个文件，每个文件大小为1K—100M。给n个词，设计算法对每个词找到所有包含它的文件，你只有100K内存!
对上千个文件生成1000个布隆过滤器，并将1000个布隆过滤器存入一个文件中，将内存分为两份，一分用来读取布隆过滤器中的词，一块用来读取文件，知道将每个布隆过滤器读完为止
10）有一个词典，包含N个英文单词，现在任意给一个字符串，设计算法找出包含这个字符串的所有英文单词!
？暂时不会
位图
<span style="font-size:18px;">#pragma once
#include<vector>
#include<iostream>
using namespace std;
class BitMap
{
public:
BitMap(size_t range)
{
_bitMap.resize((range>>5) +1);
}
void Set(size_t x)
{
size_t index=x>>5;
size_t num =x%32;
//_bitMap[index]|=tmp;
_bitMap[index]=(1<<num);
}
void Reset(size_t x)
{
size_t index=x>>5;
size_t num =x%32;
size_t tmp=0;
tmp<<=num;
_bitMap[index] &=(~(tmp));
}
bool Test(size_t x)
{
size_t index=x>>5;
size_t num =x%32;
size_t tmp=1;
tmp<<=num;
_bitMap[index] &=tmp;
return _bitMap[index];
}
~BitMap()
{}
protected:
vector<size_t> _bitMap;
};</span>
布隆过滤器
<span style="font-size:18px;">#pragma once
#include <iostream>
#include <string>
#include <vector>
#include "BitMap.h"
using namespace std;
struct __HashFunc1
{
size_t BKDRHash(const char *str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = hash * 131 + ch; // 也可以乘以31、131、1313、13131、131313..
}
return hash;
}
size_t operator()(const string& str)
{
return BKDRHash(str.c_str());
}
};
struct __HashFunc2
{
size_t SDBMHash(const char *str)
{
register size_t hash = 0;
while (size_t ch = (size_t)*str++)
{
hash = 65599 * hash + ch;
//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;
}
return hash;
}
size_t operator()(const string& str)
{
return SDBMHash(str.c_str());
}
};
struct __HashFunc3
{
size_t RSHash(const char *str)
{
register size_t hash = 0;
size_t magic = 63689;
while (size_t ch = (size_t)*str++)
{
hash = hash * magic + ch;
magic *= 378551;
}
return hash;
}
size_t operator()(const string& str)
{
return RSHash(str.c_str());
}
};
struct __HashFunc4
{
size_t APHash(const char *str)
{
register size_t hash = 0;
size_t ch;
for (long i = 0; ch = (size_t)*str++; i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
}
}
return hash;
}
size_t operator()(const string& str)
{
return APHash(str.c_str());
}
};
struct __HashFunc5
{
size_t JSHash(const char *str)
{
if(!*str)
return 0;
register size_t hash = 1315423911;
while (size_t ch = (size_t)*str++)
{
hash ^= ((hash << 5) + ch + (hash >> 2));
}
return hash;
}
size_t operator()(const string& str)
{
return JSHash(str.c_str());
}
};
template<class K=string
,class HashFunc1=__HashFunc1
,class HashFunc2=__HashFunc2
,class HashFunc3=__HashFunc3
,class HashFunc4=__HashFunc4
,class HashFunc5=__HashFunc5>
class RefBloomFilter
{
public:
RefBloomFilter(size_t num)
:_range(num*5)
,_bitMap(num*5)
{}
void Set(const K& key)
{
size_t index1=HashFunc1()(key)%_range;
size_t index2=HashFunc2()(key)%_range;
size_t index3=HashFunc3()(key)%_range;
size_t index4=HashFunc4()(key)%_range;
size_t index5=HashFunc5()(key)%_range;
_bitMap.Set(index1);
_bitMap.Set(index2);
_bitMap.Set(index3);
_bitMap.Set(index4);
_bitMap.Set(index5);
cout<<index1<<endl;
cout<<index2<<endl;
cout<<index3<<endl;
cout<<index4<<endl;
cout<<index5<<endl<<endl;
}
bool Reset(const K& key)
{
size_t index1=HashFunc1()(key)%_range;
size_t index2=HashFunc2()(key)%_range;
size_t index3=HashFunc3()(key)%_range;
size_t index4=HashFunc4()(key)%_range;
size_t index5=HashFunc5()(key)%_range;
if(_bitMap[index1]==0
||_bitMap[index2]==0
||_bitMap[index3]==0
||_bitMap[index4]==0
||_bitMap[index5]==0)
return false;
_bitMap.Reset(index1);
_bitMap.Reset(index2);
_bitMap.Reset(index3);
_bitMap.Reset(index4);
_bitMap.Reset(index5);
cout<<index1<<endl;
cout<<index2<<endl;
cout<<index3<<endl;
cout<<index4<<endl;
cout<<index5<<endl<<endl;
return true;
}
bool Test(const K& key)
{
size_t index1=HashFunc1()(key)%_range;
size_t index2=HashFunc2()(key)%_range;
size_t index3=HashFunc3()(key)%_range;
size_t index4=HashFunc4()(key)%_range;
size_t index5=HashFunc5()(key)%_range;
if(_bitMap.Test(index1)!=0
&&_bitMap.Test(index2)!=0
&&_bitMap.Test(index3)!=0
&&_bitMap.Test(index4)!=0
&&_bitMap.Test(index5)!=0)
{
cout<<index1<<endl;
cout<<index2<<endl;
cout<<index3<<endl;
cout<<index4<<endl;
cout<<index5<<endl<<endl;
return true;
}
cout<<index1<<endl;
cout<<index2<<endl;
cout<<index3<<endl;
cout<<index4<<endl;
cout<<index5<<endl<<endl;
return false;
}
protected:
BitMap _bitMap;
size_t _range;
};
void test()
{
RefBloomFilter<> bf(1);
char* str1="http://blog.csdn.net/shangguan_1234";
char* str2="http://blog.csdn.net/shangguan_1235";
char* str3="http://blog.csdn.net/shangguan_1233";
char* str4="http://blog.csdn.net/shangguan_1232";
char* str5="http://blog.csdn.net/shangguan_1231";
bf.Set(str1);
bf.Set(str2);
bf.Set(str3);
bf.Set(str4);
bf.Set(str5);
cout<<bf.Test(str1)<<endl;
cout<<bf.Test(str2)<<endl;
cout<<bf.Test(str3)<<endl;
cout<<bf.Test(str4)<<endl;
cout<<bf.Test(str5)<<endl;
}</span>
欢迎大家继续关注慧邮件邮件营销平台，也可以在我们的慧邮件官网了解更多邮件营销技巧，大数据知识，也可以通过电话：400-666-5494联系到我们，更多精彩知识、活动等着你。