阿里现在的面试这么难了吗？

内推，二面面试官约了两天后要笔试（之前听说内推没有笔试），我不敢大意，想到工作三四年了，应该不会考察特别难的算法。查了一下别人分享的面试，要不是就是没有笔试，要不是就是一些线性表，多线程顺序执行问题。我的算法基础还行，曾经也刷过题，线性表问题（比如反转链表，合并有序数组之类）、二叉树问题（ BST 等）、排序算法（ TopK，Nth 等等）、手写 BlockingQueue 、LRU 、还是多线程问题，我觉得这些对我来说没什么问题。

到了约定时间，面试官给我发了一个在线编程的网页，打开后题目已经在那里了，看起来是实际问题而不是具体的算法数据结构之类。面试官说给你 40 分钟，你把这两道题写完，我说能不能用 IDEA，面试官说不能，然后就不说话了。毫无代码提示补全，完全白板编程，不仅如此，题目描述都很简单，但是却有五六个类，之间都有关系，我抓紧认真审题，光弄懂题目都花了十多分钟，我吃惊的发现这两道题竟然都和动态规划有关，我当时心凉了一半。第一道题是用滑动窗口（双指针）找到极值，我用吃奶的力气才做完（白板编程，还有多层循环的 continue，break ）。第二道题，经过我的抽象，发现竟然是一道复杂的背包问题。

题目大致是 n 个背包，m 个物品，每个背包可以有某些物品任意件，找出最少的背包包含所有的物品。注: 此题一定有解。

    //经过我的抽象大致是这样的，重量和数量问题不用考虑
    public static class Product{}
    public static class Package{}
    //此物品是否在包裹中
    public boolean productInPackage(Package packet, Product product) { ***** }

    //完成此方法: 每个背包可以有某些物品任意件，找出最少的背包包含所有的物品
    public Map<Product, Package> findLeastPackages(List<Product> products, List<Package> packages) {}

心里真的拔凉拔凉的。时间到了我第二题只做到一半（找到了所有背包中所有的物品），后面时间不够，集合的交叉并补也记得不是很清楚了。而且只有大致的思路。也没想到最优的解法。

我 JDK 重要源码学了一遍又一半，HotSpot 源码也有所涉猎，研究 JDK 的 BlockingQueue 、ConcurrentLinkedQueue 、WorkStealingQueue，JCtools 的 SPSC 、MPSC 、MPMC，Disruptor RingBuffer, 学习各种 lock-free 算法和结构，心想自己技术水平还算可以，没想到折戟在这里。

不知道是不是内推的这个部门不招人（ JD 描述还是 9 月份），自己一直对阿里有好感，但是一面面试官的傲慢，二面出这种题目白板编程，感觉自己被耍了。我只是面一个 P6 而已，现在也是公司的一个技术小 leader，每天 5 点多就能下班了，笔试晚上 9 点半还能听到对面的人在讨论需求。说实话这些对我有影响，但不是最重要的，我想去阿里因为我对自己和技术还有追求。当然最想去阿里中间件团队，但是据说特别难，所以选择了曲线救国的方法。可是遭遇这一遭。

自己的解法，笔试结束后用 IDEA 花了近 2 个小时才写完，又花了一些时间优化了代码，但是不知道还有什么简单或最优的解法。


    public static class Product{}
    public static class Package{}
    public boolean productInPackage(Package packet, Product product) {}

    // n 个背包, m 个物品, 每个背包可以有某些物品任意件, 找出最少的背包包含所有的物品  注: 此题一定有解
    //不考虑背包的权重、背包中物品权重、物品数量和重量
    public Map<Product, Package> findLeastPackages(List<Product> products, List<Package> packages) {

        if (products == null || products.isEmpty() || packages == null || packages.isEmpty()) {
            return null;
        }

        Set<Product> productSet = new HashSet<>(products);
        Set<Package> packageSet = new HashSet<>(packages);

        int productsSize = productSet.size();
        int packagesSize = packageSet.size();

        //返回值
        Map<Product, Package> priorityPackages = new HashMap<>(productsSize);

        //包裹 <=> 包裹里物品的双向对应
        //可以使用 Guava 的 Bimap
        Map<Package, Set<Product>> allPackages = new HashMap<>(packagesSize);
        Map<Set<Product>, Package> productSetPackage = new HashMap<>(packagesSize);

        //寻找到包含数量物品种类最大的包裹
        Package maxProductsPackage = null;
        Set<Product> productTempSet = null;

        for (Package aPackage : packageSet) {

            if (aPackage == null) {
                continue;
            }

            //初始化 aPackage
            allPackages.put(aPackage, (productTempSet = new HashSet<>()));
            productSetPackage.put(productTempSet, aPackage);

            for (Product product : productSet) {
                if (product == null) {
                    continue;
                }

                //物品在背包中, 放入背包
                if (productInPackage(aPackage, product)) {
                    allPackages.get(aPackage).add(product);
                }
            }

            if (maxProductsPackage == null) {
                maxProductsPackage = aPackage;
            } else {
                maxProductsPackage = allPackages.get(aPackage).size() >= allPackages.get(maxProductsPackage).size() ? aPackage : maxProductsPackage;
            }
        }

        //已经找到背包有哪些物品
        //开始集合运算

        //maxProductsPackage 种类最多, 说明这个一定是最优里面的
        //maxProductsPackage 包含所有种类 直接返回
        if (allPackages.get(maxProductsPackage).size() == productSet.size()) {
            for (Product product : productSet) {
                priorityPackages.put(product, maxProductsPackage);
            }

            return priorityPackages;
        }

        //todo 机试的就写道这里  主要记不太清楚集合的交叉并补 API,时间也不足  (40 分钟白板写代码)
        //没有使用 lambda 、Stream API 主要是记忆问题(白板写代码), 还有通过数组包装局部变量, 还有多层循环 break


        // 1.删除 maxProductsPackage 子集的包裹
        // 2.找到其他包裹和 maxProductsPackage 差值最大的包裹, 并取并集作为新的 maxProductsPackage
        // 3.判断 maxProductsPackage 是否包含所有物品, 是的话返回, 不是的话重复第一步直到找到结果或集合为空(一定有答案)

        Set<Product> maxProducts = allPackages.get(maxProductsPackage);
        Set<Product> secondMaxProducts = null;

        //删除最大包裹
        allPackages.remove(maxProductsPackage);

        //留下来的包裹 [不在最大包裹之内, 有差值, 但不是差值最大的]  找到差值最大的合并到 maxProducts, 然后转移到 mergeSets
        HashSet<Set<Product>> remainSets = new HashSet<>(allPackages.values());

        //和最大包裹差值最大的, 已经合并到最大包裹内 [结果一定在这个里面]
        Set<Set<Product>> mergeSets = new HashSet<>(packagesSize);
        mergeSets.add(maxProducts);

        while (maxProducts.size() != productsSize) {

            //如果 remainSets 为空,且 maxProducts.size() != productsSize 说明没有答案[不会发生]
            //可以把所有包裹相加去重后如果!= productsSize, 说明没有答案, 这样可以更快排除，这里只是以防万一
            if (remainSets.isEmpty()) {
                return null;
            }

            //寻找次大的包裹, 不需要比较优先级 [使用 iterator 模式删除元素, 优化循环]
            Iterator<Set<Product>> iterator = remainSets.iterator();

            while (iterator.hasNext()) {

                Set<Product> next = iterator.next();
                next.removeAll(maxProducts);

                //是 maxProducts 的子集
                if (next.isEmpty()) {
                    iterator.remove();
                    continue;
                }

                //初始化 secondMaxProducts    可以删除次大元素减小集合
                if (secondMaxProducts == null) {
                    secondMaxProducts = next;
                } else {
                    secondMaxProducts = next.size() > secondMaxProducts.size() ? next : secondMaxProducts;
                }
            }

            // 已经找完，退出循环
            if (secondMaxProducts == null || secondMaxProducts.size() == 0) {
                break;
            }

            // 把 secondMaxProducts 加入到 maxProducts
            ////更新 maxProducts
            maxProducts.addAll(secondMaxProducts);

            //更新 mergeSets
            mergeSets.add(secondMaxProducts);

            //删除此元素
            remainSets.remove(secondMaxProducts);
            secondMaxProducts = null;
        }

        //mergeSets 即为所求
        mergeSets.forEach(set -> set.forEach(product -> priorityPackages.put(product, productSetPackage.get(set))));
        return priorityPackages;
    }