一亩三分地论坛

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

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

Google Chicago office onsite 完全面经

[复制链接] |试试Instant~ |关注本帖
zhangquan913 发表于 2015-12-28 14:47:37 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 猎头 - Onsite |Fail在职跳槽

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

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

x
这次面试的最大感觉就是,自己把leetcode很认真的又刷了一遍,cracking the coding interview 也 review 了一遍,结果一题也没有考到,考到的题目感觉都怪怪的。不知道是不是Chicago这个office的特色。
第一轮:一个中年白人,表情比较严肃,让我介绍了一下自己和现在在做的projects。剩下不到半小时,让我设计一个rate limiter,就是给定每秒接受request的最大次数,当一个新的request来的时候怎么判断是否接受。这题看似很简单,但你只要想到用queue或者其他数据结构去存储request,你就输了。我事后问了很多人,他们的思路跟我一样,都是用数据结构去存储request,这样当存储的request过多会有很多问题,是个死胡同。我在网上找了经典答案,确实非常巧妙,不用任何数据结构,也不涉及多线程问题:http://stackoverflow.com/questio ... -limiting-algorithm。当时我沿着错误的思路修修补补,面试官怎么都不满意,总提出漏洞,看来这完全不是他想要的答案。这题我认为你做过就会做,没做过的话在面试中打死你都想不到这么巧妙的解。我事后感觉第一轮被亮红灯无疑了。

第二轮:一个看起来像阿拉伯人的三四十岁的男人,问了我几个behavioral questions,当时受第一轮影响心情很不好,回答这些问题也没能很有激情。剩下大概半小时,问了我一个挺简单的算法题,按照定义好的priority,给字符串排序。比如定义好的priority list是[o, r, d, e, r],给定字符串是"horse",得到结果是"orehs",即如果字符串中的字符出现在priority list中,按priority排序,剩下字符append到后面。这题我一遍就用最优解把所有的edge case都考虑到了,面试官看完我的解基本没有异议。此轮过后士气有所恢复。

第三轮:一个白人老头儿,一脸笑呵呵的。上来就给我出了一道算法题,给你一段字符串,你怎么把它压缩成指定的格式,比如“adddbffffsssssscvvvvv”压缩成“a3xdb4xf6xsc5xv”。这题看似很简单,但坑很深。我本来还暗自高兴,三下五除二就把代码完整写出,当时想的更多的是怎么把它在时间和空间上优化,后来才感觉到这题分明是在考 edge case。比如在压缩“x”的时候怎么办,在压缩“3xd”的时候出现歧义怎么办,压缩数字的时候又怎么办。我提出用转义字符,但他说不能改变压缩格式。这题我后来做了很多改进来处理edge case,有些是自己想到的,有些是他提示的。不知道这种题这种表现算如何,是不是不应该被面试官指正啊,但这题一气呵成处理一切 edge case 似乎也太难了。
. 1point3acres.com/bbs
Lunch:一个大胡子白人小哥,陪我吃完还剩余时间,又领我看了一会儿公司小影院里面放的电影。饭菜就不说了,Chicago office跟别的地儿应该也没啥区别,但一个很特别的感觉是,这个offic亚洲人很少,基本都是白人。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第四轮:一个白人小年轻,也是一脸笑嘻嘻的,但仍然掩饰不住问题的刁钻。让我设计 load balancer,这题我之前大概看过,但也不是这次刷题遇到的。这题比较开放,我讲了几种大概的思路,但他刁钻的提出让我从多线程的角度去分析,如果一下来了太多的 load request 怎么办,如果你与 server 之间的沟通有延迟怎么办,怎么设置安全锁来保证你得到的当前各个 server 的状态是实时的。我去,我记得当时我也就看了关于 load balancer 的几种处理思路,没有考虑这么多的细节,答得不是很好。从来刷题也没刷到过考多线程这么深的问题,不知多线程问题在Google是不是很多被问到,还是我太背啊。

第五轮:一个黑人大叔,面无表情。让我设计一个service,当得到一个新数据,如何更新最近得到的N个数据的平均值。我真是受leetcode毒害太深,上来就按照根据固定输入得到固定输出的模式来写算法,后来发现这不是个简单的算法题,更新平均值算法本身很简单,难点在怎么在service中存储最近得到的数据。后来我用一个固定大小的queue来存储最近的数据,新的数据来了以后,最老的数据出队,新的数据进去,然后更新平均值。这题跟第一题属于同一类型,但比第一题简单,都是service设计,输入是源源不断的,而不是像leetcode里的算法题那样一次输入数据然后得到结果。

结果:肯定是fail了啊,第一题就废了,后面也没能力挽狂澜。这次之所以感觉考得奇怪,就是觉得跟leetcode的题目差别太大,比如第一题和最后一题都是让你设计service,而不是写一个算法,设计的时候更多要从class角度考虑,而非method层面。第二题和第三题算是leetcode式的算法题,但第三题坑太多。第四题是设计题,我本有所准备,但没想到它不是那种oop设计这么简单,线程问题被问了一大堆,汗!

评分

2

查看全部评分

本帖被以下淘专辑推荐:

silenceleaf 发表于 2015-12-29 02:06:44 | 显示全部楼层
楼主请问第三轮 如果是3xd该怎么压缩?多谢!
回复 支持 反对

使用道具 举报

哗啦啦 发表于 2016-1-12 10:01:13 | 显示全部楼层
楼主,第三轮的题不就是Leetcode的271题        Encode and Decode Strings 吗?

补充内容 (2016-1-12 10:03):
错了,不一样的,一个是压缩,一个是编码。不好意思
回复 支持 反对

使用道具 举报

哗啦啦 发表于 2016-1-12 10:04:56 | 显示全部楼层
第三轮的题目如果没有数字的话,直接就把“adddbffffsssssscvvvvv”压缩成“a3db4f6sc5v”就行了吧?
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2016-1-12 11:02:19 | 显示全部楼层
楼主能po一下第二轮的做法吗,感觉楼主第二轮很牛
回复 支持 反对

使用道具 举报

yjfox 发表于 2016-1-12 11:32:34 | 显示全部楼层
stackoverflow 里的解法是最naive的,缺点很明显,不能弹性处理,比如前半秒只有1个request,大量request集中后半秒,但这个solution无法合理处理这种情况,只能一刀切. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
楼主用queue从精确度角度看更好。只是有可能会爆掉,如果时间delta比较小,可以用定长array来模拟queue

比较高级的实现应该是bucket ticket吧
回复 支持 反对

使用道具 举报

哗啦啦 发表于 2016-1-12 13:11:02 | 显示全部楼层
yjfox 发表于 2016-1-12 11:32
stackoverflow 里的解法是最naive的,缺点很明显,不能弹性处理,比如前半秒只有1个request,大量request集 ...

queue的长度是固定的呀,为什么会爆掉?
回复 支持 反对

使用道具 举报

readman 发表于 2016-1-12 14:35:29 | 显示全部楼层
第三轮是我原题....当时那n多corn cases....
回复 支持 反对

使用道具 举报

 楼主| zhangquan913 发表于 2016-1-12 15:02:08 | 显示全部楼层
silenceleaf 发表于 2015-12-29 02:06
楼主请问第三轮 如果是3xd该怎么压缩?多谢!

压缩成1x11xx1xd
回复 支持 反对

使用道具 举报

 楼主| zhangquan913 发表于 2016-1-12 15:03:11 | 显示全部楼层
哗啦啦 发表于 2016-1-12 10:04
第三轮的题目如果没有数字的话,直接就把“adddbffffsssssscvvvvv”压缩成“a3db4f6sc5v”就行了吧?

不能改变压缩格式,也就是不能省略那个x
回复 支持 反对

使用道具 举报

 楼主| zhangquan913 发表于 2016-1-12 15:15:13 | 显示全部楼层
readman 发表于 2016-1-12 14:35
第三轮是我原题....当时那n多corn cases....

你面的也是google吗?拿到offer没啊?
回复 支持 反对

使用道具 举报

一路向北~ 发表于 2016-1-12 15:24:45 | 显示全部楼层
请问楼主面的是entry level吗?还是SE3以及往上的?
回复 支持 反对

使用道具 举报

 楼主| zhangquan913 发表于 2016-1-12 23:56:38 | 显示全部楼层
一路向北~ 发表于 2016-1-12 15:24
请问楼主面的是entry level吗?还是SE3以及往上的?

面的时候并没有说是什么级别的,但应该不是entry level,我已经有两年工作经验了。
回复 支持 反对

使用道具 举报

yjfox 发表于 2016-1-13 01:23:04 | 显示全部楼层
哗啦啦 发表于 2016-1-12 13:11
queue的长度是固定的呀,为什么会爆掉?

可以详细说下用queue准备怎么搞
一个request进来就insert一个到queue?然后统计单位时间queue的长度?
如果是这样的话,有几个缺点,
1 使用了比较复杂的数据结构,性能有影响。 2 作为一个service ratelimiter肯定希望最大化解偶,与其他无关代码没有任何联系,如果用queue,这个queue 可能就是要处理的message queue了,那还得在客户端把这个数据结构注册进ratelimiter。 3 scalability

我刚又仔细看了下stackoverflow的解答,他那个是对的,token bucket的最简化版
.鐣欏璁哄潧-涓浜-涓夊垎鍦
google的guava有类似实现,所以面试才会问这个问题。说明这个组不错哦
回复 支持 反对

使用道具 举报

csmargaret 发表于 2016-1-16 07:20:28 | 显示全部楼层
. 1point3acres.com/bbs
这样压缩不是改变目标格式了吗?按照楼主给的例子:“adddbffffsssssscvvvvv”压缩成“a3xdb4xf6xsc5xv”
回复 支持 反对

使用道具 举报

plutoman 发表于 2016-1-21 15:23:46 | 显示全部楼层
哗啦啦 发表于 2016-1-12 13:11
queue的长度是固定的呀,为什么会爆掉?

同意,queue长度是限定的,不会爆掉。stackoverflow的解也不符合原本的题意,如果要求任何1秒内不能超过threshold。
回复 支持 反对

使用道具 举报

plutoman 发表于 2016-1-21 15:30:57 | 显示全部楼层
yjfox 发表于 2016-1-13 01:23
可以详细说下用queue准备怎么搞
.1point3acres缃一个request进来就insert一个到queue?然后统计单位时间queue的长度?
...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
原本题意到底是什么?
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷任何一秒范围内不能超过N次request ? 如果是这样,那用queue是必须的。用stackoverflow token bucket 就不对了。后者是解决了另一种问题。
回复 支持 反对

使用道具 举报

plutoman 发表于 2016-1-21 15:31:05 | 显示全部楼层
yjfox 发表于 2016-1-13 01:23. From 1point 3acres bbs
可以详细说下用queue准备怎么搞
一个request进来就insert一个到queue?然后统计单位时间queue的长度?
...

原本题意到底是什么?
任何一秒范围内不能超过N次request ? 如果是这样,那用queue是必须的。用stackoverflow token bucket 就不对了。后者是解决了另一种问题。
回复 支持 反对

使用道具 举报

plutoman 发表于 2016-1-21 15:32:42 | 显示全部楼层
谢谢分享。
第一题原本题意到底是什么? . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
任何一秒范围内不能超过N次request ? 如果是这样,那用queue是必须的。用stackoverflow token bucket 就不对了。后者是解决了另一种问题。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-24 12:25:21 | 显示全部楼层
请问楼主第二题是用hashmap先扫描数组,记录位置,然后写comparator吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 20:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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