amazon电面跪了 - 未名空间MITBBS历史存档

s*g2014-06-20 07:06

1 楼

Given a 2d array, find the the shape count.就是有1的连续片段的数目。脑袋木了
， collabedit上写了一团乱麻。老爸在旁边切菜，别interviewer叫停了。。。
e.g 1
[
[101]
[010]
[111]
]
count = 3
e.g 2
[
[111]
[001]
[111]
]
count = 1
e.g 3
[
[111111111111]
[000000000001]
[111000000001]
[100000100001]
[100000000001]
[100000000001]
[111111111111]
]
count = 2

y*n2014-06-20 07:06

2 楼

DFS? 感觉这个最近考的很多？

l*a2014-06-20 07:06

3 楼

A电面考这个算难题了吧

【在 s*********g 的大作中提到】

: Given a 2d array, find the the shape count.就是有1的连续片段的数目。脑袋木了
: ， collabedit上写了一团乱麻。老爸在旁边切菜，别interviewer叫停了。。。
: e.g 1
: [
: [101]
: [010]
: [111]
: ]
: count = 3
: e.g 2

s*g2014-06-20 07:06

4 楼

如果只需要说用DFS，不用写代码，我就过了。。。。

s*g2014-06-20 07:06

5 楼

一面电面，搞这种题我认跪了，反正也办不了GC，兴趣不大。自己找虐罢了。。

【在 l*****a 的大作中提到】

: A电面考这个算难题了吧

y*n2014-06-20 07:06

6 楼

是Kurmar 还是 Gupta 面的吗?

s*g2014-06-20 07:06

7 楼

红博

y*n2014-06-20 07:06

8 楼

不过少了一个模拟考的机会，也挺可惜的。
A作为高考前的模拟考试其实蛮好的。

M*a2014-06-20 07:06

9 楼

没看懂。

s*g2014-06-20 07:06

10 楼

确实。面A的目的也就是这个。

【在 y***n 的大作中提到】

: 不过少了一个模拟考的机会，也挺可惜的。
: A作为高考前的模拟考试其实蛮好的。

s*g2014-06-20 07:06

11 楼

横竖连起来的1

【在 M**a 的大作中提到】

: 没看懂。

a*02014-06-20 07:06

12 楼

为什么切菜给你加油助威还是威胁interviewer 你父亲新疆来的？

a*02014-06-20 07:06

13 楼

为什么一定要用DFS 不是类似surrounded reigions 吗可以用 BFS
只不过要设一个variable用于记录cluster的数目
而且BFS过后的要label一下表示不能继续使用我试着贴一下代码
private void bfs(char[][] board, int i, int j) {

int row = board.length;
int col = board[0].length;
ArrayList queue = new ArrayList();

queue.add(i * col + j);
board[i][j] = 'P';

while (!queue.isEmpty()) {
int cur = queue.get(0);
queue.remove(0);
int x = cur / col;
int y = cur % col;

if (x-1 < 0 || x-1 >= row || y < 0 || y >= col || board[x-1][y] != '
1')
;
else{
queue.add((x-1) * col + y);
board[x-1][y] = 'P';
}

if (x+1 < 0 || x+1 >= row || y < 0 || y >= col || board[x+1][y] != '
1')
;
else{
queue.add((x+1) * col + y);
board[x+1][y] = 'P';
}

if (x < 0 || x >= row || y-1 < 0 || y-1 >= col || board[x][y-1] != '
1')
;
else{
queue.add((x) * col + y-1);
board[x][y-1] = 'P';
}

if (x < 0 || x >= row || y+1 < 0 || y+1 >= col || board[x][y+1] !=
'1')
;
else{ queue.add((x) * col + y+1);
board[x][y+1] = 'P';
}

}
this. count ++ // for the result
}

然后扫描每个点of the board 如果是1 就调用bfs函数访问过的1就变成P了这
样就不会重复计数了
count是 class的一个field

s*s2014-06-20 07:06

14 楼

搞siao~

【在 a**********0 的大作中提到】

: 为什么切菜给你加油助威还是威胁interviewer 你父亲新疆来的？

a*02014-06-20 07:06

15 楼

dfs类似就是扫描matrix的每个点如果是1 this.count就加一
然后dfs起得作用是label从这点延伸出去的同一个cluster的所有1都变成p 防止重复
dfs拓展需要考虑上下左右和是否是1 如果不是也没有必要dfs下去了
但是如果是leetcode 可能dfs oj无法通过不就是 surrounded 区域面积吗
当然最后破坏了数据结构
如果喜欢可以再一次扫描把P都变回来1

t*r2014-06-20 07:06

16 楼

# In this solution as soon as we find a 1, we replace
# all the elements in the shape with 2 to avoid double
# counting the 1s. Otherwise, it's simple iteration.
def count_shapes(m):
num_shapes = 0
for r in range(len(m)):
for c in range(len(m[0])):
if m[r][c] == 1:
fill_shape_with_twos(m, r, c)
num_shapes += 1
# restore the original values
for r in range(len(m)):
for c in range(len(m[0])):
m[r][c] = m[r][c] / 2
return num_shapes
def fill_shape_with_twos(m, r, c):
m[r][c] = 2
if r > 0 and m[r-1][c] == 1:
fill_shape_with_twos(m, r-1, c)
if r + 1 < len(m) and m[r+1][c] == 1:
fill_shape_with_twos(m, r+1, c)
if c > 0 and m[r][c-1] == 1:
fill_shape_with_twos(m, r, c-1)
if c + 1 < len(m[0]) and m[r][c+1] == 1:
fill_shape_with_twos(m, r, c+1)

y*n2014-06-20 07:06

17 楼

我写了一个C++ 的。
http://ideone.com/GE3w1N
一下子写对也不容易。

t*r2014-06-20 07:06

18 楼

nice solution

【在 y***n 的大作中提到】

: 我写了一个C++ 的。
: http://ideone.com/GE3w1N
: 一下子写对也不容易。

y*n2014-06-20 07:06

19 楼

其实就是求图有多少个Connected Components.

c*y2014-06-20 07:06

20 楼

看半天才看明白啥意思。。。shape count。。。说白了就是下围棋填满子以后算你有
几块棋被分断了。会画图里的填充算法就行了。弄个stack再弄个image temp buffer就
能做了。

s*g2014-06-20 07:06

21 楼

Given a 2d array, find the the shape count.就是有1的连续片段的数目。脑袋木了
， collabedit上写了一团乱麻。老爸在旁边切菜，别interviewer叫停了。。。
e.g 1
[
[101]
[010]
[111]
]
count = 3
e.g 2
[
[111]
[001]
[111]
]
count = 1
e.g 3
[
[111111111111]
[000000000001]
[111000000001]
[100000100001]
[100000000001]
[100000000001]
[111111111111]
]
count = 2

y*n2014-06-20 07:06

22 楼

DFS? 感觉这个最近考的很多？

s*g2014-06-20 07:06

23 楼

如果只需要说用DFS，不用写代码，我就过了。。。。

s*g2014-06-20 07:06

24 楼

一面电面，搞这种题我认跪了，反正也办不了GC，兴趣不大。自己找虐罢了。。

【在 l*****a 的大作中提到】

: A电面考这个算难题了吧

y*n2014-06-20 07:06

25 楼

是Kurmar 还是 Gupta 面的吗?

s*g2014-06-20 07:06

26 楼

红博

y*n2014-06-20 07:06

27 楼

不过少了一个模拟考的机会，也挺可惜的。
A作为高考前的模拟考试其实蛮好的。

M*a2014-06-20 07:06

28 楼

没看懂。

s*g2014-06-20 07:06

29 楼

确实。面A的目的也就是这个。

【在 y***n 的大作中提到】

: 不过少了一个模拟考的机会，也挺可惜的。
: A作为高考前的模拟考试其实蛮好的。

s*g2014-06-20 07:06

30 楼

横竖连起来的1

【在 M**a 的大作中提到】

: 没看懂。

a*02014-06-20 07:06

31 楼

为什么切菜给你加油助威还是威胁interviewer 你父亲新疆来的？

a*02014-06-20 07:06

32 楼

为什么一定要用DFS 不是类似surrounded reigions 吗可以用 BFS
只不过要设一个variable用于记录cluster的数目
而且BFS过后的要label一下表示不能继续使用我试着贴一下代码
private void bfs(char[][] board, int i, int j) {

int row = board.length;
int col = board[0].length;
ArrayList queue = new ArrayList();

queue.add(i * col + j);
board[i][j] = 'P';

while (!queue.isEmpty()) {
int cur = queue.get(0);
queue.remove(0);
int x = cur / col;
int y = cur % col;

if (x-1 < 0 || x-1 >= row || y < 0 || y >= col || board[x-1][y] != '
1')
;
else{
queue.add((x-1) * col + y);
board[x-1][y] = 'P';
}

if (x+1 < 0 || x+1 >= row || y < 0 || y >= col || board[x+1][y] != '
1')
;
else{
queue.add((x+1) * col + y);
board[x+1][y] = 'P';
}

if (x < 0 || x >= row || y-1 < 0 || y-1 >= col || board[x][y-1] != '
1')
;
else{
queue.add((x) * col + y-1);
board[x][y-1] = 'P';
}

if (x < 0 || x >= row || y+1 < 0 || y+1 >= col || board[x][y+1] !=
'1')
;
else{ queue.add((x) * col + y+1);
board[x][y+1] = 'P';
}

}
this. count ++ // for the result
}

然后扫描每个点of the board 如果是1 就调用bfs函数访问过的1就变成P了这
样就不会重复计数了
count是 class的一个field

a*02014-06-20 07:06

33 楼

dfs类似就是扫描matrix的每个点如果是1 this.count就加一
然后dfs起得作用是label从这点延伸出去的同一个cluster的所有1都变成p 防止重复
dfs拓展需要考虑上下左右和是否是1 如果不是也没有必要dfs下去了
但是如果是leetcode 可能dfs oj无法通过不就是 surrounded 区域面积吗
当然最后破坏了数据结构
如果喜欢可以再一次扫描把P都变回来1

t*r2014-06-20 07:06

34 楼

# In this solution as soon as we find a 1, we replace
# all the elements in the shape with 2 to avoid double
# counting the 1s. Otherwise, it's simple iteration.
def count_shapes(m):
num_shapes = 0
for r in range(len(m)):
for c in range(len(m[0])):
if m[r][c] == 1:
fill_shape_with_twos(m, r, c)
num_shapes += 1
# restore the original values
for r in range(len(m)):
for c in range(len(m[0])):
m[r][c] = m[r][c] / 2
return num_shapes
def fill_shape_with_twos(m, r, c):
m[r][c] = 2
if r > 0 and m[r-1][c] == 1:
fill_shape_with_twos(m, r-1, c)
if r + 1 < len(m) and m[r+1][c] == 1:
fill_shape_with_twos(m, r+1, c)
if c > 0 and m[r][c-1] == 1:
fill_shape_with_twos(m, r, c-1)
if c + 1 < len(m[0]) and m[r][c+1] == 1:
fill_shape_with_twos(m, r, c+1)

y*n2014-06-20 07:06

35 楼

我写了一个C++ 的。
http://ideone.com/GE3w1N
一下子写对也不容易。

t*r2014-06-20 07:06

36 楼

nice solution

【在 y***n 的大作中提到】

: 我写了一个C++ 的。
: http://ideone.com/GE3w1N
: 一下子写对也不容易。

y*n2014-06-20 07:06

37 楼

其实就是求图有多少个Connected Components.

c*y2014-06-20 07:06

38 楼

看半天才看明白啥意思。。。shape count。。。说白了就是下围棋填满子以后算你有
几块棋被分断了。会画图里的填充算法就行了。弄个stack再弄个image temp buffer就
能做了。

n*n2014-06-20 07:06

39 楼

这题我被面过。可以O（N）做出来。就是一行行扫描，基本思想就是count 有多少
disconnected shape, 如果发现两个Disconnected shape又连起来了，count --就好。

【在 c*******y 的大作中提到】

: 看半天才看明白啥意思。。。shape count。。。说白了就是下围棋填满子以后算你有
: 几块棋被分断了。会画图里的填充算法就行了。弄个stack再弄个image temp buffer就
: 能做了。

u*p2014-06-20 07:06

40 楼

现在的电面题都这样了？

m*u2014-06-20 07:06

41 楼

这题直接union find解吧。

u*n2014-06-20 07:06

42 楼

smart啊

【在 n******n 的大作中提到】

: 这题我被面过。可以O（N）做出来。就是一行行扫描，基本思想就是count 有多少
: disconnected shape, 如果发现两个Disconnected shape又连起来了，count --就好。

l*72014-06-20 07:06

43 楼

这题uf大才小用了

r*y2014-06-20 07:06

44 楼

这题目标是O(n) time, O(1)的space。如果写的DFS是O(n)space过不过也很难说

t*c2014-06-20 07:06

45 楼

这道题dfs可以做到 ontime o1space
把遇到的X都变成O
每个点最多扫描一次
计算count
实际上速度很快，貌似比union find 快

【在 r*******y 的大作中提到】

: 这题目标是O(n) time, O(1)的space。如果写的DFS是O(n)space过不过也很难说