Facebook 面试真题，最优解来了！

海量数据类处理问题，是面试中非常高频的一类问题。但是在没有任何处理经验的情况下，面试者往往很难回答上来。

为了让大家对海量数据处理的问题有一个初步的认识，我们来看一个常见的例子：

题目描述

给出两个数组，写出一个方法求出它们的交集

样例

例 1:

输入: nums1 = [1, 2, 2, 1], nums2 = [2, 2], 输出: [2]. 

例 2:

输入: nums1 = [1, 2], nums2 = [2], 输出: [2]. 

你能用 3 种方法实现吗?

方法 1：

直接求交集

# This reference program is provided by @jiuzhang.com # Copyright is reserved. Please indicate the source for forwarding class Solution: # @param {int[]} nums1 an integer array # @param {int[]} nums2 an integer array # @return {int[]} an integer array def intersection(self, nums1, nums2): # Write your code here return list(set(nums1) & set(nums2)) # Version 2: 不使用&运算符 class Solution: """ @param nums1: an integer array @param nums2: an integer array @return: an integer array """ def inersection(self, nums1, nums2): s1, s2 = set(nums1), set(nums2) return [x for x in s1 if x in s2] 

方法 2：

利用排序后二分查找即可实现

/** * This reference program is provided by @jiuzhang.com * Copyright is reserved. Please indicate the source for forwarding */ // version 1: sort & merge public class Solution { /** * @param nums1 an integer array * @param nums2 an integer array * @return an integer array */ public int[] intersection(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); int i = 0, j = 0; int[] temp = new int[nums1.length]; int index = 0; while (i < nums1.length && j < nums2.length) { if (nums1[i] == nums2[j]) { if (index == 0 || temp[index - 1] != nums1[i]) { temp[index++] = nums1[i]; } i++; j++; } else if (nums1[i] < nums2[j]) { i++; } else { j++; } } int[] result = new int[index]; for (int k = 0; k < index; k++) { result[k] = temp[k]; } return result; } } // version 2: hash map public class Solution { /** * @param nums1 an integer array * @param nums2 an integer array * @return an integer array */ public int[] intersection(int[] nums1, int[] nums2) { if (nums1 == null || nums2 == null) { return null; } HashSet<Integer> hash = new HashSet<>(); for (int i = 0; i < nums1.length; i++) { hash.add(nums1[i]); } HashSet<Integer> resultHash = new HashSet<>(); for (int i = 0; i < nums2.length; i++) { if (hash.contains(nums2[i]) && !resultHash.contains(nums2[i])) { resultHash.add(nums2[i]); } } int size = resultHash.size(); int[] result = new int[size]; int index = 0; for (Integer num : resultHash) { result[index++] = num; } return result; } } // version 3: sort & binary search public class Solution { /** * @param nums1 an integer array * @param nums2 an integer array * @return an integer array */ public int[] intersection(int[] nums1, int[] nums2) { if (nums1 == null || nums2 == null) { return null; } HashSet<Integer> set = new HashSet<>(); Arrays.sort(nums1); for (int i = 0; i < nums2.length; i++) { if (set.contains(nums2[i])) { continue; } if (binarySearch(nums1, nums2[i])) { set.add(nums2[i]); } } int[] result = new int[set.size()]; int index = 0; for (Integer num : set) { result[index++] = num; } return result; } private boolean binarySearch(int[] nums, int target) { if (nums == null || nums.length == 0) { return false; } int start = 0, end = nums.length - 1; while (start + 1 < end) { int mid = (end - start) / 2 + start; if (nums[mid] == target) { return true; } if (nums[mid] < target) { start = mid; } else { end = mid; } } if (nums[start] == target) { return true; } if (nums[end] == target) { return true; } return false; } } 

方法 3：

排序后双指针

/** * This reference program is provided by @jiuzhang.com * Copyright is reserved. Please indicate the source for forwarding */ // sort & merge class Solution { public: /** * @param nums1 an integer array * @param nums2 an integer array * @return an integer array */ vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { // Write your code here sort(nums1.begin(), nums1.end()); sort(nums2.begin(), nums2.end()); vector<int> intersect; vector<int>::iterator it1 = nums1.begin(), it2 = nums2.begin(); while ((it1 != nums1.end()) && (it2 != nums2.end())) { if (*it1 < *it2) it1++; else if (*it1 > *it2) it2++; else { intersect.push_back(*it1); it1++; it2++; } } auto last = unique(intersect.begin(), intersect.end()); intersect.erase(last, intersect.end()); return intersect; } }; 

这个问题只是一道很普通算法问题，我们可以通过 Hash 或者排序 + 二分法等方法轻松解决。但是你以为面试就到此为止了吗，面试官马上跟进的问题，可能会让你措手不及：求两个超大文件中 URLs 的交集，并且内存中不足以放下所有的 URLs。这就是一个典型的海量数据处理问题。

所谓海量数据处理，其实就是基于海量数据的存储、删除、搜索等操作。所谓海量，就是数据量太大，所以导致要么无法在短时间内迅速处理，要么无法一次性装入内存。

那应该如何解决呢？针对时间，我们可以采用更加精妙而迅速的数据结构和算法，比如 BloomFilter、Hash、堆、Bitmap 等；针对空间，无非就是：大而化小，分而治之。在这里我们先不一一展开。

根据上面的讨论，在海量数据处理类的问题中，我们总结了以下考点：

算法方面：

• 外排序算法（ External Sorting ）
• Map Reduce
• 非精确算法
• 概率算法
• 哈希算法与哈希函数（ Hash Function ）

数据结构方面：

• 哈希表（ Hash Table ）
• 堆（ Heap ）
• 布隆过滤器（ BloomFilter ）
• 位图（ Bitmap ）

以上的知识点，你了解多少呢？

如果这些名词对你来说还很陌生，不用着急~

《海量数据处理算法与面试题全集》这门原价$199 的课程，现在$1 秒杀！

参与方式：

戳我免费试听后，添加泡芙微信 jiuzhang10，回复 [ V2EX ] +试听报名截图即可$1 购买本课程。

也可扫描下方 [九章泡芙] 二维码：

参与条件：

九章新用户（未在九章官网付费过的都算新用户哦~）

※活动截止时间：北京时间 2019 年 12 月 1 日 24 点