爱刨根知识网

  1. 首页 > 经验知识 > >

大数据面试题2021

生活经验数据

每晚10点，捕获技术思考和创业资源洞察

“分而治之”( Divide and conquer)方法(又称“分治术”)，是有效算法设计中普遍采用的一种技术 。
有一个1G大小的一个文件，里面每一行是一个英文单词，词的大小不超过16字节，内存限制是1M 。请设计一个算法思路，返回频数最高的100个词.
初步一看，要处理的文件大小1G，可内存却只有1M 。我们知道1G的文件用1M的内存空间处理不太现实 。按照1M的上限来计算，假设每个单词都为16个字节，那么1M的内存可以处理多少个单词？
我们来计算下，1M = 1024 KB = 1024 * 1024 B。1M / 16B = 2^16个单词，那么1G大概有多少个单词呢？有2^26个单词，但是实际中应该不止，因为我们是按照最大单词长度来计算的，有可能有的单词只有两个字母 。
大数据面试题2021

文章插图
方案1大概思路：
  1. 分而治之/hash映射：顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为x0,x1,...x4999）中 。这样每个文件大概是200k左右 。如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M 。
  2. hash统计：对每个小文件，采用trie树/hash_map等统计每个文件中出现的词以及相应的频率 。
  3. 堆/归并排序：取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100个词及相应的频率存入文件，这时我们又得到了5000个文件 。最后把这5000个文件进行归并（类似与归并排序）的过程 。
【大数据面试题2021】类似这样的方案应该有很多，我们共同去研究学习，经验都是个人实践总结出来的，以上仅代表个人观点 。以此分享给大家，不足之处望大家留言补充 。

    推荐阅读


    上一篇：笔记本电脑桌面图标不见咋处理

    下一篇：手机号怎么查一个人的定位 定位别人的手机号怎么定