一亩三分地论坛

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

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

G家电面

[复制链接] |试试Instant~ |关注本帖
alittlesheep 发表于 2015-8-22 13:56:04 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 博士 全职@Google - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
回馈地里。电面一共两题。第一题是给一组id和表示每个id出现概率的数组,概率之和为1.要求随机生成id,使得随机出的id满足之前的概率数组。
followup:如果id很多,调用这个随机生成方法的次数也很多,怎么优化
第二题大致是背包问题的变形,物品可切分,限制条件是如果放则必须放当前总体积的一半以上,求最后的最大价值。
followup: dp的空间优化


补充内容 (2015-8-22 13:57):
大米,攒rp
. Waral 鍗氬鏈夋洿澶氭枃绔,. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2015-8-26 20:53):.鐣欏璁哄潧-涓浜-涓夊垎鍦
第二题可能没说清楚,如果某个可切分物品的总体积是V, 要求如果放,则至少要放V/2, 之后多放,每次多放1个体积单元,也就是步长为1的增加

评分

3

查看全部评分

thebestsarah 发表于 2015-8-26 13:39:22 | 显示全部楼层
楼主好人!能给我也发一份背包的code吗~拜托拜托
回复 支持 1 反对 0

使用道具 举报

 楼主| alittlesheep 发表于 2015-8-24 09:21:49 | 显示全部楼层
alucardzhou 发表于 2015-8-24 03:00
第一题感觉是设计一个hashing function.1point3acres缃
随机到一个0到1之间的double
然后将它变成ID

恩,这是将id和区间做mapping,每次random处一个0-1之间的double,查找属于哪个区间,然后是输出哪个id
.1point3acres缃
预处理得区间是O(n),查找用二分是O(lgn)
回复 支持 1 反对 0

使用道具 举报

 楼主| alittlesheep 发表于 2015-8-26 20:40:39 | 显示全部楼层
jiebour 发表于 2015-8-25 00:37
楼主,总体积一半以上,但还是需要保持整数对吧?
.1point3acres缃
恩,就是在背包的两层循环里,加上一层从 当前物品体积的一半 到 全部体积 的 步长为1 的判断
回复 支持 1 反对 0

使用道具 举报

jiebour 发表于 2015-8-22 14:40:12 | 显示全部楼层
当前总体积指的是该物品的总体积还是背包目前塞的东西的总体积?
回复 支持 反对

使用道具 举报

 楼主| alittlesheep 发表于 2015-8-22 15:55:03 | 显示全部楼层
jiebour 发表于 2015-8-22 14:40
当前总体积指的是该物品的总体积还是背包目前塞的东西的总体积?

该物品的总体积
回复 支持 反对

使用道具 举报

say543 发表于 2015-8-23 13:19:26 | 显示全部楼层
LZ 第一題有點不太懂  跟之前的面經好像不太一樣  given a probability = [.5 .1 .2 .2], label = [A B C D]  什麼是output 呢?
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-24 01:54:09 | 显示全部楼层
say543 发表于 2015-8-23 13:19
LZ 第一題有點不太懂  跟之前的面經好像不太一樣  given a probability = [.5 .1 .2 .2], label = [A B C  ...

同不懂,楼主说的略模糊啊。。。。. visit 1point3acres.com for more.
回复 支持 反对

使用道具 举报

alucardzhou 发表于 2015-8-24 02:53:12 | 显示全部楼层
第一题:
所给ID: 1, 2, 3
所给概率:0.1, 0.3, 0.6

现在我们要随机生成一个ID,这个生成方法要求按照概率来生成。
也就是10% 给出1, 30% 给出2, 60% 给出3.
以上是我的理解
回复 支持 反对

使用道具 举报

alucardzhou 发表于 2015-8-24 03:00:20 | 显示全部楼层
第一题感觉是设计一个hashing function. 1point 3acres 璁哄潧
随机到一个0到1之间的double
然后将它变成ID
1[0-0.1]; 2[0.1-0.4];  3[0.4-1]
借助我上面的例子,随机到0.88
返回id 3
回复 支持 反对

使用道具 举报

 楼主| alittlesheep 发表于 2015-8-24 09:19:53 | 显示全部楼层
alucardzhou 发表于 2015-8-24 02:53
第一题:
所给ID: 1, 2, 3. 鍥磋鎴戜滑@1point 3 acres
所给概率:0.1, 0.3, 0.6
-google 1point3acres
是的,是这样的
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-25 00:37:36 | 显示全部楼层
楼主,总体积一半以上,但还是需要保持整数对吧?
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-8-25 00:56:33 | 显示全部楼层
求楼主贴solution code
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-25 01:01:07 | 显示全部楼层
hulahu 发表于 2015-8-25 00:56. from: 1point3acres.com/bbs
求楼主贴solution code

hulahu,求看你站内信,我给你留言了。。。。。。。。
回复 支持 反对

使用道具 举报

hulahu 发表于 2015-8-25 03:09:14 | 显示全部楼层
jiebour 发表于 2015-8-25 01:01
.1point3acres缃hulahu,求看你站内信,我给你留言了。。。。。。。。

木有啊, 再发下吧。
回复 支持 反对

使用道具 举报

icloud925925 发表于 2015-8-26 01:25:47 | 显示全部楼层
求背包变形的solution code
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-26 02:09:00 | 显示全部楼层
hulahu 发表于 2015-8-25 03:09. more info on 1point3acres.com
木有啊, 再发下吧。

你看下你refer的Gmail。。。。
回复 支持 反对

使用道具 举报

w41q 发表于 2015-8-26 02:49:03 | 显示全部楼层
alittlesheep 发表于 2015-8-24 09:21
恩,这是将id和区间做mapping,每次random处一个0-1之间的double,查找属于哪个区间,然后是输出哪个id

...

请问怎么优化呢?
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-26 02:54:10 | 显示全部楼层
w41q 发表于 2015-8-26 02:49
请问怎么优化呢?
-google 1point3acres
同问怎么优化。。。。
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-8-26 02:54:22 | 显示全部楼层
w41q 发表于 2015-8-26 02:49
请问怎么优化呢?

同问,怎么优化。。。。
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-8-26 11:53:46 | 显示全部楼层
jiebour 发表于 2015-8-26 02:54
同问,怎么优化。。。。

就二分去查找区间吧
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-8-26 12:25:24 | 显示全部楼层
请问第一题id很多的情况怎么优化?感觉还是用二分啊?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 06:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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