【C++】海量数据面试题

这篇具有很好参考价值的文章主要介绍了【C++】海量数据面试题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

海量数据面试题

【C++】海量数据面试题

一、哈希切割

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址?以及如何找到top K的IP?如何直接用Linux系统命令实现?

  • 我们可以把这100G大小的文件切分成100个小文件
  • 依次读取ip地址,通过哈希函数把每个ip地址转换为一个整型,再把这些分别%100切分到这100个小文件里头

【C++】海量数据面试题

  • 此时相同的ip地址通过哈希函数转换的整型一定是相同的,最终也一定进入同一个文件,不同的ip也可能进入同一个文件,现在我们使用map容器(map<string, int> countMap)依次对每个小文件统计次数,统计完A0,把A0的次数记录下来为最大次数(pair<ip, int> maxIP),clear旧数据,再统计A1,比较A1的次数和最大次数的大小,更新最大次数,再clear掉旧数据……,依次比较,依次更新最大次数的数据。
  • 如果需要找到top K,就需要用到优先级队列(priority_queue<pair<string,int>,vector<pair<string,int>>,less>),less仿函数将比较pair中int的大小,使用小堆可满足找最大的K个值的条件。

使用上述哈希切割的方法可以找到出现次数最多的IP地址,但是会存在一个小问题:某个文件太大,导致某个相同ip太多,且映射冲突到这个编号文件的ip太多(可能又会导致内存不够了),这里我们可以try-catch捕获,伪代码如下:

try
{
	countMap[ip]++;
}
catch (exception& e)
{
	//捕获内存不足的异常,说明内存不够
	countMap.clear();
	//针对这个小文件,再次换个哈希函数,进行哈希切分,再切分成小文件
	//再对小文件依次统计
}

找到topK的Linux的指令如下:

假如有以下文件IP.log:

192.168.5.5
234.23.13.44
10.152.16.23
192.168.3.10
192.168.1.4
192.168.2.1
192.168.0.9
10.152.16.23
192.163.0.9
192.168.0.9 
69.52.220.44 
192.168.1.4 
192.168.1.5
192.163.0.9 
192.168.2.1
192.168.0.1
192.168.0.2

(1)按行排序,并将结果输出到标准输出

sort 文件名

(2)统计并显示文本文件中出现的行或列的次数

uniq -c

(3)根据出现次数倒序排序

sort -r

(4)查看开头K行

head -k

综上:显示出现次数最多的前K个IP

sort log_file | uniq -c | sort -nr | head -k

sort log_file对文件进行排序,使得相同的IP地址聚在一起,接着使用uniq -c进行去重,并将重复的次数显示在每列的旁边,通过这个次数来使用sort -nr进行降序排序,使得出现次数最高的IP地址在前面,然后使用head -k获取前k个IP地址。

运行结果:

【C++】海量数据面试题

【C++】海量数据面试题


二、位图应用

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

给定100亿个整数,设计算法找到只出现一次的整数

题目明确说找到只出现一次的整数,那说明一个整数出现的次数的情况分为如下三种状态:

  1. 出现0次
  2. 出现1次
  3. 出现2次及以上

一个比特位只能表示一种状态,但是两个比特位就能表示4种了,因此我们借助两个比特位来表示如上三种状态:

  • 00(0次)
  • 01(1次)
  • 10(2次)

所以这里我们需要重新写一个位图,两个比特位表示一个值,所以一个char只能表示4个值(8bit / 2),100亿个整数要开2^32 * 2个比特位,大概占1G。

【C++】海量数据面试题

虽然这里是两个比特位表示一个值,不过我们实际操作的时候可以设计一个类,里面封装两个bitset,并且通过后续的位运算来表示两个比特位表示一个值。

【C++】海量数据面试题

具体实现的代码如下:

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
		{
			_bs1.set(x); 
			_bs2.reset(x); // 10
		}

		// 10 不变
	}

	void PirntOnce()
	{
		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[] = { 3, 5, 6, 7, 8, 9, 33, 55, 67, 3, 3, 3, 5, 9, 33 };
	for (auto e : a)
	{
		tbs.set(e);
	}
	tbs.PirntOnce();
}

2.求两个文件交集

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

这里我们可以设计两个位图,刚好占用1G内存,按照如下方式设置

  1. 把A文件读到位图1,把B文件读到位图2
  2. 遍历两个位图,将位图1和位图2进行与&操作,结果存储在位图1中,此时位图1中映射的整数就是两个文件的交集。

【C++】海量数据面试题


3.在100亿个整数中找到出现次数不超过2次的所有整数

1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数

此题和第一题的思想是一样的,对于出现的次数,可以用两个比特位来表示,一次表示出现次数的状态:

  1. 出现0次(00)
  2. 出现1次(01)
  3. 出现2次(10)
  4. 出现3次及以上(11)

这里同样需要两个位图来解决,只需要对第一题的代码进行改造即可,最后状态是01或10的整数就是出现次数不超过2次的整数。

template<size_t N>
class two_bitset
{
public:
	void set(size_t x)
	{
		int in1 = _bs1.test(x);
		int in2 = _bs2.test(x);
		if (in1 == 0 && in2 == 0)//00
		{
			_bs2.set(x);//01
		}
		else if (in1 == 0 && in2 == 1)//01
		{
			//出现次数置为2
			_bs1.set(x);//10
			_bs2.reset(x);
		}
		else if (in1 == 1 && in2 == 0)//10
		{
			_bs2.set(x);//11
		}
	}
private:
	bitset<N> _bs1;
	bitset<N> _bs2;
};

三、布隆过滤器

1.求两文件交集(近似算法)

给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?给出近似算法

题目要求给出近视算法,也就是允许存在一些误判,那么我们就可以用布隆过滤器。

  1. 先读取其中一个文件当中的query,将其全部映射到一个布隆过滤器当中。
  2. 然后读取另一个文件当中的query,依次判断每个query是否在布隆过滤器当中,如果在则是交集(但是会存在误判的风险,不过无法避免,这也是近似算法的特点),不在则一定不是交集。

2.求两文件交集(精确算法)

给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?给出精确算法

注意:

  • 这里明确指出给出精确算法,我们不能使用布隆过滤器,因为会存在误判,要用上文一开始使用的哈希切分来解决。

我们按照如下的规则来进行哈希切割。

  • 我们假设每个query平均20byte,100亿query就是200G,我们可以把这么个文件分为1000个小文件
  • 依次读取query,通过哈希函数把每个query转换为一个整型,再把这些分别%1000切分到这1000个小文件里头,此时文件A就被分为A0 ~ A999共1000个小文件,文件B就被分为B0 ~ B999共1000个小文件。

【C++】海量数据面试题

由于在切分A文件和B文件的时候,使用的是相同的哈希函数,因此A文件和B文件中相同的query计算的是相同的i值,就被分到了对应的Ai和Bi中,因此我们只需要找到A0与B0的交集、A1与B1的交集……最终把这些集合合并起来就是文件A和文件B的总交集。

【C++】海量数据面试题

而小文件找交集的方法也很简单,如下规则:

  • 我们可以将其中一个小文件加载到内存,并放到一个set容器中,再遍历另一个小文件当中的query,依次判断每个query是否在set容器中,如果在则是交集,不在则不是交集。
  • 如果切分出来的一个小文件过大,需要将此文件再次进行切分,再走一遍这个过程即可。

3.计数法使布隆过滤器支持删除

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

布隆过滤器不能直接支持删除工作,因为在删除一个元素时,可能会影响其他元素。一种支持删除的方法(计数法删除):

  • 将布隆过滤器中的每个比特位扩展成一个小的计数器,插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一,删除元素时,给k个计数器减一,通过多占用几倍存储空间的代价来增加删除操作。

【C++】海量数据面试题

缺陷:

  1. 无法确认元素是否真正在布隆过滤器中
  2. 存在计数回绕

总结:文章来源地址https://www.toymoban.com/news/detail-420092.html

  • 布隆过滤器不支持直接删除归根结底在于其主要就是用来节省空间和提高效率的,在计数法删除时需要遍历文件或磁盘中确认待删除元素确实存在,而文件IO和磁盘IO的速度相对内存来说是很慢的,并且为位图中的每个比特位额外设置一个计数器,就需要多用原位图几倍的存储空间,这个代价也是不小的。若支持删除就不那么节省空间了,也就违背了布隆过滤器的本质需求。

到了这里,关于【C++】海量数据面试题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】哈希—— 位图 | 布隆过滤器 | 哈希切割

    🐱作者:一只大喵咪1201 🐱专栏:《数据结构与算法》 🔥格言: 你只管努力,剩下的交给时间! 哈希是一种映射思想,这里再讲解两种应用哈希思想的数据结构。 问题: 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数

    2024年02月02日
    浏览(57)
  • 哈希的应用 -- 布隆过滤器与海量数据处理

    布隆过滤器是由布隆(Burton Howard Bloom)在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构,特点是高效地插入和查询,以用来告诉你 “ 某样东西一定不存在或者可能存在 ”,它是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也

    2024年02月02日
    浏览(44)
  • 面试官:如何遍历 Redis 中的海量数据?

    来源:https://www.toutiao.com/article/6697540366528152077/ 有时候我们需要知道线上的 redis的使用情况 ,尤其需要知道一些 前缀的key值 ,让我们怎么去查看呢?今天给大家分享一个小知识点! 因为我们的用户 token缓存是采用了【user_token:userid】格式的key ,保存用户的token的值。我们运

    2024年02月11日
    浏览(44)
  • C++面试问题合集之哈希

    哈希(Hash)是一种将数据映射到固定大小的值(哈希值)的过程。在计算机科学中,哈希函数将任意长度的数据(输入)转换为固定长度的哈希值(输出)。哈希函数通过对输入数据进行计算和转换,生成一个唯一的哈希值。 哈希函数具有以下特点: 唯一性:不同的输入数

    2024年01月16日
    浏览(51)
  • 数据结构:位图、布隆过滤器以及海量数据面试题

    1.1概念 引入 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。 (1)遍历: 时间复杂度O(N) (2)排序加二分:时间复杂度O(N*logN) 其中 方法(2)是行不通 的,因为内存很难装下这么多数据(40亿整数大概为16G)。 方法(1) 可行

    2024年02月05日
    浏览(44)
  • 缓存面试解析:穿透、击穿、雪崩,一致性、分布式锁、Redis过期,海量数据查找

    在程序内部使用缓存,比如使用map等数据结构作为内部缓存,可以快速获取对象。通过将经常使用的数据存储在缓存中,可以减少对数据库的频繁访问,从而提高系统的响应速度和性能。缓存可以将数据保存在内存中,读取速度更快,能够大大缩短数据访问的时间,提升用户

    2024年02月14日
    浏览(54)
  • 【C++】位图/布隆过滤器+海量数据处理

    ✍ 作者 : 阿润菜菜 📖 专栏 : C++ 题目 给40亿个不重复的无符号整数,没排过序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。 大多数人上来会想到这两种方法:1. 遍历,时间复杂度O(N)2. 排序(O(NlogN)),利用二分查找: logN 但是第一种效率太低了,需要一个

    2024年02月06日
    浏览(49)
  • C++【位图/布隆过滤器—海量数据处理】

    先看下面的一道题 : 1.有40亿个不重复的无符号整数,无序。给一个无符号整数,如何快速判断一个数是否在这40亿个数中。 如果我们放到哈希表或红黑树中或用排序和二分查找这两种方法。 前两种方法不可行,因为40亿个整数占用大约16G的内存空间,第一要排序需要先把数

    2024年02月09日
    浏览(65)
  • 大数据面试题集锦-Hadoop面试题(一)

    目录 1、集群的最主要瓶颈 2、Hadoop运行模式 3、Hadoop生态圈的组件并做简要描述 4、解释“hadoop”和“hadoop 生态系统”两个概念 5、请列出正常工作的Hadoop集群中Hadoop都分别需要启动哪些进程,它们的作用分别是什么? 6、基于 Hadoop 生态系统对比传统数据仓库有何优势? 7、如

    2023年04月09日
    浏览(47)
  • 【Java程序员面试专栏 数据结构】四 高频面试算法题:哈希表

    一轮的算法训练完成后,对相关的题目有了一个初步理解了,接下来进行专题训练,以下这些题目就是汇总的高频题目,一个O(1)查找的利器哈希表,所以放到一篇Blog中集中练习 题目 解题思路 时间 空间 两数之和 辅助哈希 使用map存储出现过的值,key为值大小,v

    2024年02月22日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包