当前在线人数14910
首页 - 分类讨论区 - 海外生活 - 待字闺中版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
Google电面
[版面:待字闺中][首篇作者:Nerissa] , 2015年08月07日01:26:13 ,3470次阅读,28次回复
来APP回复,赚取更多伪币 关注本站公众号:
[首页] [上页][下页][末页] [分页:1 2 ]
Nerissa
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: Nerissa (Nerissa), 信区: JobHunting
标  题: Google电面
发信站: BBS 未名空间站 (Fri Aug  7 01:26:13 2015, 美东)

听起来像是欧洲人,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更是不知道怎么回答,瞎扯了一通。

请教各位大侠们,第三问该怎么考虑?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 54.]

 
datoug
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: datoug (datoug), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Fri Aug  7 01:59:26 2015, 美东)

没明白。。 continent必须得是闭环?
能讲讲你的思路不?

【 在 Nerissa (Nerissa) 的大作中提到: 】
: 听起来像是欧洲人,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
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 24.]

 
geekytrader
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: geekytrader (万物皆可易), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Fri Aug  7 02:12:26 2015, 美东)

第三题应该可以divide and conquer
(1)把矩阵分成小块读进内存,用DFS/BFS找number of islands,求一个全局的sum
(2) merge相邻小矩阵的edge(类似于 merge ranges),把减少的独立islands数从sum
里减去
【 在 Nerissa (Nerissa) 的大作中提到: 】
: 听起来像是欧洲人,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
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 45.]

 
lestrois
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: lestrois (lestrois), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Fri Aug  7 06:51:27 2015, 美东)

我觉得染色法可以解2和3。第一步,先染ocean和non-continent islands,第二步,染
continent islands,第三步染lakes,第四步找到rank 2 islands。这种方法可以针对
2bfs,也可以针对3逐行做。


【 在 Nerissa (Nerissa) 的大作中提到: 】
: 听起来像是欧洲人,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
: ...................

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 70.]

 
mitqiuoffer
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: mitqiuoffer (qiuoffer), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Sat Aug  8 19:00:39 2015, 美东)

求大神再详细解释下?

不胜感激

【 在 lestrois (lestrois) 的大作中提到: 】
: 我觉得染色法可以解2和3。第一步,先染ocean和non-continent islands,第二步,染
: continent islands,第三步染lakes,第四步找到rank 2 islands。这种方法可以针对
: 2bfs,也可以针对3逐行做。
: inside
: map.



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 67.]

 
lestrois
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: lestrois (lestrois), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Sat Aug  8 20:13:22 2015, 美东)

一起探讨一下思路,第一步其实就是从边开始把所有0以及相邻的0改变值成为2,从边
开始把1以及相邻的1改变值成为3,这样剩下的0和1就一定是lake和continent了,然后
故伎重演就行了。


【 在 mitqiuoffer (qiuoffer) 的大作中提到: 】
: 求大神再详细解释下?
: 不胜感激


--
※ 修改:·lestrois 於 Aug  8 20:14:17 2015 修改本文·[FROM: 70.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 70.]

 
Nerissa
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 7 ]

发信人: Nerissa (Nerissa), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Sun Aug  9 18:54:27 2015, 美东)

我后来在面试官提示下,想到用leetcode上surrounded region那题的思路来解决2.从4
条edge出发dfs把ocean的0都变成2,(这一步需要考虑对角线),再扫描一遍2d array
把跟2相邻的1,也就是continent找出来dfs都变成3,剩下的1就是rank 2 island,剩
下的0就是lake。
【 在 datoug (datoug) 的大作中提到: 】
: 没明白。。 continent必须得是闭环?
: 能讲讲你的思路不?
: inside
: map.



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 75.]

 
Nerissa
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 8 ]

发信人: Nerissa (Nerissa), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Sun Aug  9 19:04:13 2015, 美东)

我一开始也是说从边开始找1来确定continent。但面试官给了个反例,比如下图,里面
那个1也是continent,因为外环右上角有个0。如果从边开始找1,就不能发现里面这个
1也是continent。所以应该根据1周围有没有ocean来判断。
000000000000
011111111101
010000000001
010010000001
010000000001
011111111111
【 在 lestrois (lestrois) 的大作中提到: 】
: 一起探讨一下思路,第一步其实就是从边开始把所有0以及相邻的0改变值成为2,从边
: 开始把1以及相邻的1改变值成为3,这样剩下的0和1就一定是lake和continent了,然后
: 故伎重演就行了。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 75.]

 
Nerissa
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 9 ]

发信人: Nerissa (Nerissa), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Sun Aug  9 19:08:44 2015, 美东)

对,你的思路对第1题应该可行,可是第二题divide and conquer这种思路就不行了吧
?一旦divide会影响对ocean的判断。
【 在 geekytrader (万物皆可易) 的大作中提到: 】
: 第三题应该可以divide and conquer
: (1)把矩阵分成小块读进内存,用DFS/BFS找number of islands,求一个全局的sum
:  (2) merge相邻小矩阵的edge(类似于 merge ranges),把减少的独立islands数从
sum
: 里减去
: inside
: map.



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 75.]

 
Nerissa
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 10 ]

发信人: Nerissa (Nerissa), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Sun Aug  9 19:11:36 2015, 美东)

可不可以解释下针对3怎么逐行做?染色法的dfs不是往4个方向走吗?
【 在 lestrois (lestrois) 的大作中提到: 】
: 我觉得染色法可以解2和3。第一步,先染ocean和non-continent islands,第二步,染
: continent islands,第三步染lakes,第四步找到rank 2 islands。这种方法可以针对
: 2bfs,也可以针对3逐行做。
: inside
: map.



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 75.]

 
lestrois
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 11 ]

发信人: lestrois (lestrois), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Sun Aug  9 19:15:46 2015, 美东)

我的方法可以找到中间的continent,我的第一步之后图会变成如下,2是ocean,3是
non-continent,剩下的1就是continent。
222222222222
233333333323
232222222223
232212222223
232222222223
233333333333

【 在 Nerissa (Nerissa) 的大作中提到: 】
: 我一开始也是说从边开始找1来确定continent。但面试官给了个反例,比如下图,里面
: 那个1也是continent,因为外环右上角有个0。如果从边开始找1,就不能发现里面这个
: 1也是continent。所以应该根据1周围有没有ocean来判断。
: 000000000000
: 011111111101
: 010000000001
: 010010000001
: 010000000001
: 011111111111



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 70.]

 
lestrois
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 12 ]

发信人: lestrois (lestrois), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Sun Aug  9 19:35:42 2015, 美东)

我没有写code,只是想法说一下:
逐行扫描,同行的相同元素染成一色(颜色数字用一个新的目前最大颜色数字+1表示)
,下一行扫描时根据上一行相同列进行染色。一旦发现与相邻格不同类的,则染新的颜
色(颜色+1)。到达边界的颜色数字最后会被记录在一个列表里,这些数字根据其原始颜
色来辨别其是Ocean,or Non-continent。

举例:
0000001000000000
0000001100000000
0000110011010000
0000100100110111
0000011011110000
0001111111110000
经逐行扫描染色法后变为:
2222223444444444
2222223344444444
2222556677484444
22225669AA884BBB
22222CCD88884444
222CCCC888884444

维护一个Hashmap,保存<New Color Int, Origin Color Int>
以上包括 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。而其余数字则是内部元素,需要进一步扫描判断。

【 在 Nerissa (Nerissa) 的大作中提到: 】
: 可不可以解释下针对3怎么逐行做?染色法的dfs不是往4个方向走吗?








--
※ 修改:·lestrois 於 Aug  9 19:51:28 2015 修改本文·[FROM: 70.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 70.]

 
f1371342385
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 13 ]

发信人: f1371342385 (阿Q), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Sun Aug  9 19:45:02 2015, 美东)

请问第三个怎么做?
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 216.]

 
mitqiuoffer
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 14 ]

发信人: mitqiuoffer (qiuoffer), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Mon Aug 10 02:19:31 2015, 美东)

confused, 3不是continent吗?为什么是non-continent?


【 在 lestrois (lestrois) 的大作中提到: 】
: 我没有写code,只是想法说一下:
: 逐行扫描,同行的相同元素染成一色(颜色数字用一个新的目前最大颜色数字+1表示)
: ,下一行扫描时根据上一行相同列进行染色。一旦发现与相邻格不同类的,则染新的颜
: 色(颜色+1)。到达边界的颜色数字最后会被记录在一个列表里,这些数字根据其原始颜
: 色来辨别其是Ocean,or Non-continent。
: 举例:
: 0000001000000000
: 0000001100000000
: 0000110011010000
: 0000100100110111
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 67.]

 
CR7
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 15 ]

发信人: CR7 (CR7), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Mon Aug 10 03:38:12 2015, 美东)

按楼主的意思这个最后的1应该是3吧,感觉楼主说的continent不是指湖中间的。所以
第二遍染色应该从ocean出发,把ocean相邻的1染成3
【 在 lestrois (lestrois) 的大作中提到: 】
: 我的方法可以找到中间的continent,我的第一步之后图会变成如下,2是ocean,3是
: non-continent,剩下的1就是continent。
: 222222222222
: 233333333323
: 232222222223
: 232212222223
: 232222222223
: 233333333333



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 68.]

 
CR7
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 16 ]

发信人: CR7 (CR7), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Mon Aug 10 03:54:35 2015, 美东)

考虑对角线是什么意思?
【 在 Nerissa (Nerissa) 的大作中提到: 】
: 我后来在面试官提示下,想到用leetcode上surrounded region那题的思路来解决2.
从4
: 条edge出发dfs把ocean的0都变成2,(这一步需要考虑对角线),再扫描一遍2d
array
: 把跟2相邻的1,也就是continent找出来dfs都变成3,剩下的1就是rank 2 island,剩
: 下的0就是lake。



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 68.]

 
lestrois
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 17 ]

发信人: lestrois (lestrois), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Mon Aug 10 06:32:44 2015, 美东)

根据定义,A continent is a piece of land located in the ocean。3不是in the
ocean,而是由边际延伸出的陆地。


【 在 mitqiuoffer (qiuoffer) 的大作中提到: 】
: confused, 3不是continent吗?为什么是non-continent?

--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 70.]

 
mrfast
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 18 ]

发信人: mrfast (mr.fast), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Mon Aug 10 16:16:01 2015, 美东)

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

【 在 Nerissa (Nerissa) 的大作中提到: 】
: 听起来像是欧洲人,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
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 134.]

 
kjbl
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 19 ]

发信人: kjbl (看家本领), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Mon Aug 10 19:01:18 2015, 美东)

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)

【 在 Nerissa (Nerissa) 的大作中提到: 】
: 听起来像是欧洲人,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
: ...................




--
※ 修改:·kjbl 於 Aug 10 19:04:47 2015 修改本文·[FROM: 216.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 216.]

 
Nerissa
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 20 ]

发信人: Nerissa (Nerissa), 信区: JobHunting
标  题: Re: Google电面
发信站: BBS 未名空间站 (Tue Aug 11 00:25:50 2015, 美东)

面试官说像下面这个例子,被1包围的两个0也是ocean,所以ocean可以通过对角线延伸
,dfs的时候要考虑对角线。
000000
111000
100110
111110

【 在 CR7 (CR7) 的大作中提到: 】
: 考虑对角线是什么意思?
: 从4
: array



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 54.]

[首页] [上页][下页][末页] [分页:1 2 ]
[快速返回] [ 进入待字闺中讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996