一亩三分地论坛

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

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

Google 2016 summer intern 面经

[复制链接] |试试Instant~ |关注本帖
dukangs 发表于 2016-2-5 00:39:14 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Failfresh grad应届毕业生

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

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

x
报个谷歌的面经回馈地里. 虽然感觉谷歌没多少重题, 多少给大家一些启发.
内推的很早, 大概15年感恩节前一两周, 后来一直没联系安排面试, 可能真的很忙吧HR. 一开始给的word格式的简历, 说有问题, 然后重新发的pdf, 这里耽误了时间, 大家吸取我的教训. 和我一起投的哥们比我早几天投的,早面了一个月. 后来安排面试,因为人在国内不方便,最后推到一月15号面的.我另一个师兄通过了面试但是没过match,现在还可能offer失效,所以早点面有好处的,起码组里坑多一些.


题目:
一面:
白人小哥, 用gVoice打的听的不是很清晰, 还有就是感觉语速特别慢, 不知道是不是信号原因, 问了背包问题, 完全没准备, 因为回国玩了一个月, 题目都荒废了, 而且这个背包的问题是NP问题, 挺难的, 没想到会考, 先是说所有物品价值一样, follow up 是 物品价值有1 或 2, 在不超重的情况下怎么往包里装,价值最大,包空间无限大,但是限重.做的很差, 打算用dp,O(n^2)解决, 但是他说太复杂了,希望O(N)时间解决, 我实在想不出来线性时间解法.时间用完了,问了问题,拜拜.(第一次技术面就面谷歌感觉真作死
.鏈枃鍘熷垱鑷1point3acres璁哄潧

二面:.鏈枃鍘熷垱鑷1point3acres璁哄潧
貌似是国人大哥,用座机打的,很清楚,这里大家注意,遇到听不清的果断让对方换电话,不然会吃亏的. 问了个二叉搜索树的问题, 一听BST发现两棵树哪些节点不同,就没想太多,直接中序遍历存到链表里,然后扫一遍就完了,接着follow up了一个啥问题,有点记不清了,反正面完第一轮已经放弃希望了,而且发现一个月不写码,真的写的好慢,最后理所应当的挂了.

评分

2

查看全部评分

本帖被以下淘专辑推荐:

johnjavabean 发表于 2016-2-5 03:47:26 | 显示全部楼层
第一题直接greedy,还有就算dp复杂度也不是n^2而是nk,k是限重可以指数级增长的
回复 支持 反对

使用道具 举报

DreamBoy 发表于 2016-2-8 15:32:28 | 显示全部楼层
johnjavabean 发表于 2016-2-5 03:47. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第一题直接greedy,还有就算dp复杂度也不是n^2而是nk,k是限重可以指数级增长的

dp不是optimal的吗

补充内容 (2016-2-8 15:33):
greedy应该不行的吧 你思路怎么样的?
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-9 05:10:28 | 显示全部楼层
DreamBoy 发表于 2016-2-8 15:32
.1point3acres缃dp不是optimal的吗
. from: 1point3acres.com/bbs
补充内容 (2016-2-8 15:33):

价值一样直接用重量反序排序,价值分1和2用价值/重量排序,然后greedy,可保证最优
回复 支持 反对

使用道具 举报

一岁上山采药 发表于 2016-2-9 08:12:45 | 显示全部楼层
johnjavabean 发表于 2016-2-9 05:10
价值一样直接用重量反序排序,价值分1和2用价值/重量排序,然后greedy,可保证最优

-google 1point3acres层主英明。 但是好像greedy只能保证可分割的物品最优吧。不可分割的物品要保证最优只能dp。
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-9 09:06:20 | 显示全部楼层
一岁上山采药 发表于 2016-2-9 08:12-google 1point3acres
层主英明。 但是好像greedy只能保证可分割的物品最优吧。不可分割的物品要保证最优只能dp。

他这个限制了价值只有1和2,明显不是让你用dp的,可以先用价值/重量排序,遇到tie再按照重量轻的来排序就行了,当然如果每个物品价值都不一样那只能普通nk的dp做了...背包问题这个分为很多情况,什么可分割,不可分割,每种只有一个,每种可以拿无限个....
回复 支持 反对

使用道具 举报

一岁上山采药 发表于 2016-2-9 10:38:55 | 显示全部楼层
johnjavabean 发表于 2016-2-9 09:06
他这个限制了价值只有1和2,明显不是让你用dp的,可以先用价值/重量排序,遇到tie再按照重量轻的来排序就 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
层主英明。有这样一个case,
tag:               A,   B,  C,   D
value:            1,   2,   1,   2
wight:            1,   2,   2,   4
value/wight:    1,   1,  0.5, 0.5     
bag capacity: 7
按照层主所说,先按价值/重量 排序, tie之后按照重量轻重排序,排出来就是:
value:             1,   2,   1,   2
wight:             1,   2,   2,   4
value/wight:    1,   1,  0.5, 0.5   

那么层主的greedy按照这个顺序装容量为7的背包,只会选到前三个物品(即A,B,C),那么总重量为5, 总价值为4, 最后会剩下两个重量的空间放不下第四件物品。(实际上这个case的最优解是A,B,D)

可分割物品的意思是剩下的两个空间可以拿来装一般D物品,这样greedy可以得到最优解。而不可分割的物品就是不能放D进入背包,最后导致空间浪费,这样greedy不能得到最优解。

补充内容 (2016-2-9 10:39):
装一“半”的D物品
回复 支持 反对

使用道具 举报

DreamBoy 发表于 2016-2-9 11:11:44 | 显示全部楼层
一岁上山采药 发表于 2016-2-9 10:38
层主英明。有这样一个case,
tag:               A,   B,  C,   D
value:            1,   2,   1,   2 ...

有没有比较好的链接介绍这个的?只会最general case用dp的表示看不懂T^T
回复 支持 反对

使用道具 举报

DreamBoy 发表于 2016-2-9 11:16:56 | 显示全部楼层
johnjavabean 发表于 2016-2-9 09:06
他这个限制了价值只有1和2,明显不是让你用dp的,可以先用价值/重量排序,遇到tie再按照重量轻的来排序就 ...
. visit 1point3acres.com for more.
仔细看了看 终于明白了==原来还有这么多case长见识了==只知道英文名是knapsack problem 原来是书包的意思啊==自己之前自己看的算法也真是只学了个皮毛~~惭愧了
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-9 12:38:03 | 显示全部楼层
一岁上山采药 发表于 2016-2-9 10:38
层主英明。有这样一个case,
tag:               A,   B,  C,   D
value:            1,   2,   1,   2 ...

可能是我想错了,你这个case的确过不了,tie的时候怎么处理没想太明白....
回复 支持 反对

使用道具 举报

mint1126 发表于 2016-2-10 21:54:39 | 显示全部楼层
背包问题,动态规划,受教了
回复 支持 反对

使用道具 举报

DreamBoy 发表于 2016-2-11 01:39:23 | 显示全部楼层
johnjavabean 发表于 2016-2-9 12:38
可能是我想错了,你这个case的确过不了,tie的时候怎么处理没想太明白....

我昨天看了看 0-1问题是不能用greedy的,只有fractional可以
回复 支持 反对

使用道具 举报

mchzh 发表于 2016-2-11 01:46:04 | 显示全部楼层
google太不容易了,这题目一个都不会
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-7 02:56:00 | 显示全部楼层
第一题不知道怎么才能做到O(n), 第二题应该不用放到链表中吧
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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