Google 电面过经

网投的Google Mobile Engineer 职位，电面听声音像一个国人小哥。
非常nice， 题目是 耳灵灵，
follow up

游客，本帖隐藏的内容需要积分高于 188 才可浏览，您当前积分为 0。
查看如何攒积分 Click here for more info.

如果数据非常大无法存入内存咋办？

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

请问第二个follow up怎么答比较好呀？

不修改输入什么意思？用visited[i]记录吗

同问第二问怎么回答好呢？第二个follow up应该跟题目无关吧？

@Calval111 请问第二个follow up怎么答比较好呀？
这个我也没答好，大意就是矩阵很大，无法全部load入内存，期望地里有高手可以解答

@wubidi666  不修改输入什么意思？用visited[i]记录吗
用boolean visited[i][j] 可以的，我用的是hashmap 存储访问过的岛屿

我觉得第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
不知道这个想法对不对

pyjhzwh 发表于 2020-11-29 11:28
我觉得第2个followup 可以每次load进内存>=2行的grid，但是每次之间要有1行的overlap
比如
grid = [

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

pyjhzwh 发表于 2020-11-29 11:28
我觉得第2个followup 可以每次load进内存>=2行的grid，但是每次之间要有1行的overlap
比如
grid = [

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

ghdwfnh 发表于 2020-11-30 03:57
具体怎么实现呢？不是太明白
leetcode上可以试一下
https://leetcode.com/problems/number-of-islands/

感觉可以用union find方法