g********r
发帖数: 58 | 1 去年面的， 就一道题，上来直接问，直到结束，共45分钟。一周后得到的结果，fail
了。
题目说 围棋， 输入出任意 一个 棋盘位置， 判断是否那个位置的棋子处于被包围状
态-上下左右都是不同颜色地棋子。被包围的有可能是相同颜色地一组棋子，只要给定
位置属于那个组 也返回true.
比如 (.代表没有棋子，B代表黑，W代表白)
..B..
.BWB.
.BWB.
..B..
上来先说思路：先找出 与给定位置的棋子 相同的颜色的组。然后再判断棋子是否被黑
的包围，说着说着 意识到 只要在找组的过程中 判断是否每个相同颜色地棋子是否有
上下左右的邻居为空即可。对方表示同意 （大概说了不到5分钟）
然后就coding， 用的是BFS + stack, 边写边解释，一切也顺利。 也主动考虑了边界
条件。 不用写code地过程中忘了做duplication check,就是标出visited的位置。经过
间接提醒，让跑了个test case，发现这个问题，改了过来。 然后就是没有考虑到如果
给定位置为空的情况。对方提醒了第几行code有问题 我就意识到了。
整个过程 大家都很愉快 交流没有任何问题。对方也表现地很positive，说HR会联系你.
然后就收到拒信。 很想问问大牛 过g的phone interview 都是什么情况？都是没有任
何错误吗？我是很客观地再现了我当时的情况，fail了之后 很意外，（没有太难过，
都习惯了：））只是没有找到失败地原因。希望大家给点意见，以便我以后提高。也给
大家做个反面地例子：） |
w****a
发帖数: 710 | 2 我感觉还可以啊。给的反馈都positive，都不让过店面。
我现在开始担心我的店面了。。还没有消息 |
M********5
发帖数: 715 | 3 我也遇见过好些面的时候很positive的面试，最后莫名其妙地给fail掉了。。。都不知
道fail人的point在哪里。。。 |
j*****y
发帖数: 1071 | 4 bless
.BB..
B.WB.
B.WB.
.BWB.
..B..
这种情况算被围住了吗？
fail
【在 g********r 的大作中提到】
: 去年面的， 就一道题，上来直接问，直到结束，共45分钟。一周后得到的结果，fail
: 了。
: 题目说 围棋， 输入出任意 一个 棋盘位置， 判断是否那个位置的棋子处于被包围状
: 态-上下左右都是不同颜色地棋子。被包围的有可能是相同颜色地一组棋子，只要给定
: 位置属于那个组 也返回true.
: 比如 (.代表没有棋子，B代表黑，W代表白)
: ..B..
: .BWB.
: .BWB.
: ..B..
|
r*******h
发帖数: 315 | 5 我猜你被指出第几行有问题，这个可能是negative。因为我的经历也是很多情况没考虑
到，但幸运的是，当面试官好几次提出异议（其中一次也是用一个test case）时，每
次我都意识到可能的错误，就立即改过来了，最后也pass了。 |
M********5
发帖数: 715 | 6 可是觉得改过来了的话pass不pass那不完全就是面试官说了算了。。。哎
【在 r*******h 的大作中提到】
: 我猜你被指出第几行有问题，这个可能是negative。因为我的经历也是很多情况没考虑
: 到，但幸运的是，当面试官好几次提出异议（其中一次也是用一个test case）时，每
: 次我都意识到可能的错误，就立即改过来了，最后也pass了。
|
g********r
发帖数: 58 | 7 恩 good point, 这种情况我没有考虑到。我觉得虽然interviewer没有提出来 这很有
可能是个原因。
【在 j*****y 的大作中提到】
: bless
: .BB..
: B.WB.
: B.WB.
: .BWB.
: ..B..
: 这种情况算被围住了吗？
:
: fail
|
j*****y
发帖数: 1071 | 8 如果这个也算被围住的话，感觉很难阿
恩 good point, 这种情况我没有考虑到。我觉得虽然interviewer没有提出来 这很有
可能是个原因。
【在 g********r 的大作中提到】
: 恩 good point, 这种情况我没有考虑到。我觉得虽然interviewer没有提出来 这很有
: 可能是个原因。
|
e***s
发帖数: 799 | 9 我感觉是不是面试官只是收集你的答案，code还是会给几个人review的？ |
f*****e
发帖数: 2992 | 10 用DFS可能会好些。
【在 g********r 的大作中提到】
: 恩 good point, 这种情况我没有考虑到。我觉得虽然interviewer没有提出来 这很有
: 可能是个原因。
|
|
|
g********r
发帖数: 58 | 11 应该不会吧。我还没有听说这种phone interview的。即使是这样，code也没什么问题
，毕竟是和面试官一起过了一遍的。
【在 e***s 的大作中提到】
: 我感觉是不是面试官只是收集你的答案，code还是会给几个人review的？
|
w****a
发帖数: 710 | 12 我也觉得有这种可能。
【在 e***s 的大作中提到】
: 我感觉是不是面试官只是收集你的答案，code还是会给几个人review的？
|
g********r
发帖数: 58 | 13 是，这样的话 可能就不适合面试了。 估计interviewer也没这意思。
不过要是指出这种情况 是个plus.
【在 j*****y 的大作中提到】
: 如果这个也算被围住的话，感觉很难阿
:
: 恩 good point, 这种情况我没有考虑到。我觉得虽然interviewer没有提出来 这很有
: 可能是个原因。
|
g********r
发帖数: 58 | 14 有这种可能，不过能考虑到所有case 然后 一次bug free的 真的很难。
【在 r*******h 的大作中提到】
: 我猜你被指出第几行有问题，这个可能是negative。因为我的经历也是很多情况没考虑
: 到，但幸运的是，当面试官好几次提出异议（其中一次也是用一个test case）时，每
: 次我都意识到可能的错误，就立即改过来了，最后也pass了。
|
y****n
发帖数: 743 | 15 首先要定义，什么叫“围”。
如果“回”字，中间有空，算不算被围？
感觉这道题考得是画图的填充算法。
fail
【在 g********r 的大作中提到】
: 去年面的， 就一道题，上来直接问，直到结束，共45分钟。一周后得到的结果，fail
: 了。
: 题目说 围棋， 输入出任意 一个 棋盘位置， 判断是否那个位置的棋子处于被包围状
: 态-上下左右都是不同颜色地棋子。被包围的有可能是相同颜色地一组棋子，只要给定
: 位置属于那个组 也返回true.
: 比如 (.代表没有棋子，B代表黑，W代表白)
: ..B..
: .BWB.
: .BWB.
: ..B..
|
g******z
发帖数: 893 | 16 如果这种情况的话，能不能BFS+queue
把周围的同色棋子和空格用queue保存下来
如果queue空之前到达棋盘边界就没有被围，不然就是被围了？
【在 g********r 的大作中提到】
: 是，这样的话 可能就不适合面试了。 估计interviewer也没这意思。
: 不过要是指出这种情况 是个plus.
|
g********r
发帖数: 58 | 17 我觉得你是对了，我又看了一遍原题， 应该是不需要考虑有空的情况。
问一下， 画图的填充算法 有没有什么更好的solution？
【在 y****n 的大作中提到】
: 首先要定义，什么叫“围”。
: 如果“回”字，中间有空，算不算被围？
: 感觉这道题考得是画图的填充算法。
:
: fail
|
i*****e
发帖数: 63 | |
p*****2
发帖数: 21240 | 19 这题为什么难呀？
感觉bfs/dfs找到边界就返回false就可以了吧？难点在哪里？ |
h*u
发帖数: 122 | |
|
|
p*****2
发帖数: 21240 | 21 val m=5
val n=5
val board=Array(".BB..","B.WB.","B.WB.",".BWB.","..B..")
val visited=Array.ofDim[Boolean](m,n)
println(dfs(1,2))
def dfs(i:Int, j:Int):Boolean={
if(i<0 || i>=n || j<0 || j>=n) return true
if(board(i)(j)=='B' || visited(i)(j)) return false
visited(i)(j)=true
if(dfs(i-1,j)) return true
if(dfs(i+1,j)) return true
if(dfs(i,j-1)) return true
if(dfs(i,j+1)) return true
false
} |
e******o
发帖数: 757 | 22 厉害，我用BFS写了一大托
【在 p*****2 的大作中提到】
: val m=5
: val n=5
: val board=Array(".BB..","B.WB.","B.WB.",".BWB.","..B..")
: val visited=Array.ofDim[Boolean](m,n)
:
: println(dfs(1,2))
:
: def dfs(i:Int, j:Int):Boolean={
: if(i<0 || i>=n || j<0 || j>=n) return true
: if(board(i)(j)=='B' || visited(i)(j)) return false
|
g********r
发帖数: 58 | 23 思路和2爷的差不多。只不过没用递归。
可能题目太简单了，所以 coding 要求比较高。
【在 p*****2 的大作中提到】
: val m=5
: val n=5
: val board=Array(".BB..","B.WB.","B.WB.",".BWB.","..B..")
: val visited=Array.ofDim[Boolean](m,n)
:
: println(dfs(1,2))
:
: def dfs(i:Int, j:Int):Boolean={
: if(i<0 || i>=n || j<0 || j>=n) return true
: if(board(i)(j)=='B' || visited(i)(j)) return false
|
d**********x
发帖数: 4083 | 24 首先。。BFS and what?
其次。。因为这题很简单。。没做visited标记说不过去吧。。
fail
【在 g********r 的大作中提到】
: 去年面的， 就一道题，上来直接问，直到结束，共45分钟。一周后得到的结果，fail
: 了。
: 题目说 围棋， 输入出任意 一个 棋盘位置， 判断是否那个位置的棋子处于被包围状
: 态-上下左右都是不同颜色地棋子。被包围的有可能是相同颜色地一组棋子，只要给定
: 位置属于那个组 也返回true.
: 比如 (.代表没有棋子，B代表黑，W代表白)
: ..B..
: .BWB.
: .BWB.
: ..B..
|
r********9
发帖数: 1116 | 25 BFS+stack? 不是应该BFS+queue吗？
这道题不难，但如果置换成计算一块棋是否被包围，被包围了判断是死是活的话，好像
很难了。
关键是怎么区分内空和外空？
fail
【在 g********r 的大作中提到】
: 去年面的， 就一道题，上来直接问，直到结束，共45分钟。一周后得到的结果，fail
: 了。
: 题目说 围棋， 输入出任意 一个 棋盘位置， 判断是否那个位置的棋子处于被包围状
: 态-上下左右都是不同颜色地棋子。被包围的有可能是相同颜色地一组棋子，只要给定
: 位置属于那个组 也返回true.
: 比如 (.代表没有棋子，B代表黑，W代表白)
: ..B..
: .BWB.
: .BWB.
: ..B..
|
a******e
发帖数: 710 | 26 看不太懂，能注释一下么?
【在 p*****2 的大作中提到】
: val m=5
: val n=5
: val board=Array(".BB..","B.WB.","B.WB.",".BWB.","..B..")
: val visited=Array.ofDim[Boolean](m,n)
:
: println(dfs(1,2))
:
: def dfs(i:Int, j:Int):Boolean={
: if(i<0 || i>=n || j<0 || j>=n) return true
: if(board(i)(j)=='B' || visited(i)(j)) return false
|
h*****u
发帖数: 120 | 27 你强但是有人比你更强，就这样
fail
【在 g********r 的大作中提到】
: 去年面的， 就一道题，上来直接问，直到结束，共45分钟。一周后得到的结果，fail
: 了。
: 题目说 围棋， 输入出任意 一个 棋盘位置， 判断是否那个位置的棋子处于被包围状
: 态-上下左右都是不同颜色地棋子。被包围的有可能是相同颜色地一组棋子，只要给定
: 位置属于那个组 也返回true.
: 比如 (.代表没有棋子，B代表黑，W代表白)
: ..B..
: .BWB.
: .BWB.
: ..B..
|
j***a
发帖数: 832 | 28 is this interview for recent graduates?
I doubt if they will give those interview question for a 40 year old
architecturer
fail
【在 g********r 的大作中提到】
: 去年面的， 就一道题，上来直接问，直到结束，共45分钟。一周后得到的结果，fail
: 了。
: 题目说 围棋， 输入出任意 一个 棋盘位置， 判断是否那个位置的棋子处于被包围状
: 态-上下左右都是不同颜色地棋子。被包围的有可能是相同颜色地一组棋子，只要给定
: 位置属于那个组 也返回true.
: 比如 (.代表没有棋子，B代表黑，W代表白)
: ..B..
: .BWB.
: .BWB.
: ..B..
|
C***Y
发帖数: 1323 | 29
fail
真的是问围棋里包围定义吗？那会下围棋的不是沾光了？除了回字的case楼主没有考虑
到以外，如果是在角上，最少两个白子就可包围一黑子。在边上最少三个白子就可包围
一黑子，因为利用了border。
【在 g********r 的大作中提到】
: 去年面的， 就一道题，上来直接问，直到结束，共45分钟。一周后得到的结果，fail
: 了。
: 题目说 围棋， 输入出任意 一个 棋盘位置， 判断是否那个位置的棋子处于被包围状
: 态-上下左右都是不同颜色地棋子。被包围的有可能是相同颜色地一组棋子，只要给定
: 位置属于那个组 也返回true.
: 比如 (.代表没有棋子，B代表黑，W代表白)
: ..B..
: .BWB.
: .BWB.
: ..B..
|
p*g
发帖数: 141 | 30 这个思路是对的, 但是逻辑不对吧
应该是: 只要有一个地方是空的, 这一块棋就是活的
if ( out of boundary || B || visited ) return false
if ( empty ) return true
for ( 4 neighbours )
if ( dfs(neighbour) ) return true
return false
【在 p*****2 的大作中提到】
: val m=5
: val n=5
: val board=Array(".BB..","B.WB.","B.WB.",".BWB.","..B..")
: val visited=Array.ofDim[Boolean](m,n)
:
: println(dfs(1,2))
:
: def dfs(i:Int, j:Int):Boolean={
: if(i<0 || i>=n || j<0 || j>=n) return true
: if(board(i)(j)=='B' || visited(i)(j)) return false
|
|
|
m*******8
发帖数: 183 | |
d******e
发帖数: 117 | 32 写得不对吧。假设一个白子被4个黑子包围，这个算法不能return true
if(board(i)(j)=='.' || visited(i)(j)) return false
【在 p*****2 的大作中提到】
: val m=5
: val n=5
: val board=Array(".BB..","B.WB.","B.WB.",".BWB.","..B..")
: val visited=Array.ofDim[Boolean](m,n)
:
: println(dfs(1,2))
:
: def dfs(i:Int, j:Int):Boolean={
: if(i<0 || i>=n || j<0 || j>=n) return true
: if(board(i)(j)=='B' || visited(i)(j)) return false
|
p*****2
发帖数: 21240 | 33
我算的是活。
【在 d******e 的大作中提到】
: 写得不对吧。假设一个白子被4个黑子包围，这个算法不能return true
: if(board(i)(j)=='.' || visited(i)(j)) return false
|
g*********n
发帖数: 43 | 34 出了边界return true? 如果一个白字在边界被三个黑子围住， 应该算dead吧
: if(i<0 || i>=n || j<0 || j>=n) return true
【在 p*****2 的大作中提到】
:
: 我算的是活。
|
p*****2
发帖数: 21240 | 35
判断是否那个位置的棋子处于被包围状
态-上下左右都是不同颜色地棋子。
【在 g*********n 的大作中提到】
: 出了边界return true? 如果一个白字在边界被三个黑子围住， 应该算dead吧
: : if(i<0 || i>=n || j<0 || j>=n) return true
|
l*****a
发帖数: 14598 | 36 这题镇无聊
北美围棋大赛即将开幕，是骡子是马出来六六
http://www.mitbbs.com/article_t/Go/31229309.html
fail
【在 g********r 的大作中提到】
: 去年面的， 就一道题，上来直接问，直到结束，共45分钟。一周后得到的结果，fail
: 了。
: 题目说 围棋， 输入出任意 一个 棋盘位置， 判断是否那个位置的棋子处于被包围状
: 态-上下左右都是不同颜色地棋子。被包围的有可能是相同颜色地一组棋子，只要给定
: 位置属于那个组 也返回true.
: 比如 (.代表没有棋子，B代表黑，W代表白)
: ..B..
: .BWB.
: .BWB.
: ..B..
|
a******e
发帖数: 710 | 37 gladsomeman 说的这种情况用二爷的方法会返回true吧？
【在 p*****2 的大作中提到】
:
: 判断是否那个位置的棋子处于被包围状
: 态-上下左右都是不同颜色地棋子。
|
