一亩三分地论坛

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

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

google21号新鲜电面

[复制链接] |试试Instant~ |关注本帖
isabel1992 发表于 2015-10-23 01:45:58 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 校园招聘会 - 技术电面 |Passfresh grad应届毕业生

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

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

x
在学校career engine上投的简历,结果google很快回复,安排了21号的电面。面试是一个白人大叔,说话有点含糊不清,一开始就let's get some warm-up开始问问题。第一个问的是一个HashMap里面的key是user-defined class然后要求override一下equals函数。第二题就是考的leetcode是的count islands的题,用dfs很快搞定。结果followup让我找那种湖中岛,就是在一个岛里面有水,然后里面的岛。想了一下说先找出岛标记,然后在inside里面找。问我怎么在inside里面找,我说从一个starting point开始dfs,遇到boundary就不继续这种,结果发现找starting pointq其实挺麻烦的,因为岛的形状会很不规则。最后面试官给提示让我mark water,然后想出来可以从boundary那边bfs标记所有outside water,其他就是inside water,然后看岛有没有和outside water接壤……
说出来了大叔还算满意,然后就是瞎聊天了。觉得自己答的也就一般,毕竟是提示出来的。没想到很快就收到move forward to onsite的邮件,自己也觉得挺幸运的。
楼主在地里看了不少面经,受益良多,所以也回馈一下,顺便给自己onsite攒人品,也希望大家都能拿到满意的offer, 吼吼~~. 1point 3acres 璁哄潧

评分

1

查看全部评分

本帖被以下淘专辑推荐:

pengzewen37 发表于 2015-10-26 12:33:56 | 显示全部楼层
我觉得楼上很多人没理解对,楼主也没说清楚。要求的岛应该是被水包围,并且这个水也不与边界相连,所以才称之为岛中的湖,然后湖中岛。思路是bfs由边界水的位置遍历mark外围水,然后dfs数岛的个数,若岛与外围水相连则island保持不变,若不相连则island++
回复 支持 3 反对 0

使用道具 举报

smile~~~~ 发表于 2015-10-23 03:18:24 | 显示全部楼层
lz能不能详细说说找湖中岛的思路啊?谢谢啦~祝onsite顺利
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-10-23 03:30:53 | 显示全部楼层
请问是求有多少个岛中湖吗?
回复 支持 反对

使用道具 举报

s_asolo 发表于 2015-10-23 04:15:11 | 显示全部楼层
感觉岛屿这道题可不可以用并查集呢,找出所有的岛屿,去掉落在边界上的岛屿,剩下的就是水中的岛屿
回复 支持 反对

使用道具 举报

tangvictor 发表于 2015-10-23 05:01:19 | 显示全部楼层
感觉是Number of islands瞬间变surrounded regions。是吗?并查集是可行的我写过,但面试时间够吗?
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-10-25 03:37:46 | 显示全部楼层
smile~~~~ 发表于 2015-10-23 03:18
lz能不能详细说说找湖中岛的思路啊?谢谢啦~祝onsite顺利

是leetcode那题吧?就是不和边界相连的岛
回复 支持 反对

使用道具 举报

 楼主| isabel1992 发表于 2015-10-25 21:28:39 | 显示全部楼层
smile~~~~ 发表于 2015-10-23 03:18
lz能不能详细说说找湖中岛的思路啊?谢谢啦~祝onsite顺利

从boundary一个点开始用一个dfs可以mark所有outside的水,其他的水就是inside了。然后check每个岛相邻的水,如果和outside的水相邻就numIsland-1
回复 支持 反对

使用道具 举报

 楼主| isabel1992 发表于 2015-10-25 21:29:15 | 显示全部楼层
宝贝忆彼岸 发表于 2015-10-23 03:30.1point3acres缃
请问是求有多少个岛中湖吗?

是湖中岛,而且也可以嵌套的~~
回复 支持 反对

使用道具 举报

 楼主| isabel1992 发表于 2015-10-25 21:33:40 | 显示全部楼层
s_asolo 发表于 2015-10-23 04:15
感觉岛屿这道题可不可以用并查集呢,找出所有的岛屿,去掉落在边界上的岛屿,剩下的就是水中的岛屿

好像没有要求必须是水中岛。不过如果这样的话,我倒觉得可以boolean dfs,然后碰到是1的边界return false. 然后if(dfs(nums, i, j)) numIsland++;这样的话是不是会比并查集简单一点?
回复 支持 反对

使用道具 举报

 楼主| isabel1992 发表于 2015-10-25 21:41:02 | 显示全部楼层
tangvictor 发表于 2015-10-23 05:01. Waral 鍗氬鏈夋洿澶氭枃绔,
感觉是Number of islands瞬间变surrounded regions。是吗?并查集是可行的我写过,但面试时间够吗?

并查集的话可能会太复杂了确实不容易在面试时间中把code写出来。其实我觉得一般在电话面试中考察不到这些复杂的数据结构,更多的是简单数据结构+扩展的思路。
回复 支持 反对

使用道具 举报

ssross 发表于 2015-10-30 04:41:35 | 显示全部楼层
pengzewen37 发表于 2015-10-26 12:33
我觉得楼上很多人没理解对,楼主也没说清楚。要求的岛应该是被水包围,并且这个水也不与边界相连,所以才称 ...

请问一下能不能举个例子具体说下你的思路呢?我还是没太明白什么是岛中湖然后湖中岛?非常感谢!
回复 支持 反对

使用道具 举报

pengzewen37 发表于 2015-10-30 06:13:32 | 显示全部楼层
本帖最后由 pengzewen37 于 2015-10-29 17:15 编辑
ssross 发表于 2015-10-29 15:41
请问一下能不能举个例子具体说下你的思路呢?我还是没太明白什么是岛中湖然后湖中岛?非常感谢!

刚刚实现了一下,验证了自己的说法。
  1. 0 0 0 0 0 0 0
  2. 0 1 1 1 1 1 0
    . visit 1point3acres.com for more.
  3. 0 1 0 0 0 1 0
  4. 0 1 0 1 0 1 0. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  5. 0 1 0 0 0 1 0. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6. 0 1 1 1 1 1 0
  7. 0 0 0 0 0 0 0
  8.                
复制代码
上面👆就是一个湖中岛,可以吧中间第二层的海看成死海(不与外界连通)然后最后返回应该是island个数,1, 因为只有它一个被死海包围。做法就是四周的活海加入队列,bfs标记好所有的活海,然后islandI的dfs方法遍历所有的岛,只是需要返回boolean类型判断一下当前遍历的岛是否与活海连接。 . 1point3acres.com/bbs
实现了一遍发现,onsite要完全写出来还有时间限制还是有点小苦难的,而且如果必须是严格意义上的这种岛的话(边界都是海,没有岛),那么出现这种湖中岛的情况,matrix也要至少7 * 7 以上,不过我都是我乱yy的,具体跟面试官交流了。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 05:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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