在国外一跟老外吵架口语立刻就不够用了

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 2034|回复: 17
收起左侧

Zenifits面经

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

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

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

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

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空了

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

使用道具 举报

 楼主| 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
比如6,5,3,3这种情况,其实应该买6,5

嗯,你说的对。
那我就只能想出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的数 是肯定要花钱买的。

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

重复上述步骤?. 一亩-三分-地,独家发布

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

使用道具 举报

 楼主| 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
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

maplain 发表于 2015-10-9 14:42:30 | 显示全部楼层
bowenwang1225 发表于 2015-10-9 13:58
我还没完全理解你的方法,你可以尝试一下这个例子Check一下:6, 5,4,3,3,3,2,2
. Waral 博客有更多文章,
恩,照我上面说的那样会返回6,5,4,3,但是起码6,4,3,3就更优一些。

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

谢谢
回复 支持 反对

使用道具 举报

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)
. Waral 博客有更多文章,
不知道对不对。
回复 支持 反对

使用道具 举报

 楼主| bowenwang1225 发表于 2015-10-9 22:58:57 | 显示全部楼层
aiuou 发表于 2015-10-9 15:35
楼主我说一下我自己的想法,可能不见得对。先统计一下每个价钱商品的个数,然后sort,存成一个list. more info on 1point3acres
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。
面试遇到这个题,真是太难了。想出来也写不完 ...

感觉这个解法靠谱!时间上可以进一步稍做优化,通过更新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 ...
. from: 1point3acres
max free budget 怎么算?
这是我的代码,求优化,求指点
  1. package zenefits;

  2. import java.util.Collections;. 围观我们@1point 3 acres
  3. import java.util.Map.Entry;. from: 1point3acres
  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++){. From 1point 3acres bbs
  10.                         if(map.containsKey(value[i])){
  11.                                 map.put(value[i], map.get(value[i])+1);
  12.                         }else{
  13.                                 map.put(value[i], 1);. 1point 3acres 论坛
  14.                         }
  15.                 }
  16.                 int m=map.size(),n=value.length, max=0;. more info on 1point3acres
  17.                 long[][] a= new long [m][n+1];
  18.                 for(int i=0;i<value.length;i++){.1point3acres网
  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;. Waral 博客有更多文章,
  24.                         }. visit 1point3acres for more.
  25.                 }
  26.                 Iterator<Entry<Integer,Integer>> it = map.entrySet().iterator();
  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;
  33.                                 }else{
  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;
  39.                                                 if(index<n&&index>=0)
  40.                                                 {a[i][index]=Math.min(a[i][index], a[i-1][j]+(t-k)*entry.getKey());}
  41.                                         }
  42.                                 }
  43.                         }
  44.                 }
  45.                 long min=max;-google 1point3acres
  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.         }
  53.         public static void main(String[] args) {
  54.                 // TODO Auto-generated method stub       
  55.                   final int[][] values = {.本文原创自1point3acres论坛
  56.                                 {100, 99, 98, 98, 97, 97, 97, 97},
  57.                                 {5, 4, 3, 3},
  58.                                 {6, 5, 3, 3},. 1point 3acres 论坛
  59.                                 {100, 99, 98, 1, 1, 1},
  60.                                 {3,5,6,3}.留学论坛-一亩-三分地
  61.                             };
  62.                   for(int[] value: values)
  63.                       System.out.println("Least pay of "+Arrays.toString(value)+" is "+getLeastPay(value));
  64.         }
  65. }
复制代码
回复 支持 反对

使用道具 举报

rebe90 发表于 2015-10-11 04:47:53 | 显示全部楼层
aiuou 发表于 2015-10-10 14:37
max free budget 怎么算?
这是我的代码,求优化,求指点
. Waral 博客有更多文章,
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>());
    vector<int> prices;.1point3acres网
    unordered_map<int, int> priceType;
    int total = 0;. 1point3acres
    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();
    size_t n = nums.size() + 1;. Waral 博客有更多文章,
    vector<int> prev(n, total);
    vector<int> curr(n, total);
   
   
    // 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) {. 围观我们@1point 3 acres
                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);. 牛人云集,一亩三分地
                }
            }
        }
        prev = curr;. 牛人云集,一亩三分地
        fill_n(curr.begin(), n, total);
        max_budget += priceType[prices];
    }
   
    int res = total;. 1point 3acres 论坛
    for (size_t k = 0; k <= max_budget; k++) {
        res = min(res, prev[k]);.1point3acres网
    }
    return res;
}
回复 支持 反对

使用道具 举报

aiuou 发表于 2015-10-11 06:03:13 | 显示全部楼层

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

使用道具 举报

aiweiwei 发表于 2016-2-2 06:05:09 | 显示全部楼层
bowenwang1225 发表于 2015-10-9 11:06. 一亩-三分-地,独家发布
比如6,5,3,3这种情况,其实应该买6,5
.本文原创自1point3acres论坛
不行该是买6. 3吗
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2016-2-2 06:05:17 | 显示全部楼层
aiuou 发表于 2015-10-9 12:39
嗯,你说的对。
那我就只能想出O(n^2)的解法了。面试官要求给O(n)的解法吗?
. 1point 3acres 论坛
不行该是买6. 3吗
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-23 13:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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