海量数据处理面试题

目录

一.位图应用

二.布隆过滤器

三.哈希切割

一.位图应用

1. 给定100亿个整数，设计算法找到只出现一次的整数？

        对于这道题100亿个整数大概占用40G,1G=2^30byte,所以直接保存是不合适的,可以使用两个位图来处理,用00表示出现0次的,01表示出现一次的,10表示出现2次及以上的的

class solution
{
    public:
        void set(size t x)
        {
            if(bsl.test(x)==false && bs2.test(x)== false)//00
            {
                bsl.reset(x);
                bs2.set(x);// 01
            }
            else if(bsl.test(x)==false && bs2.test(x)== true) // 01
            {
                bsl. set(x);
                bs2.reset(x); // 10
            }
        }
    private:
        bitset _bs1;
        bitset _bs2;
};

这样就可以找出01的数,遍历所有整数,为01的就是出现一次的

2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

        方案1:将其中一个文件1的整数映射到一个位图中，读取另外一个文件2中的整数，判断在不在位图，在就是交集。消耗500M内存

        方案2:将文件1的整数映射到位图1中，将文件2的整数映射到位图2中，然后将两个位图中的数按位与。与之后为1的位就是交集。消耗内存1G

3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

         这道题和1的思路是一样的,用两个位图处理,00表示出现一次的,01表示出现一次的,10表示出现两次的,11表示出现三次及以上的

二.布隆过滤器

1.给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出 精确算法和近似算法

        query一般是sql查询语句或网络请求的url等,一般是一个字符串

        100亿个query占用多少空间?假设一个query平均30-60byte,100亿个大概300-600G

近似算法:

        将文件一的query映射到一个布隆过滤器,读取文件二的query,判断在不在布隆过滤器中

        缺陷:交集中有些数不准确,由于布隆过滤器的误判.所以一些不是交集的数也可能存在

精确计算:

        这两个文件在300-600G,没有合适的数据结构可以准确的找出交集,文件很大不能都放到内存中,所以我们可以把文件切成多个小文件,小文件数据加载到内存中

        切成多少份:一般切出来的一个小文件的大小能够放进内存中即可,这里有300-600G,切为1000份,每份300-600M,有1G内存可以放下

        如果是平均切分,那么A0可以放到内存中存储到一个set中,B0~B999小文件中的数据都需要和A0比较,以此类推,这样的优势是将部分数据放到内存中,不是暴力比较,A0的数据放到set中,效率高一些

        如果不平均切分,可以使用哈希切分,i=hashstr(query)%1000,i是多少,query就进入第Ai,Bi的文件中,文件A和文件B都这样处理

        这样的好处是:A和B中相同的query一定进入到编号相同的Ai和Bi小文件,所以下面只需要比较编号相同的找交集

2.如何扩展BloomFilter使得它支持删除元素的操作

        将每个位标记成计数器

        那么到底用几个位表示计数器?给的位如果少了,多个值映射一个位置就会导致计数器溢出.比如1byte最多计数到256,如果有260各值映射到一个位置,就会出问题,但是如果使用更多的位映射一个位置,空间消耗就大了,会影响布隆过滤器的优势——节省空间

三.哈希切割

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？ 与上题条件相同，如何找到topK的IP？

        首先这里需要做的是统计次数,我们一般用kv模型的map解决,但是这里的问题是有超过100G数据,放不到内存中

        所以我们先创建1000个小文件A0~A999,读取IP计算出i=hashstr(IP)%1000,i是多少,IP就进入多少的小文件中,相同的IP一定在同一个小文件中

        map<string,int> countMap,读取Ai中的IP统计出次数,一个读取完clear再读取下一个

        使用一个pair<string,int> max记录出现次数最多的IP,就可以求出次数最多的IP地址

        topK的问题我们需要创建堆解决