阿里現(xiàn)在的面試這么難了嗎？

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

 ? ?// n 個(gè)背包, m 個(gè)物品, 每個(gè)背包可以有某些物品任意件, 找出最少的背包包含所有的物品 ?注: 此題一定有解
 ? ?//不考慮背包的權(quán)重、背包中物品權(quán)重、物品數(shù)量和重量
 ? ?public Map findLeastPackages(List products, List packages) {

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

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

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

 ? ? ? ?//返回值
 ? ? ? ?Map priorityPackages = new HashMap<>(productsSize);

 ? ? ? ?//包裹 <=> 包裹里物品的雙向?qū)?yīng)
 ? ? ? ?//可以使用 Guava 的 Bimap
 ? ? ? ?Map> allPackages = new HashMap<>(packagesSize);
 ? ? ? ?Map, Package> productSetPackage = new HashMap<>(packagesSize);

 ? ? ? ?//尋找到包含數(shù)量物品種類最大的包裹
 ? ? ? ?Package maxProductsPackage = null;
 ? ? ? ?Set 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;
 ? ? ? ? ? ?}
 ? ? ? ?}

 ? ? ? ?//已經(jīng)找到背包有哪些物品
 ? ? ? ?//開始集合運(yùn)算

 ? ? ? ?//maxProductsPackage 種類最多, 說明這個(gè)一定是最優(yōu)里面的
 ? ? ? ?//maxProductsPackage 包含所有種類 直接返回
 ? ? ? ?if (allPackages.get(maxProductsPackage).size() == productSet.size()) {
 ? ? ? ? ? ?for (Product product : productSet) {
 ? ? ? ? ? ? ? ?priorityPackages.put(product, maxProductsPackage);
 ? ? ? ? ? ?}

 ? ? ? ? ? ?return priorityPackages;
 ? ? ? ?}

 ? ? ? ?//todo 機(jī)試的就寫道這里 ?主要記不太清楚集合的交叉并補(bǔ) API,時(shí)間也不足 ?(40 分鐘白板寫代碼)
 ? ? ? ?//沒有使用 lambda 、Stream API 主要是記憶問題(白板寫代碼), 還有通過數(shù)組包裝局部變量, 還有多層循環(huán) break


 ? ? ? ?// 1.刪除 maxProductsPackage 子集的包裹
 ? ? ? ?// 2.找到其他包裹和 maxProductsPackage 差值最大的包裹, 并取并集作為新的 maxProductsPackage
 ? ? ? ?// 3.判斷 maxProductsPackage 是否包含所有物品, 是的話返回, 不是的話重復(fù)第一步直到找到結(jié)果或集合為空(一定有答案)

 ? ? ? ?Set maxProducts = allPackages.get(maxProductsPackage);
 ? ? ? ?Set secondMaxProducts = null;

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

 ? ? ? ?//留下來的包裹 [不在最大包裹之內(nèi), 有差值, 但不是差值最大的] ?找到差值最大的合并到 maxProducts, 然后轉(zhuǎn)移到 mergeSets
 ? ? ? ?HashSet> remainSets = new HashSet<>(allPackages.values());

 ? ? ? ?//和最大包裹差值最大的, 已經(jīng)合并到最大包裹內(nèi) [結(jié)果一定在這個(gè)里面]
 ? ? ? ?Set> mergeSets = new HashSet<>(packagesSize);
 ? ? ? ?mergeSets.add(maxProducts);

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

 ? ? ? ? ? ?//如果 remainSets 為空,且 maxProducts.size() != productsSize 說明沒有答案[不會(huì)發(fā)生]
 ? ? ? ? ? ?//可以把所有包裹相加去重后如果!= productsSize, 說明沒有答案, 這樣可以更快排除，這里只是以防萬一
 ? ? ? ? ? ?if (remainSets.isEmpty()) {
 ? ? ? ? ? ? ? ?return null;
 ? ? ? ? ? ?}

 ? ? ? ? ? ?//尋找次大的包裹, 不需要比較優(yōu)先級(jí) [使用 iterator 模式刪除元素, 優(yōu)化循環(huán)]
 ? ? ? ? ? ?Iterator> iterator = remainSets.iterator();

 ? ? ? ? ? ?while (iterator.hasNext()) {

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

 ? ? ? ? ? ?// 已經(jīng)找完，退出循環(huán)
 ? ? ? ? ? ?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;
 ? ?}