《Google爱考原题学会这题谷歌offer到手！.docx》由会员分享，可在线阅读，更多相关《Google爱考原题学会这题谷歌offer到手！.docx（6页珍藏版）》请在金锄头文库上搜索。
1、Google爱考原题，学会这题谷歌offer到手！今天分享一个Google的面试考点Map Reduce，它是Google的三驾马车之一，用于进行分布式计算。Map Reduce的基本思想很简单，就是通过Map这个步骤使用多台机器并行，将所有的数据都整理为的二元组，然后在Reduce操作之前，系统会按照Key的不同，将不同的Key分给不同的机器进行处理，比如可以简单地根据hash（key）%机器数的方式来进行数据分配（这个过程叫做shuffle）。接下来，每台机器拿到数据之后，进行reduce合并统计的操作，将同一个key的数据进行处理。最终得到了每个key的处理结果。那这样的Map redu
2、ce系统有什么好处呢？其实Map Reduce 并没有结余实际上的计算时间总和，但是如果你现在有很多的计算资源（很多台机器），你可以通过 Map Reduce 的框架利用多台机器同时计算，来优化性能进行提速。Map Reduce是一套通用的分布式计算框架。这样，对于很多类似的问题，工程师并不需要每次都去自己构思如何使用多台机器优化计算的算法，只需要套用这个通用框架，就可以快速的解决问题。（比如：矩阵分解问题，Page Rank搜索排序算法）你可能会有疑问，为什么一定要使用Map Reduce来分割文件呢，单纯的分割文件分别统计是否可行呢？其实是不行的。单纯的将文件1丢给机器1，文件2丢给机器2
3、，分别统计 Top K 之后再合并，这种方法是不行的。因为最高频的那一项可能分别出现在文件1和文件2，这样就相当于降低了其出现的频率，可能造成统计结果不对。Map Reduce是大数据职位面试的敲门砖，如果你的目标岗位是Software Development Engineer，Data Engineer，Data Scientist，学会MapReduce是非常必要的。接下来我们看一道Google的面试真题。题目描述使用 map reduce 来计算单词频率。样例Example 1: Input: chunk1: Google Bye GoodBye Hadoop code chunk2:
4、lintcode code ByeOutput: Bye: 2 GoodBye: 1 Google: 1 Hadoop: 1 code: 2 lintcode: 1 Example 2: Input: chunk1: Lintcode is so so goodOutput: Lintcode: 1 good: 1 is: 1 so: 2 统计单词词频这个问题很常见，比如微博前10的热搜词。这些词是如何统计的呢？你能想到几种方法？方法1：For循环 HashMapwordcount；For each word in webpage： wordcountingword+ For循环的优点是简单，
5、但是只有一台机器，运行速度慢，内存大小受限。如果你有多台机器怎么办呢？方法2：多台机器For循环多台机器For循环合并的时候只用了1台机器，这台机器可能会成为整个系统的瓶颈。打个比方，假设现在你有1亿个key，用1000台机器去分别统计，合并时的那台机器至少要访问1000*1亿次。因此，合并的那台机器会成为系统的瓶颈。这促使我们思考，合并时是否也可以并行？如果要并行，以什么为标准来划分？机器还是key 呢？机器划分：1-10用一台机器合并，11-20用第二太机器合并，21-30用第三台机器合并.这个方法不太好，因为最后3台机器还是需要另一台机器去合并，最终会形成一个分层的树状结构。而且，下一层
6、必须等上一层做完才行，增加了整体系统地设计复杂度，还增加了他们相互之间的依赖度，会拖慢系统地运行速度。key划分：用一台机器合并所有的a，b，用另一台合并所有的c，d。正确方法是以key来划分。以key作为划分，不会有前后的依赖性，并且整个系统设计起来也比较简单。map就是把任务打散，让大家分开并行去做，reduce就是把结果合并起来。多台机器Map Rreduce中，机器1、2只负责把文章拆分为一个一个的单词，机器3、4各负责一部分word的合并。 # This reference program is provided by # Copyright is reserved. Please
7、indicate the source for forwardingclass WordCount: def mapper(self, _, line): # Write your code here for word in line.split(): yield word, 1 def reducer(self, key, values): # Write your code here yield key, sum(values) 实际上，Map Reduce只是海量数据处理类问题其中之一。海量数据类处理问题，是面试中非常高频的一类问题。但是在没有任何处理经验的情况下，面试者往往很难回答上来
8、。学好海量数据处理，你需要学会：算法方面： 外排序算法（External Sorting） Map Reduce 非精确算法 概率算法 哈希算法与哈希函数（Hash Function）数据结构方面： 哈希表（Hash Table） 堆（Heap） 布隆过滤器（BloomFilter） 位图（Bitmap）以上的知识点，你了解多少呢？如果这些名词对你来说还很陌生，不用着急海量数据处理算法与面试题全集这门原价$199的课程，现在$1秒杀！参与方式：戳我免费试听后，添加泡芙微信jiuzhang10，回复【知乎】+试听报名截图即可$1购买本课程。参与条件：九章新用户（未在九章官网付费过的都算新用户哦）
