一亩三分地论坛

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

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

Google NY 全职 onsite 四轮

[复制链接] |试试Instant~ |关注本帖
堕落的猴子 发表于 2015-9-26 09:16:54 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
同样的已挂勿念,感觉几家大公司最近的bar真是老高老高的,怎么实习了一暑假leetcode刷了2遍回来反而好像变水了。。。

=====感想=====
1,题目难度果然看运气,然而难度其实不代表什么,并没有卵用。
2,面试官彼此会通气问过的问题,所以老实交代就好。.鏈枃鍘熷垱鑷1point3acres璁哄潧
3,最近的bar真是高,挂了就赶紧move on吧,别想太多。不是像我这种特别想留纽约的,还是考虑面总部找机会transfer,大概bar低一些。
4,请带着会被挂掉这个前提阅读我的面经(sad)。当然也不要多疑,不然会觉得做什么都可能被挂,影响发挥。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 1point3acres.com/bbs
=====onsite=====. from: 1point3acres.com/bbs

一轮:白人小哥,我校友,上来寒暄了下学校的事儿,问了你最喜欢什么课,说了个课他似乎没听过。。。
1,encode and decode list of strings。
>标准题,不过是讨论性质的。我先说run length encoding,然后再提到了leetcode里的选取delimiter然后对原字符串的delimiter进行特殊处理的办法,感觉还挺满意,我提到可能用escape character也可以做到,他说是可以,也还有其他办法。然后让我不用写代码,"lets make it more complicated". from: 1point3acres.com/bbs
2,follow up,binary tree of strings,就是每个node上写一个string,依然是encode和decode,可以基于上面的encode和decode函数。
>先讨论如何表示这个tree,提到可以用类似leetcode(当然没说leetcode)那样的用#来表示空叶子的方式进行前序遍历+补全空叶子。表示空间消耗太大(2 ^ h),然后直接提示我可以用array来存,每个元素存node和他的两个孩子的index。并且简单讨论了下为啥一次遍历无法restore(包括反例)。追加讨论了下如果用array的方式存,要如何encode和decode。
>然后讨论如何序列化和反序列化一个树,因为想起来了双遍历序列化+反序列化的算法,直接说可以两次序列化(前序+中序或者后序+中序),然后恢复的时候就用两个序列化恢复。表示很有兴趣,同时表示这样的空间消耗是两份的,不过可以用这个办法。
>最后时间不是很多,就让我写了下从双遍历结果恢复tree的伪代码就结束了。(restore tree from post-order + in-order / pre-order + in-order)。-google 1point3acres
. 1point3acres.com/bbs
二轮:白人大叔,上来先聊了下project,问了下我暑假做的东西,然后和他做的东西很类似。
1,iterator design。
>也是挺标准的iterator,他们家就那么几种iterator(横的,竖的,斜的),主要是处理好boundary condition和各种null check。因为聊项目花了大概20分钟,这里写完白板代码就差不多没时间了,他拍照了下就lunch break了。

三轮:西班牙小哥,带着一个shadow旁观。上来就出题。
1,給一个matrix,里面不同cell写着不同的数字,给你一个起点,然后只要上下左右的cell的数字和你目前位置的数字相同就可以继续走,最后给出能到达的区域的周长,边缘的周长不用算。(因为原题是说你想把这个区域用篱笆围起来,但是边上篱笆已经围好了)。. from: 1point3acres.com/bbs
>很基本的dfs,走过的格子可以改成负数或者特殊字符来防止重复计算。每走一格+4个周长,然后如果访问到一个已经访问过的,就减2,然后访问到边缘就减1。写出白板代码,自带边界检查,但是一开始以为是算格子数,估计这里扣分不少。被提醒是算周长之后,简单想了下就改好了。
>是否可以优化:可以,记录目前移动的方向,然后下一步不需要走回来直接减2。. Waral 鍗氬鏈夋洿澶氭枃绔,
>是否可以不修改原matrix来纪录访问状态:我提出用比特类的元素来记录(比如bitmap和bitset),表示这样空间使用还是会和matrix的m*n相关。回答用额外数组或者set只记录访问过的格子,表示可以,问这个set要如何实现。表示可以用hashset,问这个hash函数如何写,表示用m + n来做mod操作,具体hash公式写不出来,后来想想果然不太对。
>看起来复杂度是O(|需要包围的区域的cell数|),问是否可以优化。想了几分钟感觉不太可能,和他问hint,他说你未必找得到,也可以想想证明这个无法优化。尝试对算法用数学分析来证明这是最低的复杂度,哪怕减少也不会改变大O复杂度。小哥似是而非地接受了。

四轮:白人小哥,上来一脸笑容说我们来聊一道题吧。心想不妙。
1,給一个n * n的matrix,代表一个区域,每个格子里的数字是那个格子的高度。现在matrix的右边第一列有一条河,高度是H,如果第一列有格子高度低于H,水就会灌进来,然后蔓延到区域里所有联通的且高度低于H的格子。然后给你一个起点一个终点P1和P2,试问要在K步之内从P1走到P2(走的时候无所谓区域高度,可以4个方向随便走),河的高度最大是多少。比如第一列高度都是100,然后剩下都是1(并且假设P1到P2的距离不到k),那么河的最大高度是就是101(101之前水都淹不进来). Waral 鍗氬鏈夋洿澶氭枃绔,
>直接看傻了几秒,心想好多条件啊。然后对方倒是没让我直接做,开始问我怎么分解问题。
>提取出一个基础问题,假设河的高度是H,是否P1可以在K步之内达到P2。表示先做一个dfs完成灌水(一开始说成从边上一行行扫描,后来想到要dfs才行),然后从P1开始bfs,所有被灌水的区域不考虑,看看是否能在K步之内到达P2。表示可以。问这两步的复杂度,表示前者是O(n^2),后者是O(k),所以还是O(n^2)了。
>然后如果有了基础问题的解,如何找到合适的H。表示H的上下限不是0和正无穷,至少应该是matrix里的最高点和最低点,然后进行二分查找。如果mid的高度可以让P1走到P2,那么就low = mid,不然就hi = mid - 1。表示可以。这样这一步的复杂度就是log(|min - max|)了。
>写了下bfs和二分搜索步骤的伪代码,时间快没了,问我是否可以进一步优化,表示想不到。于是告诉我上下限可以进一步根据P1和P2本身的高度进行压缩,而不是全局的上下限。这里说实话没太明白,万一我地形很诡异,用最大值隔开了河,或者用最小值包住了P1和P2,那么P1和P2本身的高度似乎无所谓啊。总之时间到了。

总之严格来说不是很出色的面试,希望能或多或少帮到后面的小伙伴吧:)



补充内容 (2015-9-26 10:39):
有同学指出来,google的面试bar和地点无关,大家可以无视我那一个猜测了。

评分

5

查看全部评分

本帖被以下淘专辑推荐:

flexwang 发表于 2015-9-28 15:09:18 | 显示全部楼层
感觉dfs遇到不能走的就周长加一比较好
回复 支持 2 反对 0

使用道具 举报

hulahu 发表于 2015-9-26 09:31:12 | 显示全部楼层
啥时面的, 楼主。。
回复 支持 反对

使用道具 举报

 楼主| 堕落的猴子 发表于 2015-9-26 09:42:55 | 显示全部楼层
hulahu 发表于 2015-9-26 09:31
啥时面的, 楼主。。

就这周面的,今天出的结果,下周一去微软的时候都不知道还有多少自信。。。
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-26 15:31:35 | 显示全部楼层
是说被水淹了就不能走了? 那个例子为什么最大不是100而是101
回复 支持 反对

使用道具 举报

 楼主| 堕落的猴子 发表于 2015-9-26 23:03:02 | 显示全部楼层
flexwang 发表于 2015-9-26 15:31
是说被水淹了就不能走了? 那个例子为什么最大不是100而是101

和河高度一样不会被灌水,所以最边上的一列100最多可以挡住高度为100的河,101的河就挡不住了。
回复 支持 反对

使用道具 举报

binomial 发表于 2015-9-26 23:21:37 | 显示全部楼层
请问楼主没有设计题吗?谢谢!. 1point3acres.com/bbs
还有,我也是一定要找纽约的,希望多多交流啊!
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-27 00:08:24 | 显示全部楼层
上下限可以设成最右边一列的最小值和最大值吗
回复 支持 反对

使用道具 举报

mikegrup 发表于 2015-9-27 00:13:00 | 显示全部楼层
第四轮的题目, 这个思路不知道对不:.鏈枃鍘熷垱鑷1point3acres璁哄潧
1. BFS 从P1到P2, 找到所有k steps以内的P1->P2的path, 保存所有路径上面的最小H (minH数组),以及出现的点(mini,minj坐标数组). 也就是说,水过了这个H那么这条路就不能走了.
2.取最大的H in minH, 假设为maxh,左右为maxi,maxj. 这样也就说只要水高度不超过maxh,P1总有至少一条路到达P2. 所有水最大高度很有可能是maxh,但是不一定,因为最有一列的值很可能挡住了maxh的水,或者是中间没有路可以到达maxh的这个点
3. BFS 从 maxi,maxj ,如果matrix的height小于maxh,就可以走,看看能不能走回河里, 也就是最右一列中高度小于等于maxh的点,如果可以,maxh即为所求.如果不可以,就比较复杂了,选出所有从maxi,maxj到最右一列的点的所有路径上的最小height的使得maxi,maxj能到到达这个点,这个height就是最优.


回复 支持 反对

使用道具 举报

 楼主| 堕落的猴子 发表于 2015-9-27 00:26:11 | 显示全部楼层
mikegrup 发表于 2015-9-27 00:13
第四轮的题目, 这个思路不知道对不:
1. BFS 从P1到P2, 找到所有k steps以内的P1->P2的path, 保存所有路径 ...

你可以想想看这个的复杂度。。。
回复 支持 反对

使用道具 举报

 楼主| 堕落的猴子 发表于 2015-9-27 00:28:31 | 显示全部楼层
flexwang 发表于 2015-9-27 00:08
上下限可以设成最右边一列的最小值和最大值吗

下限可以,上限完全可能第二列的比第一列更高,结果你用第一列的最大值来做上限,答案就错误了。
回复 支持 反对

使用道具 举报

 楼主| 堕落的猴子 发表于 2015-9-27 00:31:12 | 显示全部楼层
binomial 发表于 2015-9-26 23:21
请问楼主没有设计题吗?谢谢!
还有,我也是一定要找纽约的,希望多多交流啊!

恩我是没碰到设计,有可能会出一轮设计就是。

可以一起交流下纽约这边的公司名单啊。
回复 支持 反对

使用道具 举报

mikegrup 发表于 2015-9-27 00:51:49 | 显示全部楼层
堕落的猴子 发表于 2015-9-27 00:26
你可以想想看这个的复杂度。。。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
太变态了阿,这当场理解题目就已经很难了
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-27 21:41:25 | 显示全部楼层
为什么访问到边缘就减一
回复 支持 反对

使用道具 举报

 楼主| 堕落的猴子 发表于 2015-9-27 22:22:40 | 显示全部楼层
flexwang 发表于 2015-9-27 21:41
为什么访问到边缘就减一

因为边缘已经被篱笆围住了,不需要再加篱笆来围住。
回复 支持 反对

使用道具 举报

blactangeri 发表于 2015-9-28 00:29:06 | 显示全部楼层
lz你不是都打出来了吗怎么没过
回复 支持 反对

使用道具 举报

 楼主| 堕落的猴子 发表于 2015-9-28 00:47:10 | 显示全部楼层
blactangeri 发表于 2015-9-28 00:29
lz你不是都打出来了吗怎么没过

因为严格来说扣分点还是不少,而且其中也有运气成分。简单来说还是实力不济+运气不佳了。
回复 支持 反对

使用道具 举报

cu0817 发表于 2015-9-28 05:36:46 | 显示全部楼层
堕落的猴子 发表于 2015-9-27 00:31
恩我是没碰到设计,有可能会出一轮设计就是。

可以一起交流下纽约这边的公司名单啊。

可以同交流纽约公司的名单吗?我也是想留在纽约的 ...
回复 支持 反对

使用道具 举报

setest 发表于 2015-9-28 06:00:51 | 显示全部楼层
cu0817 发表于 2015-9-28 05:36
可以同交流纽约公司的名单吗?我也是想留在纽约的 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
同求交流~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 02:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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