一亩三分地论坛

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

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

Zenifits面经

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

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

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

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

x
刚店面完下午,买东西的题。Given prices. When you buy one item with $x, you can get any other one item that cheaper(<) than $x for free. What is the minimum money you have to pay to buy all of them. 并不是太会,求思路。主要是处理duplicates不太好弄。请大神们指点。面试的大哥提示先走一遍处理Duplicates但是并没说别的。
坐看云起 发表于 2015-10-9 10:35:14 | 显示全部楼层
建立item类,里面存每种商品的价格和数量,然后根据价格降序排列,然后。。。。 贪心吧?
回复 支持 反对

使用道具 举报

aiuou 发表于 2015-10-9 10:57:11 | 显示全部楼层
同楼上,先存item的商品和数量,排序后,放入一个stack里。先pop出最贵的商品,比如说有n个,那这n个都要买。然后查看访问stack的peek element,看看目前第二贵的商品有几个,如果大于n个,则pop出来后把商品数减n再push回去(这n个可以free拿到的),如果不足第二贵的商品数量不足n,就从第三贵的里面减。依此类推,直到stack空了. from: 1point3acres.com/bbs

不知道这个方法可行不
回复 支持 反对

使用道具 举报

 楼主| bowenwang1225 发表于 2015-10-9 11:06:30 来自手机 | 显示全部楼层
aiuou 发表于 2015-10-9 10:57
同楼上,先存item的商品和数量,排序后,放入一个stack里。先pop出最贵的商品,比如说有n个,那这n个都要买 ...

比如6,5,3,3这种情况,其实应该买6,5
回复 支持 反对

使用道具 举报

aiuou 发表于 2015-10-9 12:39:30 | 显示全部楼层
bowenwang1225 发表于 2015-10-9 11:06. 1point 3acres 璁哄潧
比如6,5,3,3这种情况,其实应该买6,5

嗯,你说的对。. more info on 1point3acres.com
那我就只能想出O(n^2)的解法了。面试官要求给O(n)的解法吗?
回复 支持 反对

使用道具 举报

 楼主| bowenwang1225 发表于 2015-10-9 12:43:21 | 显示全部楼层
aiuou 发表于 2015-10-9 12:39
嗯,你说的对。
那我就只能想出O(n^2)的解法了。面试官要求给O(n)的解法吗?

他没说最优解的time complexity但是他提示是要先过一遍处理duplicates
回复 支持 反对

使用道具 举报

maplain 发表于 2015-10-9 13:44:15 | 显示全部楼层
排序后,从左向右,第一次遇到duplicates的时候,如果左侧非duplicates的数目为m, duplicatesd的数目为n(n>=2), 那么(n-m)*duplicate的数 是肯定要花钱买的。. from: 1point3acres.com/bbs

所以不妨假设 m <= n,这个时候最贵的肯定是要买的,因为没人能带走它。最贵的买了之后,如果要带走一个非duplicate,出于贪心原则,肯定是要带走身后的,但是如果带走了身后的,意味着一定有两个duplicate的数需要花钱买。所以比较一下最大的身后的那个数的值和2*duplicate的数的值即可。-google 1point3acres

重复上述步骤?

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

使用道具 举报

 楼主| bowenwang1225 发表于 2015-10-9 13:58:55 | 显示全部楼层
maplain 发表于 2015-10-9 13:44
排序后,从左向右,第一次遇到duplicates的时候,如果左侧非duplicates的数目为m, duplicatesd的数目为n(n> ...

我还没完全理解你的方法,你可以尝试一下这个例子Check一下:6, 5,4,3,3,3,2,2
回复 支持 反对

使用道具 举报

maplain 发表于 2015-10-9 14:42:30 | 显示全部楼层
bowenwang1225 发表于 2015-10-9 13:58
我还没完全理解你的方法,你可以尝试一下这个例子Check一下:6, 5,4,3,3,3,2,2

恩,照我上面说的那样会返回6,5,4,3,但是起码6,4,3,3就更优一些。

如果把我上面说的看duplicate的顺序改成从右往左,就会返回6,4,3,3, 但是我不能很确定地保证6,4,3,3是这个例子的答案,更不能保证这个逻辑是理论上正确的。。囧==我再想想。。
. visit 1point3acres.com for more.
谢谢
回复 支持 反对

使用道具 举报

aiuou 发表于 2015-10-9 15:35:28 | 显示全部楼层
bowenwang1225 发表于 2015-10-9 13:58
我还没完全理解你的方法,你可以尝试一下这个例子Check一下:6, 5,4,3,3,3,2,2

楼主我说一下我自己的想法,可能不见得对。先统计一下每个价钱商品的个数,然后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)

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

使用道具 举报

 楼主| bowenwang1225 发表于 2015-10-9 22:58:57 | 显示全部楼层
aiuou 发表于 2015-10-9 15:35
楼主我说一下我自己的想法,可能不见得对。先统计一下每个价钱商品的个数,然后sort,存成一个list
6,5, ...

感觉靠谱!我再体会一下!感谢
回复 支持 反对

使用道具 举报

aiuou 发表于 2015-10-9 23:38:20 | 显示全部楼层
bowenwang1225 发表于 2015-10-9 22:58
感觉靠谱!我再体会一下!感谢

空间可以优化到O(n),因为每个row的值只取决于上一个row。
面试遇到这个题,真是太难了。想出来也写不完。
回复 支持 反对

使用道具 举报

rebe90 发表于 2015-10-11 04:30:12 | 显示全部楼层
aiuou 发表于 2015-10-9 09:38
空间可以优化到O(n),因为每个row的值只取决于上一个row。
面试遇到这个题,真是太难了。想出来也写不完 ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
感觉这个解法靠谱!时间上可以进一步稍做优化,通过更新maxFreeBudget来减少遍历column数,比如6,5, 4, 3, 3, 3, 2, 2这个例子,maxFreeBudget依次更新为1,2,3,6,8
回复 支持 反对

使用道具 举报

aiuou 发表于 2015-10-11 04:37:02 | 显示全部楼层
rebe90 发表于 2015-10-11 04:30
感觉这个解法靠谱!时间上可以进一步稍做优化,通过更新maxFreeBudget来减少遍历column数,比如6,5, 4 ...

max free budget 怎么算?
这是我的代码,求优化,求指点
  1. package zenefits;

  2. import java.util.Collections;
  3. import java.util.Map.Entry;. Waral 鍗氬鏈夋洿澶氭枃绔,
  4. import java.util.Set;
  5. import java.util.*;

  6. public class BuyOneGetOneFree {

  7.         public static long getLeastPay(int [] value){
  8.                 TreeMap<Integer,Integer> map = new TreeMap<Integer,Integer>(Collections.reverseOrder());
  9.                 for(int i=0;i<value.length;i++){
  10.                         if(map.containsKey(value[i])){
  11.                                 map.put(value[i], map.get(value[i])+1);
  12.                         }else{
  13.                                 map.put(value[i], 1);
  14.                         }
  15.                 }
  16.                 int m=map.size(),n=value.length, max=0;
  17.                 long[][] a= new long [m][n+1];
  18.                 for(int i=0;i<value.length;i++){
  19.                         max+=value[i];
  20.                 }
  21.                 for(int i=0;i<m;i++){
  22.                         for(int j=0;j<=n;j++){
  23.                                 a[i][j]=max;
  24.                         }
  25.                 }. From 1point 3acres bbs
  26.                 Iterator<Entry<Integer,Integer>> it = map.entrySet().iterator();. visit 1point3acres.com for more.
  27.                 for(int i=0;i<m;i++){
  28.                         Entry<Integer, Integer> entry= it. next();
  29.                         for(int j=0;j<=n;j++){
  30.                                 if(i==0){
  31.                                         a[i][entry.getValue()]=entry.getValue()*entry.getKey();
  32.                                         break;. 1point3acres.com/bbs
  33.                                 }else{.鏈枃鍘熷垱鑷1point3acres璁哄潧
  34.                                         if(a[i-1][j]==max) continue;
  35.                                         int t = entry.getValue();
  36.                                         for(int k=0;k<=j;k++){
  37.                                                 int index=j+t-2*k;
  38.                                                 if(k>t) break;.1point3acres缃
  39.                                                 if(index<n&&index>=0)
  40.                                                 {a[i][index]=Math.min(a[i][index], a[i-1][j]+(t-k)*entry.getKey());}
  41.                                         }. 1point3acres.com/bbs
  42.                                 }
  43.                         }
  44.                 }. 1point3acres.com/bbs
  45.                 long min=max;
  46.                 for(int i=0;i<n;i++){
  47.                         if(a[m-1][i]<min)
  48.                                 min=a[m-1][i];
  49.                 }
  50.                
  51.                 return min;
  52.         }. 1point 3acres 璁哄潧
  53.         public static void main(String[] args) {
  54.                 // TODO Auto-generated method stub        . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  55.                   final int[][] values = {
  56.                                 {100, 99, 98, 98, 97, 97, 97, 97},
  57.                                 {5, 4, 3, 3}, -google 1point3acres
  58.                                 {6, 5, 3, 3}, 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  59.                                 {100, 99, 98, 1, 1, 1},
  60.                                 {3,5,6,3}. 1point3acres.com/bbs
  61.                             };
  62.                   for(int[] value: values)
  63.                       System.out.println("Least pay of "+Arrays.toString(value)+" is "+getLeastPay(value)); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  64.         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  65. }
复制代码
回复 支持 反对

使用道具 举报

rebe90 发表于 2015-10-11 04:47:53 | 显示全部楼层
aiuou 发表于 2015-10-10 14:37
max free budget 怎么算?
这是我的代码,求优化,求指点

for(int j=0;j<=n;j++) 这里n可以用maxFreeBudget代替,每处理完第m行,maxFreeBudget += 第m种价格的商品的总数,这样虽然worst case time complexity没有变,但是应该可以节省一些时间,我用c++写的(不知道怎么贴代码T.T):

int buyOneGetOne(vector<int>& nums) {
    sort(nums.begin(), nums.end(),std::greater<int>());. more info on 1point3acres.com
    vector<int> prices;
    unordered_map<int, int> priceType;
    int total = 0;
    for (auto n : nums) {
        total += n;
        if (priceType.find(n) == priceType.end()) {
            prices.push_back(n);
            priceType[n] = 0;
        }
        priceType[n]++;
    }
   
    size_t m = prices.size();. From 1point 3acres bbs
    size_t n = nums.size() + 1;
    vector<int> prev(n, total);
    vector<int> curr(n, total);
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴    . 1point 3acres 璁哄潧
   
    // largest price: must buy all
    prev[priceType[prices[0]]] = prices[0] * priceType[prices[0]];
    size_t max_budget = priceType[prices[0]];
   
    for (size_t i = 1; i < m; i++) {
        int currCnt = priceType[prices];
        for (size_t j = 0; j <= max_budget; j++) {
            if (prev[j] != total) {
                for (int buy = currCnt; currCnt - buy <= j && buy >= 0; buy--) {
                    curr[j - currCnt + 2 * buy] = min(curr[j - currCnt + 2 * buy], prev[j] + buy * prices);
                }
            }
        }. visit 1point3acres.com for more.
        prev = curr;
        fill_n(curr.begin(), n, total);
        max_budget += priceType[prices];
    }-google 1point3acres
   
    int res = total;-google 1point3acres
    for (size_t k = 0; k <= max_budget; k++) {
        res = min(res, prev[k]);
    }
    return res;
}
回复 支持 反对

使用道具 举报

aiuou 发表于 2015-10-11 06:03:13 | 显示全部楼层
rebe90 发表于 2015-10-11 04:47.1point3acres缃
for(int j=0;j

我明白了,多谢多谢
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2016-2-2 06:05:09 | 显示全部楼层
bowenwang1225 发表于 2015-10-9 11:06
比如6,5,3,3这种情况,其实应该买6,5

不行该是买6. 3吗
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2016-2-2 06:05:17 | 显示全部楼层
aiuou 发表于 2015-10-9 12:39
嗯,你说的对。. more info on 1point3acres.com
那我就只能想出O(n^2)的解法了。面试官要求给O(n)的解法吗?

不行该是买6. 3吗
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 18:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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