一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3416|回复: 38
收起左侧

一道极难的Zenefits电面题

[复制链接] |试试Instant~ |关注本帖
2326 发表于 2015-10-10 10:11:44 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Zenefits - 内推 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
帮同学发的:.鏈枃鍘熷垱鑷1point3acres璁哄潧
一堆商品,买一个可以送一个,但送的那个的价格必须小于买的那个的价格(强调一下,不能等于)。给定商品总数n和每个商品的价格,求得到全部商品的最少开销。
例如:4个商品价格为[5, 4, 3, 3],最优解为9,即买5和4,送3和3。
随题附送两个test case: [100, 99, 98, 1, 1, 1], [100, 99, 98, 98, 97, 97, 97, 97]
想了一天了,还请地里的大神不吝赐教。

本帖被以下淘专辑推荐:

北美农民 发表于 2015-10-10 11:16:20 | 显示全部楼层
这题不需要dp. 就是排序后贪心, 从大到小排序后从左往右找到最大的ai, 然后从a [ i + 1] 往后找到严格小于a的数字, 配成一对买下, 直到所有商品都买完。

证明: 假设价格排序后变成ai > aj > ak > af, ai用户必须买, 没有商品价格大于ai;  如果ai带走ak或者af, 那么剩下必须买aj, 因此花费是ai + aj; 因此购买ai的赠送品只能够找ai右边最大的aj才能摆脱次大aj的开销, 之后剩下ak和af同理。 因此最小开销就是买ai, ak赠送aj和af..1point3acres缃

补充内容 (2015-10-10 09:13):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
此方法没考虑dups, 是错误的。

评分

1

查看全部评分

回复 支持 0 反对 2

使用道具 举报

July_26 发表于 2015-12-3 16:38:43 | 显示全部楼层
上一条发错,说下我的思路。

1. 价格最高的商品必须买,
2. 只需要比较两种情况: 一是 按价格从高到底的顺序从剩余商品中减去已购买的最高价商品数量,然后递归计算。   二是把价格第二高的商品也全部买下,然后从剩余商品中减去已买商品总数,递归计算。 (可证)

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
以下是代码
  1. import java.util.AbstractMap;
  2. import java.util.Arrays;
  3. import java.util.Collections;
  4. import java.util.HashMap;
  5. import java.util.LinkedList;
  6. import java.util.List;
  7. import java.util.Map;

  8. /**
  9. * Created by shuailu on 12/2/15.. visit 1point3acres.com for more.
  10. */
  11. public class LowestPrice {
  12.     public static int buyThemAll(Integer[] prices) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  13.         if (prices == null || prices.length < 1) {
  14.             return 0;
  15.         }
  16.         List<HashMap.Entry<Integer, Integer>> groupedList = groupPrices(prices);
  17.         return buyThemAll(groupedList);. visit 1point3acres.com for more.
  18.     }

  19.     public static int buyThemAll(List<HashMap.Entry<Integer, Integer>> toBuy) {
  20.         printList(toBuy);
  21.         if (toBuy == null || toBuy.isEmpty()) {
  22.             return 0;
  23.         }

  24.         int largestPrice = toBuy.get(0).getKey();
  25.         int largestNum = toBuy.get(0).getValue();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  26.         int currentAmount = (largestNum * largestPrice);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  27.         if (toBuy.size() == 1) {
  28.             return currentAmount;
  29.         }
  30.         int secondPrice = toBuy.get(1).getKey();
  31.         int secondNum = toBuy.get(1).getValue();
  32.         int secondTotal = secondPrice * secondNum;

  33.         //amount if buy second largest as well
  34.         System.out.println("Skip " + largestNum + " " + largestPrice + "s");
  35.         int amountIfBuyOne = buyThemAll(removeNLargestPrices(toBuy, largestNum * 2));
  36.         int amountIfBuyTwo = buyThemAll(removeNLargestPrices(toBuy, (largestNum + secondNum) * 2));. 1point3acres.com/bbs

  37.         currentAmount = currentAmount + Math.min(amountIfBuyOne, amountIfBuyTwo + secondTotal);. From 1point 3acres bbs
  38.         return currentAmount;
  39.     }

  40.     private static List<HashMap.Entry<Integer, Integer>> removeNLargestPrices(List<HashMap.Entry<Integer, Integer>> toBuy, int n) {
  41.         List<HashMap.Entry<Integer, Integer>> copy = new LinkedList<Map.Entry<Integer, Integer>>();
  42.         for (HashMap.Entry<Integer, Integer> entry : toBuy) {
  43.             copy.add(new AbstractMap.SimpleEntry<Integer, Integer>(entry.getKey(), entry.getValue()));
  44.         }

  45.         while (n > 0 && copy.size() > 0) {
  46.             HashMap.Entry<Integer, Integer> currentLevel = copy.get(0);
  47.             if (currentLevel.getValue() > n) {
  48.                 currentLevel.setValue(currentLevel.getValue() - n);
  49.                 return copy;
  50.             }
  51.             n = n - currentLevel.getValue();
  52.             copy.remove(0);
  53.         }
  54.         return copy;
  55.     }


  56. . From 1point 3acres bbs

  57.     private static LinkedList<HashMap.Entry<Integer, Integer>> groupPrices(Integer[] prices) {
  58.         Arrays.sort(prices, Collections.reverseOrder());
  59.         LinkedList<HashMap.Entry<Integer, Integer>> list = new LinkedList<HashMap.Entry<Integer, Integer>>();
  60.         int currentPrice = prices[0];
  61.         list.add(getEntry(currentPrice, 1));
  62.         for (int n = 1; n < prices.length; n++) {
  63.             int price = prices[n];
  64.             if (currentPrice == price) {
  65.                 list.getLast().setValue(list.getLast().getValue() + 1);
  66.             } else {
  67.                 currentPrice = price;
  68.                 list.addLast(getEntry(price, 1));
  69.             }
  70.         }
  71.         return list;
  72.     }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  73. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  74.     public static HashMap.Entry<Integer, Integer> getEntry(int price, int num) {
  75.         return new AbstractMap.SimpleEntry<Integer, Integer>(price, num);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  76.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  77. . 1point3acres.com/bbs

  78.     public static void main(String[] args) {
  79. //        System.out.println(buyThemAll(new Integer[] {5, 4, 3, 3})); // should be9. 1point 3acres 璁哄潧
  80.         System.out.println(buyThemAll(new Integer[] {6, 5, 4, 3, 3, 3})); // should be9
  81. //        System.out.println(buyThemAll(new Integer[] {100, 99, 98, 1, 1, 1 })); //should be 200
  82. //        System.out.println(buyThemAll(new Integer[] {100, 99, 98, 98, 98, 98, 97, 96})); //should be 395
  83.     }

  84.     private static void printList(List<HashMap.Entry<Integer, Integer>> list) {. from: 1point3acres.com/bbs
  85.         System.out.println("Elements in list");
  86.         for (HashMap.Entry<Integer, Integer> entry : list) {
  87.             System.out.print("price: " + entry.getKey() + ",  number" + entry.getValue());.1point3acres缃
  88.             System.out.println("\t");. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  89.         }. From 1point 3acres bbs
  90.     }. 1point 3acres 璁哄潧
  91. . visit 1point3acres.com for more.
  92. }.鏈枃鍘熷垱鑷1point3acres璁哄潧
复制代码

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷补充内容 (2015-12-3 16:49):
好吧,好像是不对的。我迅速的发现我自己的第二个test case其实是个反例,按照我的想法会返回16, 但应该是15。。。 密切关注这个帖子,求高人指导。。。
回复 支持 0 反对 1

使用道具 举报

likita1002 发表于 2015-10-10 10:38:55 | 显示全部楼层
我有一点想法,不知道对不对. 1point 3acres 璁哄潧
1. 从大到小排序
2. 假设没有duplicate,那么就是买nums[0],送nums[1],买nums[2],送nums[3]。。。两个list,买,送,L买(nums[0],nums[2]...) L送(nums[1],nums[3]...)
3.那么 有duplicate时,比如 买nums[i],送nums[i+1], nums[i] = nums[i+1] 时,就从买的那个L里,找出最小的大于nums[i]的数,和nums[i]换

example:100,99,98,1,1,1
开始:买100送99,买98送1,买1送1,1一样,1就和99换,就是买100送1,99送1,98送1

这个在[100, 99, 98, 98, 97, 97, 97, 97]这个适用,不知道能不能还有什么例子可以不适用这个方法
回复 支持 反对

使用道具 举报

 楼主| 2326 发表于 2015-10-10 10:40:31 | 显示全部楼层
likita1002 发表于 2015-10-10 10:38. From 1point 3acres bbs
我有一点想法,不知道对不对
1. 从大到小排序
2. 假设没有duplicate,那么就是买nums[0],送nums[1],买num ...

[100, 99, 98, 1, 1, 1]的最优解是:100送99,98送1,买1,买1
回复 支持 反对

使用道具 举报

yyz999 发表于 2015-10-10 10:40:46 | 显示全部楼层
likita1002 发表于 2015-10-10 10:38
我有一点想法,不知道对不对
1. 从大到小排序
2. 假设没有duplicate,那么就是买nums[0],送nums[1],买num ...

你的example就不适用吧
100 98 1 1 更便宜
回复 支持 反对

使用道具 举报

clfhaha1234 发表于 2015-10-10 10:44:56 | 显示全部楼层
贪心。
. more info on 1point3acres.com
count表示价格第i贵的商品的数量,然后2个指针,分别是赠品指针(初始在最后最便宜的商品),商品指针(初始在第二便宜的商品)
2个指针往前扫,更新count数量,并且维护商品指针在赠品指针前面,直到所有count都被清空就行。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

lz看下这样可行么?

补充内容 (2015-10-10 10:48):
[100,99,98,1,1,1]这组过不了,从前往后扫到是可以过
回复 支持 反对

使用道具 举报

 楼主| 2326 发表于 2015-10-10 10:55:09 | 显示全部楼层
clfhaha1234 发表于 2015-10-10 10:44
贪心。
. 1point3acres.com/bbs
count表示价格第i贵的商品的数量,然后2个指针,分别是赠品指针(初始在最后最便宜的商品),商 ...

请问一下,[100, 99, 2]的结果是什么?按我理解的您的算法,第一步就是买99,但最优解是:100送99,买2
回复 支持 反对

使用道具 举报

clfhaha1234 发表于 2015-10-10 11:03:51 | 显示全部楼层
2326 发表于 2015-10-10 10:55
请问一下,[100, 99, 2]的结果是什么?按我理解的您的算法,第一步就是买99,但最优解是:100送99,买2
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
从前往后扫的话就没问题,先count一下数量,然后商品指针在100,赠品指针在99往后扫

实在不行就dp[j]表示前i个count的商品剩j个赠品指标的最小费用. 1point3acres.com/bbs
dp[j]=min(dp[i-1][j+count-k]+cost[j]*k,dp[j-1]+cost[j])(0<=k<=count).
前i-1个商品每增加一个赠品限额的代价应该是递增的,所有这里应该可以二分
回复 支持 反对

使用道具 举报

likita1002 发表于 2015-10-10 11:27:36 | 显示全部楼层
2326 发表于 2015-10-10 10:40
[100, 99, 98, 1, 1, 1]的最优解是:100送99,98送1,买1,买1

啊对啊 我没想买了不送了
回复 支持 反对

使用道具 举报

303002319 发表于 2015-10-10 12:05:19 | 显示全部楼层
我的想法是:. 1point3acres.com/bbs
1.排序,从大到小,假设存放在A中
2.找到当前最大的,记录到结果中并在A中删除,同时查找比这个最大值小的值中的最大值,也就是剩余值中的最大值,若存在,则从A中删除,不存在就不做任何处理。.1point3acres缃
3.重复第二步,直到A为空。
这里假设A是个容器,如果是数组可以考虑建一个boolean的辅助数组记录元素是否被挑选过。. visit 1point3acres.com for more.

回复 支持 反对

使用道具 举报

 楼主| 2326 发表于 2015-10-10 12:20:34 | 显示全部楼层
北美农民 发表于 2015-10-10 11:16
这题不需要dp. 就是排序后贪心, 从大到小排序后从左往右找到最大的ai, 然后从a [ i + 1] 往后找到严格小 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
没有duplicate大家都会,有duplicate你的证明就不对,自己试一试[5, 4, 3, 3]的例子
回复 支持 反对

使用道具 举报

 楼主| 2326 发表于 2015-10-10 12:21:19 | 显示全部楼层
303002319 发表于 2015-10-10 12:05
我的想法是:
1.排序,从大到小,假设存放在A中.鏈枃鍘熷垱鑷1point3acres璁哄潧
2.找到当前最大的,记录到结果中并在A中删除,同时查找比 ...

请试一试[5, 4, 3, 3]
回复 支持 反对

使用道具 举报

北美农民 发表于 2015-10-10 12:38:34 | 显示全部楼层
2326 发表于 2015-10-9 23:20
没有duplicate大家都会,有duplicate你的证明就不对,自己试一试[5, 4, 3, 3]的例子
. more info on 1point3acres.com
有道理, 没想到dups会有这个情况。
回复 支持 反对

使用道具 举报

aiuou 发表于 2015-10-10 12:51:04 | 显示全部楼层
把我的解法拿出来抛个砖,另一个帖子里贴过
-google 1point3acres

楼主我说一下我自己的想法,可能不见得对。先统计一下每个价钱商品的个数,然后sort,存成一个list
6,5,3,3,3,2,2,2 就变成 6,5,3(3), 2(3)。括号里面表示这个价钱的商品有几个。然后我就maintain一个array。假设一共有n个商品,m个distinct 价格,那么array的row为m,col为n。array的column index表示,我还可以free拿几个商品(我给他起个名字叫free budget),array[j]表示在处理i个价格,并且有j个free budget的情况下,我所需要的最小开销。比如上面那个例子:一共8个商品(6,5,3,3,3,2,2,2).int [] []array= new int[4][8],array每个element的初始值设为max为所有商品价钱之和
然后我就loop m个价钱,每个商品有两种可能,一种是花钱,一种是白拿。假设每个价钱商品假设有k个,free和pay的组合最多有k+1种。按上面的例子,第一个商品价钱为6,只有1个,因为它最贵,所以必须买,买完后array[0]=[max, 6, max, max ,max ,max, max,max,max]. 6放在index为1的位置上,表明在有1个free的budget的前提下,我的最小花销为6. 然后下一轮第二个价格是5, 5有两种情况花钱和不花钱。这时候我loop array并且update相应的值。先看array[0][0]=max,第0位表示没有free的budget,那只能买,买的结果是max+5,买后的free budget变成1。于是我们拿array[0][0]和array[1][1]比较,max+5>max, 所以array[1][1]=max。接下来看array[0][1]=6,仍然两种选择,买和free,买的话,就有了2个budget,总花销为11,于是比较11和array[1][2]=max,11比较小,那么array[1][2]=11.  如果白拿的话,花销还是6,那么free budget要减1, 因为array[1][0]=max>6,所以array[1][0]=6.  接下来第三个价格是3, 一共有3个。因为array[1][0]=6, 3个都必须买,array[2][3]=3*3+6=15.  然后array[1][1]=max,可以直接跳过。 array[1][2]=11, 那么就有3种情况,3个都买,买2个,买一个。如果3个都买,array[2][5]=20。如果买2个,花销是17,对应的column index-1+2=3,  此时的array[2][3]=15<17, 所以保持15不变。 买1个的话  column index-2+1, 更新array[2][1]=14 。
就这样一点点推下去。
空间O(mn),时间O(n^2)

不知道对不对。
回复 支持 反对

使用道具 举报

tailofjune 发表于 2015-10-10 13:16:53 | 显示全部楼层
这个题如果no duplicate很好做,所以我的想法是分情况.
假设已经从大到小排好序了.
基本思路是先一路扫描,把不重复的元素先配好对.然后发现重复元素之后尝试把原来配好的对拆开与重复元素重新组合,如果价格反而升高了就保持原配对,将重复元素与后面的别的元素配对.如果配到最后没有别的元素了,就单独买.(在代码里是与0配对).
我验证了一下这几个样例是对的,不过还不太清楚是不是一定正确.
  1. -google 1point3acres
  2. import java.util.*;.鐣欏璁哄潧-涓浜-涓夊垎鍦

  3. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  4. public class Test {
  5.   public static void main(String[] args) {
  6.     final int[][] costs = {
  7.         {100, 99, 98, 98, 97, 97, 97, 97},
  8.         {5, 4, 3, 3},
  9.         {100, 99, 98, 1, 1, 1},. visit 1point3acres.com for more.
  10.     };
  11.     for(int[] cost: costs)
  12.       System.out.println("cost of "+Arrays.toString(cost)+" is "+buy(cost));
  13.   }-google 1point3acres
  14.   .鏈枃鍘熷垱鑷1point3acres璁哄潧
  15.   public static int buy(final int[] costs) {
  16.     LinkedList<Pair> pairs = new LinkedList<>();
  17.     int start = 0, end;
  18.     int count;
  19.     while(start<costs.length) {. from: 1point3acres.com/bbs
  20.       count = 0;
  21.       while(start<costs.length&&
  22.             (start==costs.length-1||costs[start]!=costs[start+1])) {
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  23.         ++count; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  24.         if(count==2) {
  25.           pairs.add(new Pair(costs[start-1], costs[start]));
  26.           count = 0;
  27.         }
  28.         ++start;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  29.       }
  30.       end = start;
  31.       while(end<costs.length&&costs[end]==costs[start])
  32.         ++end;
  33.       if(count==1) {
  34.         Pair pair = new Pair(costs[start-1], costs[start]);
  35.         int index = pairs.size(); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  36.         int temp = adjust(costs, start+1, end, pairs);
  37.         pairs.add(index, pair);
  38.         start = temp;. from: 1point3acres.com/bbs
  39.       }. 1point3acres.com/bbs
  40.       else
  41.         start = adjust(costs, start, end, pairs);
  42.     }
  43.    
  44.     return calculate(pairs);. 鍥磋鎴戜滑@1point 3 acres
  45.   }
  46.   
  47.   private static int adjust(final int[] costs, int start, int end, .鐣欏璁哄潧-涓浜-涓夊垎鍦
  48.                             final LinkedList<Pair> pairs) {. 1point 3acres 璁哄潧
  49.     ListIterator<Pair> iter = pairs.listIterator(pairs.size());
  50.     while(iter.hasPrevious()&&start+1<end) {
  51.       Pair pair = iter.previous();
  52.       if(pair.second>=costs[start]*2) .鏈枃鍘熷垱鑷1point3acres璁哄潧
  53.         break;
  54.       iter.add(new Pair(pair.second, costs[start]));. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  55.       iter.previous();
  56.       pair.second = costs[start];
  57.       start += 2;
  58.     }
  59.     int end0 = end;. From 1point 3acres bbs
  60.     while(start<end0&&end<costs.length)
  61.       pairs.add(new Pair(costs[start++], costs[end++]));
  62.     while(start<end0)
  63.       pairs.add(new Pair(costs[start++], 0));
  64.     return end;. visit 1point3acres.com for more.
  65.   }
  66.   .鐣欏璁哄潧-涓浜-涓夊垎鍦
  67.   private static int calculate(final LinkedList<Pair> pairs) {
  68.     System.out.println(pairs);. more info on 1point3acres.com
  69.     return pairs.stream().mapToInt(pair->pair.first).sum();
  70.   }
  71. }

  72. class Pair {
  73.   int first;
  74.   int second;. from: 1point3acres.com/bbs
  75.   .鐣欏璁哄潧-涓浜-涓夊垎鍦
  76.   Pair(int f, int s) {
  77.     first = f;
  78.     second = s;
  79.   }
  80.   
  81.   @Override
  82.   public String toString() {
  83.     return "("+first+","+second+")";. Waral 鍗氬鏈夋洿澶氭枃绔,
  84.   }
  85. }
复制代码
回复 支持 反对

使用道具 举报

tailofjune 发表于 2015-10-10 13:24:47 | 显示全部楼层
tailofjune 发表于 2015-10-10 13:16
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴这个题如果no duplicate很好做,所以我的想法是分情况..1point3acres缃
假设已经从大到小排好序了.
基本思路是先一路扫描, ...

测了一下上面同学的例子还是有问题,主要是这样拆开了配对的就不会再组回去了.
回复 支持 反对

使用道具 举报

wxhuann 发表于 2015-10-10 13:28:21 | 显示全部楼层
确实好像有些难度,和同学讨论了一下没有想出来解法,先马克一下。感谢楼主供题。
回复 支持 反对

使用道具 举报

303002319 发表于 2015-10-10 14:18:55 | 显示全部楼层
2326 发表于 2015-10-10 12:21
请试一试[5, 4, 3, 3]

恩,还是不行~.1point3acres缃
回复 支持 反对

使用道具 举报

edly 发表于 2015-10-10 14:54:38 | 显示全部楼层
先将重复的合并,变成若干个pair(a,b)的形式,表示有b个a元的物品,并且a递减
如[5,4,3,3]->[(5,1),(4,1),(3,2)]

DP,F[i][j]表示DP完前i个pair,其中有j个商品买了但还没有选择送的商品. from: 1point3acres.com/bbs
假设第i个pair是(ai,bi),考虑其bi个中有x是买的,那么剩下bi-x个都是送的
F[i][j + x - (bi - x)] = min{F[i - 1][j] + x * ai} (j >= 0, j - (bi - x) >= 0)

O(n^2)
回复 支持 反对

使用道具 举报

leolyq 发表于 2015-10-10 22:06:51 | 显示全部楼层
北美农民 发表于 2015-10-10 11:16
这题不需要dp. 就是排序后贪心, 从大到小排序后从左往右找到最大的ai, 然后从a [ i + 1] 往后找到严格小 ...

这个应该有问题。
[100, 99, 98, 98, 97, 97, 97, 97] 这个case应该就过不了。
按照这个算法,买100送99,买98送97,买98送97,买97,买97
实际更省的方法是:买100送97,买99送97,买98送97,买98送97

DP应该可以解决,更优化的方法还没想到
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 16:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表