o********8 发帖数: 821 | 1 1.
Question: given a text file with 3 columns -- all integers:
id,parent,weight
each line is a node, 'parent' refers to 'id' of another node.
Print out, for each node, the total weight of a subtree below this node.
2. given a matrix of 0,1, find the max square with only 1s
剩下两个都比较容易,就不列出来了 |
r******3 发帖数: 221 | 2 第二题如果没见过leetcode的话,当场想还真有点难。 |
o********8 发帖数: 821 | 3 我当时就面挂了这题 :( 搞了三四十分钟没搞定。。。
还好其他三个答得还不错,最后侥幸过了。。。
【在 r******3 的大作中提到】 : 第二题如果没见过leetcode的话,当场想还真有点难。
|
r******3 发帖数: 221 | 4 不过店面4道题,加上第二题的难度,:-),楼主很强大阿。 |
B********t 发帖数: 147 | 5 第二题的时间复杂度要求是多少?
第一题是先扫完建树再traverse还是边扫边输出
【在 o********8 的大作中提到】 : 1. : Question: given a text file with 3 columns -- all integers: : id,parent,weight : each line is a node, 'parent' refers to 'id' of another node. : Print out, for each node, the total weight of a subtree below this node. : 2. given a matrix of 0,1, find the max square with only 1s : 剩下两个都比较容易,就不列出来了
|
r*********n 发帖数: 4553 | 6 第二题可以这么做:
相邻的的三个row, a, b, c。简单起见,把a,b,c都想想成integer。
对第二个row做变换: b = (a&b) | (b&c)
类似对每个row做变换(第一行的前一行和最后一行的后一行是全0)
类似再对所有col做变换
现在矩阵所有的1都属于某一个n>=2的正方形,后面就容易了
如果变换完以后是全零
如果原始矩阵有1,那么输出是1;否则是0 |
f*******t 发帖数: 7549 | 7 第二题求的是square?那没leetcode上的max rectangle难。
记得CC150上有这道题 |
r******3 发帖数: 221 | 8 square的就2维的DP题了,比leetcode上的简单很多。 |
r*********n 发帖数: 4553 | 9 你这么一提,我才想起我上面的方法同样适用于长方形(稍微改一下),复杂度是O(N^2)
【在 f*******t 的大作中提到】 : 第二题求的是square?那没leetcode上的max rectangle难。 : 记得CC150上有这道题
|
r******3 发帖数: 221 | 10 长方形的你做一下OJ就知道对不对,长方形的题最优解也达不到N^2.
^2)
【在 r*********n 的大作中提到】 : 你这么一提,我才想起我上面的方法同样适用于长方形(稍微改一下),复杂度是O(N^2)
|
|
|
j*******t 发帖数: 223 | 11 你是面试过了多久通知过了的啊?
我都半个月了没反应,多半备胎了。
【在 o********8 的大作中提到】 : 我当时就面挂了这题 :( 搞了三四十分钟没搞定。。。 : 还好其他三个答得还不错,最后侥幸过了。。。
|
c********t 发帖数: 5706 | 12 直接用visited矩阵扫一遍不行吗?DP怎么解?
【在 r******3 的大作中提到】 : square的就2维的DP题了,比leetcode上的简单很多。
|
G****A 发帖数: 4160 | 13 同感. 第一题虽然不难,但是要readfile + 建树 + print out + testing全弄完, 怎么
也20分钟了吧.
【在 r******3 的大作中提到】 : 不过店面4道题,加上第二题的难度,:-),楼主很强大阿。
|
r******3 发帖数: 221 | 14 你这个visited矩阵不也是extra memory吗?
anyways,如果是square那么这道题是经典的DP题,解法如下:
建立一个dp[row][col]矩阵,
for (int i = 0; i < array.length; ++i)
dp[i][0] = array[i][0];
for (int j = 0; j < array[0].length; ++j)
dp[0][j] = array[0][j];
for (int i = 1; i < array.length; ++i) {
for (int j = 1; j < array[0].length; ++j) {
if (array[i][j] == 0)
dp[i][j] = 0;
else {
dp[i][j] = Math.min(Math.min(dp[i-1][j-1], dp[i-1][j]), dp[i][j-1])
+ 1;
}
}
}
然后扫一遍dp矩阵找到最大值,时空复杂度都是N^2。
【在 c********t 的大作中提到】 : 直接用visited矩阵扫一遍不行吗?DP怎么解?
|
r******3 发帖数: 221 | 15 我没明白为什么第一题是建树,比如下面的input:
id parent weight
1 3 x
2 1 y
3 2 z
那么明显是个图啊,不是树啊,除非前提条件是子node不能做上层父node的parent。
【在 G****A 的大作中提到】 : 同感. 第一题虽然不难,但是要readfile + 建树 + print out + testing全弄完, 怎么 : 也20分钟了吧.
|
f*******t 发帖数: 7549 | 16 长方形用histogram解,是标准的N*M复杂度
【在 r******3 的大作中提到】 : 长方形的你做一下OJ就知道对不对,长方形的题最优解也达不到N^2. : : ^2)
|
r******3 发帖数: 221 | 17 好吧,我记起来了,你是对的。
但是面试的时候能给出这个答案的就..........
【在 f*******t 的大作中提到】 : 长方形用histogram解,是标准的N*M复杂度
|
c********t 发帖数: 5706 | 18 明白了,多谢!用histogram解的,绝对一看就是做过的。
【在 r******3 的大作中提到】 : 你这个visited矩阵不也是extra memory吗? : anyways,如果是square那么这道题是经典的DP题,解法如下: : 建立一个dp[row][col]矩阵, : for (int i = 0; i < array.length; ++i) : dp[i][0] = array[i][0]; : for (int j = 0; j < array[0].length; ++j) : dp[0][j] = array[0][j]; : for (int i = 1; i < array.length; ++i) { : for (int j = 1; j < array[0].length; ++j) { : if (array[i][j] == 0)
|
B********t 发帖数: 147 | 19 如果是rectangle也可以用DP吧。只不过要保存长方形的长和宽。
如果定义vector> > dp
转移方程: dp[i][j].first = min(dp[i-1][j].first, dp[i-1][j-1].first) + 1;
dp[i][j].second = min(dp[i][j-1].second, dp[i-1][j-1].second)
+ 1;
最大面积就是某个dp[k][l].fisrt * dp[k][l].second
另外150题上的那个是只要border是1就行了。。。。好像不能用dp了。。
【在 r******3 的大作中提到】 : 你这个visited矩阵不也是extra memory吗? : anyways,如果是square那么这道题是经典的DP题,解法如下: : 建立一个dp[row][col]矩阵, : for (int i = 0; i < array.length; ++i) : dp[i][0] = array[i][0]; : for (int j = 0; j < array[0].length; ++j) : dp[0][j] = array[0][j]; : for (int i = 1; i < array.length; ++i) { : for (int j = 1; j < array[0].length; ++j) { : if (array[i][j] == 0)
|
c********t 发帖数: 5706 | 20 这个复杂度也是O(N*M)吧?
second)
【在 B********t 的大作中提到】 : 如果是rectangle也可以用DP吧。只不过要保存长方形的长和宽。 : 如果定义vector> > dp : 转移方程: dp[i][j].first = min(dp[i-1][j].first, dp[i-1][j-1].first) + 1; : dp[i][j].second = min(dp[i][j-1].second, dp[i-1][j-1].second) : + 1; : 最大面积就是某个dp[k][l].fisrt * dp[k][l].second : 另外150题上的那个是只要border是1就行了。。。。好像不能用dp了。。
|
B********t 发帖数: 147 | 21 是的。。。 我是想说不管是square还是rectangle都是一样的。。
但是150题上是border 我感觉dp没法搞。我当时是brute force..整的
【在 c********t 的大作中提到】 : 这个复杂度也是O(N*M)吧? : : second)
|
r*********n 发帖数: 4553 | 22 http://stackoverflow.com/questions/2478447/find-largest-rectang
怎么达不到呢,这里就有一个N^2的(他的N是元素个数,我的N是dimension)
【在 r******3 的大作中提到】 : 长方形的你做一下OJ就知道对不对,长方形的题最优解也达不到N^2. : : ^2)
|