一亩三分地论坛

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

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

Google Intern面经 1/26

[复制链接] |试试Instant~ |关注本帖
testgre 发表于 2016-1-27 06:41:40 | 显示全部楼层 |阅读模式

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

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

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

x
找实习找到现在都没有offer,心累……刚刚面完Google两轮电面,发面经攒人品求pass!是的我是话唠所以每段前加了tag方便快速浏览。
面试是学长内推的,很早就推了但是怕准备不足就约到一月底才面,觉得真是失策,听说现在bar高了position也少了,真是应该早点面的……

第一轮
[废话] 面试前提前准备好草稿纸google doc电话,结果电话来了一接,对面听不到我说话,他又recall了两次我说要不hangout吧,接通的时候已经过了10多分钟了不过hangout有个好处就是知道对方是谁一下就在linkedin找到了,然而好像也没什么用……
[自我介绍] 白人小哥,视频看着像在床上不知道是什么节奏,也不废话,说你先介绍一下自己吧,我就介绍了一下,之前没准备,说了两句就没话说了,就说要不我介绍一个项目吧,然后就介绍了本科时一个推荐系统的项目,我准备的剧本是[小哥听不懂也不感兴趣,让我直接做题],结果没想到小哥可能对这个挺了解的,一边听一边问问题,还challenge我们之前的做法……本来当时就不是研究的很深,年代还这么久远,只能胡扯了,扯了约莫10分钟小哥说emm...我还是觉得有点问题,不过没什么时间了我们做题吧。. visit 1point3acres.com for more.

[题目] 给一个helper function:rand32,能生成0<=x<=2^32的随机数x,让基于它实现rand2ToThe(n),生成0<=x<=2^n的随机数……

妈呀我脑子里链表二叉树哈希表都准备好了小哥你出数学题……只能硬上,以前想过类似的题目,我的想法是让生成的范围比需要的范围大,然后不符合要求的就扔掉,然后说我们先考虑n<=32的情况,小哥一边听一边就在google doc写起来了,让我有种面试他的感觉……写好让我算complexity,WTF……这种complexity以前都没算过,就胡扯了很多概率什么的东西,最后只好说我不懂,小哥几乎是手把手教我算了出来,方法是列递归式子,
  1. T(N) = O(1) /* 生成随机数 */ + p(/* 取到2^n之外的数 */) T(N)
复制代码
这么看来就很简单了,
  1. T(N) = 1 / p(/* 取到2^n之内的数 */) = 2^32 / 2^n
复制代码

还是基本功不够啊……在N小的时候复杂度还挺大的,说怎么优化,我说主要的浪费就在扔掉那部分,我们让那部分减小吧,比如要生成0<=x<=m的数,我们只有0<=x<=n (n>m),就把n分成k份m大小的group,只要落在这些group的都可以 %m 返回,不在group的才扔掉,写了code,小哥看了看说嗯,但是应该没有不在group里的吧因为都是2的次方,我说啊好像是……所以最后的code就长这样……(小哥说你爱写什么?我说C吧,小哥说好,然后就写了Python)
  1. <div>def rand2ToThe(n):</div><div>    return (rand32() & ((1 << n) - 1))</div>
复制代码
竟然是O(1)的说实话我做之前完全没想到……小哥看了看想了想说诶其实就是生成32位你再截最后n位嘛,我觉得妈呀小哥的确是挺聪明的……我反正是没想到……然后小哥说如果n大于32呢,我说有了之前的结论这个就简单了,生成好几个32位的随机数拼起来再截最后n位好了,小哥说怎么拼呢?我还以为想问高精度加减乘除法,说了一溜,小哥说不不不我不是问这个,搞了好久才明白小哥要的答案是左移再or起来……交流障碍……

[follow up] 然后小哥说要不来个rand3ToThe(n)?妈呀还来……我想了几个方法好像都不work,我说要不就
  1. return rand2ToThe(log(3^n)/log(2))
复制代码
吧,还能推广到k^n,小哥说emm好像make sense,再想想说不对,你这个log(3^n)/log(2)不是整数啊……搞搞搞搞了好久最后我能想到的只有
  1. num = rand2ToThe(ceiling(log(k^n)/log(2))),如果不在k^n之内的扔掉,否则返回
复制代码
小哥说这个复杂度呢,我随口说了这样估计和最开始的方法一样挺大的,小哥又想了想说em好像不对,我写了等式,
  1. <div>x = ceiling(log(k^n)/log(2))</div><div>l = 2^x - 2^x / k^n</div><div>O() = 2^x / l</div>
复制代码
小哥说你看这里其实2^x - k^n是不超过2的,所以最后的复杂度还是近似O(N/2+1) (N/2 是我说的求k^n至少要n/2)……真是服得没有脾气……
第一轮的总体感觉就是上数学课老师一直在说我只能点头的感觉……只做了一题还基本是小哥做出来的……
最后电话响了,我特别不好意思说小哥实在对不起第二轮来了,要不byebye了?不知道小哥有没有生气……

第二轮

[废话] 照样先打了两次电话,我有经验了说要不hangout吧,没耽误多少时间。看名字是亚裔,但是没有口音,上来就不废话做题。

[题目一] “有一个2d matrix……”我就乐了,range sum 和 search a 2d matrix 我虽然没有都做,但是大概看过怎么做。他给的题是range sum 2d matrix - mutable,还是简单版,只query [0,0] to [x,y]。我知道可以做到O(logN),次优也可以做到O(N),可是我一念之差想着要不装装没做过?就给了个 set: O(1), query: O(NM) 的算法,然后我说啊好像好大啊,小哥说嗯是挺大,不过如果 set >> query会很有用,我说啊有道理,然后小哥说如果 query>>set 呢?我就说看着像dp啊,把pseudo code写出来了,本来准备主动提出写 set query 均O(N)的写法的,因为O(logN)的没写过……结果小哥说嗯要不我们来设计几个test case?妈呀早知道上来给O(N)了……然后设计了几个test case,以前没有做过,只能想出几个边界条件。最后小哥说嗯我们来个example walk through一下吧。

[题目一解法] 这道题我看过三种解法,一种是每次query现算那么 set:O(1), query:O(NM); 一种是dp,dp[j] = sum((0,0) ... (i,j)),每次set更新dp数组,set:O(NM), query:O(1);另一种我只知道可用线段树或者树状数组做,可以做到set和query都是O(logN),但是觉得好复杂就没看……

[题目二] 然后小哥说再来一题吧,给一个列表的数字,用他们和加减乘除算出一个数,输出所有可能的结果。这个以前没见过,我说要不DFS?用set记录最后的结果,时间复杂度O(4^N),他说那写吧,我就写了pseudo code,然后小哥说你这太pseudo了,我赶紧改了下……改完我说诶这种题好像都可以加memorization诶,还滔滔不绝,小哥说不这题不行,我想了想好像的方法的确不work……小哥就check了一下好像没问题,然后让设计test case,照样不懂,小哥说嗯没了,我还以为要优化呢……最后小哥说时间不多了你提问吧,我就问了几个问题小哥好像很赶时间,就bye了。

第二轮两道题都没有做优化,心里虚的很,小哥也不爱说话,我一直瞎逼逼说冷笑话他也不接着,觉得真是心累。第二轮第二题我不知道能不能优化,大家有什么想法么?
. visit 1point3acres.com for more.
总结:
1. 实习应该早准备早找,晚了难不难我不知道,至少心理压力很大
2. 装逼要懂得拿捏,我介绍简历时装逼来了个推荐系统结果没想到小哥懂,range sum 2d matrix装逼就连优化都没做
3. Google的题目感觉还真的不难,但是我自己就真的做不出来,还是服得没有脾气……

求offer啊一天天过去找不到实习真是要疯了另外我看以前的帖子好像有主动要求加面的?不知大家知不知道要怎么申请?可是这样好不好呢?如果万一幸运过了而加面跪了不是犯傻了……

. 1point3acres.com/bbs

补充内容 (2016-1-27 06:43):. more info on 1point3acres.com
原来code里换行会把包着的<div>也加上……大家把<div>脑补成换行吧……或者版主能不能帮忙编辑一下谢谢!-google 1point3acres

补充内容 (2016-1-28 12:18):
想起来第一轮的时候我当时说错了,求k^n时间复杂度是logN……真是要哭
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2016-2-2 12:05):
今天下午收到邮件说next step!感谢大家的鼓励!不过听说team match也不是容易的,继续攒人品!!如果有朋友有team match的消息能不能麻烦告知呀!多谢多谢!!

评分

2

查看全部评分

本帖被以下淘专辑推荐:

singku 发表于 2016-1-27 08:07:23 | 显示全部楼层
我也是刚面完 心累啊。
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-1-27 09:01:15 | 显示全部楼层
第二面挺友善的...不过第一面这个数学题真是..........
回复 支持 反对

使用道具 举报

 楼主| testgre 发表于 2016-1-27 10:00:25 | 显示全部楼层
singku 发表于 2016-1-27 08:07
我也是刚面完 心累啊。

祝一起进pool!
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-1-27 15:28:52 | 显示全部楼层
2^n其实可以分段generate,如果n>32,那么generate一个32的,然后左移32,再generate 32的。 如果n<32,其实直接截取后半部分就行了,例如n=5,直接 &000011111就行了。至于3^n就不知道了。。。
回复 支持 反对

使用道具 举报

 楼主| testgre 发表于 2016-1-27 15:38:43 | 显示全部楼层
zxl9171 发表于 2016-1-27 15:28
2^n其实可以分段generate,如果n>32,那么generate一个32的,然后左移32,再generate 32的。 如果n

是的,2^n就是按你说的那么做!不过我花了好久才做出来……
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-1-28 02:15:23 | 显示全部楼层
testgre 发表于 2016-1-27 15:38
是的,2^n就是按你说的那么做!不过我花了好久才做出来……

但是3^n还是没想出来。。。难道是取最小的大于3^n的2^k,如果超过3^n就重新roll?
回复 支持 反对

使用道具 举报

 楼主| testgre 发表于 2016-1-28 04:11:11 | 显示全部楼层
zxl9171 发表于 2016-1-28 02:15
但是3^n还是没想出来。。。难道是取最小的大于3^n的2^k,如果超过3^n就重新roll?

我只知道这种解法,看起来效率还不错,不过不知道还有没有更好的做法~
回复 支持 反对

使用道具 举报

yixianpig 发表于 2016-1-30 10:15:11 | 显示全部楼层
testgre 发表于 2016-1-28 04:11
我只知道这种解法,看起来效率还不错,不过不知道还有没有更好的做法~

关于那个rand3ToThe(n),可不可以先generate a random number through the helper function rand32, then divide it by 2^32, then multiply it by 3^n...这方法好像耍赖了
回复 支持 反对

使用道具 举报

 楼主| testgre 发表于 2016-1-30 11:10:37 | 显示全部楼层
yixianpig 发表于 2016-1-30 10:15.鏈枃鍘熷垱鑷1point3acres璁哄潧
关于那个rand3ToThe(n),可不可以先generate a random number through the helper function rand32, then ...

哈哈我觉得数学题并没有耍不耍赖啦~
只是我觉得这个方法可能不work?我的想法是因为这些函数返回的都是整数,所以我理解的这个做法是把2^32个整数映射到3^n个整数去,因为数量不一样我们应该不能保证这3^n个整数等概率被抽中?
比如说,rand32只能返回2^32个整数,在n比较大的时候是没有办法把这2^32个整数一一映射到3^n个整数去的,所以有些数会选不到;而在n比较小的时候,如果把这2^32个整数多对一映射到3^n个整数去,这个可能并不能保证每一个3^n内的整数都有相同个数的2^32整数映射过来,也就是说这3^n个整数并不等概率了。
回复 支持 反对

使用道具 举报

yixianpig 发表于 2016-1-30 11:22:40 | 显示全部楼层
testgre 发表于 2016-1-30 11:10
哈哈我觉得数学题并没有耍不耍赖啦~
只是我觉得这个方法可能不work?我的想法是因为这些函数返回的都是 ...

对耶,这个好难...感觉小哥就随便一问,肯定不会算面试有效成绩的恩恩!!
回复 支持 反对

使用道具 举报

 楼主| testgre 发表于 2016-1-30 11:31:08 | 显示全部楼层
yixianpig 发表于 2016-1-30 11:22
对耶,这个好难...感觉小哥就随便一问,肯定不会算面试有效成绩的恩恩!!

然而过了三天都没有消息心累
回复 支持 反对

使用道具 举报

singku 发表于 2016-1-30 12:29:08 | 显示全部楼层
testgre 发表于 2016-1-30 11:31.鏈枃鍘熷垱鑷1point3acres璁哄潧
然而过了三天都没有消息心累
.1point3acres缃
楼主我早上发邮件问了 HR说要1-2周才发拒信。
回复 支持 反对

使用道具 举报

 楼主| testgre 发表于 2016-1-30 13:07:22 | 显示全部楼层
singku 发表于 2016-1-30 12:29
楼主我早上发邮件问了 HR说要1-2周才发拒信。

是说两三天收不到消息的话就是悲剧了,但是要等1-2周才会收到拒信……?
回复 支持 反对

使用道具 举报

singku 发表于 2016-1-31 00:09:37 来自手机 | 显示全部楼层
回复 支持 反对

使用道具 举报

 楼主| testgre 发表于 2016-1-31 04:10:38 | 显示全部楼层

??我只看到空白……
回复 支持 反对

使用道具 举报

singku 发表于 2016-1-31 04:28:34 | 显示全部楼层
testgre 发表于 2016-1-31 04:10
??我只看到空白……

BUG了。。。少于8个字符还不能发出去呢. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我是说我逗你玩。HR说的是1-2周出具体结果,可能是拒也可能是过
回复 支持 反对

使用道具 举报

 楼主| testgre 发表于 2016-1-31 04:35:20 | 显示全部楼层
singku 发表于 2016-1-31 04:28
BUG了。。。少于8个字符还不能发出去呢
我是说我逗你玩。HR说的是1-2周出具体结果,可能是拒也可能是过

那只能等了 祝一起过哈!
回复 支持 反对

使用道具 举报

singku 发表于 2016-1-31 05:58:41 | 显示全部楼层
testgre 发表于 2016-1-31 04:35
那只能等了  祝一起过哈!

烧香拜佛求过,不过还是要做好最坏的打算呢,好好继续刷题 准备其他的面试吧。
回复 支持 反对

使用道具 举报

singku 发表于 2016-2-2 03:58:58 | 显示全部楼层
楼主及时汇报结果哈
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 03:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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