10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 14249|回复: 95
收起左侧

刚结束的google onsite/Seattle office

  [复制链接] |试试Instant~ |关注本帖
sheepmiemies 发表于 2016-4-30 08:05:33 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - Other - Onsite |Otherfresh grad应届毕业生

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
运气还行,没遇到特别难的题,可惜自己表现的还是不算很好,表现8分以上肯定offer的话,估计在6分左右。。求问有没有类似经历,可不可以请求加面,怎么求加面?
先说说城市体验吧,西雅图还是传说的那样,总是阴天,偶有小雨,不过onsite快结束的那会开始放晴了,还有点热,很像家乡的天气。downtown实在很拥挤,各种单行线,3点多开始堵车,想找到宾馆停车的地方很艰难。。。城市算在山坡上吧,有不少坡,当然比不上三番的陡峭哈哈哈。不过如果不是准备顺便玩一趟,来google onsite还是不要rental car了,太麻烦。。。

google office位置还算有点偏,拐了好几道弯各种小路才绕过去,面对面两栋4层左右的房子,前台进去checkin,居然左侧就是食堂。。。整个流程下来感觉格局非常神奇,没搞懂各个区域到底怎么划分的,而且到处都要刷badge,包括电梯。。。之前onsite联系的hr会带你稍微走一下,然后直接带到会议室,她就撤退了。前两轮面试的地方是个比较大的会议室,整面墙都是白板随便写非常爽。.1point3acres缃

第一轮:
白人大哥。上来就直接说开始coding。
第一题binary tree to double linkedlist,要求in-place,挺简单的偏偏好久没刷类似的题了,讲思路,写代码,debug,跑case,总共花了半个小时左右,中间有些小bug涂涂改改写好了。
第二题感谢地里面经,是string encoding,就是aaabbb变3xa3xb那一道题,写了encode的代码,follow u带着一步一步发觉有哪些问题,比如原始string就是3xa怎么办,回答是把数字和x都编码。再问怎么简化一点,答是只用encode数字不用管x。再问如果有重复数字比如2222a呢,答压缩数字4x2a。再问如果有一百万个数字是0123456789012345……的循环,最后跟一个x怎么办,答如果x结尾不用管,不压缩了就。整个过程一半自己想出来一半靠他提示,他其实一直再问,"so what's the general rules?"。。。就是说分情况讨论之前提到的几种情况,保证能够顺利decode。并且不要求每次encode之后string都变短,但是总体上average是变短的。这轮代码写得还行,就是最后general rule答得不好,感觉一般。而且没留时间问问题。。
. Waral 鍗氬鏈夋洿澶氭枃绔,
第二轮:.鏈枃鍘熷垱鑷1point3acres璁哄潧
白人小哥,又一个上来就直接问问题,不过小哥一直笑呵呵的,但是我总感觉是戏谑的笑容。。。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。 查看如何攒积分
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

我给了一些比较简单的意见,比如优先级,基于时间,或者基于比例或者用随机数,都不行。因为他说这是个简单的系统,没法学习,如果每个组定优先级,那谁都说他们组的信息更重要;如果说时间,那每个组都在每天的最后写log。。。再说随机数或者比例,这样的话会变相鼓励某个组多写log,以提高被选中的数量。简直就有点懵,然后还给了个case,比如前面三个组都有上百条,但是第四个组只有1条,buffer只有100,按比例的话,第四个组就没有log了。。。我给了另一个方法,是先拿出50%的buffer让所有组均分,剩下的部分再想其他办法。他说均分的方法可以,然后那会30分钟过去了,他说先写点code吧,我说好,然后就把这部分code写完了,中途有些counter小bug被发现了汗颜。。。最后我给他的方案是,先拿50%保证每个组都分得有,而且需求比较小的组可能还会有剩,剩余的回收过来,然后不停地迭代平均分配,直到所有的都分完。感觉有一个小亮点就是,本来需要写两个function,我说可以改传递参数,直接重用,讲了下思路,就结束了。又是一个没有提问的一轮。。。。

吃饭,伙食一般啊感觉,白人小哥告诉我这边是吃汉堡和印度菜吧好像,对面有pizza,salad和sushi还有vegi,我说有肉就行,他就笑。。就去吃了点pizza,弄了点小牛排和sushi,那sushi真够小的,就矿泉水瓶盖俩那么大。。。然后聊天,逛逛,看到健身房和game room,还在game room玩了会类似于冰壶的那种游戏。前两轮中途完全没休息,在吃饭聊天已经很累了,但是没好意思说让我去歇会。。。
. more info on 1point3acres.com
第三轮:
白人大哥,声音有点沙哑,一会严肃一会微笑的,又是上来就coding!!!google家好直接。。。
这题很常规,也是面得最顺的一轮。题目是,设计一个class来re-arrange array。一开始会给两个array,这两个array存在一个pattern,然后给你一个input array,让你根据pattern给output,例如:A:1,2,3,4 -->B: 4,3,2,1这样的pattern, 如果在给你一组数是5678,那你就返回8765。相当于对应index。


一开始有点懵,就说,对每个A中的元素,在B中scan来找他对应的index,这样建立一个index mapping,时间复杂度是O(N^2),想了两分钟,脑袋简直停滞了。。他说我们先写个code,然后就把这个code写了。写完了以后follow up,他说你的code如果有duplicate就不work了呀,我说那我加一个flag array,每次选了一个位置之后把对应位置置为1. 再follow up他举了个例子,其实就是A和B中的元素不完全对应,意思就是check validation,然后我给写了。这时候如果一个client他需要用多个pattern你的code会是怎样的,就是声明一个新obj然后初始化,再调用就行了。这时候开始要优化了,毕竟O(N^2)太慢了,突然才发现自己傻逼,其实就是一个double mapping,先用一个map记录A中每个数字的索引,然后第二个map建立A的索引指向B的索引就行了,对于duplicate element,我们只需要把第二个map的value设成一个list,每次取其中一个就行了,他假设相同元素无所谓先后顺序。顺利写完code,基本上没什么bug,不过刚问两个问题还意犹未尽呢,第四轮又来了。。。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
第四轮:
白人小哥,一头飘逸的(男生中的)长发,时不时会遮住左眼,看着相当高冷,但是偶尔又笑得很和蔼,但是马上又变回去。写code的时候,偶尔往回看的时候,发现他似乎在看着天花板若有所思。。。
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。 查看如何攒积分

第二题,给一个迷宫,当时心里很忐忑,心想会不会中奖,结果中奖了。。。
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。 查看如何攒积分
但是既然是迷宫思路就应该是DFS/BFS求解吧,一般都是DFS找出口很暴力。但是这道题的问题是,没有给迷宫的其他信息,怎么保存状态呢?我说要不用一个vector<pair<int,int>>来保存path,记录在某个方向前进了多少步,在用一个map记录走了那些方向,这样遇到死胡同就用最后一条记录来roll-back,小哥说因吹丝挺。。。。然后写到一半,他才突然又提示说,你可以从graph的角度思考,晕。。。然后我就说设计一个Point class,来边走边建图,Point里面用一个vector存四个方向的point,然后用一个flag数组来记录哪些方向走过了。他说make sense。不过最后一轮这实在太累了,脑袋有点转不动,代码没写完,给他讲了思路,他就拍照了。。。那十几二十行代码,感觉拍下来好惨。。。。他还特意留了时间,然后跟他问了几个问题。LZ只能按捺着心情和疲劳强行问了几个,就结束了。。。


很神奇的是,前三轮的面试官他们居然都在用纸来抄代码,估计还有一些对此人的评价吧,感觉擦擦改改的时候好对不起他们。回来的时候,西雅图downtown居然3点就开始堵车。。。。

再次求问有没有类似经历,可不可以请求加面,怎么求加面?
-google 1point3acres


补充内容 (2016-5-25 00:59):
三周过去了,昨天问HR说她去问问然后告诉我。。。当时onsite完了说好的1~2weeks呢。。。

评分

8

查看全部评分

本帖被以下淘专辑推荐:

jeremy_sea 发表于 2016-5-9 14:44:37 | 显示全部楼层
4.1题 应该有多种解法,不同操作的trade off。 其实和2d matrix mutable有点点像。 随便写了下
  1. from collections import defaultdict
  2. class StrOldIndex:
  3.     def __init__(self, s):
  4.         self.str = s
  5.         self.index_map = {}
  6.         for i, c in enumerate(s):
  7.             self.index_map[i] = i

  8.     # O(n) to add str. But O(1) to read the str
  9.     def add(self, i, c):
  10.         idx = self.index_map[i]
  11.         self.str = self.str[:idx] + c +self.str[idx:]. from: 1point3acres.com/bbs
  12.         for k, v in self.index_map.iteritems():
  13.             if k >= i:
  14.                 self.index_map[k] += 1. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  15.     # O(n) in str replace
  16.     def replace(self, i, c):
  17.         idx = self.index_map[i]. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  18.         self.str = self.str[:idx] + c + self.str[idx+1:]. 鍥磋鎴戜滑@1point 3 acres

  19.     # O(n) in delete, need to update indexes after i
  20.     def delete(self,i):
  21.         self.replace(i, '')
  22.         for k, v in self.index_map.iteritems():
  23.             if k >= i:
  24.                 self.index_map[k] -= 1

  25. class StrOldIndex2:
  26.     def __init__(self,s):
  27.         self.str = s
  28.         self.str_lst = defaultdict(list)
  29.         for i, c in enumerate(s):
  30.             self.str_lst[i].append(c)

  31.     # O(1) in add. But read takes O(n).1point3acres缃
  32.     def add(self, i, c):
  33.         self.str_lst[i].append(c)-google 1point3acres

  34.     def replace(self, i, c):
  35.         old_list = self.str_lst[i]
  36.         new_list = [c].extend(old_list[1:])
  37.         self.str_lst[i] = new_list

  38.     def delete(self, i):
  39.         self.replace(i, '')

  40. s=StrOldIndex('abc')
  41. s.add(1,'a')
  42. assert s.str == 'aabc'
  43. s.add(2,'c')
  44. assert s.str == 'aabcc'

复制代码

回复 支持 1 反对 0

使用道具 举报

jeremy_sea 发表于 2016-5-9 14:51:25 | 显示全部楼层
第三题非常straightforward. 代码如下,有需要的拿去
  1. class Solution:
  2.     def __init__(self, a1, a2):
  3.         self.index_mapping = {}. from: 1point3acres.com/bbs
  4.         self.pattern_mapping = {}
  5.         assert len(a1) == len(a2). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  6.         for i, d in enumerate(a1):
  7.             self.index_mapping[d] = i
  8. . more info on 1point3acres.com
  9.         for i, d in enumerate(a2):
  10.             self.pattern_mapping[i] = self.index_mapping[d]


  11.     def matching(self, input):
  12.         res = []
  13.         assert len(input)==len(self.index_mapping)
  14.         for i, d in enumerate(input):
  15.             res.append(input[self.pattern_mapping[i]]). visit 1point3acres.com for more.
  16.         return res


  17. a1 = [4,3,2,1]. 1point3acres.com/bbs
  18. b1 = [1,2,3,4]
  19. s=Solution(a1, b1). 1point 3acres 璁哄潧
  20. assert s.matching([5,6,7,8]) == [8,7,6,5]
  21. a1 = [1,2,3,4]
  22. b1 = [2,4,1,3]. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  23. s2=Solution(a1, b1).1point3acres缃
  24. assert s2.matching([5,6,7,8]) == [6,8,5,7]
复制代码
回复 支持 1 反对 0

使用道具 举报

mzli1989 发表于 2016-4-30 08:42:04 | 显示全部楼层
祝楼主好运!
其实感觉除了最后一轮,其他轮楼主面的都还不错吧
最后一轮疲惫了面试官或许也能理解
回复 支持 反对

使用道具 举报

lihao814386741 发表于 2016-5-1 03:55:46 | 显示全部楼层
鹏鹏面的还是不错的, 题目都是挺难的。感觉有的时候不太准,有的时候自己感觉不好,但是面试官觉得好的话也会给很高分数的, 加面应该是自己控制不了的。继续move on。
回复 支持 反对

使用道具 举报

 楼主| sheepmiemies 发表于 2016-5-1 07:07:06 | 显示全部楼层
mzli1989 发表于 2016-4-30 08:42
祝楼主好运!
其实感觉除了最后一轮,其他轮楼主面的都还不错吧
最后一轮疲惫了面试官或许也能理解

嗯嗯,但愿最后一轮不要太惨哈哈
回复 支持 反对

使用道具 举报

 楼主| sheepmiemies 发表于 2016-5-1 07:07:31 | 显示全部楼层
lihao814386741 发表于 2016-5-1 03:55. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
鹏鹏面的还是不错的, 题目都是挺难的。感觉有的时候不太准,有的时候自己感觉不好,但是面试官觉得好的话 ...

嗯嗯,加面貌似是转SEIT的加面,先不管他了到时候再说吧
回复 支持 反对

使用道具 举报

windream1991 发表于 2016-5-3 08:38:48 | 显示全部楼层
感觉你面的大部分题都不太常规。。。。你后面还有面试吗
回复 支持 反对

使用道具 举报

 楼主| sheepmiemies 发表于 2016-5-4 08:09:40 | 显示全部楼层
windream1991 发表于 2016-5-3 08:38
感觉你面的大部分题都不太常规。。。。你后面还有面试吗

嗯,主要第二轮和第四轮不常规,第二轮属于一般吧,第四轮是第二题思路说了没写完。。。还有个wayfair在做OA,然后哲哥说准备好了可以再试试我们去年暑假老东家

突然想起,早就想问,你这个秃瓢是谁啊,你微信头像应该也是这哥们吧哈哈哈
-google 1point3acres
补充内容 (2016-5-8 09:36):
卧槽才发现打错字,是说图片。。。

补充内容 (2016-5-8 09:36):
不是秃瓢。。。
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-5-8 07:09:31 | 显示全部楼层
感觉楼主的题好难啊。。。
回复 支持 反对

使用道具 举报

 楼主| sheepmiemies 发表于 2016-5-8 09:39:00 | 显示全部楼层
caiqi8877 发表于 2016-5-8 07:09
感觉楼主的题好难啊。。。

第二轮和第四轮是有点,比较考验交流和对实际问题的抽象能力~
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-5-8 12:30:44 | 显示全部楼层
sheepmiemies 发表于 2016-5-8 09:39
第二轮和第四轮是有点,比较考验交流和对实际问题的抽象能力~
.鐣欏璁哄潧-涓浜-涓夊垎鍦
祝楼主好运!
回复 支持 反对

使用道具 举报

CrossTheWall 发表于 2016-5-8 18:26:57 | 显示全部楼层
第四轮操作原始index的那题,不能直接用map来存Iterator吧?因为string的Iterator会在增删操作发生时全部失效, 除非你事先把string用一个list离散开
回复 支持 反对

使用道具 举报

 楼主| sheepmiemies 发表于 2016-5-8 23:13:03 | 显示全部楼层

多谢!
回复 支持 反对

使用道具 举报

 楼主| sheepmiemies 发表于 2016-5-8 23:29:31 | 显示全部楼层
CrossTheWall 发表于 2016-5-8 18:26
第四轮操作原始index的那题,不能直接用map来存Iterator吧?因为string的Iterator会在增删操作发生时全部失 ...

不好意思我忘了补充了。。。我是用list存的,iterator并不会受到影响,而且如果用string/vector来增删会出现数据移动,所以不会选这两个结构的除非每次都是从最后增删。C++里的vector的iterator确实会失效,但是string的不会失效,但是会移动。
回复 支持 反对

使用道具 举报

CrossTheWall 发表于 2016-5-9 00:47:23 | 显示全部楼层
sheepmiemies 发表于 2016-5-8 23:29
不好意思我忘了补充了。。。我是用list存的,iterator并不会受到影响,而且如果用string/vector来增删会 ...

恩, 如果面试官允许用list把string离散开就行,如果不让离散化,我想他的目的应该就是让你用线段树或树状数组了,对某个id的Add和delete操作相当于先看[0, id-1]的区间被累加或减少了几次,这样就能知道下标移动的步数,只是这样复杂度就是logn了,不像list那样O(1)操作。
回复 支持 反对

使用道具 举报

CrossTheWall 发表于 2016-5-9 00:51:46 | 显示全部楼层

祝楼主能拿到offer,我觉得看你描述的情况,应该还是比较有胜算的。 G家题是挺难,但好像对bug free卡得不是那么严,我近期电面G家,写错了个地方(挺严重),不过感谢面试官不杀之恩,近期要去onsite了
回复 支持 反对

使用道具 举报

 楼主| sheepmiemies 发表于 2016-5-9 01:48:47 | 显示全部楼层
CrossTheWall 发表于 2016-5-9 00:47
恩, 如果面试官允许用list把string离散开就行,如果不让离散化,我想他的目的应该就是让你用线段树或树 ...

嗯嗯,你说得对,google家比较看重交流和逻辑吧,代码实现相对没那么严格。感觉你的基础很扎实,而且看帖子很仔细,我觉得你没问题的!也谢你吉言啦!

再说一个个人意见,因为每一轮他们都会把你的代码写下来/拍下来,想清楚逻辑再写尽量少涂改可能会比较好,会觉得你思路清晰吧。我面的时候感觉涂抹有点多。。。
回复 支持 反对

使用道具 举报

caiqi8877 发表于 2016-5-9 03:09:26 | 显示全部楼层
CrossTheWall 发表于 2016-5-9 00:47-google 1point3acres
恩, 如果面试官允许用list把string离散开就行,如果不让离散化,我想他的目的应该就是让你用线段树或树 ...

请问下什么叫把string离散开,不是很明白。。。
回复 支持 反对

使用道具 举报

stellari 发表于 2016-5-9 03:44:26 | 显示全部楼层
感谢楼主分享面经。不过最后一题我认为“沿着一边墙”的策略依然是可以的。这种策略其实本来就是DFS的一种简化说法。你不需要知道预先哪边是墙,只要在每一点用forward函数按顺时针顺序遍历可前进的3个方向即可。. 鍥磋鎴戜滑@1point 3 acres

唯一的问题是这里只能向“右”转身,所以每次到达迷宫中的一个位置时,可以先向右旋转3次,这样就等于向左转了1次。如果此时forward能成功就沿着这个方向走,如果不行的话,再向右旋转1次,再尝试forward……如此尝试3次forward后如果都不成功的话,因为此时的方向和来时的方向正好相反,因此调用forward原路返回即可。.鏈枃鍘熷垱鑷1point3acres璁哄潧
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
也就是说,每到一个节点,最少旋转3次,最多旋转6次。但是不用建图,不用任何额外数组储存走过的方向信息。
回复 支持 反对

使用道具 举报

ok123 发表于 2016-5-9 04:57:00 | 显示全部楼层
迷宫想复杂了吧?
跟一般的迷宫题是一样的
def DFS():
    while True:. Waral 鍗氬鏈夋洿澶氭枃绔,
        forward()  # 不管return value
        turn_right() #
        forward()   # dfs 返回了,试试西边
        turn_right()
        turn_right()  #跳过北边
        forward()    # 试试东边

补充内容 (2016-5-9 04:57):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
假设,最初是自北向南
回复 支持 反对

使用道具 举报

ok123 发表于 2016-5-9 05:05:09 | 显示全部楼层
ok123 发表于 2016-5-9 04:57
迷宫想复杂了吧?
跟一般的迷宫题是一样的
def DFS():

错了,改一下
def DFS():
        if forward() == True:
            DFS()
        turn_right() #.1point3acres缃
        if forward() == True:   # dfs 返回了,试试西边
             DFS()
        turn_right()
        turn_right()  #跳过北边
        forward()    # 试试东边
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-21 06:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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