一亩三分地论坛

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

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

9月24日Google NYC Onsite 新鲜面经

[复制链接] |试试Instant~ |关注本帖
batman4001 发表于 2015-9-25 05:48:02 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
今天刚刚在NYC的office onsite完,把面经分享给大家:

第一轮:白人大叔,挺和蔼的。上来先问了一下简历上intern的事情,然后问做过的project有哪些challenge,之后出题:

给一个整数n,返回前n个fibonacci number相邻pair的最后一个digit。听起来有点绕,其实不难,比如:

n = 8
fibonacci: [0, 1, 1, 2, 3, 5, 8, 13]
return: [ (0, 1), (1, 1), (1, 2), (2, 3), (3, 5), (5, 8), (8, 3) ]

很简单,先生成前n个number到list,然后第二遍loop返回pair。

follow up:怎样确定有没有cycle?如果n很大怎么办?
维护一个visited set,每次检查一下。
很多solution: 可以用long, 用string, 或者cache,或者distributed system
.鐣欏璁哄潧-涓浜-涓夊垎鍦
然后问最多需要查多少次就可以确定cycle的存在?
这个自己脑抽了,理解了好久才明白过来,就是计算有多少个可能的pair,10 * 10。

第二轮: 白人阿姨, 态度很好,经常给好的feedback。

. more info on 1point3acres.com
给一颗二叉树,返回重复的subtree。比如:

                      1
                    /    \
                  2      3
                 /       /   \
               4      2     4
                      /
                    4

结果应该返回[ ( 2 -> 4), (4) ] 两颗树。

也很简单,BFS遍历,存每个substree到list里,然后用双重循坏找。其中需要写一个helper function判断两棵树是否相同。

follow up:time complexity, 以及如何优化。

得到subtree list之后提前处理,把root value unique的除掉。
. 1point 3acres 璁哄潧
第三轮:国人小哥。开始要出跟上一轮一样的题,我跟他讲题出过了,所以换了一道。

设计一个fraction number 的class,要求实现equals和String toDecimal()。

toDecimal是leetcode原题,equals的话注意先得到gcd,然后除了之后再比较。还有分子分母是否为0,符号不一样等等都需要考虑。细节挺多的。

第四轮:白人大叔。这一轮比之前都难,虽然是面经题,不过之前的面经很简略,没有实现。

给一个二维boolean array, true代表greyed, 要找出所有可能的正方形。比如:

0 1 0
0 0 0
1 0 0

一共有8个正方形(边长为1的7个,为2的1个,为3的0个)。注意matrix的边长可能不等。

这道题一开始出来有点蒙,心想完蛋了。面试官也面无表情,坐在那一句话不说, 没有任何提示。好在最后经过思索还是搞出来了。用DP对matrix先预处理,方法有点类似之前地里面经出现的计算matrix中rectangle面积的题,dp[j]代表从(0, 0) 到 (i, j) 里面所有可用的grid的数量。具体方法大家可以自己思索一下。

写到最后差不多全部出来了,面试官居然出现了笑容,话也多了起来,轻松了不少。这一场压力还是比较大的。


差不多这就是全部了,感谢地里的面经,真的从中受益了很多,所以我也一定会跟大家分享。

最后提一句,如果出现面试中重复题的一定要提出来,这个很容易查到了,不然会对你有很差的印象。中午lunch的时候再次确认了这一点。

就这些了,希望能有好的结果。大家共勉!

评分

6

查看全部评分

本帖被以下淘专辑推荐:

darkwowgamer 发表于 2015-9-25 15:49:28 | 显示全部楼层
http://www.jiuzhang.com/solutions/maximal-square/
. from: 1point3acres.com/bbs
链接里第一种解法, 得出int[][] res之后遍历矩阵叠加就行了.
. visit 1point3acres.com for more.
从状态转移方程能看出res[i][j]除了表示边长也能表示以该点作为右下角的正方形有几个
回复 支持 4 反对 0

使用道具 举报

darkwowgamer 发表于 2015-9-25 07:42:52 | 显示全部楼层
batman4001 发表于 2015-9-25 07:26
这个我记得,感觉比这个还要复杂一些。

leetcode那道得出动归的结果后, 把所有dp相加得到的就是所有的正方形了吧. 比如说dp[j] = 3, 表示以(i, j)作为右下角的square有3个, 因为每个正方形只有唯一的右下角, 所以相加得到总square数量. 有不对的地方还望指出
回复 支持 4 反对 0

使用道具 举报

blactangeri 发表于 2015-9-25 11:33:50 | 显示全部楼层
lz 第二题 你是指 2 -> 4, (2 -> 4)吧
回复 支持 1 反对 0

使用道具 举报

jiebour 发表于 2015-9-25 05:56:45 | 显示全部楼层
最后一个题就是leetcode原题的一点变形吧,不一样部分就是找所有,那个是找最大
回复 支持 反对

使用道具 举报

JimLuo 发表于 2015-9-25 06:39:25 | 显示全部楼层
谢谢楼主分享,祝楼主早日拿到offer!!
回复 支持 反对

使用道具 举报

 楼主| batman4001 发表于 2015-9-25 06:42:26 | 显示全部楼层
jiebour 发表于 2015-9-25 05:56
最后一个题就是leetcode原题的一点变形吧,不一样部分就是找所有,那个是找最大

是哪个题?我找了一下没找到
回复 支持 反对

使用道具 举报

 楼主| batman4001 发表于 2015-9-25 06:42:45 | 显示全部楼层
JimLuo 发表于 2015-9-25 06:39.鏈枃鍘熷垱鑷1point3acres璁哄潧
谢谢楼主分享,祝楼主早日拿到offer!!

谢谢!一起加油!
回复 支持 反对

使用道具 举报

darkwowgamer 发表于 2015-9-25 06:45:35 | 显示全部楼层
batman4001 发表于 2015-9-25 06:42
是哪个题?我找了一下没找到

https://leetcode.com/problems/maximal-square/. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

补充内容 (2015-9-25 06:45):
我猜是这个吧
回复 支持 反对

使用道具 举报

cathycat 发表于 2015-9-25 07:06:20 | 显示全部楼层
follow up:怎样确定有没有cycle?如果n很大怎么办?
回复 支持 反对

使用道具 举报

cathycat 发表于 2015-9-25 07:06:44 | 显示全部楼层
cathycat 发表于 2015-9-25 07:06
follow up:怎样确定有没有cycle?如果n很大怎么办?

请问这个cycle时怎么定义的呢?没有理解
谢谢
回复 支持 反对

使用道具 举报

 楼主| batman4001 发表于 2015-9-25 07:26:23 | 显示全部楼层
darkwowgamer 发表于 2015-9-25 06:45
https://leetcode.com/problems/maximal-square/

补充内容 (2015-9-25 06:45):

这个我记得,感觉比这个还要复杂一些。
回复 支持 反对

使用道具 举报

 楼主| batman4001 发表于 2015-9-25 07:28:49 | 显示全部楼层
cathycat 发表于 2015-9-25 07:06
请问这个cycle时怎么定义的呢?没有理解
谢谢

cycle的意思就是出现了之前出现过的pair,这样整个序列又会同之前一样了。
回复 支持 反对

使用道具 举报

cathycat 发表于 2015-9-25 07:35:42 | 显示全部楼层
batman4001 发表于 2015-9-25 07:28
cycle的意思就是出现了之前出现过的pair,这样整个序列又会同之前一样了。

懂了,谢谢 祝你早日拿到offer
回复 支持 反对

使用道具 举报

 楼主| batman4001 发表于 2015-9-25 07:52:02 | 显示全部楼层
darkwowgamer 发表于 2015-9-25 07:42. from: 1point3acres.com/bbs
leetcode那道得出动归的结果后, 把所有dp相加得到的就是所有的正方形了吧. 比如说dp[j] = 3, 表示以(i, j ...

正方形不一定必须要从左上角开始计算的,所以不能是简单相加。你看我上面举得例子,边长为2的正方形就不是从(0,0)算起的。另外maximal square里面的结果表示的是最大square的size,而不是数量吧。。
回复 支持 反对

使用道具 举报

darkwowgamer 发表于 2015-9-25 08:11:48 来自手机 | 显示全部楼层
结果是表示的最大size,但也可以理解成以该位置作为右下角的正方形的数量,感觉应该是这样,不知道有没有同学能找个反例
回复 支持 反对

使用道具 举报

cbwcs 发表于 2015-9-25 08:31:38 | 显示全部楼层
darkwowgamer 发表于 2015-9-25 07:42. 1point3acres.com/bbs
leetcode那道得出动归的结果后, 把所有dp相加得到的就是所有的正方形了吧. 比如说dp[j] = 3, 表示以(i, j ...

支持你这个答案!
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-9-25 09:08:45 | 显示全部楼层
batman4001 发表于 2015-9-25 07:52
正方形不一定必须要从左上角开始计算的,所以不能是简单相加。你看我上面举得例子,边长为2的正方形就不 ...

相加应该是对的
回复 支持 反对

使用道具 举报

M_Jason 发表于 2015-9-25 09:55:36 | 显示全部楼层
楼主看起来答得不错啊,应该会有好结果的~
回复 支持 反对

使用道具 举报

leixiang5 发表于 2015-9-25 10:48:18 | 显示全部楼层
重复题要提出来??他们如何查到啊?是不是所有面试官要上交面试的题目?
回复 支持 反对

使用道具 举报

 楼主| batman4001 发表于 2015-9-25 11:14:27 | 显示全部楼层
M_Jason 发表于 2015-9-25 09:55
楼主看起来答得不错啊,应该会有好结果的~

多谢啦!
回复 支持 反对

使用道具 举报

 楼主| batman4001 发表于 2015-9-25 11:14:48 | 显示全部楼层
leixiang5 发表于 2015-9-25 10:48
重复题要提出来??他们如何查到啊?是不是所有面试官要上交面试的题目?

   对的。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 01:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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