数据分析师访谈中最常见的十个访谈问题！

以下是由荣达教育的编辑组织的数据分析师访谈中经常遇到的十个数据分析访谈问题. 让我们看一下数据分析师访谈中最常见的十个访谈问题:

1. 大量的日志数据，提取某天最常访问百度的IP

首先是这一天，将访问百度日志中的IP取出并逐个写入大文件中. 请注意，该IP为32位，最多2 ^ 32个IP. 您还可以使用映射方法（例如取模1000）将整个大文件映射为1000个小文件，然后在每个小文件中查找频率最高的IP（可以使用hash_map进行频率统计，然后找到最频繁的A）和相应的频率. 然后，在1000个最大的IP中，找到您想要的频率最高的IP.

或如下:

算法: 分而治之+哈希

1. 该IP地址的最大值为2 ^ 32 = 4G，因此无法完全加载到内存中进行处理；

2. 您可以考虑``分而治之''的思想，并根据IP地址的Hash（IP）24值将巨大的IP日志存储到1024个小文件中. 这样，每个小文件最多包含4MB IP地址；

3. 对于每个小文件，您可以构建一个哈希图，以IP为键，并以出现次数为值，并同时记录出现次数最多的IP地址；

4. 您可以获取1024个小文件中出现频率最高的IP，然后按照常规的排序算法获得出现频率最高的IP；

2. 搜索引擎将通过日志文件记录用户用于每次搜索的所有搜索字符串. 每个查询字符串的长度为1-255字节.

假设当前有1000万条记录（这些查询字符串的可重复性相对较高，尽管总数为1000万，但是如果删除重复项，则不会超过300万条. 查询字符串的可重复性越高） ，则表示查询的用户越多，受欢迎程度就越高. ），请计算10个最受欢迎的查询字符串，并且所需的内存不能超过1G.

本文介绍了典型的Top K算法，

在本文中，给出的最终算法是:

第一步是预处理大量数据，并在O（N）时间内使用Hash表完成统计（以前写为排序，并在此进行了修改数据分析师笔试题，2011年4月27日）；

第二步是借助此数据结构查找TopK. 时间复杂度为N’logK.

也就是说，借助堆结构，我们可以查找和调整/移动日志时间. 因此，请维护一个小的根堆K（在本主题中为10），然后遍历300万个Query以与根元素进行比较. 因此，我们最终的时间复杂度为: O（N）+ N'* O（LogK），（N为1000万，N'为300万）. 好的，有关更多详细信息，请参阅原始文本.

或者: 使用特里树，关键字字段存储查询字符串的出现次数，没有出现为0. 最后，使用10个元素的最小频率对出现频率进行排序.

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

解决方案: 依次读取文件. 对于每个单词x，取哈希（x）P00，然后将其保存到5000个小文件中（记录为x0，x1，... x4999）. 因此每个文件大约20万.

如果某些文件的大小超过1M，则可以继续以类似的方式对其进行划分，直到通过分解获得的小文件的大小不超过1M.

对于每个小文件，计算出现在每个文件中的单词和相应的频率（可以使用trie tree / hash_map等），然后取出频率最高的100个单词（可以将最小的堆与100个节点）），并将100个单词和相应的频率保存到文件中，因此又得到了5000个文件. 下一步是合并（类似于合并排序）这5000个文件.

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

这也是典型的TOP K算法，解决方案如下:

方案1:

顺序读取10个文件，然后根据哈希（查询）的结果将查询写入另外10个文件（表示为）. 这样，每个新生成的文件的大小也约为1G（假设哈希函数是随机的）.

找到一台具有约2G内存的机器，并使用hash_map（查询，query_count）来计算每个查询依次出现的次数. 使用快速/堆/合并排序可以按出现的次数进行排序. 将排序的查询和相应的query_cout输出到文件. 这样就产生了10个有序文件（表示为）.

合并和排序这10个文件（将内部排序和外部排序合并）.

方案2:

通常，查询的总数是有限的，但是重复的次数却相对较大. 所有查询都可以一次添加到内存中. 这样，我们可以使用trie tree / hash_map直接计算每个查询的出现次数，然后根据出现的次数进行快速/堆/合并排序.

方案3:

类似于方案1，但是在完成哈希并划分为多个文件之后，您可以将它们分配给多个文件进行处理，采用分布式体系结构进行处理（例如MapReduce），最后合并它们.

5. 给定两个文件a和b，每个文件存储50亿个url，每个URL占用64个字节，并且内存限制为4G. 让您找出a和b文件的通用网址吗？

解决方案1: 您可以估计每个文件的大小为5G×64 = 320G，这远远大于4G的内存限制. 因此，不可能将其完全加载到内存中进行处理. 考虑分而治之的方法.

遍历文件a，为每个URL查找哈希（URL）00，然后根据获得的值将URL存储到1000个小文件（表示为a0，a1，...，a999）中. 因此，每个小文件约为300M.

遍历文件b，并使用与a相同的方法将URL存储到1000个小文件（记录为b0，b1，...，b999）. 以这种方式处理后，所有可能相同的URL都位于相应的小文件（a0vsb0，a1vsb1，...，a999vsb999）中，并且不对应的小文件不能具有相同的URL. 然后，我们只需要1000对具有相同URL的小文件即可.

要在每对小文件中找到相同的URL，可以将其中一个小文件的URL存储在hash_set中. 然后遍历另一个小文件的每个URL，以查看它是否在刚刚构造的hash_set中. 如果是，则它是通用URL，可以将其存储在文件中.

方案2: 如果允许一定的错误率，则可以使用Bloom过滤器，并且4G内存可以表示大约340亿位. 使用Bloom过滤器将其中一个文件中的URL映射到这340亿位，然后一一读取其他文件的URL，并检查它们是否与Bloom过滤器相同. 如果是这样，则这些URL应该是通用URL（请注意会有一定的错误率）.

Bloom过滤器将在以后的博客中详细说明.

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: 您也可以使用与第一个问题类似的方法来分割小文件. 然后在小文件中找到唯一的整数并将其排序. 然后再次合并，注意删除重复的元素.

7. 腾讯访谈问题: 给出40亿个未排序的唯一无符号整数，然后再给出一个数字. 如何快速确定这个数字是否在这40亿个数字之中？

类似于上面的问题6，我的第一个反应是快速排序+二进制搜索. 还有其他更好的方法:

解决方案1: 哦，申请512M内存，一位代表一个无符号的int值. 读取40亿个数字，设置相应的位，读取要查询的数字，并检查相应的位是否为1，即存在为1，存在为0

解决方案2: 在“ Programming Pearls”中已很好地描述了此问题，您可以参考以下思路进行探索:

因为2 ^ 32超过40亿，所以其中可能有或没有给定数字；

在这里，我们用32位二进制数表示40亿个数字中的每个数字

假设这40亿个数字开始放入一个文件中.

然后将这40亿个数字分为两类:

1. 最高位是0

2. 最高位是1

将这两个类别分为两个文件，一个文件<= 20亿，另一个文件>> 20亿（相当于一半）；

= 20亿（等于减半）；

与您要查找的数字的最高位进行比较，然后输入相应的文件进行查找

然后将此文件分为两类:

1. 第二个最高有效位是0

2. 第二高的位是1

将这两种类型写入两个文件，一个文件<= 10亿，另一个文件>> 10亿（相当于减半）；

= 10亿（等于减半）；

与您要查找的数字的倒数第二位比较，然后转到相应的文件以查找.

…….

同样，您可以找到它，并且时间复杂度为O（logn）. 解决方案2已完成.

附加: 在这里，我们简要介绍位图方法:

使用位图方法确定整数数组中是否存在重复项

确定集合中是否存在重复项是常见的编程任务之一. 当集合中的数据量很大时，我们通常希望扫描几次. 目前，不希望使用双循环方法.

位图方法更适合这种情况. 其方法是根据集合中的最大元素最大值创建一个长度为max + 1的新数组，然后再次扫描原始数组. 遇到新数组时，请给出其编号. 在位置1，如果遇到5，则新数组的第六个元素设置为1，因此下次遇到5时，新数组的第一个元素设置为1，表示数据必须存在与以前的数据有些重复. 这种将新数组重置为零并对其进行初始化的方法与位图处理方法相似，因此称为位图方法. 最坏的情况是2N. 如果您知道数组的最大值，则可以预先使新数组的效率提高一倍.

欢迎，提出更好的想法或方法，并一起交流​​.

8. 如何找到海量数据中重复次数最多的人？

解决方案: 首先进行哈希处理，然后映射到一个小文件，在每个小文件中找到重复次数最多的文件，并记录重复次数. 然后在上一步获得的数据中找出重复次数最多的那个是您要寻找的那个（有关详细信息，请参阅上一个问题）.

9，数以千万计的数据（重复），计算出现次数最多的前N个数据

解决方案: 数千万或数十亿的数据. 当前机器的内存应该能够被存储. 因此，请考虑使用hash_map /搜索二叉树/红黑树来统计数据. 然后是取出前N个出现次数最多的数据，这可以通过第二个问题中提到的堆机制来完成.

10. 一个文本文件，大约10,000行，每行一个单词. 需要对出现频率最高的前10个单词进行计数. 请思考并进行时间复杂度分析.

选项1: 此问题考虑时间效率. 使用特里树来计算每个单词出现的次数数据分析师笔试题，时间复杂度为O（nle）（le表示单词的平均长度）. 然后就是找出出现频率最高的前10个单词，可以通过堆来实现. 如上一个问题所述，时间复杂度为O（nlg10）. 因此，总时间复杂度是O（nle）和O（nlg10）中的较大者.

在100w个数字中附加最大的100个数字.

方案2: 在上一个问题中，我们提到它是通过最少100个元素的堆完成的. 复杂度为O（100w * lg100）.

解决方案3: 使用快速排序的想法. 每次分割后，仅考虑比轴大的部分. 当大于轴的部分大于100时，使用传统的排序算法对前100个进行排序. 复杂度为O（100w * 100）.

选项4: 采用部分消除方法. 选择，排序和记录前100个元素，并将其记录为序列L. 然后与有序100个元素中的最小元素相比，一次扫描其余元素x. 如果大于此最小值，则使用插入排序的想法删除最小的元素并将x插入序列中. L in. 循环浏览，直到您扫描完所有元素. 复杂度为O（100w * 100）.

这些是荣达教育（Rongda Education）的数据分析师培训学习编辑分享的十个最常见的数据分析师访谈问题. 希望对小伙伴有帮助. 荣达教育IT培训机构可以为您提供良好的技术学习，更好地了解每个学习者的需求，并为每个学习者的特定需求配置最合适的资产组合，这无疑更符合学习者的需求.

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