一亩三分地论坛

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

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

热乎乎的Google Onsite面经

[复制链接] |试试Instant~ |关注本帖
coolis 发表于 2015-4-6 06:09:25 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Google - 猎头 - Onsite |Otherfresh grad应届毕业生

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

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

x
这个礼拜刚结束Google Onsite,三番阳光沙滩比基尼实在是让人不想回到寒冷的大纽约。先在地里发个面经,求攒人品。至于能不能过就看老天爷了。
前一天6个半小时jetBlue从大纽约直飞三番,实在无力吐槽jetBlue的服务了,没吃没喝,就随便发点水和snacks。还好事先有准备,在机场买了一大盒自选沙拉,当大家都饥肠辘辘咕咕叫的时候,我开始贱贱的大快朵颐起来,能感受到边上小美眉怨恨的小眼神估计已经在心里把我大卸八块了~

一落地,拿了Google给租的车就直奔酒店,酒店在sunnyvale,离三番大概40分钟车程,距离mountain vieW大概十多分钟就到了,整体条件还不错,有早餐和happy hour snacks,将就着吃一下吧~因为第二天一早就要去面试,对湾区的路又不熟,怕自己开车万一遇上堵车或者走错路什么的会耽误面试,所以和酒店订了shuttle bus早上去Google的building。


第二天起床, 加州早上的阳光实在是整个人都愉快起来了,吃完早饭,和几个小伙伴一起坐着酒店的大van,一路吹着牛逼唱着歌就来到了Google。


不扯犊子了,直接上题:

第一轮:
Given a heatmap which is a 3 dimension matirx and define a movement rule: a point on the heatmap can only go down hill. Ask: given some points on the heatmap, find out the higest point that can meet all the given points.
说白了就是给个矩阵,上面都有自己的value,然后movement规定了只能从大的value走到小的value,然后再给几个点,问可以到这些点的最高的点是哪一个。

给了两个sulution:
1. 类似least common ancestor, 对每一个点做dfs,向下找到要找的点,直到找到所有点,然后把root记为可能的最高点,每次update可能的最高点。time complexity O(n**2)
2. 对给定的点反过来向上uphill做BFS,然后一个map记录矩阵上每个点被访问了几次。然后再来个for loop检查矩阵上被所有给定的点访问过的最高点。time complexity O(n)
然后在白板上把第二个solution implement了一下。-google 1point3acres

第二轮:. 鍥磋鎴戜滑@1point 3 acres
第二轮来了个老硬,问了两个题,第一题先上来热身一下,问有好多个口袋,里面放了不同数量的硬币,并且口袋被从1到N标记了。两个人问游戏,每次可以从口袋里拿出和标记数一样多的硬币,知道有一方不能再拿硬币为止,然后那个人就输了。问给定这样的口袋,谁会赢。
我一开始以为是之前地里有人遇到过的++--的string的那个题,但是听老硬说是个热身题,应该不会太难,再仔细一想,发现只要看一共可以做多少起拿硬币的动作,如果是奇数次就是先手赢,偶数次就是后手赢。我说了想法,老硬哈哈一笑说,简单吧,我们就不写code了,现在正式上题。然后第二道来了,也是我整个面试做的最不好的一道题。
.鏈枃鍘熷垱鑷1point3acres璁哄潧

第二题还是有很多口袋,里面好多硬币,然后可以对第i个和第i+1个做combine,combine的cost是第i个和第i+1个口袋里硬币数的sum,问怎么样做combine可以都到最少的cost。我一上来觉得这道应该用DP做,但是和老硬讨论了20分钟也没有什么好的方法,老硬似乎也不太满意,然后我就开始威逼利诱套hint,老硬说要把大case分成小case,我一下反应过来是要brute force做recursion,然后5分钟秒掉code,不过最后还是让老硬抓出一个小bug。诶,估计要挂就是挂在了这一轮。. more info on 1point3acres.com

第三轮:
吃过午饭开始了第三轮,来了个文质彬彬的百人,还用彩打把题打在了纸上。
问给一串UTF8的binary code, 和UTF8的rules,求一共有多少个character。因为之前做过中文的UTF8的encoding和decoding,所以对UTF8的规则比较熟,就是用一个mask去check会有多少个offset,然后再看offset是不是都是valid的,如果是valid的就是一个character。
For example: 1110XXXXX 10XXXXXX 10XXXXXX 代表是一个三个bytes的character,第一个byte的1110 XXXX说明了后面的两个byte是我的offset,应该是以10开头的。

这题不难,不过也让抓到了一个bug,估计feedback也不是很好。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

第四轮:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第四轮来了个中国人,上来就问那道++--的题目,我自知不会做,所以就直接说我早上面试的时候做过这道题了,面试官一听就说,那我们就换一道吧(哈哈,分分钟玩死面试官)。然后就给换了一道array的题,问说给两个array,比较这两个array是不是一样的order。
For example, 3 5 2和400 700 100是一个order,但是3 5 2 和100 700 300就不是一个order。.1point3acres缃

我说sort肯定能做,时间是nlogn。面试官说sort是个好方法,但有没有更好一点的,我一听,这是要linear时间啊,这不是难为老子吗?就在我焦头烂额的时候,面试官说我想你从server client的角度去考虑,在server端不在意时间,但是client端坐compare要尽量快。收到KMP算法的启发,我想可以实现存两张表L和S,记录第i个element应该在大于L[i]并且小于S[i]。这样在server上建表的时间是nlogn,但是client compare的时间就变成了n。面试官貌似还比较满意,然后有追问如果n特别大想提高average时间怎么办。我说可以用multithreading,每个thread有一个自己的table,然后第k个thread就compare n/k 个数。面试官听了觉得也可以,又追问如果n特别特别大而bandwidth很小,传不了table怎么办,我说那就做realtime的check,来一个数check一下,比如之前已经compare好了k个数,来了第k+1个就和之前的k个做比较,然后update S和L。面试官最后想说其实第k+1和之前的k个数做linear search就行了。我想想也是,server上也不在乎这点时间。

总体面下来一般般,估计是要跪,就当是个经验吧。而且面试的时候完全没有问到什么behaviour的问题,都是nice to meet you之后就直奔题目,然后一直写到下一个面试官进来。我本来准备的介绍简历的话和最后要问面试官的问题都没用上。。。

评分

5

查看全部评分

本帖被以下淘专辑推荐:

refurbish 发表于 2015-4-6 17:22:53 | 显示全部楼层
第四题太坑了,后台预处理,那啥问题都能线型了,还搞毛啊。楼主也真够冒险的,他们面试官其实能看到之前人出的题目的,后面系统里好像也能查,要是写到comment里。。。
回复 支持 1 反对 0

使用道具 举报

asdfyou6 发表于 2015-4-7 04:37:32 | 显示全部楼层
三番阳光沙滩比基尼?

一年四季都看不到这个
回复 支持 1 反对 0

使用道具 举报

Arthur2012 发表于 2015-4-6 08:54:04 | 显示全部楼层
lz的第二面第三题是石子归并问题,如果给出O(n^3)的解法不知道可不可以。
回复 支持 1 反对 0

使用道具 举报

池大侠 发表于 2015-4-6 08:16:53 | 显示全部楼层
hhh...我就不上题了。。目测已跪。。猜猜我是谁。。
回复 支持 反对

使用道具 举报

sunfish 发表于 2015-4-6 11:03:57 | 显示全部楼层
请问++--是那道题啊?
回复 支持 反对

使用道具 举报

shinichish 发表于 2015-4-6 11:36:28 | 显示全部楼层
楼主面的题好难啊。。。应该没问题的,Google最近bar放低了
回复 支持 反对

使用道具 举报

rogerdai 发表于 2015-4-6 12:02:12 | 显示全部楼层
求问string ++--是哪题?
回复 支持 反对

使用道具 举报

 楼主| coolis 发表于 2015-4-6 12:41:05 | 显示全部楼层
池大侠 发表于 2015-4-6 08:16
hhh...我就不上题了。。目测已跪。。猜猜我是谁。。

快来也把你的题放上来,多赞赞rp
回复 支持 反对

使用道具 举报

 楼主| coolis 发表于 2015-4-6 12:54:17 | 显示全部楼层
Arthur2012 发表于 2015-4-6 08:54
lz的第二面第三题是石子归并问题,如果给出O(n^3)的解法不知道可不可以。

原来真的是,还是自己dp学的不扎实,没想到解法。
回复 支持 反对

使用道具 举报

 楼主| coolis 发表于 2015-4-6 13:22:17 | 显示全部楼层
sunfish 发表于 2015-4-6 11:03
请问++--是那道题啊?
. 1point 3acres 璁哄潧
请看链接的第二题
++--
回复 支持 反对

使用道具 举报

 楼主| coolis 发表于 2015-4-6 13:22:58 | 显示全部楼层
rogerdai 发表于 2015-4-6 12:02
求问string ++--是哪题?

链接第二题. 1point3acres.com/bbs
++--
回复 支持 反对

使用道具 举报

refurbish 发表于 2015-4-6 16:27:48 | 显示全部楼层
Arthur2012 发表于 2015-4-6 08:54. from: 1point3acres.com/bbs
lz的第二面第三题是石子归并问题,如果给出O(n^3)的解法不知道可不可以。

看了lz描述,半天没看懂题意,到你这里豁然开朗
回复 支持 反对

使用道具 举报

狂暴CNM地 发表于 2015-4-6 23:21:57 | 显示全部楼层
Arthur2012 发表于 2015-4-6 08:54
lz的第二面第三题是石子归并问题,如果给出O(n^3)的解法不知道可不可以。

石子归并?  这个题感觉就是算法导论上  Matrix multiplication的变种吧   递归指数级  DP的话n^3
回复 支持 反对

使用道具 举报

Arthur2012 发表于 2015-4-6 23:33:06 | 显示全部楼层
狂暴CNM地 发表于 2015-4-6 23:21
石子归并?  这个题感觉就是算法导论上  Matrix multiplication的变种吧   递归指数级  DP的话n^3

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷恩恩,矩阵连乘的变种,DP可以优化到n^2.鏈枃鍘熷垱鑷1point3acres璁哄潧
http://blog.csdn.net/acdreamers/article/details/18039073
回复 支持 反对

使用道具 举报

fishyuze 发表于 2015-4-7 03:06:24 | 显示全部楼层
对给定的点反过来向上uphill做BFS,然后一个map记录矩阵上每个点被访问了几次。然后再来个for loop检查矩阵上被所有给定的点访问过的最高点。time complexity O(n).

反向bfs复杂度似乎没法降吧 应该还是O(kn)的吧 k是给的destination个数 n是矩阵所有点的个数?.1point3acres缃
回复 支持 反对

使用道具 举报

 楼主| coolis 发表于 2015-4-7 03:49:55 | 显示全部楼层
fishyuze 发表于 2015-4-7 03:06. From 1point 3acres bbs
反向bfs复杂度似乎没法降吧 应该还是O(kn)的吧 k是给的destination个数 n是矩阵所有点的个数?

恩,还是O(kn)
回复 支持 反对

使用道具 举报

fishyuze 发表于 2015-4-7 05:01:18 | 显示全部楼层
asdfyou6 发表于 2015-4-7 04:37.鏈枃鍘熷垱鑷1point3acres璁哄潧
三番阳光沙滩比基尼?

一年四季都看不到这个

这个真没有
回复 支持 反对

使用道具 举报

fishyuze 发表于 2015-4-7 05:29:56 | 显示全部楼层
面试官说sort是个好方法,但有没有更好一点的,我一听,这是要linear时间啊,


弄个counting sort是线性的 否则难优化了吧 似乎可以规约到排序 然后证明基于比较的方法不可能更优了?
回复 支持 反对

使用道具 举报

 楼主| coolis 发表于 2015-4-7 11:31:35 | 显示全部楼层
fishyuze 发表于 2015-4-7 05:29
弄个counting sort是线性的 否则难优化了吧 似乎可以规约到排序 然后证明基于比较的方法不可能更优了?

counting sort的N不能太大,但是这里是任意array。我没有想出什么更好的算法,所以只能从后台预处理的角度去做了,不知道有没有大神有更牛的算法。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 02:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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