3. 面试题实战
3.1 哈希切割
❓ 给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
✅ 找到次数这种问题，我们首先想到的就是map，但是IP地址一般是127.0.0.1这种类型，超过100G的内容没办法放在一个map中，所以没有办法这样使用。那么我们需要做的事情就是将这内容进行切分，然后对切分的小文件进行次数统计。注意，这里的切分是有一些讲究的。如果直接对这些文件进行平均切分的话，是没有办法在一个小文件中计算出同一个IP地址出现的次数的。所以这里需要用到哈希切割。使用一个哈希函数将IP转换成整型，然后让出现哈希冲突的IP放进同一个小文件中，然后分别统计这些小文件中IP每个IP出现的次数。这种方法的巧妙之处在于利用哈希函数将所有相同的IP都放在了同一个文件中，所以统计每个小文件的时候都能够拿到当前IP出现的次数。
注：可以将进行该方法之后的小文件当作一个一个的哈希桶来看。
❓如果分成的小文件也过大怎么办？
✅ 这里的小文件可以分成两种情况：
- 该文件中冲突的IP很多，大多都是不同的IP，此时直接使用map是统计不下的，对于这个问题我们的解决方案是：换一个哈希函数，再次进行切分
- 该文件的冲突IP很多，大多数都是相同的IP，此时直接使用map是可以统计的下的，直接使用map统计即可。
❓那么其实问题又来了：怎么区分这两种情况呢？
✅实际上这里不需要区分，直接使用map统计即可，如果map的insert出现报错（相当于new失败），new失败之后会抛异常，此时捕捉异常即可，然后对次异常的处理就是情况一的方案。
❓ 与上题条件相同，如何找到top K的IP？
✅ 首先进行上述的操作，然后能够得到所有IP的出现次数，然后对这个数据使用优先级队列来存放，然后popK次，所得到的就是top K的IP。
3.2 位图的应用
❓给定100亿个整数，设计算法找到只出现一次的整数？
✅首先可以明确一点，就是对于100亿个整数，数据量过于大，因此这里考虑使用位图的方式来解决。题目要求我们找到只出现一次的数，分析一下，我们需要知道的数的状态，那么这个数的出现情况，我们需要关注的只有出现0次，出现1次，出现一次以上这三种情况，那么对于我们之前设计的位图来说，这里的改变就是两个位(00,01,10)来表示一个数的状态即可。
为了代码实现的方便，我们采用构建两个位图来做这件事情，第一个位图用来表示第一个位，第二个位图表示第二个位，那么就可以简单的手搓一个两个位图结合的类
template<size_t N> class twobitset { public: void set(size_t x) { if (!_bs1.test(x) && !_bs2.test(x))//00 { _bs2.set(x);//变成01 } else if (!_bs1.test(x) && _bs2.test(x))//01 { //变成10 _bs1.set(x); _bs2.reset(x); } // 10 不变 } void outputOnce()//打印只出现一次的数 { for (size_t i = 0; i < N; ++i) { if (!_bs1.test(i) && _bs2.test(i)) { cout << i << endl; } } cout << endl; } private: bitset<N> _bs1; bitset<N> _bs2; };
用这个类就可以很轻松的判断某个数是否只出现了一次，同时也实现了输出所有只出现了一次的数的接口，下面就简单写个测试函数试验一下
void test_twobitset() { twobitset<100> tbs; int a[] = { 2,4,56,67,6,34,1,5,6,4,3,33,5 }; for (auto e : a) { tbs.set(e); } tbs.outputOnce(); }
❓给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
✅拿到题目我们首先想到的就是使用位图的方式，将其中一个文件映射到位图中，然后遍历另一个文件确定在位图中是否存在。但是，对于这种方式，最终产生的结果需要进行一次去重，原因是当我们遍历的第二个文件中有重复的内容，此内容恰好又在交集中，那么此内容就将是重复的内容，因此需要对结果进行去重。
这里为了省略去重的部分，我们可以考虑使用两个位图，分别存放两个文件，然后遍历两个位图，当两个位图的某一位都是1时，此位对应的内容就是交集。
❓位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
✅看到此问题，就能立刻想到第一个问题，只是这里的有一点细微的差别就是需要找的时不超过2次的整数，那么我们的思路就是一样的，只是所对应的00表示0次，01表示1次，10表示2次，11表示3次及以上。
3.3 布隆过滤器
❓给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法
✅query一般是查询指令，可能是一个网络请求，或者是一个SQL语句，这里假设平均每个query是50byte，100亿个query合计大概是500G的大小，所以这个数据量是非常巨大的。
那么我们的近似算法就能够想到使用布隆过滤器来进行操作，将两个文件分别放入到两个布隆过滤器中，然后查找相同位的值都为1的，它所对应的文件就是交集，当然由于布隆过滤器是一种概率模型，所以这里得到的只能是近似的内容。
如果要求精确算法的话，我们能够考虑到的思路就是上述3.1的第一个问题，将大文件进行哈希切割，然后拿到多个小文件，对这些小文件进行操作即可。
❓如何扩展BloomFilter使得它支持删除元素的操作
✅由于BloomFilter的插入思路是使用多个哈希函数，将值映射到多个位上，所以这里某一个位上的状态可能是多个值映射的，因此这里不能直接将要删除的值对应的哈希地址进行置0操作，这个时候我们可以考虑对每个位增加一个计数器，用来表示当前位被多少个值使用。
当然，这种方式会造成较大的空间浪费，违背了BloomFilter的初衷，所以我们是不建议对BloomFilter进行增加删除操作的。感兴趣的小伙伴可以参考一下这个博客，里面对删除进行了详细的讲解：博客链接
本章完……
ry，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法**
✅query一般是查询指令，可能是一个网络请求，或者是一个SQL语句，这里假设平均每个query是50byte，100亿个query合计大概是500G的大小，所以这个数据量是非常巨大的。
那么我们的近似算法就能够想到使用布隆过滤器来进行操作，将两个文件分别放入到两个布隆过滤器中，然后查找相同位的值都为1的，它所对应的文件就是交集，当然由于布隆过滤器是一种概率模型，所以这里得到的只能是近似的内容。
如果要求精确算法的话，我们能够考虑到的思路就是上述3.1的第一个问题，将大文件进行哈希切割，然后拿到多个小文件，对这些小文件进行操作即可。
❓如何扩展BloomFilter使得它支持删除元素的操作
✅由于BloomFilter的插入思路是使用多个哈希函数，将值映射到多个位上，所以这里某一个位上的状态可能是多个值映射的，因此这里不能直接将要删除的值对应的哈希地址进行置0操作，这个时候我们可以考虑对每个位增加一个计数器，用来表示当前位被多少个值使用。
当然，这种方式会造成较大的空间浪费，违背了BloomFilter的初衷，所以我们是不建议对BloomFilter进行增加删除操作的。感兴趣的小伙伴可以参考一下这个博客，里面对删除进行了详细的讲解：博客链接
本章完……
