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