一亩三分地论坛

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

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

新鲜谷歌Onsite面经

[复制链接] |试试Instant~ |关注本帖
superbeet 发表于 2016-9-9 06:23:44 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - Onsite |Other在职跳槽

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

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

x
年初时候面过一次Google,一共五轮有一轮代码没写完挂了。不过可能平均成绩差的不远,这次的Recruiter直接安排了两轮Onsite。. 1point3acres.com/bbs
如果有了解类似我这种情况的坛友,请留个言有事请教~. 鍥磋鎴戜滑@1point 3 acres

第一轮,美国白人小哥。思维迅速,性格活泼。设计一个代码比较器。

第二轮,印度大叔,迟到了15分钟,好像是面试安排有问题,他以为取消了。。。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
一组array中有M个stack,每个stack里面有数量多个数字。问N次操作后能拿到的数字和最大是多少。

大家好运~ 攒人品,求offer~

评分

1

查看全部评分

本帖被以下淘专辑推荐:

william_gong 发表于 2016-9-9 10:48:46 | 显示全部楼层
请问啥叫代码比较器?谢谢
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-9-9 10:55:29 | 显示全部楼层
bless LZ. 请问一组array有M个stack,意思是array 的element都是stack吗?还是啥意思?多谢
回复 支持 反对

使用道具 举报

veryblues 发表于 2016-9-9 11:36:55 | 显示全部楼层
william_gong 发表于 2016-9-9 10:48
请问啥叫代码比较器?谢谢

可能是指git diff之类的功能
回复 支持 反对

使用道具 举报

火火火bit 发表于 2016-9-9 11:37:18 | 显示全部楼层
请问N次操作是pop n次吗
回复 支持 反对

使用道具 举报

 楼主| superbeet 发表于 2016-9-9 11:53:01 | 显示全部楼层
houqingniao 发表于 2016-9-9 10:55. Waral 鍗氬鏈夋洿澶氭枃绔,
bless LZ. 请问一组array有M个stack,意思是array 的element都是stack吗?还是啥意思?多谢

类似git diff
回复 支持 反对

使用道具 举报

 楼主| superbeet 发表于 2016-9-9 11:54:01 | 显示全部楼层
火火火bit 发表于 2016-9-9 11:37
请问N次操作是pop n次吗

对,进行N次pop操作后。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-9-9 12:57:21 | 显示全部楼层
第二轮题目不是很清楚楼主的意思,现在假设是说给定一个vector<stack<int>>类型的arr, 并且M=arr.size(), 求N次pop操作可以取出的最大值。因为在没有pop之前是不可能知道stack除了顶端之外的值,所以这道题我觉得应该问得更具体一些,就是问用贪心算法每次pop arr 中最大栈顶,然后N次这样后的操作所取的值总和。否则任何方式都无法保证一定取值总和最大。
如果是贪心算法,建一个max heap, 元素为pair<int,int>, 其中first是栈顶值,second 是该栈在arr 中的指标,按first 丛小到大定义heap 的排序。每次pop heap取当前最大值,并用pair second 判断该栈是否在arr 中已空,若未空,pop该栈顶并push 到heap 中。重复该操作N次或heap为空,whichever comes first. 该题和Leetcode 中tweeter design 的设计get most recent 10 tweets from self and followees 是一样的算法。
回复 支持 反对

使用道具 举报

Josh 发表于 2016-9-9 12:59:48 | 显示全部楼层
记得之前面经见过一道题跟楼主第二题很像:给n堆硬币,每次只能从堆顶拿一枚,问拿k个硬币最大数额是多少。应该是dp解。
回复 支持 反对

使用道具 举报

mingzhou1987 发表于 2016-9-9 13:44:42 | 显示全部楼层
贪心应该不行吧,假设某个stack底有一个超大的数,顶端是一个超小的数,不是永远选不到这个。
回复 支持 反对

使用道具 举报

火火火bit 发表于 2016-9-9 13:51:32 | 显示全部楼层
Josh 发表于 2016-9-9 12:59
记得之前面经见过一道题跟楼主第二题很像:给n堆硬币,每次只能从堆顶拿一枚,问拿k个硬币最大数额是多少。 ...
. 1point3acres.com/bbs
求解。。能想到用记忆化搜索来剪枝,但复杂度不会分析
回复 支持 反对

使用道具 举报

 楼主| superbeet 发表于 2016-9-9 13:59:55 | 显示全部楼层
Josh 发表于 2016-9-9 12:59
记得之前面经见过一道题跟楼主第二题很像:给n堆硬币,每次只能从堆顶拿一枚,问拿k个硬币最大数额是多少。 ...

在哪里看到的?
回复 支持 反对

使用道具 举报

daniel_hl 发表于 2016-9-9 14:47:40 | 显示全部楼层
diff那个是类似于edit distance吗
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-9-9 21:17:42 | 显示全部楼层

http://www.1point3acres.com/bbs/ ... read&tid=189741. visit 1point3acres.com for more.

第一题
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-9-9 21:23:06 | 显示全部楼层
火火火bit 发表于 2016-9-9 13:51
求解。。能想到用记忆化搜索来剪枝,但复杂度不会分析

你的记忆化搜索打算纪录哪些状态呢?
回复 支持 反对

使用道具 举报

 楼主| superbeet 发表于 2016-9-10 00:29:26 | 显示全部楼层
有坛友了解碰到"面试官迟到很久面试很仓促"这种情况,应该怎么处理呢?
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-9-10 05:42:15 | 显示全部楼层
mingzhou1987 发表于 2016-9-9 13:44
贪心应该不行吧,假设某个stack底有一个超大的数,顶端是一个超小的数,不是永远选不到这个。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
你说的没错。关键是这个“使取出的值总和最大”怎么理解。因为STL API对于stack只提供查询top的值,在没有pop之前永远不知道地下的元素值。所以我对这道题的假设是提前不能知道除stack top之外的元素值。那么在没有额外信息的条件下就只有贪心算法了。
事实上,可以很容易举反例说明无论怎么pop都不可能保证取出的值总和最大。例如N=2,每个stack只有2个元素,所有top元素都是1, 但只有一个stack底的元素很大。理论上pop的最优方式是就pop光这个stack的2个元素,但初始状态下无法确定这个stack在array中的哪一个。
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-9-10 05:45:00 | 显示全部楼层
楼主可以再具体澄清一下“N次操作后能拿到的数字和最大是多少” 是怎么定义的吗?在初始状态下我们是否可以知道每个stack中所有元素的值?还是只能通过stack::peek只知道顶端的值?
回复 支持 反对

使用道具 举报

南慕伦 发表于 2016-9-10 07:26:26 | 显示全部楼层
dp啦
dp[i][j]表示前i个栈取j个数字的最大值
显然dp[i][j] = max{dp[i-1][k] + sum[i][0..(j-k-1)]}
边界条件就是dp[0][j] = 0
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-9-10 09:53:15 | 显示全部楼层
OK. I see. 用DP就相当于可以不断地用前i个stack用不同的pop方式来查看stack top下面的若干值,而且可以将pop出来的元素再push回去复原,之前计算dp[i][j]用的pop不计入最终的N次操着(这样的确是可以保证策划出最大总和的)。我以为是面对M个stack就一共只给N次pop的机会,一旦用过不可以后悔(这样是不可能0风险的)。如果的这样的话可以用array重新叙述题目更清楚:给一个vector<vector<int>> arr, 其中M = arr.size(), 但arr[i].size()对不同的i可以不同。要求取一个arr的二维总size为N的子集,限制每个arr[i]只能取连续的前几个(也允许根本不取)。 这样就明确说明所有arr中的元素是都可以预知的,个人感觉这样就比较明确。当然也许真正面试中可以真正澄清这些问题,呵呵,只是个人看法而已。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 06:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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