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


 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;
}