数据分析师常见的7项书面测试问题和答案

针对数据分析师的7个常见书面问答: 探索性数据分析的重点是发现数据中的新特征，而确认性数据分析的重点在于对现有假设的验证或伪造. 以下是J.L.建议阅读的实际应用问题和经验的摘要. 1.海量日志数据提取某天最多访问百度的IP. 第一天是今天，将访问百度的日志中的IP取出并逐个写入大文件中. 请注意，该IP是32位，最多2 ^ 32个IP. 您还可以使用映射方法（例如modulo 1000）将整个大文件映射到1000个小文件，然后在每个小文件中找到频率最高的IP（可以使用hash_map进行频率统计，然后找到最频繁的A）和相应的频率. 然后，在1000个最大的IP中，找到所需频率最高的IP. 或如下所示: 算法思想: 分而治之+哈希1. IP地址的最大值为2 ^ 32 = 4G，因此无法完全加载到内存中进行处理； 2.您可以考虑根据IP地址使用“分而治之”的想法. 哈希（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）时间内用哈希表完成它. 统计信息（以前写为排序，特此修订. 2011年7月7日）；第二步是找到具有堆数据结构的Top K，时间复杂度为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）. 因此数据分析师笔试题，每个文件约为200k. 如果某些文件的大小超过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过滤器相同. 如果是这样，则这些网址应为通用网址（请注意会有一定的错误率）.

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亿个唯一的无符号int整数（未排序），然后给出另一个数字. 如何快速确定这个数字是否在这40亿个数字之中？与上面的问题6相似，我的第一个反应是快速排序+二进制搜索. 以下是其他更好的方法: 解决方案1: 哦，申请512M内存，一位代表一个无符号的int值.

读取40亿个数字，设置相应的位，读取要查询的数字，并检查相应的位是否为1，如果为1，则存在，如果为0，则不存在. 解决方案2: “编程珍珠”中已很好地描述了此问题，您可以参考以下思想进行讨论: 另外，由于2 ^ 32超过40亿，因此其中可能有一个给定的数字；在这里，我们将40亿个数字中的每个数字都用32位二进制表示. 假设这40亿个数字开始放入文件中.

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