一亩三分地论坛

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

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

Google Youtube Onsite面经

[复制链接] |试试Instant~ |关注本帖
samurai_sz 发表于 2015-1-31 15:18:56 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 硕士 全职@Google - 内推 - Onsite |Other

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

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

x
发面经攒人品。Mountain View Campus,十点半多左右开始。一共四轮,到两点半结束。
第一轮面试官像是个中东人。给你一个matrix,每个cell都有一个collor的标记在里面。给你任何一个点,返回这个点所在的同色的区域块组成的多边形的周长。follow up是如果同一个user、同一个matrix,很多次测试不同的点,怎样提高效率;接下来他问了个题,说是不需要写代码,只想看看我怎么想这个问题,说是一次party完以后,有的人负责酒水费用有的人负责汽油费用有的人负责。。这样形成一个有向图的结构,A欠B多少钱,B欠C多少钱,C可能欠A、B分别多少钱,问怎么reduce/combine到最后形成一些pairs,比如A欠B 20,C欠A20,reduce到最后只需要C给B20块就行。这个pairs表达的transactions做到最小。这题想了半天跟他说dfs、然后一边走一边修改edge最后还是没给出一个具体的答案。看来本人脑子太笨。。。无法符合Google Coder的要求啊
第二轮是个老印。上来第一题是leetcode merge interval的变种,不是让你返回所有线段集合,返回所有线段组成区间的长度。第二题也是leetcode原题,maximun consequetive sequence in matrix
第三轮最坑,先进来一个shadow,过会儿又来了个老印男的(最近已经很努力攒RP了啊,怎么又是个老印),这厮进来开始问简历,web server使用多线程处理用户请求还是多进程处理,进程间怎么通信,线程和进程区别什么,什么是死锁,如何防止死锁,什么是virtual memory,什么是page fault等等。然后写Pascal Triangle,写完他让我reduce空间复杂度到O(1),立刻傻了眼。。。后来shadow还问我简历(你个shadow就别开口了啊),让我举个javascript的binding的例子。。。楼主实在是忘得一干二净了啊。。
第四轮是个日本妹子。进来就让做题,这题没见过:一种encoding只有1 byte encode或者两byte encode两种形式,如果说第一byte的第一个bit是0,那么这个bit开始的这个byte encode一个字符;如果第一个byte的第一位是1,那么他一定是两个byte encode一个字符,并且他的第二个byte的首bit可以是1或者0. 题目要求,给你一串encode,请问最后一个字符是一个byte encode的还是两个byte encode的。不允许顺序parse bit串。这题完了她又问了个power(int x, int y) 估计是看我第一题做的慢,属于比较弱B的candidate,出个水题让我缓口气,怕我晕死在里面。该轮两道题也都拍了照。
面完出来发现我是这次一起去youtube onsite的小伙伴们最后一个面完的(因为一开始就是被pick up的最晚的几个之一,比绝大部分candidate迟40分钟开始)。问问小伙伴们发现都被code 拍照了。似乎不是像以前说的那样有bug才拍。不过总的来说自己面得还是不行,但是实力摆在那儿,也没办法。总结经验教训最重要。move on了。希望后面的面试能够好运

. 鍥磋鎴戜滑@1point 3 acres
. 1point3acres.com/bbs
补充内容 (2015-2-1 02:56):
大米啊。。俺想看别人的附件都看不到。。

补充内容 (2015-2-12 08:51):
杨辉三角那个应该是两个数和的幂产生的每一层。(a + b)^n展开式的系数就是第n层。

补充内容 (2015-2-12 14:17):. From 1point 3acres bbs
第一轮第二题那个pair感觉应该是求二分图的最大权匹配。先把每个点拆成两个点,比如一个A只有出度,一个A'只有入度。然后在这个二分图里面求其最大权匹配。网上搜这个:二分匹配总结(匈牙利算法+最大权+最小权)

补充内容 (2015-2-18 10:38):
1.30面的,2. 10HR 要成绩单通知进HC。2月17号HR通知挂了。。。也没有问feedback,感觉可能跟第三轮有关系。想吐槽下这老印的题目出的不行,有点“知之为知之,不知为挂” 的意思;此外可能4轮没有出彩的feedback。

评分

15

查看全部评分

本帖被以下淘专辑推荐:

 楼主| samurai_sz 发表于 2015-2-1 07:11:55 | 显示全部楼层
yourway 发表于 2015-2-1 06:19
.鏈枃鍘熷垱鑷1point3acres璁哄潧啊,是我考虑不周,你说的对。. From 1point 3acres bbs

是不是可以这样:

恩。这个是对的。我就是用个counter,要么是1要么是2,每往前走八位flip一次,走到头了或者遇到0了就return counter
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (2015-2-2 03:24):
第一题 就是BFS,从当前点开始往外扩散,每当遇到一个新的色块,就不需要再把这个新的色块放进队列了,同时对结果++,意味着找到了一个新的边的一部分。如果是同色,继续放进队列,继续BFS。

评分

2

查看全部评分

回复 支持 2 反对 0

使用道具 举报

可爱的帕吉 发表于 2015-1-31 15:56:05 | 显示全部楼层
pascal 三角m 行n列是 m choose n (zero based). 找一下 m choose n 和 m choose n - 1 的关系,然后就可以线性时间常数空间进行计算了。以前高中数学竞赛学组合看过这个公式。
回复 支持 反对

使用道具 举报

kuyen 发表于 2015-2-1 00:18:46 | 显示全部楼层
第四轮第一题什么思路,如果不能parse bit的话?
回复 支持 反对

使用道具 举报

 楼主| samurai_sz 发表于 2015-2-1 02:07:38 | 显示全部楼层
kuyen 发表于 2015-2-1 00:18
第四轮第一题什么思路,如果不能parse bit的话?

倒着parse,慢慢的你会找出规律
回复 支持 反对

使用道具 举报

yourway 发表于 2015-2-1 03:13:45 | 显示全部楼层
samurai_sz 发表于 2015-1-31 13:07
倒着parse,慢慢的你会找出规律
.1point3acres缃
不知道我理解的对不对。

我觉得只要判断倒数第二、三个 byte 就可以了吧。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
如果倒数第二个 byte 小于128,就说明该 byte 是一个单 byte 字符或者双 byte 字符的第二个 byte ==》最后一个字符是单 byte 字符;

如果倒数第二个byte 大于等于 128。再看倒数第三个 byte,如果倒数第三个 byte 小于127,说明最后后一个字符是双 byte 字符,否则是单 byte 字符。

补充内容 (2015-1-31 14:15):
文中的“如果倒数第三个 byte 小于127,” 应该是  “如果倒数第三个 byte 小于128,”
回复 支持 反对

使用道具 举报

 楼主| samurai_sz 发表于 2015-2-1 03:52:47 | 显示全部楼层
yourway 发表于 2015-2-1 03:13
不知道我理解的对不对。

我觉得只要判断倒数第二、三个 byte 就可以了吧。

那如果倒数第三个byte开头不是0而是1呢?
回复 支持 反对

使用道具 举报

yourway 发表于 2015-2-1 04:23:07 | 显示全部楼层
samurai_sz 发表于 2015-1-31 14:52
那如果倒数第三个byte开头不是0而是1呢?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
你是问当倒数第二个 byte 小于 128 的条件吗?.鏈枃鍘熷垱鑷1point3acres璁哄潧

如果倒数第二个 byte 是小于 128 的(以 0 开头),如过倒数第三个字符也小于128 (以0开头),说明倒数第三个和倒数第二个 byte 是两个单 byte 的字符。如果倒数第三个字符大于等于128(以1开头),说明倒数第三个和第二个 byte 是一个双 byte 的字符。无论上述的那两种情况,最后一个字符都是单 byte 字符。. 1point 3acres 璁哄潧

只有倒数第二个 byte 是大于等于128的(以 1 开头)时候,才需要判断倒数第三个字符。
回复 支持 反对

使用道具 举报

 楼主| samurai_sz 发表于 2015-2-1 05:05:29 | 显示全部楼层
yourway 发表于 2015-2-1 04:23
你是问当倒数第二个 byte 小于 128 的条件吗?.1point3acres缃

如果倒数第二个 byte 是小于 128 的(以 0 开头),如 ...

那如果倒数第四个是1,那么他和倒数第三个组成两个byte字符(因为2byte encode第二个byte首字符可以是0或者1)。你怎么可以下结论看到第三个就断定他是和后面一起组成的呢?
回复 支持 反对

使用道具 举报

everending 发表于 2015-2-1 06:03:56 | 显示全部楼层
第一题那个directed graph with weight挺难的啊,我只知道如何达到pairs数最少,但是怎么把多余的pairs的weight分配到其他pairs就不知道了
回复 支持 反对

使用道具 举报

yourway 发表于 2015-2-1 06:19:45 | 显示全部楼层
samurai_sz 发表于 2015-1-31 16:05. from: 1point3acres.com/bbs
那如果倒数第四个是1,那么他和倒数第三个组成两个byte字符(因为2byte encode第二个byte首字符可以是0或 ...

啊,是我考虑不周,你说的对。

是不是可以这样:.1point3acres缃
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
首先判断最后一个 byte 是否小于128 ,如果不是,那么最后一个字符必然是双 byte 的字符。
. 鍥磋鎴戜滑@1point 3 acres
如果是,则继续往前找,直到找到下一个小于 128 的字节或者字符串的开始,然后判断访问了多少个大于等于128的字节。如果是奇数个,则最后一个字符是双字节。如果有偶数个,则最后一个字符是单字节。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.



回复 支持 反对

使用道具 举报

圆梦梦剧场 发表于 2015-2-1 06:50:11 | 显示全部楼层
yourway 发表于 2015-2-1 06:19. visit 1point3acres.com for more.
啊,是我考虑不周,你说的对。
. more info on 1point3acres.com
是不是可以这样:

我觉得这个方法应该是对的!!!
回复 支持 反对

使用道具 举报

 楼主| samurai_sz 发表于 2015-2-1 08:16:54 | 显示全部楼层
yourway 发表于 2015-2-1 06:19
啊,是我考虑不周,你说的对。

是不是可以这样:

论坛bug了刚刚发的没法出去
恩。这样是对的。我当时就是弄个counter,在while循环里面1和2来回flip 这个counter,到头了或者碰到byte开头是0就返回。
回复 支持 反对

使用道具 举报

yapingchen1990 发表于 2015-2-1 11:51:13 | 显示全部楼层
楼主,第一题的follow up 怎么提高效率啊。。。没想出来
回复 支持 反对

使用道具 举报

 楼主| samurai_sz 发表于 2015-2-1 12:12:25 | 显示全部楼层
yapingchen1990 发表于 2015-2-1 11:51
楼主,第一题的follow up 怎么提高效率啊。。。没想出来

我给他稀里哗啦说了一堆方法,比如访问过的点对应的节点全部存hashmap里,那些点的value值是多边形的周长;他问我如果不用hashtable这样多的空间咋办,我就说如果你允许我就把周长mark到原matrix我访问过的点里去。如果不可以就另外创建一个matrix存已经遍历过的点所在的多边形的周长。。。诸如此类吧。。
回复 支持 反对

使用道具 举报

yapingchen1990 发表于 2015-2-1 12:46:00 | 显示全部楼层
samurai_sz 发表于 2015-2-1 12:12
我给他稀里哗啦说了一堆方法,比如访问过的点对应的节点全部存hashmap里,那些点的value值是多边形的周长 ...

楼主 有考你system design方面的内容么
回复 支持 反对

使用道具 举报

mengxiangjia 发表于 2015-2-1 13:44:01 | 显示全部楼层
第一题要怎么做,dfs吗
回复 支持 反对

使用道具 举报

 楼主| samurai_sz 发表于 2015-2-1 15:51:26 | 显示全部楼层
mengxiangjia 发表于 2015-2-1 13:44
第一题要怎么做,dfs吗

BFS 字数字数
回复 支持 反对

使用道具 举报

 楼主| samurai_sz 发表于 2015-2-1 15:51:53 | 显示全部楼层
yapingchen1990 发表于 2015-2-1 12:46
楼主 有考你system design方面的内容么

没。。字数字数
回复 支持 反对

使用道具 举报

yapingchen1990 发表于 2015-2-6 04:52:41 | 显示全部楼层
samurai_sz 发表于 2015-2-1 07:11
.鐣欏璁哄潧-涓浜-涓夊垎鍦恩。这个是对的。我就是用个counter,要么是1要么是2,每往前走八位flip一次,走到头了或者遇到0了就retu ...

楼主,你第一题用bfs,的确能找到这个多边形里的所有的同色色块,但是求周长的话,我感觉是转换成矩形求,是么、
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 16:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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