[传输]数据处理中面试问题的方法(2)

关于位图，请阅读此文章: . 以下是有关位图的应用，直接用于第6和7道的问题:

6. 在2.5亿个整数中找到唯一的整数. 请注意，内存不足以容纳这2.5亿个整数.

计划1: 使用2位图（每个位分配2位，00表示不存在，01表示一次，10表示多次，11表示无意义），总共2 ^ 32 * 2位= 1 GB内存也可以接受. 然后扫描这2.5亿个整数以查看位图中的相应位. 如果00更改为01，01更改为10，而10保持不变. 描述完成后，检查位图并输出与01对应的整数.

选项2: 您还可以通过类似于问题1的方法对小文件进行划分. 然后在小文件中找到唯一的整数并将其排序. 然后再次合并，注意删除重复的元素.

7. 腾讯访谈问题: 给出40亿个不重复，不排序的无符号int整数，然后给出一个数字. 如何快速判断这个数字是否在这40亿个数字之中？

计划1: 哦，申请512M内存，一位代表一个无符号的int值. 读入40亿个数字，设置对应的位，读入要查询的数字，检查对应的位是否为1，其中1表示存在，0表示没有.

特里树

应用范围: 数据量大，重复很多，但是小的数据类型可以放入内存

基本原理和要点: 实现方式，表示结点子代的方式

扩展: 压缩实现.

问题示例:

1）. 有10个文件，每个文件为1G，每个文件的每一行存储用户的查询，并且每个文件的查询可以重复. 我希望您按查询频率排序.

2）. 1000万个字符串，其中一些是相同的（重复的），您需要删除所有重复的字符串，并保持字符串不重复. 如何设计和实现它？

3）. 寻找受欢迎的查询: 查询字符串的重复次数相对较高，尽管总数为1000万，但是如果删除重复，则不会超过300万，每次不会超过255个字节.

有关Trie树的更多信息，请参阅本文: 从Trie树（字典树）到后缀树.

索引

应用范围: 添加，删除和修改大量数据

基本原理和要点: 使用数据的设计和实现方法来处理海量数据的添加，删除和修改.

倒排索引（倒排索引）

适用范围: 搜索引擎，关键字查询

基本原理和要点: 为什么叫倒排索引？使用索引方法可以在全文搜索中存储文档或一组文档中单词的存储位置的映射.

以英语为例，以下是要索引的文本:

T0 =“就是它了”

T1 =“这是什么”

T2 =“这是一根香蕉”

我们可以获得以下反向文件索引:

“ a”: {2}

“香蕉”: {2}

“是”: {0，1，2}

“它”: {0，1，2}

“什么”: {0，1}

搜索条件“ what”，“ is”和“ it”将对应于集合的交集.

开发了一个前向索引来存储每个文档中的单词列表. 前向索引查询通常满足每个文档的频繁全文查询顺序以及验证文档中每个单词的验证顺序. 在前向索引中，文档占据中心位置，并且每个文档都指向它包含的一系列索引项. 换句话说，文档指向包含它的单词，而反向索引指向指向包含它的文档的单词. 很容易看到相反的关系.

扩展:

一个问题的例子: 一个文档检索系统，该系统查询包含某个单词的文件，例如对普通学术论文的关键词搜索.

有关倒排索引的应用，请参阅: 第23章和第4章: 杨氏矩阵搜索海量数据处理方案，无重复代码实践的关键字哈希，以及第26章: 基于给定的编码和文档生成倒排索引的实践.

应用范围: 大数据排序，重复数据删除

基本原理和要点: 外部排序合并方法，替代选择失败者树的原理，最佳合并树

扩展:

问题示例:

1）. 有一个大小为1G的文件，其中每行是一个单词，该单词的大小不超过16个字节，并且内存限制大小为1M. 返回频率最高的100个单词.

此数据具有明显的特征. 字长为16个字节，但用于哈希的内存只有1m，因此可以用于排序. 内存可用作输入缓冲区.

有关多重合并算法和外部排序的特定应用场景，请参阅本文: 第10章，如何对10 ^ 7数据磁盘文件进行排序.

适用范围: 数据量很大，但是数据类型可以放入内存中

基本原理和要点: 将数据移交给不同的机器进行处理，数据分割和结果精简.

扩展:

问题示例:

1）. MapReduce的规范示例应用程序是对一组文档中每个不同单词的出现进行计数的过程:

2）. 海量数据分布在100台计算机中，找到了一种方法来有效地计算这批数据的TOP10.

3）. 总共有N台计算机，每台计算机上有N个数字. 每台机器最多可以存储O（N）个数字并进行操作. 如何找到N ^ 2个数字的中位数？

有关更多详细信息，请参阅: 谈论从Hadhoop框架和MapReduce模式进行的海量数据处理，以及对MapReduce技术的初步了解和学习.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-246793-2.html