一亩三分地论坛

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

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

刚结束的google onsite/Seattle office

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

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

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

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

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

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

第一轮:. 鍥磋鎴戜滑@1point 3 acres
白人大哥。上来就直接说开始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答得不好,感觉一般。而且没留时间问问题。。. from: 1point3acres.com/bbs

第二轮:
白人小哥,又一个上来就直接问问题,不过小哥一直笑呵呵的,但是我总感觉是戏谑的笑容。。。
问题是,有一个simple log system,可以给每个team服务,每条log的形式是<team name, message>。每天结束的时候,每个组会调用API返回,只能返回给定数量message比如100条,而且这是所有message中的100条,不是某个组的100条。而且该API每天的返回信息是固定的。让你设计一下怎么返回,让每个组都满意,因为如果某个组返回的信息太少,那个组肯定不满意。所有message都存在disk上,你能拿到所有message。

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

吃饭,伙食一般啊感觉,白人小哥告诉我这边是吃汉堡和印度菜吧好像,对面有pizza,salad和sushi还有vegi,我说有肉就行,他就笑。。就去吃了点pizza,弄了点小牛排和sushi,那sushi真够小的,就矿泉水瓶盖俩那么大。。。然后聊天,逛逛,看到健身房和game room,还在game room玩了会类似于冰壶的那种游戏。前两轮中途完全没休息,在吃饭聊天已经很累了,但是没好意思说让我去歇会。。。

第三轮:
白人大哥,声音有点沙哑,一会严肃一会微笑的,又是上来就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。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. 鍥磋鎴戜滑@1point 3 acres

一开始有点懵,就说,对每个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的时候,偶尔往回看的时候,发现他似乎在看着天花板若有所思。。。
第一题,给定一个string,比如abc,设计add/replace/delete,三个function都会传入一个index,并且同一个index不会被用两次。index还有个特殊的地方,就是它只会是原始数据的index,比如abc,那就只有012。 如果调用 "add(1, a), add(2,c)"会变成aabcc,也就是操作会发生在原始的index上。给的解决方案就是用一个map存<index, iterator>然后对iterator进行操作,写了一些伪代码,他说ok这是warm up。
第二题,给一个迷宫,当时心里很忐忑,心想会不会中奖,结果中奖了。。。他说只给你两个API:(1) bool forward(); (2) turn_right(); 不给其他任何信息,第一个API会尝试在当前方向往前移动一步,如果遇到wall会返回false;第二个API就是转向;然后如果在forward的时候遇到出口就会退出,不用担心。这轮真是体现出对实际问题的抽象能力还是太弱了。。。一开始说很naive的方法就是遇到墙就turn right,其实不是,因为常用的沿着一边墙的方法对这道题行不通,因为你不知道那边是墙。。。但是既然是迷宫思路就应该是DFS/BFS求解吧,一般都是DFS找出口很暴力。但是这道题的问题是,没有给迷宫的其他信息,怎么保存状态呢?我说要不用一个vector<pair<int,int>>来保存path,记录在某个方向前进了多少步,在用一个map记录走了那些方向,这样遇到死胡同就用最后一条记录来roll-back,小哥说因吹丝挺。。。。然后写到一半,他才突然又提示说,你可以从graph的角度思考,晕。。。然后我就说设计一个Point class,来边走边建图,Point里面用一个vector存四个方向的point,然后用一个flag数组来记录哪些方向走过了。他说make sense。不过最后一轮这实在太累了,脑袋有点转不动,代码没写完,给他讲了思路,他就拍照了。。。那十几二十行代码,感觉拍下来好惨。。。。他还特意留了时间,然后跟他问了几个问题。LZ只能按捺着心情和疲劳强行问了几个,就结束了。。。


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

再次求问有没有类似经历,可不可以请求加面,怎么求加面?. Waral 鍗氬鏈夋洿澶氭枃绔,



.鏈枃鍘熷垱鑷1point3acres璁哄潧补充内容 (2016-5-25 00:59):
三周过去了,昨天问HR说她去问问然后告诉我。。。当时onsite完了说好的1~2weeks呢。。。

评分

8

查看全部评分

本帖被以下淘专辑推荐:

jeremy_sea 发表于 2016-5-9 14:51:25 | 显示全部楼层
第三题非常straightforward. 代码如下,有需要的拿去
  1. class Solution:
  2.     def __init__(self, a1, a2):
  3.         self.index_mapping = {}
  4.         self.pattern_mapping = {}
  5.         assert len(a1) == len(a2)
  6.         for i, d in enumerate(a1):
  7.             self.index_mapping[d] = i. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  8.         for i, d in enumerate(a2):. more info on 1point3acres.com
  9.             self.pattern_mapping[i] = self.index_mapping[d]. visit 1point3acres.com for more.


  10.     def matching(self, input):
  11.         res = []
  12.         assert len(input)==len(self.index_mapping)
  13.         for i, d in enumerate(input):. 鍥磋鎴戜滑@1point 3 acres
  14.             res.append(input[self.pattern_mapping[i]])
  15.         return res

  16. .鏈枃鍘熷垱鑷1point3acres璁哄潧
  17. a1 = [4,3,2,1]
  18. b1 = [1,2,3,4]
  19. s=Solution(a1, b1)
  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)
  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,然后哲哥说准备好了可以再试试我们去年暑假老东家

突然想起,早就想问,你这个秃瓢是谁啊,你微信头像应该也是这哥们吧哈哈哈
.鏈枃鍘熷垱鑷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. more info on 1point3acres.com
感觉楼主的题好难啊。。。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
第二轮和第四轮是有点,比较考验交流和对实际问题的抽象能力~
回复 支持 反对

使用道具 举报

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 | 显示全部楼层
caiqi8877 发表于 2016-5-8 12:30. Waral 鍗氬鏈夋洿澶氭枃绔,
祝楼主好运!

多谢!
回复 支持 反对

使用道具 举报

 楼主| 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家比较看重交流和逻辑吧,代码实现相对没那么严格。感觉你的基础很扎实,而且看帖子很仔细,我觉得你没问题的!也谢你吉言啦!. 1point3acres.com/bbs

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

使用道具 举报

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

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

使用道具 举报

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

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

使用道具 举报

ok123 发表于 2016-5-9 04:57:00 | 显示全部楼层
迷宫想复杂了吧?
跟一般的迷宫题是一样的
def DFS():
    while True:
        forward()  # 不管return value. visit 1point3acres.com for more.
        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. From 1point 3acres bbs
迷宫想复杂了吧?
跟一般的迷宫题是一样的
def DFS():

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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