贡献几道题目 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

贡献几道题目

贡献几道题目# JobHunting - 待字闺中

g*j2012-12-01 08:12

1 楼

1 给你一堆interval，然后给定一个interval，如果这个interval和其他三个以下的
interval有concurrent的overlap，则返回true，否则返回false
比如
已有 1－3， 4－5， 6-8，9-10，给定1 －10，返回true，因为1-10只跟其中任
意一个有overlap，concurrent的overlap最多才2个
已有 1 －6 3- 7 2－8 给定 4-6，返回false，因为来三个都跟4-6有
overlap 5-6
2 给定一个0和1的矩阵，返回连成一片的1的block的个数，只考虑前后左右四个
neighbor。
0 1 0 0 1 0 0
0 1 1 0 1 0 0
0 1 1 0 1 0 0
0 0 0 0 0 0 0 返回2

如果这个矩阵足够大，一个机器处理不了，怎么半？

b*m2012-12-01 08:12

2 楼

第二题我在A家onsite也被考到。

g*j2012-12-01 08:12

3 楼

what's your solution?

【在 b***m 的大作中提到】

: 第二题我在A家onsite也被考到。

b*m2012-12-01 08:12

4 楼

不考虑大scale，从左上角开始扫描，扫描到第一个1，做DFS扫描，每扫描到一个1就置
0，直到不能再扫描位置，计数器加1。然后从这个位置继续往后走，找到下一个1，继
续DFS……基本没有别的更好的方法了。如果是大scale，只能根据内存大小对数据做分
割，每块单独计算，然后统一做边界扫描，合并毗邻的块。

【在 g***j 的大作中提到】

: what's your solution?

f*e2012-12-01 08:12

5 楼

先一行一行的扫，把连续的1片段标号并且记录下来1,2,3,...
然后再一列一列的扫，就看哪些标号是equivalent的。
比如
0000
0110
0111
0001
0111
0000
先扫行:
0000
0110
0222
0003
0444
0000
再扫列
扫第二列发现1=2(1 and 2 is equivalent)
扫第4列，发现2=3=4，所以只有一个component。可以很容易的拓展到分割算法。

【在 b***m 的大作中提到】

:
: 不考虑大scale，从左上角开始扫描，扫描到第一个1，做DFS扫描，每扫描到一个1就置
: 0，直到不能再扫描位置，计数器加1。然后从这个位置继续往后走，找到下一个1，继
: 续DFS……基本没有别的更好的方法了。如果是大scale，只能根据内存大小对数据做分
: 割，每块单独计算，然后统一做边界扫描，合并毗邻的块。

l*o2012-12-01 08:12

6 楼

如果考虑scale
比如
0 0 0 0
1 1 0 1
1 1 1 1
0 0 0 0
要分成
两个
0 0 0 0
1 1 0 1
1 1 1 1
0 0 0 0
那么我们要对每一个拆分出去的matrix加一列表示来自0还是来自1
比如
0 0 0
1 0 1
1 1 1
0 0 0
对于这个矩阵,先搜最左一列. 所有来自于1的,我们只做dfs mark为false,表示搜过.
但结果并不+1. 同理扩展到N个拆分矩阵.

b*e2012-12-01 08:12

7 楼

没必要做DFS。只要两行两行的扫描染色:
- 下行的颜色根据上行的颜色定。
- 上下两行有重叠的段下行段就染就和上行段染相同的颜色。如果下行某段和上行多
段相重
叠，则多色归一。
- 下面一行如果有一段没有和上行有任何重叠则下行此段新起一种颜色。
- 下行染完色后，如果发现上行的某个颜色消失了，就output一个连续块。
这个问题每次看两行就行了。而且不用多看，look_ahead(1)就可以了。

【在 b***m 的大作中提到】

e*e2012-12-01 08:12

8 楼

New approach, but doesn't work on the case in Original Post.

【在 f*****e 的大作中提到】

: 先一行一行的扫，把连续的1片段标号并且记录下来1,2,3,...
: 然后再一列一列的扫，就看哪些标号是equivalent的。
: 比如
: 0000
: 0110
: 0111
: 0001
: 0111
: 0000
: 先扫行:

h*u2012-12-01 08:12

9 楼

mark~

l*a2012-12-01 08:12

10 楼

第二题的block需要是正方形吗？还是长方形也可以？

g*j2012-12-01 08:12

11 楼

随便形状

【在 l*****a 的大作中提到】

: 第二题的block需要是正方形吗？还是长方形也可以？

h*n2012-12-01 08:12

12 楼

怎么没人讨论第一题呢，
第一题是用interval tree来搞么
感觉直接扫一遍，计数就行了，不知道有没有理解对

【在 g***j 的大作中提到】

: 1 给你一堆interval，然后给定一个interval，如果这个interval和其他三个以下的
: interval有concurrent的overlap，则返回true，否则返回false
: 比如
: 已有 1－3， 4－5， 6-8，9-10，给定1 －10，返回true，因为1-10只跟其中任
: 意一个有overlap，concurrent的overlap最多才2个
: 已有 1 －6 3- 7 2－8 给定 4-6，返回false，因为来三个都跟4-6有
: overlap 5-6
: 2 给定一个0和1的矩阵，返回连成一片的1的block的个数，只考虑前后左右四个
: neighbor。
: 0 1 0 0 1 0 0

g*j2012-12-01 08:12

13 楼

具体怎么做，可以说说么？

【在 h****n 的大作中提到】

: 怎么没人讨论第一题呢，
: 第一题是用interval tree来搞么
: 感觉直接扫一遍，计数就行了，不知道有没有理解对

h*e2012-12-01 08:12

14 楼

恩线段树。。

【在 h****n 的大作中提到】

: 怎么没人讨论第一题呢，
: 第一题是用interval tree来搞么
: 感觉直接扫一遍，计数就行了，不知道有没有理解对

p*22012-12-01 08:12

15 楼

第一题就算用interval tree来搞怎么搞？
找到和给定interval overlap的很容易，关键是还要找这些之间也需要overlap才行。
这个怎么操作比较容易？

l*b2012-12-01 08:12

16 楼

扫描边界有问题吧
1 1 1 1
1 0 0 1
和
1 0 0 1
1 1 1 1
往一起一拼是一个

【在 b***m 的大作中提到】

l*b2012-12-01 08:12

17 楼

多色归一实现起来好像不容易呀，例如前一行已经染好
3 0 2 0 1 0 1 0 2 0 3
下一行是
1 1 1 1 1 0 1 1 1 1 1
按说应该全部归一。但是前半段扫完以后不知道后半段的情况，不知道该怎么办了。。

【在 b***e 的大作中提到】

: 没必要做DFS。只要两行两行的扫描染色:
: - 下行的颜色根据上行的颜色定。
: - 上下两行有重叠的段下行段就染就和上行段染相同的颜色。如果下行某段和上行多
: 段相重
: 叠，则多色归一。
: - 下面一行如果有一段没有和上行有任何重叠则下行此段新起一种颜色。
: - 下行染完色后，如果发现上行的某个颜色消失了，就output一个连续块。
: 这个问题每次看两行就行了。而且不用多看，look_ahead(1)就可以了。

k*g2012-12-01 08:12

18 楼

第二题不就是max rectangle的变种么, O(N^2)

b*e2012-12-01 08:12

19 楼

大不了扫两遍，第一遍只染色，第二遍同一段的归一。总之对于每一行都是一个O(n)的
问题。每次只要看两行即可。前面的行扫完了全扔掉。只需要两行的内存。

【在 l*******b 的大作中提到】

: 多色归一实现起来好像不容易呀，例如前一行已经染好
: 3 0 2 0 1 0 1 0 2 0 3
: 下一行是
: 1 1 1 1 1 0 1 1 1 1 1
: 按说应该全部归一。但是前半段扫完以后不知道后半段的情况，不知道该怎么办了。。

g*j2012-12-01 08:12

20 楼

我也不知道，谁来谈谈？

【在 p*****2 的大作中提到】

: 第一题就算用interval tree来搞怎么搞？
: 找到和给定interval overlap的很容易，关键是还要找这些之间也需要overlap才行。
: 这个怎么操作比较容易？

p*y2012-12-01 08:12

21 楼

从左向右，从上到下扫描的话
3 0 2 0 1 0 1 0 2 0 3
这种情况不可能吧，3和3之间肯定只有3。

【在 l*******b 的大作中提到】

b*e2012-12-01 08:12

22 楼

可能。三个碗扣一起就是这个样子。

【在 p*********y 的大作中提到】

: 从左向右，从上到下扫描的话
: 3 0 2 0 1 0 1 0 2 0 3
: 这种情况不可能吧，3和3之间肯定只有3。