L*Y
2 楼
G的第一面，听口音是个国人大哥。
没做出来，好郁闷...
Suppose we are given S rectangles on 2 dimensional space:
1) each one is specified x1, y1, x2, y2
2) calculate the area covered by these S rectangles.
没做出来，好郁闷...
Suppose we are given S rectangles on 2 dimensional space:
1) each one is specified x1, y1, x2, y2
2) calculate the area covered by these S rectangles.
h*G
3 楼
有几十块快过期了.
实在找不到有啥可买的.
实在找不到有啥可买的.
l*t
4 楼
【 以下文字转载自 Dreamer 讨论区 】
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: 大家都有过man crush吗？
发信站: BBS 未名空间站 (Wed Jul 9 02:14:25 2014, 美东)
我直男一个，最近很confuse， 有一个man crush，最近公司的同事，很优秀，有个
project实在做不出，他主动进组来帮，结果人家几下就搞定了最后还没抢功说我们自
己做出来的，就突然很崇拜。然后偷偷去facebook看了下，才知道人家一路藤校，还看
到了人家貌似有好几个summer houses，估计是家里很有钱，因为他还年轻不可能自己
赚的。长的也非常挺拔，像年轻版的赵文瑄。这就是传说中的高富帅聪善美吗？ 后来
我们一起出差了几次，就成了好朋友，周末有时候约打球。最近不知怎么的，老盼望着
周末一起打球。
这正常吗？也没什么幻想，就是一种很难说清楚的感觉，有点崇拜，有点喜欢很难用语言
表达的感觉 。大家都没有过对自己同性别的很崇拜的人crush过吗？
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: 大家都有过man crush吗？
发信站: BBS 未名空间站 (Wed Jul 9 02:14:25 2014, 美东)
我直男一个，最近很confuse， 有一个man crush，最近公司的同事，很优秀，有个
project实在做不出，他主动进组来帮，结果人家几下就搞定了最后还没抢功说我们自
己做出来的，就突然很崇拜。然后偷偷去facebook看了下，才知道人家一路藤校，还看
到了人家貌似有好几个summer houses，估计是家里很有钱，因为他还年轻不可能自己
赚的。长的也非常挺拔，像年轻版的赵文瑄。这就是传说中的高富帅聪善美吗？ 后来
我们一起出差了几次，就成了好朋友，周末有时候约打球。最近不知怎么的，老盼望着
周末一起打球。
这正常吗？也没什么幻想，就是一种很难说清楚的感觉，有点崇拜，有点喜欢很难用语言
表达的感觉 。大家都没有过对自己同性别的很崇拜的人crush过吗？
c*7
5 楼
no rebate, kills the deal
f*t
6 楼
暴力做法蛮简单的吧，所有矩形面积之和减掉矩形相交面积之和
func CalcTotalArea(rectangles []Rectangle) int {
area := 0
for r, idx := range rectangles {
area += (r.x2 - r.x1) * (r.y2 - r.y1)
for i := idx + 1; i < len(rectangles); i++ {
r2 := rectangles[i]
x1 := max(r.x1, r2.x1)
y1 := max(r.y1, r2.y1)
x2 := min(r.x2, r2.x2)
y2 := min(r.y2, r2.y2)
if x1 < x2 && y1 < y2 {
area -= (x2 - x1) * (y2 - y1)
}
}
}
return area
}
func CalcTotalArea(rectangles []Rectangle) int {
area := 0
for r, idx := range rectangles {
area += (r.x2 - r.x1) * (r.y2 - r.y1)
for i := idx + 1; i < len(rectangles); i++ {
r2 := rectangles[i]
x1 := max(r.x1, r2.x1)
y1 := max(r.y1, r2.y1)
x2 := min(r.x2, r2.x2)
y2 := min(r.y2, r2.y2)
if x1 < x2 && y1 < y2 {
area -= (x2 - x1) * (y2 - y1)
}
}
}
return area
}
b*e
7 楼
xbox gc
【在 h**G 的大作中提到】
: 有几十块快过期了.
: 实在找不到有啥可买的.
【在 h**G 的大作中提到】
: 有几十块快过期了.
: 实在找不到有啥可买的.
H*7
8 楼
想想文革时十亿人对腊肉的崇拜
r*c
9 楼
yes, there is a rebate
a*5
10 楼
看错了 以为是要求所有矩形相交区域的面积
h*G
11 楼
不打xbox很久了
没需求啊
【在 b*****e 的大作中提到】
: xbox gc
没需求啊
【在 b*****e 的大作中提到】
: xbox gc
m*m
12 楼
爱情不分种族性别
【在 l****t 的大作中提到】
: 【 以下文字转载自 Dreamer 讨论区 】
: 发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
: 标 题: 大家都有过man crush吗？
: 发信站: BBS 未名空间站 (Wed Jul 9 02:14:25 2014, 美东)
: 我直男一个，最近很confuse， 有一个man crush，最近公司的同事，很优秀，有个
: project实在做不出，他主动进组来帮，结果人家几下就搞定了最后还没抢功说我们自
: 己做出来的，就突然很崇拜。然后偷偷去facebook看了下，才知道人家一路藤校，还看
: 到了人家貌似有好几个summer houses，估计是家里很有钱，因为他还年轻不可能自己
: 赚的。长的也非常挺拔，像年轻版的赵文瑄。这就是传说中的高富帅聪善美吗？ 后来
: 我们一起出差了几次，就成了好朋友，周末有时候约打球。最近不知怎么的，老盼望着
【在 l****t 的大作中提到】
: 【 以下文字转载自 Dreamer 讨论区 】
: 发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
: 标 题: 大家都有过man crush吗？
: 发信站: BBS 未名空间站 (Wed Jul 9 02:14:25 2014, 美东)
: 我直男一个，最近很confuse， 有一个man crush，最近公司的同事，很优秀，有个
: project实在做不出，他主动进组来帮，结果人家几下就搞定了最后还没抢功说我们自
: 己做出来的，就突然很崇拜。然后偷偷去facebook看了下，才知道人家一路藤校，还看
: 到了人家貌似有好几个summer houses，估计是家里很有钱，因为他还年轻不可能自己
: 赚的。长的也非常挺拔，像年轻版的赵文瑄。这就是传说中的高富帅聪善美吗？ 后来
: 我们一起出差了几次，就成了好朋友，周末有时候约打球。最近不知怎么的，老盼望着
c*7
13 楼
thanks, can you offer a rebate link?
【在 r**c 的大作中提到】
: yes, there is a rebate
b*0
14 楼
如果有三块及以上重合 好像就不行了吧
【在 f*******t 的大作中提到】
: 暴力做法蛮简单的吧，所有矩形面积之和减掉矩形相交面积之和
: func CalcTotalArea(rectangles []Rectangle) int {
: area := 0
: for r, idx := range rectangles {
: area += (r.x2 - r.x1) * (r.y2 - r.y1)
: for i := idx + 1; i < len(rectangles); i++ {
: r2 := rectangles[i]
: x1 := max(r.x1, r2.x1)
: y1 := max(r.y1, r2.y1)
: x2 := min(r.x2, r2.x2)
【在 f*******t 的大作中提到】
: 暴力做法蛮简单的吧，所有矩形面积之和减掉矩形相交面积之和
: func CalcTotalArea(rectangles []Rectangle) int {
: area := 0
: for r, idx := range rectangles {
: area += (r.x2 - r.x1) * (r.y2 - r.y1)
: for i := idx + 1; i < len(rectangles); i++ {
: r2 := rectangles[i]
: x1 := max(r.x1, r2.x1)
: y1 := max(r.y1, r2.y1)
: x2 := min(r.x2, r2.x2)
c*e
15 楼
当然有过
【在 l****t 的大作中提到】
: 【 以下文字转载自 Dreamer 讨论区 】
: 发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
: 标 题: 大家都有过man crush吗？
: 发信站: BBS 未名空间站 (Wed Jul 9 02:14:25 2014, 美东)
: 我直男一个，最近很confuse， 有一个man crush，最近公司的同事，很优秀，有个
: project实在做不出，他主动进组来帮，结果人家几下就搞定了最后还没抢功说我们自
: 己做出来的，就突然很崇拜。然后偷偷去facebook看了下，才知道人家一路藤校，还看
: 到了人家貌似有好几个summer houses，估计是家里很有钱，因为他还年轻不可能自己
: 赚的。长的也非常挺拔，像年轻版的赵文瑄。这就是传说中的高富帅聪善美吗？ 后来
: 我们一起出差了几次，就成了好朋友，周末有时候约打球。最近不知怎么的，老盼望着
【在 l****t 的大作中提到】
: 【 以下文字转载自 Dreamer 讨论区 】
: 发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
: 标 题: 大家都有过man crush吗？
: 发信站: BBS 未名空间站 (Wed Jul 9 02:14:25 2014, 美东)
: 我直男一个，最近很confuse， 有一个man crush，最近公司的同事，很优秀，有个
: project实在做不出，他主动进组来帮，结果人家几下就搞定了最后还没抢功说我们自
: 己做出来的，就突然很崇拜。然后偷偷去facebook看了下，才知道人家一路藤校，还看
: 到了人家貌似有好几个summer houses，估计是家里很有钱，因为他还年轻不可能自己
: 赚的。长的也非常挺拔，像年轻版的赵文瑄。这就是传说中的高富帅聪善美吗？ 后来
: 我们一起出差了几次，就成了好朋友，周末有时候约打球。最近不知怎么的，老盼望着
x*g
17 楼
x,y 是int吗？如果是，唯一能想到的用matrix（all 0s），扫一个个rectangles 变1
，最后数1的个数~~当然实在太暴力了
，最后数1的个数~~当然实在太暴力了
l*t
18 楼
zkss
【在 c********e 的大作中提到】
: 当然有过
【在 c********e 的大作中提到】
: 当然有过
c*7
19 楼
thanks
great deal
great deal
Y*G
20 楼
下面的代码我测试通过了。
public class Rect {
int x;
int y;
int width;
int height;
public Rect(int x, int y, int width, int height) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
public int getArea() {
return width * height;
}
Rect intersect(Rect other) {
int newX0 = Math.max(x, other.x);
int newY0 = Math.max(y, other.y);
int newX1 = Math.min(x + width, other.x + other.width);
int newY1 = Math.min(y + height, other.y + other.height);
if (newX1 <= newX0 && newY1 <= newY0) {
return null;
}
return new Rect(newX0, newY0, newX1 - newX0, newY1 - newY0);
}
}
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class AppMain {
private static int getTotalArea(List rects) {
if (rects.size() == 0) {
return 0;
}
if (rects.size() == 1) {
return rects.get(0).getArea();
}
Rect first = rects.get(0);
List subList = rects.subList(1, rects.size());
int sum1 = first.getArea();
int sum2 = getTotalArea(subList);
List intersect = new LinkedList<>();
for (Rect rect : subList) {
Rect newRect = first.intersect(rect);
if (newRect != null) {
intersect.add(newRect);
}
}
return sum1 + sum2 - getTotalArea(intersect);
}
public static void main(String[] args) {
List rects = Arrays.asList(
new Rect(0, 0, 2, 2),
new Rect(1, 1, 3, 3),
new Rect(-1, -1, 2, 2)
);
int sum = getTotalArea(rects);
System.out.printf("%d%n", sum);
}
}
public class Rect {
int x;
int y;
int width;
int height;
public Rect(int x, int y, int width, int height) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
public int getArea() {
return width * height;
}
Rect intersect(Rect other) {
int newX0 = Math.max(x, other.x);
int newY0 = Math.max(y, other.y);
int newX1 = Math.min(x + width, other.x + other.width);
int newY1 = Math.min(y + height, other.y + other.height);
if (newX1 <= newX0 && newY1 <= newY0) {
return null;
}
return new Rect(newX0, newY0, newX1 - newX0, newY1 - newY0);
}
}
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class AppMain {
private static int getTotalArea(List
if (rects.size() == 0) {
return 0;
}
if (rects.size() == 1) {
return rects.get(0).getArea();
}
Rect first = rects.get(0);
List
int sum1 = first.getArea();
int sum2 = getTotalArea(subList);
List
for (Rect rect : subList) {
Rect newRect = first.intersect(rect);
if (newRect != null) {
intersect.add(newRect);
}
}
return sum1 + sum2 - getTotalArea(intersect);
}
public static void main(String[] args) {
List
new Rect(0, 0, 2, 2),
new Rect(1, 1, 3, 3),
new Rect(-1, -1, 2, 2)
);
int sum = getTotalArea(rects);
System.out.printf("%d%n", sum);
}
}
a*e
21 楼
高中班里有个跳民族舞的男孩，眉清目秀的还有酒窝，有次过年表演节目，这货上台跳
胡旋舞，看着看着竟然吃惊的发现自己硬了。从此好长一段时间怀疑自己是不是给。。
。
胡旋舞，看着看着竟然吃惊的发现自己硬了。从此好长一段时间怀疑自己是不是给。。
。
s*g
22 楼
limit 2，可以一个信封么？
还是需要两个order，生成两个receipt？多谢
【在 r**c 的大作中提到】
: http://g-ecx.images-amazon.com/images/G/01/00/00/11/80/96/10/1180961050._V194796921_.pdf
还是需要两个order，生成两个receipt？多谢
【在 r**c 的大作中提到】
: http://g-ecx.images-amazon.com/images/G/01/00/00/11/80/96/10/1180961050._V194796921_.pdf
t*3
23 楼
swipe line，见topcoder的一篇tutorial。
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
R*a
24 楼
结果发现真的是？
【在 a*******e 的大作中提到】
: 高中班里有个跳民族舞的男孩，眉清目秀的还有酒窝，有次过年表演节目，这货上台跳
: 胡旋舞，看着看着竟然吃惊的发现自己硬了。从此好长一段时间怀疑自己是不是给。。
: 。
【在 a*******e 的大作中提到】
: 高中班里有个跳民族舞的男孩，眉清目秀的还有酒窝，有次过年表演节目，这货上台跳
: 胡旋舞，看着看着竟然吃惊的发现自己硬了。从此好长一段时间怀疑自己是不是给。。
: 。
c*7
25 楼
2 order
【在 s********g 的大作中提到】
: limit 2，可以一个信封么？
: 还是需要两个order，生成两个receipt？多谢
w*n
26 楼
(0, 0, 1, 1)和 (1， 0， 1， 2) 算是合法输入么？
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
T*e
27 楼
高中生那不算，高中生看着豆瓣酱都能硬
【在 a*******e 的大作中提到】
: 高中班里有个跳民族舞的男孩，眉清目秀的还有酒窝，有次过年表演节目，这货上台跳
: 胡旋舞，看着看着竟然吃惊的发现自己硬了。从此好长一段时间怀疑自己是不是给。。
: 。
【在 a*******e 的大作中提到】
: 高中班里有个跳民族舞的男孩，眉清目秀的还有酒窝，有次过年表演节目，这货上台跳
: 胡旋舞，看着看着竟然吃惊的发现自己硬了。从此好长一段时间怀疑自己是不是给。。
: 。
f*5
28 楼
rrdw,剪了UPC还能在ebay上卖么？买家不挑刺儿？
l*n
29 楼
我了个擦。。。为啥电面考这么难啊。。。sweep line algorithm啊。。。这面试无论
如何都得跪吧。。。
如何都得跪吧。。。
a*e
30 楼
没机会检验啊，更喜欢女人。后来看中国古典文学，发现有很多玩戏子的达官贵人，比
如贾宝玉薛蟠什么的，就释然了。
【在 R***a 的大作中提到】
: 结果发现真的是？
如贾宝玉薛蟠什么的，就释然了。
【在 R***a 的大作中提到】
: 结果发现真的是？
d*f
31 楼
no need, always do 2 in 1 order
【在 c*********7 的大作中提到】
:
: 2 order
【在 c*********7 的大作中提到】
:
: 2 order
b*e
32 楼
顶。
【在 t*****3 的大作中提到】
: swipe line，见topcoder的一篇tutorial。
【在 t*****3 的大作中提到】
: swipe line，见topcoder的一篇tutorial。
w*1
33 楼
释然什么，这叫bi
【在 a*******e 的大作中提到】
: 没机会检验啊，更喜欢女人。后来看中国古典文学，发现有很多玩戏子的达官贵人，比
: 如贾宝玉薛蟠什么的，就释然了。
【在 a*******e 的大作中提到】
: 没机会检验啊，更喜欢女人。后来看中国古典文学，发现有很多玩戏子的达官贵人，比
: 如贾宝玉薛蟠什么的，就释然了。
d*1
34 楼
价格变了？
h*9
35 楼
请问坐标都是int吗？如果是的话，能不能把它离散化，用一个一个的像素点来表示一
个个矩形（被矩形覆盖的点设为1，否则为0），最后算一下1的个数。时间复杂度有点
高，不过不这么算真的挺复杂的。
个个矩形（被矩形覆盖的点设为1，否则为0），最后算一下1的个数。时间复杂度有点
高，不过不这么算真的挺复杂的。
G*g
36 楼
虽然我对你传达的思想表示支持，但还得帮助你纠正一下事实：
文革时对腊肉的崇拜人数大概在6亿到7亿之间。
【在 H******7 的大作中提到】
: 想想文革时十亿人对腊肉的崇拜
文革时对腊肉的崇拜人数大概在6亿到7亿之间。
【在 H******7 的大作中提到】
: 想想文革时十亿人对腊肉的崇拜
l*i
37 楼
不错的自用deal! in for 1
a*m
38 楼
g店面正常差不多是这个难度。
【在 l*****n 的大作中提到】
: 我了个擦。。。为啥电面考这么难啊。。。sweep line algorithm啊。。。这面试无论
: 如何都得跪吧。。。
【在 l*****n 的大作中提到】
: 我了个擦。。。为啥电面考这么难啊。。。sweep line algorithm啊。。。这面试无论
: 如何都得跪吧。。。
l*t
39 楼
并且其中只有大约一半是同性
【在 G******g 的大作中提到】
: 虽然我对你传达的思想表示支持，但还得帮助你纠正一下事实：
: 文革时对腊肉的崇拜人数大概在6亿到7亿之间。
【在 G******g 的大作中提到】
: 虽然我对你传达的思想表示支持，但还得帮助你纠正一下事实：
: 文革时对腊肉的崇拜人数大概在6亿到7亿之间。
l*a
40 楼
选择package是不是要retail那种，一单下两个，一起claim rebate?
谢谢
【在 d********f 的大作中提到】
: no need, always do 2 in 1 order
谢谢
【在 d********f 的大作中提到】
: no need, always do 2 in 1 order
a*5
41 楼
扫描线吧。。想不到其他方法了
H*7
42 楼
别忘了亚非拉兄弟
ouSheng (水果王) 的大作中提到: 】
ouSheng (水果王) 的大作中提到: 】
c*7
43 楼
是不是可以下4个单？
f*w
44 楼
似乎计算几何里面算contour有标准算法 如果能用上标准算法就没啥难度
不过那个算法连叫啥我都早就还给老师了
不过那个算法连叫啥我都早就还给老师了
m*n
45 楼
Huan2007经常发贴不经大脑似的，
我怀疑他要么未成年，要么智商不够。
【在 G******g 的大作中提到】
: 虽然我对你传达的思想表示支持，但还得帮助你纠正一下事实：
: 文革时对腊肉的崇拜人数大概在6亿到7亿之间。
我怀疑他要么未成年，要么智商不够。
【在 G******g 的大作中提到】
: 虽然我对你传达的思想表示支持，但还得帮助你纠正一下事实：
: 文革时对腊肉的崇拜人数大概在6亿到7亿之间。
s*g
46 楼
那submit rebate的时候也是一个信封么？
【在 d********f 的大作中提到】
: no need, always do 2 in 1 order
【在 d********f 的大作中提到】
: no need, always do 2 in 1 order
x*u
47 楼
这就是我喜欢非老中面世的原因.
中国人出的题都偏难, 无它, 显摆自己厉害罢了.
你说出这种topcoder里的题有意义吗?
我碰巧接触过, 就做得出.
没碰过, 牛吨他师傅来了都搞不定.
中国人出的题都偏难, 无它, 显摆自己厉害罢了.
你说出这种topcoder里的题有意义吗?
我碰巧接触过, 就做得出.
没碰过, 牛吨他师傅来了都搞不定.
p*g
48 楼
套用我同学的话：
每个人心中都有一座断背山
【在 l****t 的大作中提到】
: 并且其中只有大约一半是同性
每个人心中都有一座断背山
【在 l****t 的大作中提到】
: 并且其中只有大约一半是同性
c*7
49 楼
算了不弄了，每次rebate都很慢
n*n
50 楼
不是吧。这题考的是知识面。有几个人能直接在45分钟发现scan line算法？
【在 a********m 的大作中提到】
: g店面正常差不多是这个难度。
【在 a********m 的大作中提到】
: g店面正常差不多是这个难度。
i*a
51 楼
他在暗示你呢
[发表自未名空间手机版 - m.mitbbs.com]
【在 p*********g 的大作中提到】
: 套用我同学的话：
: 每个人心中都有一座断背山
[发表自未名空间手机版 - m.mitbbs.com]
【在 p*********g 的大作中提到】
: 套用我同学的话：
: 每个人心中都有一座断背山
b*s
52 楼
是一个信封一个rebate，买2个要2个信封。
One receipt per envelope
【在 s********g 的大作中提到】
: 那submit rebate的时候也是一个信封么？
One receipt per envelope
【在 s********g 的大作中提到】
: 那submit rebate的时候也是一个信封么？
B*1
53 楼
那么我跪了，这个我以后就拿来面烙印。
【在 a********m 的大作中提到】
: g店面正常差不多是这个难度。
【在 a********m 的大作中提到】
: g店面正常差不多是这个难度。
p*g
54 楼
她是女的...特弱小的那种 (-___-|||)
【在 i****a 的大作中提到】
: 他在暗示你呢
:
: [发表自未名空间手机版 - m.mitbbs.com]
【在 i****a 的大作中提到】
: 他在暗示你呢
:
: [发表自未名空间手机版 - m.mitbbs.com]
c*7
55 楼
算了不弄了，每次rebate都很慢
b*n
56 楼
这还让人活么
【在 a********m 的大作中提到】
: g店面正常差不多是这个难度。
【在 a********m 的大作中提到】
: g店面正常差不多是这个难度。
s*g
57 楼
got it！ 多谢～～～
【在 b****s 的大作中提到】
: 是一个信封一个rebate，买2个要2个信封。
: One receipt per envelope
【在 b****s 的大作中提到】
: 是一个信封一个rebate，买2个要2个信封。
: One receipt per envelope
b*n
58 楼
大牛所言及时，对三哥这个题都算便宜他们了
【在 B*******1 的大作中提到】
: 那么我跪了，这个我以后就拿来面烙印。
【在 B*******1 的大作中提到】
: 那么我跪了，这个我以后就拿来面烙印。
k*1
59 楼
这个音箱好用吗?最近想添置音箱~看了看BOSE都没有什么deal
h*n
60 楼
不正常。
【在 a********m 的大作中提到】
: g店面正常差不多是这个难度。
【在 a********m 的大作中提到】
: g店面正常差不多是这个难度。
L*Y
61 楼
大哥，不会是你面的吧... 手下留情...
【在 a********m 的大作中提到】
: g店面正常差不多是这个难度。
【在 a********m 的大作中提到】
: g店面正常差不多是这个难度。
a*m
62 楼
冷静点应该能想到吧。从最直接的2维canvas描点，仔细考虑优化一下到1维扫描线也是
正常思路，毕竟也没啥其他的方向。难道是俺2年前看的那遍cc150还有残留印象所以不
觉得很离谱？
代码确实烦，俺是肯定写不完。但是应该意思到就差不多。
G有人店面比onsite简单一点，有人直接上onsite的题目。记得讨论哪个比较好的时候
倾向后者的多一些。
【在 n******n 的大作中提到】
: 不是吧。这题考的是知识面。有几个人能直接在45分钟发现scan line算法？
正常思路，毕竟也没啥其他的方向。难道是俺2年前看的那遍cc150还有残留印象所以不
觉得很离谱？
代码确实烦，俺是肯定写不完。但是应该意思到就差不多。
G有人店面比onsite简单一点，有人直接上onsite的题目。记得讨论哪个比较好的时候
倾向后者的多一些。
【在 n******n 的大作中提到】
: 不是吧。这题考的是知识面。有几个人能直接在45分钟发现scan line算法？
a*m
63 楼
不可能是。。。。俺问dp，比较容易聊天和提示。。。下手轻重区别在给分上。。。。
【在 L****Y 的大作中提到】
: 大哥，不会是你面的吧... 手下留情...
【在 L****Y 的大作中提到】
: 大哥，不会是你面的吧... 手下留情...
n*n
64 楼
这题on-site也过分了。测能力，而不是测知识，除非楼主自己强调计算几何背景
【在 a********m 的大作中提到】
: 冷静点应该能想到吧。从最直接的2维canvas描点，仔细考虑优化一下到1维扫描线也是
: 正常思路，毕竟也没啥其他的方向。难道是俺2年前看的那遍cc150还有残留印象所以不
: 觉得很离谱？
: 代码确实烦，俺是肯定写不完。但是应该意思到就差不多。
: G有人店面比onsite简单一点，有人直接上onsite的题目。记得讨论哪个比较好的时候
: 倾向后者的多一些。
【在 a********m 的大作中提到】
: 冷静点应该能想到吧。从最直接的2维canvas描点，仔细考虑优化一下到1维扫描线也是
: 正常思路，毕竟也没啥其他的方向。难道是俺2年前看的那遍cc150还有残留印象所以不
: 觉得很离谱？
: 代码确实烦，俺是肯定写不完。但是应该意思到就差不多。
: G有人店面比onsite简单一点，有人直接上onsite的题目。记得讨论哪个比较好的时候
: 倾向后者的多一些。
m*a
65 楼
二维线段树也可以搞吧
k*r
66 楼
A U B U C = A + B + C - AB - AC -BC + ABC
以此类推S个矩形的并集，只需要写出两个矩形相交的function，再反复调用即可。
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
以此类推S个矩形的并集，只需要写出两个矩形相交的function，再反复调用即可。
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
a*m
67 楼
不脚着和几何有啥关系和需要啥背景知识。。。。经典skyline注水那题算几何题么？
如果你脚着算的话那这题也算吧。。。。
俺脚着如果想到几何背景那10有(关键字)是想歪了。除非是面计算机图形方面的职位。
【在 n******n 的大作中提到】
: 这题on-site也过分了。测能力，而不是测知识，除非楼主自己强调计算几何背景
如果你脚着算的话那这题也算吧。。。。
俺脚着如果想到几何背景那10有(关键字)是想歪了。除非是面计算机图形方面的职位。
【在 n******n 的大作中提到】
: 这题on-site也过分了。测能力，而不是测知识，除非楼主自己强调计算几何背景
L*Y
68 楼
俺没有计算几何背景...
【在 n******n 的大作中提到】
: 这题on-site也过分了。测能力，而不是测知识，除非楼主自己强调计算几何背景
【在 n******n 的大作中提到】
: 这题on-site也过分了。测能力，而不是测知识，除非楼主自己强调计算几何背景
a*m
69 楼
这个俺脚着太难了。。。。
矩阵相交n种情况呀。这么算是指数复杂度了吧。
【在 k****r 的大作中提到】
: A U B U C = A + B + C - AB - AC -BC + ABC
: 以此类推S个矩形的并集，只需要写出两个矩形相交的function，再反复调用即可。
矩阵相交n种情况呀。这么算是指数复杂度了吧。
【在 k****r 的大作中提到】
: A U B U C = A + B + C - AB - AC -BC + ABC
: 以此类推S个矩形的并集，只需要写出两个矩形相交的function，再反复调用即可。
n*n
70 楼
想当然。你自己写写看
【在 k****r 的大作中提到】
: A U B U C = A + B + C - AB - AC -BC + ABC
: 以此类推S个矩形的并集，只需要写出两个矩形相交的function，再反复调用即可。
【在 k****r 的大作中提到】
: A U B U C = A + B + C - AB - AC -BC + ABC
: 以此类推S个矩形的并集，只需要写出两个矩形相交的function，再反复调用即可。
s*e
71 楼
我也觉得过了，这个难度到底是希望别人做出来还是做不出来好？
n*n
72 楼
那题的nlogn解法，没竞赛训练过，有几个人能现想出来？
【在 a********m 的大作中提到】
: 不脚着和几何有啥关系和需要啥背景知识。。。。经典skyline注水那题算几何题么？
: 如果你脚着算的话那这题也算吧。。。。
: 俺脚着如果想到几何背景那10有(关键字)是想歪了。除非是面计算机图形方面的职位。
【在 a********m 的大作中提到】
: 不脚着和几何有啥关系和需要啥背景知识。。。。经典skyline注水那题算几何题么？
: 如果你脚着算的话那这题也算吧。。。。
: 俺脚着如果想到几何背景那10有(关键字)是想歪了。除非是面计算机图形方面的职位。
a*m
73 楼
思路对最重要。最佳算法确实很多是当场写不出来的。
这题俺脚着把扫描函数单独写出来，用最土的办法实现，然后告诉说这块的最优算法需
要慢慢写就可以过关。这种麻烦的复杂度如果是俺都不是必须要求，因为俺自己想出来
也费半天劲，太技巧了，不过如果能说出来算可以加分吧。
【在 n******n 的大作中提到】
: 那题的nlogn解法，没竞赛训练过，有几个人能现想出来？
这题俺脚着把扫描函数单独写出来，用最土的办法实现，然后告诉说这块的最优算法需
要慢慢写就可以过关。这种麻烦的复杂度如果是俺都不是必须要求，因为俺自己想出来
也费半天劲，太技巧了，不过如果能说出来算可以加分吧。
【在 n******n 的大作中提到】
: 那题的nlogn解法，没竞赛训练过，有几个人能现想出来？
r*g
74 楼
好难啊 明天我也要面G 压力好大
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
r*g
75 楼
我记得以前有个关于rect的
是对x排序
然后另取一个set存储rect
第一次见到x的就加入
第二次见到的就删除啥的
不知道能不能adapt到这里
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
是对x排序
然后另取一个set存储rect
第一次见到x的就加入
第二次见到的就删除啥的
不知道能不能adapt到这里
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
a*m
76 楼
这种原题你来考烙印？难道你就是传说中的卧底？
【在 B*******1 的大作中提到】
: 那么我跪了，这个我以后就拿来面烙印。
【在 B*******1 的大作中提到】
: 那么我跪了，这个我以后就拿来面烙印。
a*m
77 楼
记住一要冷静。二要一步步来，通常从最土的方法出发比较好，给提示也容易。一下想
太多很容易回不来，面试官想帮你都很难。
【在 r*g 的大作中提到】
: 好难啊 明天我也要面G 压力好大
太多很容易回不来，面试官想帮你都很难。
【在 r*g 的大作中提到】
: 好难啊 明天我也要面G 压力好大
s*a
78 楼
这个应该是最标准的二维线段数吧
估计他只期望你写出一个最简单的每次刷新面积的做法
用线段数应该只是说说思路就好吧
大家碰到难题不要怕 想到什么说什么 能把想到的写出来就好 难题会基础算法再在讨
论中得出更好的算法基本就能在面试中得高分了 反倒简单题要小心coding 小错误就可
能跪掉
估计他只期望你写出一个最简单的每次刷新面积的做法
用线段数应该只是说说思路就好吧
大家碰到难题不要怕 想到什么说什么 能把想到的写出来就好 难题会基础算法再在讨
论中得出更好的算法基本就能在面试中得高分了 反倒简单题要小心coding 小错误就可
能跪掉
A*e
79 楼
二维线段数？最简单的每次刷新面积的做法？
【在 s****a 的大作中提到】
: 这个应该是最标准的二维线段数吧
: 估计他只期望你写出一个最简单的每次刷新面积的做法
: 用线段数应该只是说说思路就好吧
: 大家碰到难题不要怕 想到什么说什么 能把想到的写出来就好 难题会基础算法再在讨
: 论中得出更好的算法基本就能在面试中得高分了 反倒简单题要小心coding 小错误就可
: 能跪掉
【在 s****a 的大作中提到】
: 这个应该是最标准的二维线段数吧
: 估计他只期望你写出一个最简单的每次刷新面积的做法
: 用线段数应该只是说说思路就好吧
: 大家碰到难题不要怕 想到什么说什么 能把想到的写出来就好 难题会基础算法再在讨
: 论中得出更好的算法基本就能在面试中得高分了 反倒简单题要小心coding 小错误就可
: 能跪掉
M*e
80 楼
MC可以吗...
[发表自未名空间手机版 - m.mitbbs.com]
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
[发表自未名空间手机版 - m.mitbbs.com]
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
l*v
81 楼
妈呀，这道题拿过来面小印，10个人里面，能有1个通过G家店面吗？
m*1
82 楼
弱弱的问一下， 这个题是不是信息给少了呀，rectangles只给两个点，不能确定这个
rectangle的大小吧。是不是默认所有的边都和x，y 轴平行呀？？
rectangle的大小吧。是不是默认所有的边都和x，y 轴平行呀？？
l*r
83 楼
我店面时问的是S个圆的cover 面积 给定的是圆心坐标和半径
这道题我答得相当完美
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
这道题我答得相当完美
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
s*r
84 楼
个人感觉狗狗的店面比onsite难搞，俺店面就没pass过，最多到第二轮
c*d
85 楼
矩形的还好说，圆的咋算呢？
【在 l******r 的大作中提到】
: 我店面时问的是S个圆的cover 面积 给定的是圆心坐标和半径
: 这道题我答得相当完美
【在 l******r 的大作中提到】
: 我店面时问的是S个圆的cover 面积 给定的是圆心坐标和半径
: 这道题我答得相当完美
y*i
86 楼
感觉可以用求两个直方图面积的差来做：
1）根据矩形的左边（矩形有四边）位置排序，左右边位置类似Leetcode的Integer
Interval
2）然后根据矩形上边最大值的组合组成直方图，求直方图覆盖面积
3）然后根据矩形下边最小值的组合组成直方图，求直方图覆盖面积
4）求面积差
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
1）根据矩形的左边（矩形有四边）位置排序，左右边位置类似Leetcode的Integer
Interval
2）然后根据矩形上边最大值的组合组成直方图，求直方图覆盖面积
3）然后根据矩形下边最小值的组合组成直方图，求直方图覆盖面积
4）求面积差
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
l*r
87 楼
需要把笛卡尔坐标换成极坐标
【在 c****d 的大作中提到】
: 矩形的还好说，圆的咋算呢？
【在 c****d 的大作中提到】
: 矩形的还好说，圆的咋算呢？
c*d
88 楼
看不出来换成极坐标的优势。。。
【在 l******r 的大作中提到】
: 需要把笛卡尔坐标换成极坐标
【在 l******r 的大作中提到】
: 需要把笛卡尔坐标换成极坐标
c*n
89 楼
基本上是skyline 吧（课本里的用来讲 divide and conquer 的例子）
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
b*y
90 楼
这种题和工作有半毛钱关系....
x*u
91 楼
算了吧, 如果他们面世的题目和工作有关系的更不好整.
宁愿接受现在的虐待.
【在 b*******y 的大作中提到】
: 这种题和工作有半毛钱关系....
宁愿接受现在的虐待.
【在 b*******y 的大作中提到】
: 这种题和工作有半毛钱关系....
b*i
92 楼
好像很麻烦啊，匆匆想到下面三种解法，抛砖引玉。
1. 暴力求解，时间复杂度至少是O(S^3)，我不确定
找到下面各种矩形
R0 = 相交至少0次的矩形 （就是原来的矩形）
R1 = 相交至少1次的矩形，(就是上一步R0的交集，复杂度O(S^2), 如果为空，就不要
往下算了)
R2 = 相交至少2次的矩形 (就是上一步R1的交集)
...
R(S-1) = 相交至少S-1次的矩形
结果是R0-R1+...
2. 分割矩形， 时间复杂度至少是O(S^2)，我不确定
从1个矩形开始，加入第2个矩形后，如果有相交，记录他们分割的小矩形。
再加入第3个矩形，跟前面的小矩形如果有相交，记录他们分割的小矩形。
...
结果是所有分割后小矩形的面积之和。
3. 另外坐标是整数，离散化方法。
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
1. 暴力求解，时间复杂度至少是O(S^3)，我不确定
找到下面各种矩形
R0 = 相交至少0次的矩形 （就是原来的矩形）
R1 = 相交至少1次的矩形，(就是上一步R0的交集，复杂度O(S^2), 如果为空，就不要
往下算了)
R2 = 相交至少2次的矩形 (就是上一步R1的交集)
...
R(S-1) = 相交至少S-1次的矩形
结果是R0-R1+...
2. 分割矩形， 时间复杂度至少是O(S^2)，我不确定
从1个矩形开始，加入第2个矩形后，如果有相交，记录他们分割的小矩形。
再加入第3个矩形，跟前面的小矩形如果有相交，记录他们分割的小矩形。
...
结果是所有分割后小矩形的面积之和。
3. 另外坐标是整数，离散化方法。
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
b*i
93 楼
看前面文章，有swipe line的方法，太高级了，学习了。
【在 b*******i 的大作中提到】
: 好像很麻烦啊，匆匆想到下面三种解法，抛砖引玉。
: 1. 暴力求解，时间复杂度至少是O(S^3)，我不确定
: 找到下面各种矩形
: R0 = 相交至少0次的矩形 （就是原来的矩形）
: R1 = 相交至少1次的矩形，(就是上一步R0的交集，复杂度O(S^2), 如果为空，就不要
: 往下算了)
: R2 = 相交至少2次的矩形 (就是上一步R1的交集)
: ...
: R(S-1) = 相交至少S-1次的矩形
: 结果是R0-R1+...
【在 b*******i 的大作中提到】
: 好像很麻烦啊，匆匆想到下面三种解法，抛砖引玉。
: 1. 暴力求解，时间复杂度至少是O(S^3)，我不确定
: 找到下面各种矩形
: R0 = 相交至少0次的矩形 （就是原来的矩形）
: R1 = 相交至少1次的矩形，(就是上一步R0的交集，复杂度O(S^2), 如果为空，就不要
: 往下算了)
: R2 = 相交至少2次的矩形 (就是上一步R1的交集)
: ...
: R(S-1) = 相交至少S-1次的矩形
: 结果是R0-R1+...
a*5
94 楼
这种题标准解法（未必是最优）应该是扫描线+二分。说标准意思是可以写出模板来，
类似的题一套就行了。
但是问题是真的45分钟可以搞定？我大二时候做类似的merge矩形的题，扫描线+二分，
光写码就写了快俩小时。。后面DEBUG什么的，POJ还出各种奇奇怪怪的问题，弄了两天
才过。。
【在 b*******i 的大作中提到】
: 看前面文章，有swipe line的方法，太高级了，学习了。
类似的题一套就行了。
但是问题是真的45分钟可以搞定？我大二时候做类似的merge矩形的题，扫描线+二分，
光写码就写了快俩小时。。后面DEBUG什么的，POJ还出各种奇奇怪怪的问题，弄了两天
才过。。
【在 b*******i 的大作中提到】
: 看前面文章，有swipe line的方法，太高级了，学习了。
q*n
95 楼
我晕，这么难！！
b*i
96 楼
恩，很难做完啊，太打击了，偶觉得我前面的弱智解法写完都勉强（一个解法也就需要
一个基本的求交函数反复调用，或者分割函数反复调用）
【在 a********5 的大作中提到】
: 这种题标准解法（未必是最优）应该是扫描线+二分。说标准意思是可以写出模板来，
: 类似的题一套就行了。
: 但是问题是真的45分钟可以搞定？我大二时候做类似的merge矩形的题，扫描线+二分，
: 光写码就写了快俩小时。。后面DEBUG什么的，POJ还出各种奇奇怪怪的问题，弄了两天
: 才过。。
一个基本的求交函数反复调用，或者分割函数反复调用）
【在 a********5 的大作中提到】
: 这种题标准解法（未必是最优）应该是扫描线+二分。说标准意思是可以写出模板来，
: 类似的题一套就行了。
: 但是问题是真的45分钟可以搞定？我大二时候做类似的merge矩形的题，扫描线+二分，
: 光写码就写了快俩小时。。后面DEBUG什么的，POJ还出各种奇奇怪怪的问题，弄了两天
: 才过。。
a*5
97 楼
想了又想 好像也没啥特别好的办法
还有一种解法就是算S1+S2+S3+..+SN-S1S2-S1S3-...-SN-1SN + S1S2S3...
但是这个解法是指数级的
【在 b*******i 的大作中提到】
: 恩，很难做完啊，太打击了，偶觉得我前面的弱智解法写完都勉强（一个解法也就需要
: 一个基本的求交函数反复调用，或者分割函数反复调用）
还有一种解法就是算S1+S2+S3+..+SN-S1S2-S1S3-...-SN-1SN + S1S2S3...
但是这个解法是指数级的
【在 b*******i 的大作中提到】
: 恩，很难做完啊，太打击了，偶觉得我前面的弱智解法写完都勉强（一个解法也就需要
: 一个基本的求交函数反复调用，或者分割函数反复调用）
E*H
98 楼
店面就这么难，直接跪了。
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
x*m
99 楼
坐标离散的话最弱的方法还挺简单的，弄两个数组分别存每个x最大和最小的y最后相加
就行。连续的话就想不起来了……
就行。连续的话就想不起来了……
a*e
100 楼
这个题相当简单，是从 rectangle set 映射到 disjoint rectangle set 的操作。然
后可以继续分解为将单个 rectangle 插入到 disjoint rectangle set 的操作就好了
。效率取决于这个 disjoint set 的实现，用 sparse 矩阵方式可做。
我十几年前就写过这样一个程序，用来计算 2D GUI 每次更新渲染时对应到屏幕上的
dirty set，非常简单，效率也很好。
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
后可以继续分解为将单个 rectangle 插入到 disjoint rectangle set 的操作就好了
。效率取决于这个 disjoint set 的实现，用 sparse 矩阵方式可做。
我十几年前就写过这样一个程序，用来计算 2D GUI 每次更新渲染时对应到屏幕上的
dirty set，非常简单，效率也很好。
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
p*r
101 楼
对的，这是几何类题目的常见套路题，没搞过ACM不知道套路确实挺难
Line Sweep 可以解决这些，链接在
https://www.topcoder.com/community/data-science/data-science-tutorials/line-
sweep-algorithms/
【在 t*****3 的大作中提到】
: swipe line，见topcoder的一篇tutorial。
s*n
102 楼
因为很多都是刷题进去的 不考考别人怎么对得起度过的光阴
【在 x********u 的大作中提到】
: 这就是我喜欢非老中面世的原因.
: 中国人出的题都偏难, 无它, 显摆自己厉害罢了.
: 你说出这种topcoder里的题有意义吗?
: 我碰巧接触过, 就做得出.
: 没碰过, 牛吨他师傅来了都搞不定.
【在 x********u 的大作中提到】
: 这就是我喜欢非老中面世的原因.
: 中国人出的题都偏难, 无它, 显摆自己厉害罢了.
: 你说出这种topcoder里的题有意义吗?
: 我碰巧接触过, 就做得出.
: 没碰过, 牛吨他师傅来了都搞不定.
b*e
103 楼
大哥，真不怕遭雷劈么？
【在 a*****e 的大作中提到】
: 这个题相当简单，是从 rectangle set 映射到 disjoint rectangle set 的操作。然
: 后可以继续分解为将单个 rectangle 插入到 disjoint rectangle set 的操作就好了
: 。效率取决于这个 disjoint set 的实现，用 sparse 矩阵方式可做。
: 我十几年前就写过这样一个程序，用来计算 2D GUI 每次更新渲染时对应到屏幕上的
: dirty set，非常简单，效率也很好。
【在 a*****e 的大作中提到】
: 这个题相当简单，是从 rectangle set 映射到 disjoint rectangle set 的操作。然
: 后可以继续分解为将单个 rectangle 插入到 disjoint rectangle set 的操作就好了
: 。效率取决于这个 disjoint set 的实现，用 sparse 矩阵方式可做。
: 我十几年前就写过这样一个程序，用来计算 2D GUI 每次更新渲染时对应到屏幕上的
: dirty set，非常简单，效率也很好。
h*n
104 楼
现在的人都怎么了？
你花了n个小时想出来的思路，如果没有注释的话让别人45分钟看懂都不容易，你居然
让人现场写bug free代码，还“简单”？
我也给你出道简单题：如果只有fp32的加减乘和位运算指令，怎么实现符合c99标准，
返回bitexact结果的fp32 fmod（）函数？
对我来说就是十几行代码的事儿。给你45分钟试试。
【在 a*****e 的大作中提到】
: 这个题相当简单，是从 rectangle set 映射到 disjoint rectangle set 的操作。然
: 后可以继续分解为将单个 rectangle 插入到 disjoint rectangle set 的操作就好了
: 。效率取决于这个 disjoint set 的实现，用 sparse 矩阵方式可做。
: 我十几年前就写过这样一个程序，用来计算 2D GUI 每次更新渲染时对应到屏幕上的
: dirty set，非常简单，效率也很好。
你花了n个小时想出来的思路，如果没有注释的话让别人45分钟看懂都不容易，你居然
让人现场写bug free代码，还“简单”？
我也给你出道简单题：如果只有fp32的加减乘和位运算指令，怎么实现符合c99标准，
返回bitexact结果的fp32 fmod（）函数？
对我来说就是十几行代码的事儿。给你45分钟试试。
【在 a*****e 的大作中提到】
: 这个题相当简单，是从 rectangle set 映射到 disjoint rectangle set 的操作。然
: 后可以继续分解为将单个 rectangle 插入到 disjoint rectangle set 的操作就好了
: 。效率取决于这个 disjoint set 的实现，用 sparse 矩阵方式可做。
: 我十几年前就写过这样一个程序，用来计算 2D GUI 每次更新渲染时对应到屏幕上的
: dirty set，非常简单，效率也很好。
a*e
105 楼
思路在那里，也很简单，至少我认为比 topcoder 上那个 line sweep 的解法写起来简
单，45 分钟写个大概不成问题。效率问题可以讨论。
【在 b***e 的大作中提到】
: 大哥，真不怕遭雷劈么？
单，45 分钟写个大概不成问题。效率问题可以讨论。
【在 b***e 的大作中提到】
: 大哥，真不怕遭雷劈么？
a*e
106 楼
大多数面试只是看你的解题思路，和写程序的基本功，水平在那里，有点小 bug 有什
么关系。起码我面别人都是本着这个指导思想。
你要是觉得我的解题思路不对，欢迎指正。
另外，你说的题我现在做不了，不过如果面试官愿意讲讲 ieee754 和 c99 标准是什么
，我倒是可以和他商讨一下解法。
【在 h*********n 的大作中提到】
: 现在的人都怎么了？
: 你花了n个小时想出来的思路，如果没有注释的话让别人45分钟看懂都不容易，你居然
: 让人现场写bug free代码，还“简单”？
: 我也给你出道简单题：如果只有fp32的加减乘和位运算指令，怎么实现符合c99标准，
: 返回bitexact结果的fp32 fmod（）函数？
: 对我来说就是十几行代码的事儿。给你45分钟试试。
么关系。起码我面别人都是本着这个指导思想。
你要是觉得我的解题思路不对，欢迎指正。
另外，你说的题我现在做不了，不过如果面试官愿意讲讲 ieee754 和 c99 标准是什么
，我倒是可以和他商讨一下解法。
【在 h*********n 的大作中提到】
: 现在的人都怎么了？
: 你花了n个小时想出来的思路，如果没有注释的话让别人45分钟看懂都不容易，你居然
: 让人现场写bug free代码，还“简单”？
: 我也给你出道简单题：如果只有fp32的加减乘和位运算指令，怎么实现符合c99标准，
: 返回bitexact结果的fp32 fmod（）函数？
: 对我来说就是十几行代码的事儿。给你45分钟试试。
b*e
107 楼
So what's your point? It is normal to have such questions in phone
interviews? Seriously? Especially in for a candidate you are supposed to
help? And you'd say this question is "very easy". Fuck dude, this fucking
45 mins include "hello", "how are you" shit and introduce yourself shit etc.
This shit is not like you go there and get your shit head down and start
to code.
And dude, this is not fucking asking you for a "大概". This is fucking
Google interview and chances are, "大概" is not meeting the bar. And fuck
dude, no one is fucking "discussing" performance issue here with you in an
interview. You are supposed to tell it. Overall dude, what da fuck are
you talking about? I am not understanding any of it. 你丫是不是被劈多了就
不怕了？
【在 a*****e 的大作中提到】
: 思路在那里，也很简单，至少我认为比 topcoder 上那个 line sweep 的解法写起来简
: 单，45 分钟写个大概不成问题。效率问题可以讨论。
interviews? Seriously? Especially in for a candidate you are supposed to
help? And you'd say this question is "very easy". Fuck dude, this fucking
45 mins include "hello", "how are you" shit and introduce yourself shit etc.
This shit is not like you go there and get your shit head down and start
to code.
And dude, this is not fucking asking you for a "大概". This is fucking
Google interview and chances are, "大概" is not meeting the bar. And fuck
dude, no one is fucking "discussing" performance issue here with you in an
interview. You are supposed to tell it. Overall dude, what da fuck are
you talking about? I am not understanding any of it. 你丫是不是被劈多了就
不怕了？
【在 a*****e 的大作中提到】
: 思路在那里，也很简单，至少我认为比 topcoder 上那个 line sweep 的解法写起来简
: 单，45 分钟写个大概不成问题。效率问题可以讨论。
x*k
108 楼
这楼不是拿来bso。你觉得简单，恭喜你水平高。现在讨论的是这题适不适合电面。就
算不考虑老中帮，这题也过分了。
就好像说，请用O（N）的效率实现substring search，面试的要是不知道kmp就挂了。
lz不知道sweep line也挂了。
另外针对显示屏幕的sparse矩阵容易，要是scale是2M*2M你怎么办？
【在 a*****e 的大作中提到】
: 这个题相当简单，是从 rectangle set 映射到 disjoint rectangle set 的操作。然
: 后可以继续分解为将单个 rectangle 插入到 disjoint rectangle set 的操作就好了
: 。效率取决于这个 disjoint set 的实现，用 sparse 矩阵方式可做。
: 我十几年前就写过这样一个程序，用来计算 2D GUI 每次更新渲染时对应到屏幕上的
: dirty set，非常简单，效率也很好。
算不考虑老中帮，这题也过分了。
就好像说，请用O（N）的效率实现substring search，面试的要是不知道kmp就挂了。
lz不知道sweep line也挂了。
另外针对显示屏幕的sparse矩阵容易，要是scale是2M*2M你怎么办？
【在 a*****e 的大作中提到】
: 这个题相当简单，是从 rectangle set 映射到 disjoint rectangle set 的操作。然
: 后可以继续分解为将单个 rectangle 插入到 disjoint rectangle set 的操作就好了
: 。效率取决于这个 disjoint set 的实现，用 sparse 矩阵方式可做。
: 我十几年前就写过这样一个程序，用来计算 2D GUI 每次更新渲染时对应到屏幕上的
: dirty set，非常简单，效率也很好。
x*k
109 楼
一般这种考知识面的题应该出多道，尤其是这种难题，面试者能回答对一道就应该放过
。
。
T*u
110 楼
过程不是independent的
【在 k****r 的大作中提到】
: A U B U C = A + B + C - AB - AC -BC + ABC
: 以此类推S个矩形的并集，只需要写出两个矩形相交的function，再反复调用即可。
【在 k****r 的大作中提到】
: A U B U C = A + B + C - AB - AC -BC + ABC
: 以此类推S个矩形的并集，只需要写出两个矩形相交的function，再反复调用即可。
L*Y
111 楼
收到拒信了...
“Thank you for taking the time out to talk to us. We carefully reviewed
your candidature, and unfortunately we would not be able to move forward in
the process.”
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
“Thank you for taking the time out to talk to us. We carefully reviewed
your candidature, and unfortunately we would not be able to move forward in
the process.”
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
s*r
112 楼
take it easy，绿面屡败，最后拿到offer很多。真跟高考复读一样，差的就是临场发
挥和运气
in
【在 L****Y 的大作中提到】
: 收到拒信了...
: “Thank you for taking the time out to talk to us. We carefully reviewed
: your candidature, and unfortunately we would not be able to move forward in
: the process.”
挥和运气
in
【在 L****Y 的大作中提到】
: 收到拒信了...
: “Thank you for taking the time out to talk to us. We carefully reviewed
: your candidature, and unfortunately we would not be able to move forward in
: the process.”
x*k
113 楼
move on吧，坚持一下，机会总会有的。想想现在总比08/09形势好。
in
【在 L****Y 的大作中提到】
: 收到拒信了...
: “Thank you for taking the time out to talk to us. We carefully reviewed
: your candidature, and unfortunately we would not be able to move forward in
: the process.”
in
【在 L****Y 的大作中提到】
: 收到拒信了...
: “Thank you for taking the time out to talk to us. We carefully reviewed
: your candidature, and unfortunately we would not be able to move forward in
: the process.”
w*n
114 楼
貌似这是coursera 算法I里讲的原题。。。
k*r
115 楼
说这题very easy 是有点bso的嫌疑
不过公正的说，这个把rectangle set 转换成disjoint set的思路确实是比较简便易行
的，而且对这类题的变型具有普适性
另外一个思路是转化为hisogram
这两个思路练熟了，大部分几何题，包括这道题，是可以半小时搞定
不过公正的说，这个把rectangle set 转换成disjoint set的思路确实是比较简便易行
的，而且对这类题的变型具有普适性
另外一个思路是转化为hisogram
这两个思路练熟了，大部分几何题，包括这道题，是可以半小时搞定
w*p
116 楼
面试这种就是做出来不见得是水平，没做出来，也不见得没水平的题，不太适合做店面
题。
这种没做过的，就是纯粹运气。
我在看的时候也就2分钟左右，想到scan line。 之前也没做过，看过。目前没太做题。
不过要是在面试的压力下，很肯能会想偏了。
我一般是前几天在钻什么，面试的时候不由自主的就套上了。然后就跪了。
【在 n******n 的大作中提到】
: 不是吧。这题考的是知识面。有几个人能直接在45分钟发现scan line算法？
题。
这种没做过的，就是纯粹运气。
我在看的时候也就2分钟左右，想到scan line。 之前也没做过，看过。目前没太做题。
不过要是在面试的压力下，很肯能会想偏了。
我一般是前几天在钻什么，面试的时候不由自主的就套上了。然后就跪了。
【在 n******n 的大作中提到】
: 不是吧。这题考的是知识面。有几个人能直接在45分钟发现scan line算法？
h*d
117 楼
我做的谷歌家的电面就很容易，感觉还是看运气
【在 h*********n 的大作中提到】
: 不正常。
【在 h*********n 的大作中提到】
: 不正常。
e*i
118 楼
@alanine, Dude, if u are so bull, what not show ur code?
F*n
119 楼
我觉得这个题出得挺好的，
O(n^2)的算法不难写，
更好的算法是大牛
in
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
O(n^2)的算法不难写，
更好的算法是大牛
in
【在 L****Y 的大作中提到】
: G的第一面，听口音是个国人大哥。
: 没做出来，好郁闷...
: Suppose we are given S rectangles on 2 dimensional space:
: 1) each one is specified x1, y1, x2, y2
: 2) calculate the area covered by these S rectangles.
l*0
120 楼
电面怎么面啊？是电话吗？电话怎么写代码？还是online面试？
A*o
121 楼
都是牛人啊
F*n
122 楼
不用 line sweep 的简单解法：
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.List;
public class Aggregation
{
protected List rects;
protected Aggregation overlap;
public Aggregation()
{
this.rects = new ArrayList<>();
this.overlap = new Aggregation();
}
public void add(Rectangle2D r)
{
List intersects = new ArrayList<>(this.rects.size());
for (Rectangle2D rect : this.rects)
{
if (r.equals(rect)) return;
if (r.intersects(rect))
{
Rectangle2D dest = new Rectangle2D.Double();
Rectangle2D.intersect(r, rect, dest);
intersects.add(dest);
}
}
this.rects.add(r);
for (Rectangle2D intersect : intersects) {
this.overlap.add(intersect);
}
}
public double calculateArea()
{
if (this.rects.size() == 0) return 0; // forgot this one:)
double area = 0;
for (Rectangle2D rect : this.rects)
{
area += rect.getWidth() * rect.getHeight();
}
return area - this.overlap.calculateArea();
}
}
import java.awt.geom.Rectangle2D;
import java.util.ArrayList;
import java.util.List;
public class Aggregation
{
protected List
protected Aggregation overlap;
public Aggregation()
{
this.rects = new ArrayList<>();
this.overlap = new Aggregation();
}
public void add(Rectangle2D r)
{
List
for (Rectangle2D rect : this.rects)
{
if (r.equals(rect)) return;
if (r.intersects(rect))
{
Rectangle2D dest = new Rectangle2D.Double();
Rectangle2D.intersect(r, rect, dest);
intersects.add(dest);
}
}
this.rects.add(r);
for (Rectangle2D intersect : intersects) {
this.overlap.add(intersect);
}
}
public double calculateArea()
{
if (this.rects.size() == 0) return 0; // forgot this one:)
double area = 0;
for (Rectangle2D rect : this.rects)
{
area += rect.getWidth() * rect.getHeight();
}
return area - this.overlap.calculateArea();
}
}
e*i
123 楼
@Foxman, ur code not only loops forever, but also the idea behind it is
totally wrong. What if 3 rectangles intersect?
totally wrong. What if 3 rectangles intersect?
F*n
124 楼
有些边界条件忘了加，但这个Idea不会loop forever,
第一层Aggregation contains rects
第二层Aggregation contains intersections of rects,
第三层Aggregation contains intersections of intersections,
...
只要rects不相等，必然最后有一层没有intersection
多个Rectangle也没问题，这是一个递归迭代
【在 e*******i 的大作中提到】
: @Foxman, ur code not only loops forever, but also the idea behind it is
: totally wrong. What if 3 rectangles intersect?
第一层Aggregation contains rects
第二层Aggregation contains intersections of rects,
第三层Aggregation contains intersections of intersections,
...
只要rects不相等，必然最后有一层没有intersection
多个Rectangle也没问题，这是一个递归迭代
【在 e*******i 的大作中提到】
: @Foxman, ur code not only loops forever, but also the idea behind it is
: totally wrong. What if 3 rectangles intersect?
e*i
125 楼
@Foxman, Please test ur code yourself, u will see what is wrong even after
ur changes
ur changes
m*t
126 楼
test 相交的所有可能性是 exponential 的解法 ：）最坏的情况下所有的 rectangle
都有重叠的部分 （重叠的层数是 N）。暴力递归很可能挂掉在半途。
【在 F****n 的大作中提到】
: 有些边界条件忘了加，但这个Idea不会loop forever,
: 第一层Aggregation contains rects
: 第二层Aggregation contains intersections of rects,
: 第三层Aggregation contains intersections of intersections,
: ...
: 只要rects不相等，必然最后有一层没有intersection
: 多个Rectangle也没问题，这是一个递归迭代
都有重叠的部分 （重叠的层数是 N）。暴力递归很可能挂掉在半途。
【在 F****n 的大作中提到】
: 有些边界条件忘了加，但这个Idea不会loop forever,
: 第一层Aggregation contains rects
: 第二层Aggregation contains intersections of rects,
: 第三层Aggregation contains intersections of intersections,
: ...
: 只要rects不相等，必然最后有一层没有intersection
: 多个Rectangle也没问题，这是一个递归迭代
相关阅读
很黄很暴力啊！话说你的菊花真是漂亮啊！Re: 大家申请几所学校阿？青春就爱囧系列^^ (转载)这不是散步（图）zz最新囧事集合！看看看看你不笑都不行！.女城管你不害人就是给社会做贡献了（继续搞笑）关于那篇'致猥琐清华男'的Re: 全然败坏的永生进来 (转载)麦当劳是否会腐烂?(连续24天，5月19最新更新)资本主义道路在中国是不能成功的”——邓小平 (转载)彪悍：爷不是你的小浣熊，玩不出你的其乐无穷SB平稳奥秘：办好关键在敏感词 zz游行(zt)旁边这个要谋反啊！青媚狐"uptoyou”译成“上你” 女老师怒殴学生超级雷人的横批。。。 上联：春 下联：曾惊！叫aaa来拖车，结果它自己路上爆胎了 (转载)