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

内推，二面面试官约了两天后要笔试（之前听说内推没有笔试），我不敢大意，想到工作三四年了，应该不会考察特别难的算法。查了一下别人分享的面试，要不是就是没有笔试， 要不是就是一些线性表，多线程顺序执行问题。我的算法基础还行，曾经也刷过题，线性表问题（比如反转链表，合并有序数组之类）、二叉树问题（ 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; }