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