由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Amazon algorithm question, google
相关主题
leetcode中那道Set Matrix Zeroes怎么做Print out all elements in a sorted matrix
set matrix zero最少用多少space?请教 rotate the image
这两道题(CareerCup 150)的答案是不是有问题啊?狗家 onsite 求bless
请教CareerCup中的ROBOT MATRIX PATH那道题面试问题请教
求分析这题的时间复杂度careercup书上一个老题
question about MATLAB matrix squaring (转载)抛砖引玉:Careercup 150题中的错误
请教一道careercup 150上的题G题一道(2)
本版mj pdf合集matrix question
相关话题的讨论汇总
话题: matrix话题: row话题: amazon话题: 第一列话题: column
进入JobHunting版参与讨论
1 (共1页)
b********e
发帖数: 693
1
Given a NxN matrix with 0s and 1s. Now whenever you encounter a 0 make the
corresponding row and column elements 0.
Flip 1 to 0 and 0 remains as they are.
for example
1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
results in
0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0
my solution is define a function remove1(x1,y1,x2,y2)
(x1,y1) is the matrix start point, and (x2,y2) is the end point
if(i,j) == 1, we need remove all 1 from i row and j column
so we divide into four small matrix
resrucive
t****a
发帖数: 1212
2
I don't think you are right.
when you dive in some small matrix, find a 0, and start removing 1, you
might miss the 1 in another small matrix
b********e
发帖数: 693
3
you are the man:)
do you have any solution?

【在 t****a 的大作中提到】
: I don't think you are right.
: when you dive in some small matrix, find a 0, and start removing 1, you
: might miss the 1 in another small matrix

s****a
发帖数: 50
4
How about use 2 arrays row[] and col[](all initialized 1) to record whether
each row and column should contain 1? Just scan the matrix to and set row[i
] = 0 and col[j] = 0 when matrix[i][j] = 0. Then set each matrix[i][j] = row
[i]*col[j].
Complexity is O(n^2).

【在 b********e 的大作中提到】
: you are the man:)
: do you have any solution?

l******c
发帖数: 2555
5
this is a MSFT onsite question(I was asked), no extra space allowed
I don't know which tech company first asked this question, seems they copy the questions each other.

【在 b********e 的大作中提到】
: Given a NxN matrix with 0s and 1s. Now whenever you encounter a 0 make the
: corresponding row and column elements 0.
: Flip 1 to 0 and 0 remains as they are.
: for example
: 1 0 1 1 0
: 0 1 1 1 0
: 1 1 1 1 1
: 1 0 1 1 1
: 1 1 1 1 1
: results in

t*****j
发帖数: 1105
6
把matrix第一行和第一栏作为临时存储空间
对于每一row, 加到第一row(或者&&也行)。该函数变成
4 3 5 5 3
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
同理 对于第一列,则函数变成
20 3 5 5 3
3 1 1 1 0
5 1 1 1 1
4 0 1 1 1
5 1 1 1 1
扫描第一行及第一列(除A1,1以外),若不足n,则改行全部改0,否则改1.
20 0 1 1 0
3 0 1 1 0
5 0 1 1 0
4 0 1 1 0
5 0 1 1 0
把matrix第一行和第一栏作为临时存储空间
对于每一row, 加到第一row(或者&&也行)。该函数变成
4 3 5 5 3
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
同理 对于第一列,则函数变成
20 3 5 5 3
3 1 1 1 0
5 1 1 1 1
4 0 1 1 1
5 1 1 1 1
扫描第一行及第一列(除A1,1以外),若不足n,则该行全部改0,否则改此累计数字改
为1。
20 0 1 1 0
0 0 0 0 0
1 0

【在 b********e 的大作中提到】
: Given a NxN matrix with 0s and 1s. Now whenever you encounter a 0 make the
: corresponding row and column elements 0.
: Flip 1 to 0 and 0 remains as they are.
: for example
: 1 0 1 1 0
: 0 1 1 1 0
: 1 1 1 1 1
: 1 0 1 1 1
: 1 1 1 1 1
: results in

h**k
发帖数: 3368
7
对于A1,1 若第一行或者第一列其他数字有0,则第一行第一列全改为0.
你怎么做到这个的?既然你已经用第一行和第一列存了临时的和,原来的数据已经不在
了啊

【在 t*****j 的大作中提到】
: 把matrix第一行和第一栏作为临时存储空间
: 对于每一row, 加到第一row(或者&&也行)。该函数变成
: 4 3 5 5 3
: 0 1 1 1 0
: 1 1 1 1 1
: 1 0 1 1 1
: 1 1 1 1 1
: 同理 对于第一列,则函数变成
: 20 3 5 5 3
: 3 1 1 1 0

t*****j
发帖数: 1105
8
扫描第一行及第一列(除A1,1以外),若不足n,则该行全部改0,否则改此累计数字改
为1。
这句话是把非A11的累计数字位都改了。

【在 h**k 的大作中提到】
: 对于A1,1 若第一行或者第一列其他数字有0,则第一行第一列全改为0.
: 你怎么做到这个的?既然你已经用第一行和第一列存了临时的和,原来的数据已经不在
: 了啊

b*****n
发帖数: 221
9
CareerCup上的原题?
l******c
发帖数: 2555
10
CareerCup 没有给出正确答案

【在 b*****n 的大作中提到】
: CareerCup上的原题?
相关主题
question about MATLAB matrix squaring (转载)Print out all elements in a sorted matrix
请教一道careercup 150上的题请教 rotate the image
本版mj pdf合集狗家 onsite 求bless
进入JobHunting版参与讨论
a**********k
发帖数: 1953
11
I would use bit AND (&) operation (cumulatively).
time: O(n^2), space O(1).
b******y
发帖数: 126
12
1,按行扫描,如果遇到0,将该行所有1改成2,换到下一行
2,按列扫描,如果遇到0,将该列所有1改成2,换到下一列
3,扫描整个矩阵a[i][j]/=2;
time:O(mn), space 0
t*****j
发帖数: 1105
13
and 和 累加 其实一样,都行。

【在 a**********k 的大作中提到】
: I would use bit AND (&) operation (cumulatively).
: time: O(n^2), space O(1).

s***e
发帖数: 793
14
this is not space 0
because, if each element in the matrix is stored in a bit. how would this
work?

【在 b******y 的大作中提到】
: 1,按行扫描,如果遇到0,将该行所有1改成2,换到下一行
: 2,按列扫描,如果遇到0,将该列所有1改成2,换到下一列
: 3,扫描整个矩阵a[i][j]/=2;
: time:O(mn), space 0

s***e
发帖数: 793
15
you are assuming the element in the matrix is an integer instead of a
boolean, which is a strong assumption

【在 t*****j 的大作中提到】
: 把matrix第一行和第一栏作为临时存储空间
: 对于每一row, 加到第一row(或者&&也行)。该函数变成
: 4 3 5 5 3
: 0 1 1 1 0
: 1 1 1 1 1
: 1 0 1 1 1
: 1 1 1 1 1
: 同理 对于第一列,则函数变成
: 20 3 5 5 3
: 3 1 1 1 0

1 (共1页)
进入JobHunting版参与讨论
相关主题
matrix question求分析这题的时间复杂度
~~问两道AMAZON电面题question about MATLAB matrix squaring (转载)
One question on Careercup请教一道careercup 150上的题
发现了一个资料http直接下载的地方,另附找工作小经验!本版mj pdf合集
leetcode中那道Set Matrix Zeroes怎么做Print out all elements in a sorted matrix
set matrix zero最少用多少space?请教 rotate the image
这两道题(CareerCup 150)的答案是不是有问题啊?狗家 onsite 求bless
请教CareerCup中的ROBOT MATRIX PATH那道题面试问题请教
相关话题的讨论汇总
话题: matrix话题: row话题: amazon话题: 第一列话题: column