一亩三分地

 找回密码 注册账号

扫描二维码登录本站

微信公众号
扫码关注公众号
留学申请号
扫码关注留学申请公众号
查看: 2599|回复: 14
收起左侧

Google 电面过经

[复制链接] |只看干货 |面试经验, 美国面经, mobileeng, google
地里的匿名用户
地里的匿名用户  发表于 2020-11-27 15:42:44 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎

2020(7-9月) MobileEng 硕士 全职@Google - 网上海投 - 技术电面  | Pass/Offer | 在职跳槽

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
网投的Google Mobile Engineer 职位,电面听声音像一个国人小哥。
非常nice, 题目是 耳灵灵,
follow up
游客,本帖隐藏的内容需要积分高于 188 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
如果数据非常大无法存入内存咋办?

评分

参与人数 4大米 +9 收起 理由
清道神君 + 5
fmusk + 1 给你点个赞!
umialpha + 2 给你点个赞!
StupidCorn + 1 给你点个赞!

查看全部评分


上一篇:狗狗挂经
下一篇:Square OA 面经
我的人缘0

升级   11.48%

本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   86% (129)
 
 
14% (21)    👎
本帖最后由 umialpha 于 2020-11-30 13:55 编辑

followup 2 的时候 我觉得可以多说一点思路:
1. 能否预处理输入,比如用bitmap或者稀疏矩阵的话可以压缩输入,然后尝试放入内存。
2. 如果1走不通,再想并行化。对于并行化,可以用UnionFind的思路。1)按照block切分,每个worker负责block处理内部的merge逻辑,
2)master处理block的merge操作。






回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (57)
 
 
3% (2)    👎
请问第二个follow up怎么答比较好呀?
回复

使用道具 举报

我的人缘0

升级   91%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   83% (683)
 
 
16% (131)    👎
不修改输入什么意思?用visited[i]记录吗
回复

使用道具 举报

我的人缘0

升级   36.71%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (94)
 
 
4% (4)    👎
同问第二问怎么回答好呢?第二个follow up应该跟题目无关吧?
回复

使用道具 举报

我的人缘0

升级   56.25%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (18)
 
 
0% (0)    👎
@Calval111 请问第二个follow up怎么答比较好呀?
这个我也没答好,大意就是矩阵很大,无法全部load入内存,期望地里有高手可以解答
回复

使用道具 举报

我的人缘0

升级   56.25%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (18)
 
 
0% (0)    👎
@wubidi666  不修改输入什么意思?用visited[i]记录吗
用boolean visited[i][j] 可以的,我用的是hashmap 存储访问过的岛屿
回复

使用道具 举报

我的人缘0

升级   36.5%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (14)
 
 
6% (1)    👎
我觉得第2个followup 可以每次load进内存>=2行的grid,但是每次之间要有1行的overlap
比如
grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
第一次 处理row 0 & row1用BFS
第二次 处理row1 & row2,这时候就不用管row1了,因为如果row1要和row2有相连的islands,那他们相连的部分必定会经过row1
在处理 row2 & row3, etc
不知道这个想法对不对
回复

使用道具 举报

我的人缘0

升级   56.25%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (18)
 
 
0% (0)    👎
pyjhzwh 发表于 2020-11-29 11:28
我觉得第2个followup 可以每次load进内存>=2行的grid,但是每次之间要有1行的overlap
比如
grid = [

我觉得这个idea不错,就可以把大的grid分成多个小的subgrid来处理,每个subgrid 跟相邻的subgrid有重叠的一个row 跟col. 这样就可以把岛屿连上了。
回复

使用道具 举报

我的人缘0

升级   97.5%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (104)
 
 
0% (0)    👎
pyjhzwh 发表于 2020-11-29 11:28
我觉得第2个followup 可以每次load进内存>=2行的grid,但是每次之间要有1行的overlap
比如
grid = [

具体怎么实现呢?不是太明白
leetcode上可以试一下
https://leetcode.com/problems/number-of-islands/
回复

使用道具 举报

我的人缘0

升级   97.5%

本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (104)
 
 
0% (0)    👎
ghdwfnh 发表于 2020-11-30 03:57
具体怎么实现呢?不是太明白
leetcode上可以试一下
https://leetcode.com/problems/number-of-islands/

感觉可以用union find方法
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

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