L****Y
发帖数: 355 | 1 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. |
f*******t
发帖数: 7549 | 2 暴力做法蛮简单的吧，所有矩形面积之和减掉矩形相交面积之和
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
} |
a********5
发帖数: 1631 | |
b********0
发帖数: 62 | 4 如果有三块及以上重合 好像就不行了吧
【在 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)
|
x**********g
发帖数: 44 | 5 x,y 是int吗？如果是，唯一能想到的用matrix（all 0s），扫一个个rectangles 变1
，最后数1的个数~~当然实在太暴力了 |
Y**G
发帖数: 1089 | 6 下面的代码我测试通过了。
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);
}
} |
t*****3
发帖数: 112 | 7 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.
|
w******n
发帖数: 61 | 8 (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*****n
发帖数: 246 | 9 我了个擦。。。为啥电面考这么难啊。。。sweep line algorithm啊。。。这面试无论
如何都得跪吧。。。 |
b***e
发帖数: 1419 | 10 顶。
【在 t*****3 的大作中提到】
: swipe line，见topcoder的一篇tutorial。
|
|
|
h**********9
发帖数: 43 | 11 请问坐标都是int吗？如果是的话，能不能把它离散化，用一个一个的像素点来表示一
个个矩形（被矩形覆盖的点设为1，否则为0），最后算一下1的个数。时间复杂度有点
高，不过不这么算真的挺复杂的。 |
a********m
发帖数: 15480 | 12 g店面正常差不多是这个难度。
【在 l*****n 的大作中提到】
: 我了个擦。。。为啥电面考这么难啊。。。sweep line algorithm啊。。。这面试无论
: 如何都得跪吧。。。
|
a********5
发帖数: 1631 | |
f*****w
发帖数: 2602 | 14 似乎计算几何里面算contour有标准算法 如果能用上标准算法就没啥难度
不过那个算法连叫啥我都早就还给老师了 |
x********u
发帖数: 1150 | 15 这就是我喜欢非老中面世的原因.
中国人出的题都偏难, 无它, 显摆自己厉害罢了.
你说出这种topcoder里的题有意义吗?
我碰巧接触过, 就做得出.
没碰过, 牛吨他师傅来了都搞不定. |
n******n
发帖数: 12088 | 16 不是吧。这题考的是知识面。有几个人能直接在45分钟发现scan line算法？
【在 a********m 的大作中提到】
: g店面正常差不多是这个难度。
|
B*******1
发帖数: 2454 | 17 那么我跪了，这个我以后就拿来面烙印。
【在 a********m 的大作中提到】
: g店面正常差不多是这个难度。
|
b*****n
发帖数: 618 | 18 这还让人活么
【在 a********m 的大作中提到】
: g店面正常差不多是这个难度。
|
b*****n
发帖数: 618 | 19 大牛所言及时，对三哥这个题都算便宜他们了
【在 B*******1 的大作中提到】
: 那么我跪了，这个我以后就拿来面烙印。
|
h*********n
发帖数: 11319 | 20 不正常。
【在 a********m 的大作中提到】
: g店面正常差不多是这个难度。
|
|
|
L****Y
发帖数: 355 | 21 大哥，不会是你面的吧... 手下留情...
【在 a********m 的大作中提到】
: g店面正常差不多是这个难度。
|
a********m
发帖数: 15480 | 22 冷静点应该能想到吧。从最直接的2维canvas描点，仔细考虑优化一下到1维扫描线也是
正常思路，毕竟也没啥其他的方向。难道是俺2年前看的那遍cc150还有残留印象所以不
觉得很离谱？
代码确实烦，俺是肯定写不完。但是应该意思到就差不多。
G有人店面比onsite简单一点，有人直接上onsite的题目。记得讨论哪个比较好的时候
倾向后者的多一些。
【在 n******n 的大作中提到】
: 不是吧。这题考的是知识面。有几个人能直接在45分钟发现scan line算法？
|
a********m
发帖数: 15480 | 23 不可能是。。。。俺问dp，比较容易聊天和提示。。。下手轻重区别在给分上。。。。
【在 L****Y 的大作中提到】
: 大哥，不会是你面的吧... 手下留情...
|
n******n
发帖数: 12088 | 24 这题on-site也过分了。测能力，而不是测知识，除非楼主自己强调计算几何背景
【在 a********m 的大作中提到】
: 冷静点应该能想到吧。从最直接的2维canvas描点，仔细考虑优化一下到1维扫描线也是
: 正常思路，毕竟也没啥其他的方向。难道是俺2年前看的那遍cc150还有残留印象所以不
: 觉得很离谱？
: 代码确实烦，俺是肯定写不完。但是应该意思到就差不多。
: G有人店面比onsite简单一点，有人直接上onsite的题目。记得讨论哪个比较好的时候
: 倾向后者的多一些。
|
m******a
发帖数: 84 | |
k****r
发帖数: 807 | 26 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.
|
a********m
发帖数: 15480 | 27 不脚着和几何有啥关系和需要啥背景知识。。。。经典skyline注水那题算几何题么？
如果你脚着算的话那这题也算吧。。。。
俺脚着如果想到几何背景那10有(关键字)是想歪了。除非是面计算机图形方面的职位。
【在 n******n 的大作中提到】
: 这题on-site也过分了。测能力，而不是测知识，除非楼主自己强调计算几何背景
|
L****Y
发帖数: 355 | 28 俺没有计算几何背景...
【在 n******n 的大作中提到】
: 这题on-site也过分了。测能力，而不是测知识，除非楼主自己强调计算几何背景
|
a********m
发帖数: 15480 | 29 这个俺脚着太难了。。。。
矩阵相交n种情况呀。这么算是指数复杂度了吧。
【在 k****r 的大作中提到】
: A U B U C = A + B + C - AB - AC -BC + ABC
: 以此类推S个矩形的并集，只需要写出两个矩形相交的function，再反复调用即可。
|
n******n
发帖数: 12088 | 30 想当然。你自己写写看
【在 k****r 的大作中提到】
: A U B U C = A + B + C - AB - AC -BC + ABC
: 以此类推S个矩形的并集，只需要写出两个矩形相交的function，再反复调用即可。
|
|
|
s*****e
发帖数: 1679 | 31 我也觉得过了，这个难度到底是希望别人做出来还是做不出来好？ |
n******n
发帖数: 12088 | 32 那题的nlogn解法，没竞赛训练过，有几个人能现想出来？
【在 a********m 的大作中提到】
: 不脚着和几何有啥关系和需要啥背景知识。。。。经典skyline注水那题算几何题么？
: 如果你脚着算的话那这题也算吧。。。。
: 俺脚着如果想到几何背景那10有(关键字)是想歪了。除非是面计算机图形方面的职位。
|
a********m
发帖数: 15480 | 33 思路对最重要。最佳算法确实很多是当场写不出来的。
这题俺脚着把扫描函数单独写出来，用最土的办法实现，然后告诉说这块的最优算法需
要慢慢写就可以过关。这种麻烦的复杂度如果是俺都不是必须要求，因为俺自己想出来
也费半天劲，太技巧了，不过如果能说出来算可以加分吧。
【在 n******n 的大作中提到】
: 那题的nlogn解法，没竞赛训练过，有几个人能现想出来？
|
r*g
发帖数: 186 | 34 好难啊 明天我也要面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.
|
r*g
发帖数: 186 | 35 我记得以前有个关于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.
|
a********m
发帖数: 15480 | 36 这种原题你来考烙印？难道你就是传说中的卧底？
【在 B*******1 的大作中提到】
: 那么我跪了，这个我以后就拿来面烙印。
|
a********m
发帖数: 15480 | 37 记住一要冷静。二要一步步来，通常从最土的方法出发比较好，给提示也容易。一下想
太多很容易回不来，面试官想帮你都很难。
【在 r*g 的大作中提到】
: 好难啊 明天我也要面G 压力好大
|
s****a
发帖数: 794 | 38 这个应该是最标准的二维线段数吧
估计他只期望你写出一个最简单的每次刷新面积的做法
用线段数应该只是说说思路就好吧
大家碰到难题不要怕 想到什么说什么 能把想到的写出来就好 难题会基础算法再在讨
论中得出更好的算法基本就能在面试中得高分了 反倒简单题要小心coding 小错误就可
能跪掉 |
A*******e
发帖数: 2419 | 39 二维线段数？最简单的每次刷新面积的做法？
【在 s****a 的大作中提到】
: 这个应该是最标准的二维线段数吧
: 估计他只期望你写出一个最简单的每次刷新面积的做法
: 用线段数应该只是说说思路就好吧
: 大家碰到难题不要怕 想到什么说什么 能把想到的写出来就好 难题会基础算法再在讨
: 论中得出更好的算法基本就能在面试中得高分了 反倒简单题要小心coding 小错误就可
: 能跪掉
|
M****e
发帖数: 3715 | 40 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.
|
|
|
l*****v
发帖数: 122 | 41 妈呀，这道题拿过来面小印，10个人里面，能有1个通过G家店面吗？ |
m********1
发帖数: 31 | 42 弱弱的问一下， 这个题是不是信息给少了呀，rectangles只给两个点，不能确定这个
rectangle的大小吧。是不是默认所有的边都和x，y 轴平行呀？？ |
l******r
发帖数: 18699 | 43 我店面时问的是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.
|
s*****r
发帖数: 43070 | 44 个人感觉狗狗的店面比onsite难搞，俺店面就没pass过，最多到第二轮 |
c****d
发帖数: 2418 | 45 矩形的还好说，圆的咋算呢？
【在 l******r 的大作中提到】
: 我店面时问的是S个圆的cover 面积 给定的是圆心坐标和半径
: 这道题我答得相当完美
|
y**i
发帖数: 1112 | 46 感觉可以用求两个直方图面积的差来做：
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
发帖数: 18699 | 47 需要把笛卡尔坐标换成极坐标
【在 c****d 的大作中提到】
: 矩形的还好说，圆的咋算呢？
|
c****d
发帖数: 2418 | 48 看不出来换成极坐标的优势。。。
【在 l******r 的大作中提到】
: 需要把笛卡尔坐标换成极坐标
|
c******n
发帖数: 4965 | 49 基本上是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.
|
b*******y
发帖数: 2048 | |
|
|
x********u
发帖数: 1150 | 51 算了吧, 如果他们面世的题目和工作有关系的更不好整.
宁愿接受现在的虐待.
【在 b*******y 的大作中提到】
: 这种题和工作有半毛钱关系....
|
b*******i
发帖数: 20 | 52 好像很麻烦啊，匆匆想到下面三种解法，抛砖引玉。
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
发帖数: 20 | 53 看前面文章，有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+...
|
a********5
发帖数: 1631 | 54 这种题标准解法（未必是最优）应该是扫描线+二分。说标准意思是可以写出模板来，
类似的题一套就行了。
但是问题是真的45分钟可以搞定？我大二时候做类似的merge矩形的题，扫描线+二分，
光写码就写了快俩小时。。后面DEBUG什么的，POJ还出各种奇奇怪怪的问题，弄了两天
才过。。
【在 b*******i 的大作中提到】
: 看前面文章，有swipe line的方法，太高级了，学习了。
|
q***n
发帖数: 3594 | |
b*******i
发帖数: 20 | 56 恩，很难做完啊，太打击了，偶觉得我前面的弱智解法写完都勉强（一个解法也就需要
一个基本的求交函数反复调用，或者分割函数反复调用）
【在 a********5 的大作中提到】
: 这种题标准解法（未必是最优）应该是扫描线+二分。说标准意思是可以写出模板来，
: 类似的题一套就行了。
: 但是问题是真的45分钟可以搞定？我大二时候做类似的merge矩形的题，扫描线+二分，
: 光写码就写了快俩小时。。后面DEBUG什么的，POJ还出各种奇奇怪怪的问题，弄了两天
: 才过。。
|
a********5
发帖数: 1631 | 57 想了又想 好像也没啥特别好的办法
还有一种解法就是算S1+S2+S3+..+SN-S1S2-S1S3-...-SN-1SN + S1S2S3...
但是这个解法是指数级的
【在 b*******i 的大作中提到】
: 恩，很难做完啊，太打击了，偶觉得我前面的弱智解法写完都勉强（一个解法也就需要
: 一个基本的求交函数反复调用，或者分割函数反复调用）
|
E*H
发帖数: 1207 | 58 店面就这么难，直接跪了。
【在 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
发帖数: 108 | 59 坐标离散的话最弱的方法还挺简单的，弄两个数组分别存每个x最大和最小的y最后相加
就行。连续的话就想不起来了…… |
a*****e
发帖数: 1700 | 60 这个题相当简单，是从 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.
|
|
|
p*****r
发帖数: 1883 | 61
对的，这是几何类题目的常见套路题，没搞过ACM不知道套路确实挺难
Line Sweep 可以解决这些，链接在
https://www.topcoder.com/community/data-science/data-science-tutorials/line-
sweep-algorithms/
【在 t*****3 的大作中提到】
: swipe line，见topcoder的一篇tutorial。
|
s********n
发帖数: 4535 | 62 因为很多都是刷题进去的 不考考别人怎么对得起度过的光阴
【在 x********u 的大作中提到】
: 这就是我喜欢非老中面世的原因.
: 中国人出的题都偏难, 无它, 显摆自己厉害罢了.
: 你说出这种topcoder里的题有意义吗?
: 我碰巧接触过, 就做得出.
: 没碰过, 牛吨他师傅来了都搞不定.
|
b***e
发帖数: 1419 | 63 大哥，真不怕遭雷劈么？
【在 a*****e 的大作中提到】
: 这个题相当简单，是从 rectangle set 映射到 disjoint rectangle set 的操作。然
: 后可以继续分解为将单个 rectangle 插入到 disjoint rectangle set 的操作就好了
: 。效率取决于这个 disjoint set 的实现，用 sparse 矩阵方式可做。
: 我十几年前就写过这样一个程序，用来计算 2D GUI 每次更新渲染时对应到屏幕上的
: dirty set，非常简单，效率也很好。
|
h*********n
发帖数: 11319 | 64 现在的人都怎么了？
你花了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
发帖数: 1700 | 65 思路在那里，也很简单，至少我认为比 topcoder 上那个 line sweep 的解法写起来简
单，45 分钟写个大概不成问题。效率问题可以讨论。
【在 b***e 的大作中提到】
: 大哥，真不怕遭雷劈么？
|
a*****e
发帖数: 1700 | 66 大多数面试只是看你的解题思路，和写程序的基本功，水平在那里，有点小 bug 有什
么关系。起码我面别人都是本着这个指导思想。
你要是觉得我的解题思路不对，欢迎指正。
另外，你说的题我现在做不了，不过如果面试官愿意讲讲 ieee754 和 c99 标准是什么
，我倒是可以和他商讨一下解法。
【在 h*********n 的大作中提到】
: 现在的人都怎么了？
: 你花了n个小时想出来的思路，如果没有注释的话让别人45分钟看懂都不容易，你居然
: 让人现场写bug free代码，还“简单”？
: 我也给你出道简单题：如果只有fp32的加减乘和位运算指令，怎么实现符合c99标准，
: 返回bitexact结果的fp32 fmod（）函数？
: 对我来说就是十几行代码的事儿。给你45分钟试试。
|
b***e
发帖数: 1419 | 67 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 分钟写个大概不成问题。效率问题可以讨论。
|
x****k
发帖数: 2932 | 68 这楼不是拿来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，非常简单，效率也很好。
|
x****k
发帖数: 2932 | 69 一般这种考知识面的题应该出多道，尤其是这种难题，面试者能回答对一道就应该放过
。 |
T*****u
发帖数: 7103 | 70 过程不是independent的
【在 k****r 的大作中提到】
: A U B U C = A + B + C - AB - AC -BC + ABC
: 以此类推S个矩形的并集，只需要写出两个矩形相交的function，再反复调用即可。
|
|
|
L****Y
发帖数: 355 | 71 收到拒信了...
“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
发帖数: 43070 | 72 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.”
|
x****k
发帖数: 2932 | 73 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.”
|
w******n
发帖数: 61 | 74 貌似这是coursera 算法I里讲的原题。。。 |
k*******r
发帖数: 355 | 75 说这题very easy 是有点bso的嫌疑
不过公正的说，这个把rectangle set 转换成disjoint set的思路确实是比较简便易行
的，而且对这类题的变型具有普适性
另外一个思路是转化为hisogram
这两个思路练熟了，大部分几何题，包括这道题，是可以半小时搞定 |
w********p
发帖数: 948 | 76 面试这种就是做出来不见得是水平，没做出来，也不见得没水平的题，不太适合做店面
题。
这种没做过的，就是纯粹运气。
我在看的时候也就2分钟左右，想到scan line。 之前也没做过，看过。目前没太做题。
不过要是在面试的压力下，很肯能会想偏了。
我一般是前几天在钻什么，面试的时候不由自主的就套上了。然后就跪了。
【在 n******n 的大作中提到】
: 不是吧。这题考的是知识面。有几个人能直接在45分钟发现scan line算法？
|
h*d
发帖数: 19309 | 77 我做的谷歌家的电面就很容易，感觉还是看运气
【在 h*********n 的大作中提到】
: 不正常。
|
e*******i
发帖数: 56 | 78 @alanine, Dude, if u are so bull, what not show ur code? |
F****n
发帖数: 3271 | 79 我觉得这个题出得挺好的，
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
发帖数: 1012 | 80 电面怎么面啊？是电话吗？电话怎么写代码？还是online面试？ |
|
|
A*********o
发帖数: 48 | |
F****n
发帖数: 3271 | 82 不用 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();
}
} |
e*******i
发帖数: 56 | 83 @Foxman, ur code not only loops forever, but also the idea behind it is
totally wrong. What if 3 rectangles intersect? |
F****n
发帖数: 3271 | 84 有些边界条件忘了加，但这个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?
|
e*******i
发帖数: 56 | 85 @Foxman, Please test ur code yourself, u will see what is wrong even after
ur changes |
m*********t
发帖数: 527 | 86 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也没问题，这是一个递归迭代
|
