由买买提看人间百态

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 ladderFB 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