f******5
发帖数: 104 | 1 最近在看和计算几何的问题，不少问题需要这2个算法，
如果遇到用到扫描线或者interval tree， 涉及到delete操作，基本不可能写完代码吧。
网上也找不到怎么使用现成的data structure库可以用，如果面试的时候想到这2个算
法，怎么处理？
求教有经验的大牛
比如Hacking google interview中 的这道题：
Describe an algorithm that takes an unsorted array of axis-aligned
rectangles and returns any pair of rectangles that overlaps, if there is
such a pair. Axis-aligned means that all the rectangle sides are either
parallel or perpendicular to the x- and y-axis. You can assume that each
rectangle object has two variables in it: the x-y coordinates of the upper-
left corner and the bottom-right corner. |
H*****s
发帖数: 28 | 2 augmented interval tree被考过，还是需要熟悉一下的
吧。
【在 f******5 的大作中提到】
: 最近在看和计算几何的问题，不少问题需要这2个算法，
: 如果遇到用到扫描线或者interval tree， 涉及到delete操作，基本不可能写完代码吧。
: 网上也找不到怎么使用现成的data structure库可以用，如果面试的时候想到这2个算
: 法，怎么处理？
: 求教有经验的大牛
: 比如Hacking google interview中 的这道题：
: Describe an algorithm that takes an unsorted array of axis-aligned
: rectangles and returns any pair of rectangles that overlaps, if there is
: such a pair. Axis-aligned means that all the rectangle sides are either
: parallel or perpendicular to the x- and y-axis. You can assume that each
|
f******5
发帖数: 104 | |
n******n
发帖数: 12088 | 4 不可能熟悉所有题。遇到就认命
【在 H*****s 的大作中提到】
: augmented interval tree被考过，还是需要熟悉一下的
:
: 吧。
|
x*******9
发帖数: 138 | 5 跪吧。。。
除非你运气好还记得。。。
面试让写线段树。。。我觉得这真是日狗。。。 |
