logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
Google电面
avatar
Google电面# JobHunting - 待字闺中
N*a
1 楼
听起来像是欧洲人，accent听起来有点吃力，先上题目：
1.leetcode上原题 number of islands
2.follow up：count rank 2 islands, where a rank 2 island is an island inside
a lake located on a continent. A continent is a piece of land located in
the ocean; the ocean is any body of water that touches the edges of the map.
Example:
000000000
000001100
001111100
011000100
001010100
001000100
001111100
000000000
上面这个例子里应该返回1.
3.If the input 2d array is too large to fit in memory, how to handle?
我从第二个follow up开始就回答的磕磕绊绊，最后也没写code，一直在跟面试官讨论
。后来思路终于讨论出来了，但第二个follow up面试官提示说water的那个dfs和第一
问里的dfs有什么不同，后来明白他想说water的dfs要考虑对角线情况。第三个follow
up更是不知道怎么回答，瞎扯了一通。
请教各位大侠们，第三问该怎么考虑？
avatar
d*g
2 楼
没明白。。 continent必须得是闭环？
能讲讲你的思路不？

inside
map.

【在 N*****a 的大作中提到】
: 听起来像是欧洲人，accent听起来有点吃力，先上题目：
: 1.leetcode上原题 number of islands
: 2.follow up：count rank 2 islands, where a rank 2 island is an island inside
: a lake located on a continent. A continent is a piece of land located in
: the ocean; the ocean is any body of water that touches the edges of the map.
: Example:
: 000000000
: 000001100
: 001111100
: 011000100
avatar
g*r
3 楼
第三题应该可以divide and conquer
（1）把矩阵分成小块读进内存，用DFS/BFS找number of islands，求一个全局的sum
(2) merge相邻小矩阵的edge（类似于 merge ranges）,把减少的独立islands数从sum
里减去

inside
map.

【在 N*****a 的大作中提到】
: 听起来像是欧洲人，accent听起来有点吃力，先上题目：
: 1.leetcode上原题 number of islands
: 2.follow up：count rank 2 islands, where a rank 2 island is an island inside
: a lake located on a continent. A continent is a piece of land located in
: the ocean; the ocean is any body of water that touches the edges of the map.
: Example:
: 000000000
: 000001100
: 001111100
: 011000100
avatar
l*s
4 楼
我觉得染色法可以解2和3。第一步，先染ocean和non-continent islands，第二步，染
continent islands，第三步染lakes，第四步找到rank 2 islands。这种方法可以针对
2bfs，也可以针对3逐行做。

inside
map.

【在 N*****a 的大作中提到】
: 听起来像是欧洲人，accent听起来有点吃力，先上题目：
: 1.leetcode上原题 number of islands
: 2.follow up：count rank 2 islands, where a rank 2 island is an island inside
: a lake located on a continent. A continent is a piece of land located in
: the ocean; the ocean is any body of water that touches the edges of the map.
: Example:
: 000000000
: 000001100
: 001111100
: 011000100
avatar
m*r
5 楼
求大神再详细解释下？
不胜感激

【在 l******s 的大作中提到】
: 我觉得染色法可以解2和3。第一步，先染ocean和non-continent islands，第二步，染
: continent islands，第三步染lakes，第四步找到rank 2 islands。这种方法可以针对
: 2bfs，也可以针对3逐行做。
:
: inside
: map.
avatar
l*s
6 楼
一起探讨一下思路，第一步其实就是从边开始把所有0以及相邻的0改变值成为2，从边
开始把1以及相邻的1改变值成为3，这样剩下的0和1就一定是lake和continent了，然后
故伎重演就行了。

【在 m*********r 的大作中提到】
: 求大神再详细解释下？
: 不胜感激
avatar
N*a
7 楼
我后来在面试官提示下，想到用leetcode上surrounded region那题的思路来解决2.从4
条edge出发dfs把ocean的0都变成2，（这一步需要考虑对角线），再扫描一遍2d array
把跟2相邻的1，也就是continent找出来dfs都变成3，剩下的1就是rank 2 island，剩
下的0就是lake。

【在 d****g 的大作中提到】
: 没明白。。 continent必须得是闭环？
: 能讲讲你的思路不？
:
: inside
: map.
avatar
N*a
8 楼
我一开始也是说从边开始找1来确定continent。但面试官给了个反例，比如下图，里面
那个1也是continent，因为外环右上角有个0。如果从边开始找1，就不能发现里面这个
1也是continent。所以应该根据1周围有没有ocean来判断。
000000000000
011111111101
010000000001
010010000001
010000000001
011111111111

【在 l******s 的大作中提到】
: 一起探讨一下思路，第一步其实就是从边开始把所有0以及相邻的0改变值成为2，从边
: 开始把1以及相邻的1改变值成为3，这样剩下的0和1就一定是lake和continent了，然后
: 故伎重演就行了。
avatar
N*a
9 楼
对，你的思路对第1题应该可行，可是第二题divide and conquer这种思路就不行了吧
？一旦divide会影响对ocean的判断。

sum

【在 g*********r 的大作中提到】
: 第三题应该可以divide and conquer
: （1）把矩阵分成小块读进内存，用DFS/BFS找number of islands，求一个全局的sum
: (2) merge相邻小矩阵的edge（类似于 merge ranges）,把减少的独立islands数从sum
: 里减去
:
: inside
: map.
avatar
N*a
10 楼
可不可以解释下针对3怎么逐行做？染色法的dfs不是往4个方向走吗？

【在 l******s 的大作中提到】
: 我觉得染色法可以解2和3。第一步，先染ocean和non-continent islands，第二步，染
: continent islands，第三步染lakes，第四步找到rank 2 islands。这种方法可以针对
: 2bfs，也可以针对3逐行做。
:
: inside
: map.
avatar
l*s
11 楼
我的方法可以找到中间的continent，我的第一步之后图会变成如下，2是ocean，3是
non-continent，剩下的1就是continent。
222222222222
233333333323
232222222223
232212222223
232222222223
233333333333

【在 N*****a 的大作中提到】
: 我一开始也是说从边开始找1来确定continent。但面试官给了个反例，比如下图，里面
: 那个1也是continent，因为外环右上角有个0。如果从边开始找1，就不能发现里面这个
: 1也是continent。所以应该根据1周围有没有ocean来判断。
: 000000000000
: 011111111101
: 010000000001
: 010010000001
: 010000000001
: 011111111111
avatar
l*s
12 楼
我没有写code，只是想法说一下：
逐行扫描，同行的相同元素染成一色（颜色数字用一个新的目前最大颜色数字+1表示）
，下一行扫描时根据上一行相同列进行染色。一旦发现与相邻格不同类的，则染新的颜
色(颜色+1)。到达边界的颜色数字最后会被记录在一个列表里，这些数字根据其原始颜
色来辨别其是Ocean，or Non-continent。
举例：
0000001000000000
0000001100000000
0000110011010000
0000100100110111
0000011011110000
0001111111110000
经逐行扫描染色法后变为：
2222223444444444
2222223344444444
2222556677484444
22225669AA884BBB
22222CCD88884444
222CCCC888884444
维护一个Hashmap，保存
以上包括 map.Add(2, 0); map.Add(3, 1) ... map.Add(A, 0); map.Add(B, 1) ...
一旦接触到边，我们记录下来到边的数字有2,3,4,8,B,C，这些不是Ocean，就是
non-continent。而其余数字则是内部元素，需要进一步扫描判断。

【在 N*****a 的大作中提到】
: 可不可以解释下针对3怎么逐行做？染色法的dfs不是往4个方向走吗？
avatar
f*5
13 楼
请问第三个怎么做？
avatar
m*r
14 楼
confused, 3不是continent吗?为什么是non-continent？

【在 l******s 的大作中提到】
: 我没有写code，只是想法说一下：
: 逐行扫描，同行的相同元素染成一色（颜色数字用一个新的目前最大颜色数字+1表示）
: ，下一行扫描时根据上一行相同列进行染色。一旦发现与相邻格不同类的，则染新的颜
: 色(颜色+1)。到达边界的颜色数字最后会被记录在一个列表里，这些数字根据其原始颜
: 色来辨别其是Ocean，or Non-continent。
: 举例：
: 0000001000000000
: 0000001100000000
: 0000110011010000
: 0000100100110111
avatar
C*7
15 楼
按楼主的意思这个最后的1应该是3吧，感觉楼主说的continent不是指湖中间的。所以
第二遍染色应该从ocean出发，把ocean相邻的1染成3

【在 l******s 的大作中提到】
: 我的方法可以找到中间的continent，我的第一步之后图会变成如下，2是ocean，3是
: non-continent，剩下的1就是continent。
: 222222222222
: 233333333323
: 232222222223
: 232212222223
: 232222222223
: 233333333333
avatar
C*7
16 楼
考虑对角线是什么意思？

从4
array

【在 N*****a 的大作中提到】
: 我后来在面试官提示下，想到用leetcode上surrounded region那题的思路来解决2.从4
: 条edge出发dfs把ocean的0都变成2，（这一步需要考虑对角线），再扫描一遍2d array
: 把跟2相邻的1，也就是continent找出来dfs都变成3，剩下的1就是rank 2 island，剩
: 下的0就是lake。
avatar
l*s
17 楼
根据定义，A continent is a piece of land located in the ocean。3不是in the
ocean，而是由边际延伸出的陆地。

【在 m*********r 的大作中提到】
: confused, 3不是continent吗?为什么是non-continent？
avatar
m*t
18 楼
can we do the follownig
o start at the border of the map, do BFS to figure out all the nodes that
are ocean. mark them as ocean "O"
o do the following until all the nodes are visited.
a. if it is "1", then check if any of its neighbor has "O" or if it is
at the borer. if yes, then mark it and all its BFS children's as continent,
mark as "C"
b. if all its neighbor is either "0" or "1", then its BFS children's are
rank 2 island, mark them "I", and increase the island count by 1

inside
map.

【在 N*****a 的大作中提到】
: 听起来像是欧洲人，accent听起来有点吃力，先上题目：
: 1.leetcode上原题 number of islands
: 2.follow up：count rank 2 islands, where a rank 2 island is an island inside
: a lake located on a continent. A continent is a piece of land located in
: the ocean; the ocean is any body of water that touches the edges of the map.
: Example:
: 000000000
: 000001100
: 001111100
: 011000100
avatar
k*l
19 楼
2.
How about this:
1) find lakes
lake is a graph of 0 not connected to any edge, label them 'L'
2) find all islands that only connected to Lake 'L' nothing else (no 0 or
edge)

inside
map.

【在 N*****a 的大作中提到】
: 听起来像是欧洲人，accent听起来有点吃力，先上题目：
: 1.leetcode上原题 number of islands
: 2.follow up：count rank 2 islands, where a rank 2 island is an island inside
: a lake located on a continent. A continent is a piece of land located in
: the ocean; the ocean is any body of water that touches the edges of the map.
: Example:
: 000000000
: 000001100
: 001111100
: 011000100
avatar
N*a
20 楼
面试官说像下面这个例子，被1包围的两个0也是ocean，所以ocean可以通过对角线延伸
，dfs的时候要考虑对角线。
000000
111000
100110
111110

【在 C*7 的大作中提到】
: 考虑对角线是什么意思？
:
: 从4
: array
avatar
m*t
21 楼
this seems not a big issue, right? it is just the definition of what ocean
is. did I miss something?

【在 N*****a 的大作中提到】
: 面试官说像下面这个例子，被1包围的两个0也是ocean，所以ocean可以通过对角线延伸
: ，dfs的时候要考虑对角线。
: 000000
: 111000
: 100110
: 111110
avatar
C*7
22 楼
哦，谢谢

【在 N*****a 的大作中提到】
: 面试官说像下面这个例子，被1包围的两个0也是ocean，所以ocean可以通过对角线延伸
: ，dfs的时候要考虑对角线。
: 000000
: 111000
: 100110
: 111110
avatar
C*7
23 楼
你的方法相当于排除法，实现起来复杂度很高，需要大量重复dfs

【在 k**l 的大作中提到】
: 2.
: How about this:
: 1) find lakes
: lake is a graph of 0 not connected to any edge, label them 'L'
: 2) find all islands that only connected to Lake 'L' nothing else (no 0 or
: edge)
:
: inside
: map.
avatar
k*l
24 楼
恩，有道理，这么改善如何
1。从四边开始找海，所有找到的on the fly填成陆地
这样剩下的水就是湖了
2. 再从四边开始找陆地,找到的当即填成海
剩下的1就是湖中岛了

【在 C*7 的大作中提到】
: 你的方法相当于排除法，实现起来复杂度很高，需要大量重复dfs
avatar
T*U
25 楼
如果没有ocean呢？比如
11111
10001
10101
10001
11111
边界开始的1算不算continent?

从4
array

【在 N*****a 的大作中提到】
: 我后来在面试官提示下，想到用leetcode上surrounded region那题的思路来解决2.从4
: 条edge出发dfs把ocean的0都变成2，（这一步需要考虑对角线），再扫描一遍2d array
: 把跟2相邻的1，也就是continent找出来dfs都变成3，剩下的1就是rank 2 island，剩
: 下的0就是lake。
avatar
k*r
26 楼
这个应该没关系吧，按照要求，里面的0都碰不到海，所以都不是海啊。

【在 T****U 的大作中提到】
: 如果没有ocean呢？比如
: 11111
: 10001
: 10101
: 10001
: 11111
: 边界开始的1算不算continent?
:
: 从4
: array
avatar
T*U
27 楼
那外圈的1是不是都算rank 2 island了呢？
按他的算法continent的定义比较关键，我觉得接触edge的都算continent, 因为
leetcode原题是说边界以外都算水。

【在 k****r 的大作中提到】
: 这个应该没关系吧，按照要求，里面的0都碰不到海，所以都不是海啊。
avatar
T*U
28 楼
有一个暴力法
第一次遍历求出联通union find的矩阵，分块存储，合并也很简单。
第二次在找出是和边界联通的水，变成2；比如找m[2][4]是否联通，找到他的parent是
m[100][100]在第5个硬盘存储块上,就要把第5个存储块读进来，一直找到最后的parent。
第三次找到和边界或者2联通的1，就是3
剩下的就是合并块的思路。这个方法超级多硬盘读写，不知道能不能被通过

【在 N*****a 的大作中提到】
: 对，你的思路对第1题应该可行，可是第二题divide and conquer这种思路就不行了吧
: ？一旦divide会影响对ocean的判断。
:
: sum
相关阅读
我曾经被老板骚扰过，现在找工作心里总是有阴影Job referI-9填错了怎么办airbnb racism问一个怎么存很大两维数组电话面试问题求教H1B回国时买往返机票还是单程机票？Uber Storage Team招人硅谷的华为里头管事的也应该拉出来批斗一下求推荐可靠的online CS course (Data structure..)值得一听，诚恳的职业发展建议two sigma现在属于第几梯队？【hiring】AT&T Lab@ NJ: CS,EE,SE,Applied Math【内部推荐】推荐Google软件工程师，面试准备建议有没有湾区公司employee的学历统计阿三经理只招阿三2个offer求比较意见芝加哥地区求工作[Cupertino] 内部推荐机会，苹果DDR PHY组 (转载)公司要求出具 90天没有 unemployment 的证明
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。