我就是好奇,男生女生找工作真的有什么区别?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 9798|回复: 15
收起左侧

Pocket Gems面经题求助

[复制链接] |试试Instant~ |关注本帖
我的人缘0
xiuluoxn 发表于 2016-12-28 12:42:56 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (6)
 
 
0% (0)  踩

2016(10-12月) 码农类General 硕士 实习@PoketGem - Other - 技术电面  | Other | fresh grad应届毕业生

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

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

x
这两天就要面试第二轮了,在地里看见到面经题毫无思路,求各路大神帮助,在此跪谢!传说中的背包装宝石题目,地理最近好多人电面问到了。

/*
You’re playing your favorite RPG, and your character has just found a room full of treasure. You have n inventory slots. Luckily, objects of the same type stack together, with the maximum size of the stack depending on the type (e.g. coins might stack to 10, diamonds to 5, armor to 1, etc.). Each stack (or partial stack) takes up 1 inventory slot. Each item has a selling value (e.g. a single diamond might be worth 10, so a stack of 5 diamonds would be worth 50). You want to maximize the total selling value of the items in your inventory.
. 鐗涗汉浜戦泦,涓 来源一亩.三分地论坛.

补充内容 (2016-12-28 12:44):
/*
You’re playing your favorite RPG, and your character has just found a room full of treasure. You have n inventory slots. Luckily, objects of the same type stack together, with the maximum size ...

评分

参与人数 2大米 +8 收起 理由
singer82 + 3 很有用的信息!
newgod2500 + 5 感谢分享!

查看全部评分


上一篇:Amazon OA2 用priority_queue可以自己寫comparator function嗎?
下一篇:BB电面

本帖被以下淘专辑推荐:

我的人缘0
38448787825 发表于 2017-7-10 01:18:38 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  100% (4)
 
 
0% (0)  踩

if(amt>maxStack){. 1point3acres
                maxHeap.add(value*maxStack);
                maxHeap.add(value*(amt-maxStack));
            } . from: 1point3acres
这块是不是有点问题 amt 比没有说一定会小于2倍的maxStack 呀  用个循环或者直接算也行
回复

使用道具 举报

我的人缘0
 楼主| xiuluoxn 发表于 2016-12-28 12:45:07 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  100% (6)
 
 
0% (0)  踩
/*
You’re playing your favorite RPG, and your character has just found a room full of treasure. You have n inventory slots. Luckily, objects of the same type stack together, with the maximum size of the stack depending on the type (e.g. coins might stack to 10, diamonds to 5, armor to 1, etc.). Each stack (or partial stack) takes up 1 inventory slot. Each item has a selling value (e.g. a single diamond might be worth 10, so a stack of 5 diamonds would be worth 50). You want to maximize the total selling value of the items in your inventory.
Write a function to find the set of things to bring home that maximizes the total value.
Input:. 牛人云集,一亩三分地
n: The number of inventory slots. Waral 博客有更多文章,
items: Array of item types, one for each item in the room
item_infos: Array of structs, one for each unique item type
struct ItemInfo {
    String name;
    int value;
    int maximum_stack_size;
}
. from: 1point3acres

Output:
The maximum total value. 1point 3acres 论坛

. from: 1point3acres
Example input


n: 3
items: [“diamond”, “ruby”, “armor”, “diamond”, “diamond”, “ruby”, “diamond”, “diamond”, “diamond”, “diamond”, “diamond” “armor”]. 1point3acres.com/bbs
item_infos:[. 围观我们@1point 3 acres
{.留学论坛-一亩-三分地
    name=”diamond”
    value=10
    maximum_stack_size=5
},
{
    name=”ruby”.
    value=5
    maximum_stack_size=5.
},
{
    name=”armor”. 一亩-三分-地,独家发布
    value=25
    maximum_stack_size=1
}
]


Example output. 1point3acres
105 (1 stack of 5 diamonds worth 50, 1 partial stack of 3 diamonds worth 30, 1 stack of 1 armor worth 25)
. 牛人云集,一亩三分地
*/
回复

使用道具 举报

我的人缘0
kunge12345 发表于 2016-12-28 13:25:13 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  91% (227)
 
 
8% (21)  踩
这题就是greedy吧,看面经很多人说用个堆,然后就能转换成top K了,不太能明白。。。我用的最朴素的办法。。。放一个算一下。。。
  1. class Tuple{
  2.     String name;
  3.     int value;
  4.     int maximum_stack_size;
  5.     public Tuple(String name, int value, int maximum_stack_size){
  6.         this.name = name;
  7.         this.value = value;
  8.         this.maximum_stack_size = maximum_stack_size;
  9.     }
    .本文原创自1point3acres论坛
  10. }. 一亩-三分-地,独家发布

  11. public class Main {

  12.     public static int maxValue(int n, String[] items, Tuple[] item_infos){. 1point3acres
  13.         int val = 0;. 牛人云集,一亩三分地
  14.         HashMap<String, Integer> maxMap = new HashMap<>(); 来源一亩.三分地论坛.
  15.         HashMap<String, Integer> valMap = new HashMap<>();
  16.         HashMap<String, Integer> countMap = new HashMap<>();
  17.         for (Tuple item_info : item_infos){
  18.             maxMap.put(item_info.name, item_info.maximum_stack_size);.1point3acres网
  19.             valMap.put(item_info.name, item_info.value);
  20.         }
  21.         for(String item : items){
  22.             countMap.put(item, countMap.getOrDefault(item, 0) + 1);
  23.         }
  24.         for(int i = 0; i < n && !countMap.isEmpty(); i++){
  25.             int max = 0;
  26.             String select = "";
  27.             int num = 0;. 一亩-三分-地,独家发布
  28.             for (String item : countMap.keySet()){
  29.                 int count = countMap.get(item);.1point3acres网
  30.                 if(count >= maxMap.get(item)){
  31.                     if(maxMap.get(item) * valMap.get(item) > max) {
  32.                         select = item;
  33.                         num = maxMap.get(item);-google 1point3acres
  34.                         max = maxMap.get(item) * valMap.get(item);
  35.                     }
  36.                 }
  37.                 else{-google 1point3acres
  38.                     if (count * valMap.get(item) > max){
    .本文原创自1point3acres论坛
  39.                         select = item;
  40.                         num = count;
  41.                         max = count * valMap.get(item);
  42.                     }
  43.                 }
  44.             }. From 1point 3acres bbs
  45.             val += max;
  46.             if(!select.equals("")){
  47.                 countMap.put(select, countMap.get(select) - num);
  48.                 if (countMap.get(select) == 0){
  49.                     countMap.remove(select);
  50.                 }
  51.             }
  52.         }
  53.         return val;
  54.     }
  55. . more info on 1point3acres
  56.     public static void main(String[] args) {
  57.         // write your code here
  58.         Tuple[] tuples = new Tuple[3];
  59.         tuples[0] = new Tuple("diamond", 10, 5);
  60.         tuples[1] = new Tuple("ruby", 5, 5);
  61.         tuples[2] = new Tuple("armor", 25, 1);
  62.         String[] items = {"diamond", "ruby", "armor", "diamond", "diamond", "ruby", "diamond", "diamond", "diamond", "diamond",
  63.          "diamond", "armor"};
  64.         System.out.println(maxValue(3, items, tuples));
  65. -google 1point3acres
  66.     }
  67. }
复制代码

评分

参与人数 1大米 +3 收起 理由
cxb1027 + 3 感谢分享!

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| xiuluoxn 发表于 2016-12-28 12:44:21 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (6)
 
 
0% (0)  踩
上面题目被截断了
回复

使用道具 举报

我的人缘0
swufejun 发表于 2016-12-28 13:33:00 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  93% (208)
 
 
6% (15)  踩
kunge12345 发表于 2016-12-28 00:25
这题就是greedy吧,看面经很多人说用个堆,然后就能转换成top K了,不太能明白。。。我用的最朴素的办法。 ...

我有些明白了...用一个maxHeap吧,比如说ruby的信息是value10, item10, 一个stack能放5个ruby,diamond的value是100,item2,一个stack一个diamond,这时候写一个堆,diamond就在最顶端,
回复

使用道具 举报

我的人缘0
kunge12345 发表于 2016-12-28 14:03:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (227)
 
 
8% (21)  踩
我的理解是,对于每个item,可以用总的个数除以一个stack最多能放的个数,得到放满的stack个数,并算这些stack的value,并且丢到heap里面,然后再算余数对应stack的value,丢到heap里去,最后取top k...我不明白的事....这么算复杂度真的有优化么?假设k很小,item很多...岂不是做了很多没必要的维护堆的操作?sift up/sift down
回复

使用道具 举报

我的人缘0
 楼主| xiuluoxn 发表于 2016-12-28 14:21:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (6)
 
 
0% (0)  踩
听你这么一说忽然有点理解了heap做法。
Mobile Apps Category (English)728x90
回复

使用道具 举报

我的人缘0
 楼主| xiuluoxn 发表于 2016-12-28 17:05:51 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (6)
 
 
0% (0)  踩
kunge12345 发表于 2016-12-28 14:03
我的理解是,对于每个item,可以用总的个数除以一个stack最多能放的个数,得到放满的stack个数,并算这些st ...

突然想到heap的优化了, 你的code复杂度是O(k*n), 相对于每个slot, worst case要遍历整个items(或余下的)一遍. 而heap的做法,复杂度是O(nlog(k)),只用遍历一遍, 然后存入一个大小为k的heap就完事了. 不知道我的想法有没有道理.
回复

使用道具 举报

我的人缘0
kunge12345 发表于 2016-12-28 23:06:37 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (227)
 
 
8% (21)  踩
xiuluoxn 发表于 2016-12-28 17:05
突然想到heap的优化了, 你的code复杂度是O(k*n), 相对于每个slot, worst case要遍历整个items(或余下的) ...

有道理!这样就比朴素方法好了!
回复

使用道具 举报

我的人缘0
reboot329 发表于 2016-12-28 23:23:03 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (84)
 
 
4% (4)  踩
我是按每种东西的最大数量打包,不够的也打成一个包。PQ存包,comparator按照包里的总价值,然后就是k largest了。。
回复

使用道具 举报

我的人缘0
 楼主| xiuluoxn 发表于 2016-12-29 04:02:18 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (6)
 
 
0% (0)  踩
reboot329 发表于 2016-12-28 23:23. 一亩-三分-地,独家发布
我是按每种东西的最大数量打包,不够的也打成一个包。PQ存包,comparator按照包里的总价值,然后就是k larg ...

没错,这样就可以简化成top k的缩减版了
回复

使用道具 举报

我的人缘0
zws1818918 发表于 2017-1-17 19:19:03 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  76% (19)
 
 
24% (6)  踩
xiuluoxn 发表于 2016-12-28 17:05
突然想到heap的优化了, 你的code复杂度是O(k*n), 相对于每个slot, worst case要遍历整个items(或余下的) ...

想请问下楼主,heap的做法为什么是nlog(k)呢?
回复

使用道具 举报

我的人缘0
allenxn24 发表于 2017-1-18 03:56:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (19)
 
 
0% (0)  踩
遍历整个数组是n (item 个数), 遍历同时维护k size的heap是log(k). 所以我觉得是nlog(k).
回复

使用道具 举报

我的人缘0
CSIYI 发表于 2017-6-29 03:12:59 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (16)
 
 
0% (0)  踩

  1. public static int maxValue(int n, String[] stuff, item[] items ){
  2.         Map<String, Integer> cntMap = new HashMap<String,Integer>();
  3.         for(String s:stuff){
  4.             cntMap.put(s,cntMap.getOrDefault(s,0)+1);
  5.         }
  6.         PriorityQueue<Integer> maxHeap =
  7.                          new PriorityQueue<>((x,y)->(y-x));
  8.         Map<String, item> itemMap = new HashMap<String, item>();.留学论坛-一亩-三分地
  9.         for(item i: items){
  10.             itemMap.put(i.name, i);. 一亩-三分-地,独家发布
  11.         }
  12.         
  13.         for(String key: cntMap.keySet()){
  14.             int amt = cntMap.get(key);
  15.             int maxStack = itemMap.get(key).max_stack;. 围观我们@1point 3 acres
  16.             int value = itemMap.get(key).value;
  17.             if(amt>maxStack){. 一亩-三分-地,独家发布
  18.                 maxHeap.add(value*maxStack);
  19.                 maxHeap.add(value*(amt-maxStack));
  20.             }else{
  21.                 maxHeap.add(value*amt);
  22.             }
  23.             -google 1point3acres
  24.         }. 留学申请论坛-一亩三分地
  25.         int t=0, rlt = 0;
  26.         while(t<n){
    . 围观我们@1point 3 acres
  27.             rlt+=maxHeap.poll();
  28.             t++;
  29.         }.留学论坛-一亩-三分地
  30.         return rlt;
  31.         
  32.     }
复制代码
回复

使用道具 举报

我的人缘0
zzzShxin 发表于 2018-1-2 05:18:02 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (12)
 
 
0% (0)  踩

maxHeap.add(value*(amt-maxStack));
这一句是不是有问题啊 amt-maxStack有可能依然大于maxStack,那么就不可以放入堆中吧
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

custom counter

GMT+8, 2018-7-20 09:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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