由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字 访问原贴
JobHunting版 - amazon电面跪了
相关主题
● 讨论一道面试题● Tree的traversal也分BFS和DFS？
● A家面经 (三轮电面）● FB Onsite新题，有人能看看吗？
● G intern电面面经● 隔壁讨论FB变态面试官，请教一下leetcode 301题怎么解最优？
● 贡献Amazon的电面经验● 要电面小印，CS QA, 求能考察真实水平的题目，算法，数据结构等
● 总结一下我的经历，回报版上。● 赞人品，也发Twitter 电面面经，又挂了！！(add Amazon 1st phone interview 面经)
● 一道G题● 好吧，RP总算小爆发了一次
● leetcode出了新题word ladder● 报个电面面经,估计没戏了
● G家面经总结，顺便求个bless，和一起找工作的同学们共勉● 帕兰提尔 电面面经
相关话题的讨论汇总
话题: col话题: shape话题: board话题: twos话题: count
进入JobHunting版参与讨论
1 (共1页)
s*********g
发帖数: 849
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***n
发帖数: 1594
2
DFS? 感觉这个最近考的很多？
l*****a
发帖数: 14598
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*********g
发帖数: 849
4
如果只需要说用DFS，不用写代码，我就过了。。。。
s*********g
发帖数: 849
5
一面电面，搞这种题我认跪了，反正也办不了GC，兴趣不大。自己找虐罢了。。

【在 l*****a 的大作中提到】
: A电面考这个算难题了吧
y***n
发帖数: 1594
6
是Kurmar 还是 Gupta 面的吗?
s*********g
发帖数: 849
7
红博
y***n
发帖数: 1594
8
不过少了一个模拟考的机会，也挺可惜的。
A作为高考前的模拟考试其实蛮好的。
M**a
发帖数: 848
9
没看懂。
s*********g
发帖数: 849
10
确实。面A的目的也就是这个。

【在 y***n 的大作中提到】
: 不过少了一个模拟考的机会，也挺可惜的。
: A作为高考前的模拟考试其实蛮好的。
相关主题
● 一道G题● Tree的traversal也分BFS和DFS？
● leetcode出了新题word ladder● FB Onsite新题，有人能看看吗？
● G家面经总结，顺便求个bless，和一起找工作的同学们共勉● 隔壁讨论FB变态面试官，请教一下leetcode 301题怎么解最优？
进入JobHunting版参与讨论
s*********g
发帖数: 849
11
横竖连起来的1

【在 M**a 的大作中提到】
: 没看懂。
a**********0
发帖数: 422
12
为什么切菜 给你加油助威还是威胁interviewer 你父亲新疆来的？
a**********0
发帖数: 422
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******s
发帖数: 84
14
搞siao~

【在 a**********0 的大作中提到】
: 为什么切菜 给你加油助威还是威胁interviewer 你父亲新疆来的？
a**********0
发帖数: 422
15
dfs类似 就是扫描matrix的每个点 如果是1 this.count就加一
然后dfs起得作用是label从这点延伸出去的同一个cluster的所有1都变成p 防止重复
dfs拓展需要考虑上下左右和是否是1 如果不是 也没有必要dfs下去了
但是如果是leetcode 可能dfs oj无法通过 不就是 surrounded 区域面积吗
当然最后破坏了数据结构
如果喜欢 可以再一次扫描 把P都变回来1
t**r
发帖数: 3428
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***n
发帖数: 1594
17
我写了一个C++ 的。
http://ideone.com/GE3w1N
一下子写对也不容易。
t**r
发帖数: 3428
18
nice solution

【在 y***n 的大作中提到】
: 我写了一个C++ 的。
: http://ideone.com/GE3w1N
: 一下子写对也不容易。
y***n
发帖数: 1594
19
其实就是求图有多少个Connected Components.
c*******y
发帖数: 98
20
看半天才看明白啥意思。。。shape count。。。说白了就是下围棋填满子以后算你有
几块棋被分断了。会画图里的填充算法就行了。弄个stack再弄个image temp buffer就
能做了。
相关主题
● 要电面小印，CS QA, 求能考察真实水平的题目，算法，数据结构等● 报个电面面经,估计没戏了
● 赞人品，也发Twitter 电面面经，又挂了！！(add Amazon 1st phone interview 面经)● 帕兰提尔 电面面经
● 好吧，RP总算小爆发了一次● 分享面试经历
进入JobHunting版参与讨论
s*********g
发帖数: 849
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***n
发帖数: 1594
22
DFS? 感觉这个最近考的很多？
s*********g
发帖数: 849
23
如果只需要说用DFS，不用写代码，我就过了。。。。
s*********g
发帖数: 849
24
一面电面，搞这种题我认跪了，反正也办不了GC，兴趣不大。自己找虐罢了。。

【在 l*****a 的大作中提到】
: A电面考这个算难题了吧
y***n
发帖数: 1594
25
是Kurmar 还是 Gupta 面的吗?
s*********g
发帖数: 849
26
红博
y***n
发帖数: 1594
27
不过少了一个模拟考的机会，也挺可惜的。
A作为高考前的模拟考试其实蛮好的。
M**a
发帖数: 848
28
没看懂。
s*********g
发帖数: 849
29
确实。面A的目的也就是这个。

【在 y***n 的大作中提到】
: 不过少了一个模拟考的机会，也挺可惜的。
: A作为高考前的模拟考试其实蛮好的。
s*********g
发帖数: 849
30
横竖连起来的1

【在 M**a 的大作中提到】
: 没看懂。
相关主题
● uber 电面面经● A家面经 (三轮电面）
● 报个Google电面面经● G intern电面面经
● 讨论一道面试题● 贡献Amazon的电面经验
进入JobHunting版参与讨论
a**********0
发帖数: 422
31
为什么切菜 给你加油助威还是威胁interviewer 你父亲新疆来的？
a**********0
发帖数: 422
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**********0
发帖数: 422
33
dfs类似 就是扫描matrix的每个点 如果是1 this.count就加一
然后dfs起得作用是label从这点延伸出去的同一个cluster的所有1都变成p 防止重复
dfs拓展需要考虑上下左右和是否是1 如果不是 也没有必要dfs下去了
但是如果是leetcode 可能dfs oj无法通过 不就是 surrounded 区域面积吗
当然最后破坏了数据结构
如果喜欢 可以再一次扫描 把P都变回来1
t**r
发帖数: 3428
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***n
发帖数: 1594
35
我写了一个C++ 的。
http://ideone.com/GE3w1N
一下子写对也不容易。
t**r
发帖数: 3428
36
nice solution

【在 y***n 的大作中提到】
: 我写了一个C++ 的。
: http://ideone.com/GE3w1N
: 一下子写对也不容易。
y***n
发帖数: 1594
37
其实就是求图有多少个Connected Components.
c*******y
发帖数: 98
38
看半天才看明白啥意思。。。shape count。。。说白了就是下围棋填满子以后算你有
几块棋被分断了。会画图里的填充算法就行了。弄个stack再弄个image temp buffer就
能做了。
n******n
发帖数: 602
39
这题我被面过。可以O（N）做出来。就是一行行扫描，基本思想就是count 有多少
disconnected shape, 如果发现两个Disconnected shape又连起来了，count --就好。

【在 c*******y 的大作中提到】
: 看半天才看明白啥意思。。。shape count。。。说白了就是下围棋填满子以后算你有
: 几块棋被分断了。会画图里的填充算法就行了。弄个stack再弄个image temp buffer就
: 能做了。
u****p
发帖数: 526
40
现在的电面题都这样了？
相关主题
● 贡献Amazon的电面经验● leetcode出了新题word ladder
● 总结一下我的经历，回报版上。● G家面经总结，顺便求个bless，和一起找工作的同学们共勉
● 一道G题● Tree的traversal也分BFS和DFS？
进入JobHunting版参与讨论
m******u
发帖数: 18
41
这题直接union find解吧。
u***n
发帖数: 21026
42
smart啊

【在 n******n 的大作中提到】
: 这题我被面过。可以O（N）做出来。就是一行行扫描，基本思想就是count 有多少
: disconnected shape, 如果发现两个Disconnected shape又连起来了，count --就好。
l****7
发帖数: 133
43
这题uf大才小用了
r*******y
发帖数: 270
44
这题目标是O(n) time, O(1)的space。如果写的DFS是O(n)space过不过也很难说
t**c
发帖数: 480
45
这道题dfs可以做到 ontime o1space
把遇到的X都变成O
每个点最多扫描一次
计算count
实际上速度很快，貌似比union find 快

【在 r*******y 的大作中提到】
: 这题目标是O(n) time, O(1)的space。如果写的DFS是O(n)space过不过也很难说
1 (共1页)
进入JobHunting版参与讨论
相关主题
● 帕兰提尔 电面面经● 总结一下我的经历，回报版上。
● 分享面试经历● 一道G题
● uber 电面面经● leetcode出了新题word ladder
● 报个Google电面面经● G家面经总结，顺便求个bless，和一起找工作的同学们共勉
● 讨论一道面试题● Tree的traversal也分BFS和DFS？
● A家面经 (三轮电面）● FB Onsite新题，有人能看看吗？
● G intern电面面经● 隔壁讨论FB变态面试官，请教一下leetcode 301题怎么解最优？
● 贡献Amazon的电面经验● 要电面小印，CS QA, 求能考察真实水平的题目，算法，数据结构等
相关话题的讨论汇总
话题: col话题: shape话题: board话题: twos话题: count

未名新帖统计// 7月16日

#版面帖数(主题数)
-全站4871 (796)
1Military3777 (569)
2Stock341 (51)
3Joke117 (17)
4History116 (3)
5Automobile100 (9)
6USANews55 (9)
7Midlife45 (1)
8Headline41 (41)
9Dreamer33 (13)
10FleaMarket32 (20)
11Living30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)

历史上的今天

  1. faintcat妹妹看进来～～ 发表于12年前.
  2. NSC, PD 1/7/2007, EB2, ... 发表于11年前.
  3. [FBA求购]MJVE2 758 MJVM2 ... 发表于6年前.
  4. 老生常谈,归与不归 发表于10年前.
  5. 【申请】Seattle西雅图 版版主——申请人... 发表于9年前.
  6. 宝宝出生，头骨骨折，求祝福 发表于9年前.
  7. 求推荐舒缓优美的古典音乐 发表于11年前.
  8. 百分之一的北京人上北大 中国网友愤怒(转载） 发表于10年前.
  9. 新人带狗狗Bailey来报道 发表于12年前.
  10. 全世界最有价值的运动队 发表于10年前.
  11. 请问大切诺基的质量如何 发表于6年前.
  12. TNND，军版全是BKC 发表于15年前.
  13. Inception 发表于12年前.
  14. 微软的有些家属可真恶心，为了卖保险脸都不要了 发表于10年前.
  15. 每周坐高铁的苦逼来说说感受吧!! 发表于9年前.
除非另有声明，本站内容采用Creative Commons BY-NC-SA 3.0协议进行许可，转载请注明来自未名观察 - 隐私政策2011-07-24 10:06:12由admin编辑