一亩三分地论坛

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

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

Google “愤怒”的onsite SETI面经

[复制链接] |试试Instant~ |关注本帖
crimsonfaith91 发表于 2016-10-4 11:59:10 | 显示全部楼层 |阅读模式

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

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

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

x
标题有点怪。其实是很生气自己onsite表现后两轮不好,栽在communication。.鐣欏璁哄潧-涓浜-涓夊垎鍦
我面的是SETI,原因是听说SETI拿offer比较简单。. Waral 鍗氬鏈夋洿澶氭枃绔,
结果面试后发现问题简单到可以说一塌糊涂。

第一轮、白人面试官兼host
面试前,因为房间被占用,所以我们俩在外交流了下。我起初不知道他是第一位面试官,还向他问了面试技巧的guidance。=.=
第一道是把数组向右移k位。我慢慢做,还讲了如果k是negative就意味着像左移。
第二道是找BST第二大的element。用reverse inorder traversal做了。
第三道是把c string去除空位。
感觉这一轮应该是hire / strong hire。因为三题都bug-free。

然后后面三轮都可以说是跪了。=.=

第二轮、印度面试官
我最怕名企的烙印,之前在亚马逊实习时被印度mentor黑得很惨,面微软时有一轮印度面试官也是百般刁难。
这一轮有可能被黑,大家帮我分析下。
. 1point 3acres 璁哄潧
第一题是给一个数组:1,1,7,8,8-google 1point3acres
1,1是一个pair;8,8是另一个pair。请返回7,因为7仅出现一次。
我说用xor,他说能更快吗?
O(lg n)?怎么可能?后来才问明白pair的元素都是adjacent的。例如两个1都是彼此靠近。
但记得很清楚他只说pair,又没说一定要adjacent。
写了个binary search给他。bug-free。. from: 1point3acres.com/bbs

第二题Android Unlock Patterns.1point3acres缃
他从最原本的问题问起:走完9个键盘有多少种可能性。我分析了下,给了9 factorial。
他接着问给个range(例如,4到9)又会有多少种可能性。我分析了下,给了9 * 8 * 7 * 6 + 9 * 8 * 7 * 6 * 5 + .... more info on 1point3acres.com
他就问了leetcode的版本。我解释了下,然后有趣的事发生了:他不给写代码,说时间要到了。
我感觉有问题,一直不direct的要求,最后还是给了写。说他看错时间了,还有10分钟。
我写得不好,有3个bugs:一个自己发现,一个是漏了个for loop因为误会问题,一个他指出给了几次hint我才答对。=.=

有种感觉被黑,因为写完后找出bug后还有1分钟问他问题。。。最后我还提醒他拍下照。:)

后来吃饭,被白人面试官带去cafeteria。
问了他一些问题。. from: 1point3acres.com/bbs
吃完饭他把我带去wrong room。是吃饭前的room,但已经被另一位Google engineer霸占了。
后来他帮我问了coordinator发现地点改了。。
第三轮的面试官也来错地方。。. more info on 1point3acres.com

第三轮、(应该是)华人面试官(有可能是ABC或韩国人)
Rate Limiter,跟leetcode的那题不同,这题如果一秒内超过query per second限制需要wait一下。
给个class
class RateLimiter {
     void setLimit(int query_per_second);
     void wait();. visit 1point3acres.com for more.
};
wait()是要有block的semantics。其实这一题打得很不好,在他的提示下找到了要wait多久(有个formula),最后用了queue给了个O(n)解法。

他接着问O(1)解法。
时间用完了、代码改了好多篇依旧无法找到O(1)解法。。
他给了提示用bucket,我也尝试做了:把queue分为10个部分,每个代表100 millisecond。但有burst时依旧O(N)。
最后第四轮面试官来敲门了,他给了提示说可以把一个bucket内的queries都设为同样timestamp。
我当时才领悟到,原来可以如此。
回家后想了下:O(1)解法不是要牺牲correctness吗?之前有讲到不同granularity,但把bucket内的queries设为同样timestamp不能保证limit正确啊。
他又没说可以不准确,我要怎样想得出啊??Granularity这个词implicitly imply? LOL
记得去年电话面试Google时面试官有说他想要个更快的但可能会出错的解法,但这轮面试官没说啊。
感觉上这一轮就是一直想O(1)解法,一直判断出还是O(N)。
我一直都在wrong direction,而面试官却一直说嗯嗯嗯。=.=

第四轮、华人女生面试官(应该是中国女生)+ 白人shadow
问题很简单,但这一轮的面试官是我的interview anti-loop。无论如何沟通,她还是无法了解我的approach。。。

给某一天的file,记载着questionnaire回答者的讯息:. from: 1point3acres.com/bbs
{UserId, Timestamp (minute), City}.鏈枃鍘熷垱鑷1point3acres璁哄潧
{100,201608080003,“NY”}
{101,201608080102,“CA”}. From 1point 3acres bbs
{102,201608080102,“CA”}
{103,201608080154,“IL”}
{104,201608080154,“CA”}
Timstamp是有序的。请打印过去一小时的city ratio。例如走到user ID 104要打印:
(101, 3/4)
(102, 3/4). visit 1point3acres.com for more.
(103, 1/4)
(104, 3/4)
因为走到104时,user ID 100的entry已经expire。剩下有三个CA,一个IL。

她讲得不清楚但给了类似以上的例子,但我开始时误会了问题。
面试官说timestamp是based on minute的,所以误会timestamp的最后四个号码代表的都是minute(当时想了下60 * 24,一天有1320分钟)。
但其实是小时和分钟。例如201608080003是2016年8月8号00时03分钟。. From 1point 3acres bbs
后来clarify后,慢慢改成用queue + hashmap + hourly city count variable的解法。. more info on 1point3acres.com

解释了好久,面试官依旧不清不楚。说了好多次用queue是为了去除expire的entries。
讨论了好久,她还是在问相似的问题。。
最后没剩多少时间写了下代码,一个loop没counter++,一写完还没来得及查看就立即被她指出。
然后写完queue的代码,她说pop operation后array index会变。我听不明白,跟她解释了许久,她之后才发现我在pop queue。。
我当时心里想:开玩笑吗?我一边写了多行queue的代码,一边讲到口都要沙哑了,之前解释时也提到了queue很多次。. 1point 3acres 璁哄潧
现在因为时间剩不多,字体有点乱,写了queue的pop operation,怎么array index会变啊?. 鍥磋鎴戜滑@1point 3 acres

看来我跟面试官沟通不来啊。如果不是有shadow,我会要求用中文跟她解释。=.=. 鍥磋鎴戜滑@1point 3 acres

结束前我问了下engineer如何合作解决棘手的问题,她答非所问,好像在说自己不知道。我心里都凉了。
旁边的白人shadow立即圆场,回答了我的问题,说会有meeting什么的。
我真的无话可说。白人shadow能明白我说的英文,但华人面试官听不明白啊。。

我不觉得面试官有黑我的意思,但这种程度的沟通等于没戏了。。
想不到准备了5个月,竟然栽在communication。。.鏈枃鍘熷垱鑷1point3acres璁哄潧

总结:
(1) 如果stuck,一定要更加积极问hint。有些面试官在你in the wrong direction时也相当被动,一定要积极用example来搞清楚问题。
(2) 沟通很重要。不管面试官英文好不好,都要有能力让ta明白。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴


评分

2

查看全部评分

本帖被以下淘专辑推荐:

aonecode 发表于 2016-10-5 10:16:03 | 显示全部楼层
楼主这实力是刚刚的,只是运气问题面试官比较奇特,相信很快就会有别家的好消息了加油共勉
回复 支持 1 反对 0

使用道具 举报

hcheng81 发表于 2016-10-5 02:15:42 | 显示全部楼层
lz你不要担心阿,我觉得你面的很好。听说shadow也有可能是来检测这个面试官是否合格的。不要担心。
回复 支持 1 反对 0

使用道具 举报

hcheng81 发表于 2016-10-13 00:56:07 | 显示全部楼层
leonardcohen 发表于 2016-10-9 22:22
hi, what does shadow mean in chinese? thanks.

。。。就是。。影子。。。这里应该是说另一个面试官就在旁边静悄悄的呆着没什么作用吧。。。
回复 支持 1 反对 0

使用道具 举报

WhatsFLAG 发表于 2016-10-4 13:06:41 | 显示全部楼层
楼主请问SETI是什么啊?
回复 支持 反对

使用道具 举报

 楼主| crimsonfaith91 发表于 2016-10-4 13:29:25 | 显示全部楼层
WhatsFLAG 发表于 2016-10-4 13:06
.鏈枃鍘熷垱鑷1point3acres璁哄潧楼主请问SETI是什么啊?
-google 1point3acres
Software Engineer, Tools and Infrastructure
回复 支持 反对

使用道具 举报

wsrrzxl 发表于 2016-10-4 14:18:04 | 显示全部楼层
LZ能细说一下RateLimiter那道题吗
回复 支持 反对

使用道具 举报

chopinzwz 发表于 2016-10-4 14:21:00 | 显示全部楼层
SETI做的东西没什么前途呀,以后楼主应该能得到更好的offer
回复 支持 反对

使用道具 举报

elfandi 发表于 2016-10-4 15:10:04 | 显示全部楼层
g的面试这德行也是惊了。。。
回复 支持 反对

使用道具 举报

WhatsFLAG 发表于 2016-10-5 06:15:04 | 显示全部楼层
crimsonfaith91 发表于 2016-10-4 13:29
Software Engineer, Tools and Infrastructure
. 鍥磋鎴戜滑@1point 3 acres
感觉出题的套路有点让我看不懂。。。风格和其他面经不太一样啊
回复 支持 反对

使用道具 举报

wangyuesong2 发表于 2016-10-5 07:21:10 | 显示全部楼层
求问楼主电面面的什么题啊?SETI的电面难吗
回复 支持 反对

使用道具 举报

virpro 发表于 2016-10-5 09:56:22 | 显示全部楼层
第四轮如果input是array或者list可以直接用two pointer?
回复 支持 反对

使用道具 举报

virpro 发表于 2016-10-5 09:57:14 | 显示全部楼层
第三题能否详解一下,是要求实现这个RateLimiter吗?
回复 支持 反对

使用道具 举报

 楼主| crimsonfaith91 发表于 2016-10-5 10:12:15 | 显示全部楼层
wsrrzxl 发表于 2016-10-4 14:18
LZ能细说一下RateLimiter那道题吗
. 1point3acres.com/bbs
跟这题相似:http://blog.gainlo.co/index.php/ ... design-hit-counter/
回复 支持 反对

使用道具 举报

 楼主| crimsonfaith91 发表于 2016-10-5 10:12:38 | 显示全部楼层
chopinzwz 发表于 2016-10-4 14:21
SETI做的东西没什么前途呀,以后楼主应该能得到更好的offer

但愿啊。谢谢
回复 支持 反对

使用道具 举报

 楼主| crimsonfaith91 发表于 2016-10-5 10:13:15 | 显示全部楼层
elfandi 发表于 2016-10-4 15:10
g的面试这德行也是惊了。。。

主要面的不是SWE,面试官水准降得太多了。。
回复 支持 反对

使用道具 举报

 楼主| crimsonfaith91 发表于 2016-10-5 10:13:51 | 显示全部楼层
hcheng81 发表于 2016-10-5 02:15. 鍥磋鎴戜滑@1point 3 acres
lz你不要担心阿,我觉得你面的很好。听说shadow也有可能是来检测这个面试官是否合格的。不要担心。

多谢啊!怪不得那位shadow在抄笔记,也帮我圆场。
回复 支持 反对

使用道具 举报

 楼主| crimsonfaith91 发表于 2016-10-5 10:14:33 | 显示全部楼层
WhatsFLAG 发表于 2016-10-5 06:15. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
感觉出题的套路有点让我看不懂。。。风格和其他面经不太一样啊

除了第3轮,所有问题都比地里其他面经简单多了。
回复 支持 反对

使用道具 举报

 楼主| crimsonfaith91 发表于 2016-10-5 10:15:08 | 显示全部楼层
wangyuesong2 发表于 2016-10-5 07:21
求问楼主电面面的什么题啊?SETI的电面难吗
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
没电话面试。直接给onsite。
回复 支持 反对

使用道具 举报

 楼主| crimsonfaith91 发表于 2016-10-5 10:16:11 | 显示全部楼层
virpro 发表于 2016-10-5 09:56
第四轮如果input是array或者list可以直接用two pointer?

我觉得two pointers可以,但还是要个hashmap。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 20:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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