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

[hakunamatata11]

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

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

题目描述

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

样例

例 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 intersection(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 点