一亩三分地论坛

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

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

日本之旅:Google 东京 onsite,憾失offer

[复制链接] |试试Instant~ |关注本帖
CrossTheWall 发表于 2016-6-21 12:25:03 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 博士 全职@Google - 内推 - Onsite |Fail在职跳槽

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

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

x


楼主在帝都工作, 今年跳槽期, 找朋友内推了Amazon(北京部)和google(东京部)。 Amzon持续了3周,一轮电面6轮onsite,这个不多说了。 5月之前Google两次电面换来东京的onsite机会,东京分部确实不错,在六本木Ropping Hills的44楼,天气好的时候据说可以看到富士山。 我到了那边后,被台湾的一个MM HR带着逛了一圈, 然后在一个会议室等面试官了,上午两轮后,午餐时间,貌似东京google的餐厅没有美国那边豪华,走的是日式简约路线,饭菜么,真心不如楼下那些居酒屋、小餐馆的好吃。。下午三轮,然后我被送出Ropping Hill,开始了9天的日本自由行。返回北京时,在机场收到HR邮件,说因为有两个题没给出最优解,没拿到offer, 然后约了下周给我电话分析详细的反馈。

Google跪了,确实比较遗憾。我这次设计题不少,有三轮算是比较圆满,中间一轮有个俄罗斯人的题不会做,第一轮的题没给出最优解,所以我早料到了结果。 回北京后拿了A家SDEII的offer,准备走transfer路线来美帝了。

好了,不再赘述,直接上题:

1. 给我一个整数, 让我封装RGB三种颜色,并且定义一个颜色加法。 问题是给一堆这种RGB,和一个目标颜色,写一个函数判断能否从这堆RGB里通过定义的加法得到目标颜色。 这题我觉得DFS就能解,直接写了个递归算法。然后他说,你这个复杂度多少?我说每个颜色有取和不取两种选择,所以理论是2^n, 但我们可以通过剪枝来缩小复杂度的量级, 我说这取决于定义的加法运算,如果是按位或来叠加颜色,剪枝就很容易。然后他说,你觉得有无更优的策略, 我这里就没得出更好的。。。接着他又来一设计题:压缩大型的文本文件。

2. 你的手机无法定位自己了,但是能通过一个数据库定位周围能探测的基站位置,现在探测出了一堆周围的基站经纬坐标和信号强度,让你估算自己当前位置的经纬度。 这个题我直接有点懵了,但俄罗斯人比较厚道说,无论如何也要给个解决方案写出代码,于是我写了个根据信号强度为Kernel权重来插值计算的代码,就是所谓的反距离权重。我也分析了如果这些位置是形成了Convex Hull可以这么做,不然是不靠谱的(面试反馈里说我把问题复杂化了,估计俄罗斯人不太明白Convex Hull这些)。 然后就是一设计题:快速得到google的关键词词组, 比如你敲入google, 马上返回google map, google image, google file system 等等。 我给出了多重trie树的设计,他没表示反对。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
.1point3acres缃
3. 给一堆box, 任何一个box只有长宽高都小于另一个才能装进去,每个box可以自由旋转,问这堆box能做成最深几层? 这个就是变种版本的最长递增序列问题。
. from: 1point3acres.com/bbs
4. 一个长串,一个目标串,找到长串里的第一个子串,这个子串是目标串的某个排列组合。 然后Follow up是如果放在分布式集群上如何并行优化?这题follow up是精华,基本思想是把原串分割分给不同机器(并处理划分边界),但因为目的是找到第一个, 所以可以利用类似二分的思想来处理划分边界,然后迭代这个过程。 这轮是个日本人,日本人的英语普遍真是没救了,不过比阿三还是好懂不少。

5. 一个像素平面,一个操作流集合,每个操作要么是在某个位置点一个点,要么是取消上一步操作,让你即时输出每一步操作后,像素板上形成了几个“岛屿”。岛屿是指相连的像素块 。Follow up是如何扩展到3D全息图. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴6. 一堆人,每个人有自己的google日历的繁忙区间,让你计算所有人都不忙的最长时间段。


评分

4

查看全部评分

youto 发表于 2016-6-21 14:01:14 | 显示全部楼层
这是一个老帖子了吧,lz是来挣积分的?
回复 支持 0 反对 5

使用道具 举报

 楼主| CrossTheWall 发表于 2016-6-21 14:04:19 | 显示全部楼层
youto 发表于 2016-6-21 14:01
这是一个老帖子了吧,lz是来挣积分的?
. visit 1point3acres.com for more.
。。。。那你找找那个老帖子。我这就是发生在两周前的事,还历历在目。积分这东西我根本不care,只是分享一下,找找一起讨论题目的人
回复 支持 4 反对 0

使用道具 举报

complete_46 发表于 2016-6-21 23:38:49 | 显示全部楼层
CrossTheWall 发表于 2016-6-21 15:37
如果简单而论,我在帝都待了10年,有点烦了。国内国外各有利弊吧,我们都是权衡利弊作出的选择,没有对错 ...
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
可能有点毁三观 我觉得美国太破了。。
回复 支持 1 反对 0

使用道具 举报

nano 发表于 2016-6-21 14:03:41 | 显示全部楼层
thanks for sharing. 楼主已经很牛了,第一题RGB那个感觉有点像k-sum,就是k个值相加得到预定目标,当然还的决定K,可以先从k=2开始试,弄个set 存已经有的颜色,然后目标颜色减已有颜色看看是不是存在在set里面了,如果有就直接返回,没有的话把向减的颜色作为下一轮目标颜色的备选,k=2没有luck的话换k=3,从目标颜色备选序列里面出发,同样做类似的事情。其实也是递归的dfs, 复杂度是 n+n^2+...+n^k ~O(n^k).第二题你想的真的挺复杂的,我是不太理解convex hull是什么,查了也不知道为什么应用在这里,感觉基本就考虑信号的衰减是距离的monotone decreasing function, 然后每个基站周围可以画一个个圈,圈上的信号强度假设相等,题目就变成n个圆找交点的问题,当然,我完全认为信号没有变频也没有相位叠加
回复 支持 反对

使用道具 举报

 楼主| CrossTheWall 发表于 2016-6-21 14:33:35 | 显示全部楼层
nano 发表于 2016-6-21 14:03
thanks for sharing. 楼主已经很牛了,第一题RGB那个感觉有点像k-sum,就是k个值相加得到预定目标,当然还的 ...

多谢啊!你真的给了我很好的提示。第一题我觉得你的解就是他想要的,有点像压缩DP或者增量生成, 逐渐增大K值来逼近目标,不过貌似这里不能颜色重用,所以我觉得要保留下ID的值的, 貌似需要以颜色为key, 然后对应的值是一个vector<set>, 以此来看是否颜色的ID已经用过了。 这个面试时我没想到,看来确实需要进一步历练。

第二题,我当时急了,临时用了自己做流体模拟时用到的类似粒子系统插值的算法,所谓convex Hull就是插值点被周围样本点均匀“wrap”的意思。 你说的这个N圆求交让我眼前一亮,貌似有点像等高线求交一样。不过我还是觉得这样会解不出来,比如你周围2个基站,你怎么从两圈圆环的交点确定当前的位置呢?
回复 支持 反对

使用道具 举报

dg7743 发表于 2016-6-21 15:25:12
CrossTheWall 发表于 2016-6-21 14:33
多谢啊!你真的给了我很好的提示。第一题我觉得你的解就是他想要的,有点像压缩DP或者增量生成, 逐渐增 ...

第一轮代码可参考http://www.jiuzhang.com/solutions/k-sum/
支持 反对

complete_46 发表于 2016-6-21 15:26:37 | 显示全部楼层
为啥要来美帝呢 我很想回去 想听听楼主看法
回复 支持 反对

使用道具 举报

 楼主| CrossTheWall 发表于 2016-6-21 15:37:08 | 显示全部楼层
complete_46 发表于 2016-6-21 15:26
为啥要来美帝呢 我很想回去 想听听楼主看法
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
如果简单而论,我在帝都待了10年,有点烦了。国内国外各有利弊吧,我们都是权衡利弊作出的选择,没有对错之分。 对我自己来说,更好的空气质量、食品安全、教育环境占的比重更大。 不知你为何想回去呢?
回复 支持 反对

使用道具 举报

adrian_yang84 发表于 2016-6-21 16:10:53 | 显示全部楼层
谢谢楼主分享!

第一题:
我想不出比指数更快的优化。能想到的小优化是,利用R,G,B三个数,分别限定边界,从给定的集合中先排除一些数。(因为它们越加越大)
第二题:
画圈的方法很好。
另外想到的解法是,设存在这样的关系:(x,y为待求。xi,yi,di分别为基站坐标与距离关系)(x-xi)^2 + (y-yi)^2 = di^2.
而实际上是有误差的。所以我们的目标是误差最小(其实就是画圈的话,不一定会焦点重合,所以我们找中间点).1point3acres缃
那么变成如下目标函数:
min{sigma((x-xi)^2+ (y-yi)^2 - di^2)^2}
对这个函数求导,然后用梯度下降法,迭代解之。. Waral 鍗氬鏈夋洿澶氭枃绔,

多重trie,能详细说说么?

第四题:
想问一下为什么分布式的话,用二分的思想

第五题:
有人说要用并查集来解“岛屿”问题。我不懂并查集。
是这样么?你当时怎么解的,面试官又是怎么说的呢?. Waral 鍗氬鏈夋洿澶氭枃绔,

多谢了~

回复 支持 反对

使用道具 举报

zjuzqh 发表于 2016-6-21 16:27:43 | 显示全部楼层
1. 最长递增序列楼主用的O(N^2)还是O(NlogN)解法呢? 2. 第五题,二维平面并查集leetcode原题,三维的话,应该就考察坐标映射吧。(x,y,z)--》x*m*n+y*n+z ; 3. 第6题,除了给各个区间,应该还会给起始时间点吧。求区间间隔,区间排序后,贪心求解。
回复 支持 反对

使用道具 举报

 楼主| CrossTheWall 发表于 2016-6-21 16:58:45 | 显示全部楼层
adrian_yang84 发表于 2016-6-21 16:10.鏈枃鍘熷垱鑷1point3acres璁哄潧
谢谢楼主分享!

第一题:

第一题我觉得nano的方法是最好的,把K逐渐增大,然后cache之前的结果。注意啊,不一定是越加越大,加法运算可自定义,可以按位或,可以整数加法(这样考虑溢出,因为单字节来encode一个颜色分量)

第二题,感觉你连梯度下降和最小二乘都用上了啊,这题我觉得更像设计题,我得仔细再想想。这次面试就是跪在1、2两题上了。
多重trie,就是如果是一般字母,就按一般的方式建一个字母分支, 但如果碰到空格,我们就让它指向另一个trie,这个trie的所有词相当于能和上一层的词组成词组。例如 google map, google image, 那么,google后面的空格指向 map和image组成的trie。 .鏈枃鍘熷垱鑷1point3acres璁哄潧
. Waral 鍗氬鏈夋洿澶氭枃绔,
第四题, 每台机器先处理边界的一系列substring window,如果发现可行, 就舍弃后面的串。如果所有的边界window都不符合,那就让所有机器并行处理属于自己的那部分字串即可。 重复这个划分-检测的过程. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

第五题就是并查集,不过呢对于撤销操作,需要回滚对并查集的操作。 这轮面试官很满意,剩下15分钟和旁听的那位闲聊
回复 支持 反对

使用道具 举报

 楼主| CrossTheWall 发表于 2016-6-21 17:05:11 | 显示全部楼层
zjuzqh 发表于 2016-6-21 16:27.鏈枃鍘熷垱鑷1point3acres璁哄潧
1. 最长递增序列楼主用的O(N^2)还是O(NlogN)解法呢? 2. 第五题,二维平面并查集leetcode原题,三维的话 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
最长递增序列那题,用平方级复杂度就行。我提到有个log级的,面试官说那个太tricky了,面试时不要求。第五题比那个Number of islandII多了个撤销操作,这个地方要回滚并查集的。 三维容易,就是8个邻居,坐标按你说的方式映射。

第6题, 我的方法是把全部时间点都排个序,然后按CG中的判断相交重叠数的方式求解(当然,也可以merge interval)。 排序的时候,面试官问能优化吗?后来我发现这里排序就是merge一系列的有序数组,这样比直接扔一起排序快
回复 支持 反对

使用道具 举报

vivaroma 发表于 2016-6-21 18:56:19 | 显示全部楼层
google东京是日本人用英语面试?
回复 支持 反对

使用道具 举报

pustar 发表于 2016-6-21 18:57:47 | 显示全部楼层
1题类似“用硬币凑一定数额的钱”?,DP?. 1point 3acres 璁哄潧
3题类似leetcode 354        Russian Doll Envelopes
5题类似leetcode 200        Number of Islands,只是改成了3维?
6题类似leetcode         56        Merge Intervals
回复 支持 反对

使用道具 举报

 楼主| CrossTheWall 发表于 2016-6-21 19:04:15 | 显示全部楼层
vivaroma 发表于 2016-6-21 18:56
鏉ユ簮涓浜.涓夊垎鍦拌鍧. google东京是日本人用英语面试?

有美国人、保加利亚人、俄罗斯,日本人只是少数
回复 支持 反对

使用道具 举报

codyman 发表于 2016-6-21 20:59:03 | 显示全部楼层
楼主之前在帝都哪家公司?
回复 支持 反对

使用道具 举报

zjuzqh 发表于 2016-6-21 21:26:52 | 显示全部楼层
CrossTheWall 发表于 2016-6-21 17:05
最长递增序列那题,用平方级复杂度就行。我提到有个log级的,面试官说那个太tricky了,面试时不要求。第 ...

我觉得撤销操作,可以对每个点记录两个祖先,一个是最新的,一个是次新的。撤销某个点时,把某个点的周围点的祖先更新为原来即可。

所有人都不忙的最长时间段。我的理解是求若干区间间隔的最大值。直接对区间排序,先start,后end排序。然后扫描区间。这里每次记录当前区间最大的end值,对于每个区间,若它的start>maxEnd,则区间间隔产生,更新结果。还要更新当前的maxEnd.

补充内容 (2016-6-21 21:28):
当前区间最大的end值。改为已扫描的若干区间的最大end值。
回复 支持 反对

使用道具 举报

yzl232 发表于 2016-6-21 22:31:40 | 显示全部楼层
谷歌东京听说也是讲英语不讲日语, 对吗?
回复 支持 反对

使用道具 举报

readman 发表于 2016-6-21 22:32:47 | 显示全部楼层
看了以上的帖子...
我小声问一句...
. 1point 3acres 璁哄潧
第一题 不就是背包问题么....

第二题 不就是Steiner tree problem么....

第三题  lc 套娃原题..
. From 1point 3acres bbs
第四题 lc Minimum Window Substring. follow up: 切分长串然后在不同机器上数出来每个字母的个数? 我还想不到这个和二分有什么关系....二分不是要有序么....也许是我弱爆了.... Waral 鍗氬鏈夋洿澶氭枃绔,

第五题 u-f 上没也说过了. visit 1point3acres.com for more.

第六题 merge interval
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 04:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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