y****r
发帖数: 17 | 1 今天面试给了一道数据结构题，哥们用个二叉树摆弄半天最后还是载了。
谁给说说咋整的
implement a data structure that stores non-overlaping line segments of the
form ((x1,0)(x2,1))(that is, the bottom vertex has y-coordinate 0, and the
top vertex has y-coordinate 1.)
Describe (in pseudocode) a data structure that:
A: when a new line segment is inserted, checks in O(log n) time (where n is
the number of line segments in the data structure) if the new line segment
intersects any of the original ones, and inserts it in the data structure in
O | a******t
发帖数: 100 | 2 A)
Given (a, 0) (b, 1)
Find how many x1's are smaller than a.
Find how many x2's are smaller than b.
If the number is not the same, there is an intersection.
B) Find how many x1's are smaller than x
Find how many x2's are smaller than x.
return the smaller one.
【在 y****r 的大作中提到】
: 今天面试给了一道数据结构题，哥们用个二叉树摆弄半天最后还是载了。
: 谁给说说咋整的
: implement a data structure that stores non-overlaping line segments of the
: form ((x1,0)(x2,1))(that is, the bottom vertex has y-coordinate 0, and the
: top vertex has y-coordinate 1.)
: Describe (in pseudocode) a data structure that:
: A: when a new line segment is inserted, checks in O(log n) time (where n is
: the number of line segments in the data structure) if the new line segment
: intersects any of the original ones, and inserts it in the data structure in
: O
| a****s
发帖数: 7 | 3 A is nice, but B is wrong I think.
For B, we can just define a compare function of x and a segment, and use this
compare function to search the tree.
【在 a******t 的大作中提到】
: A)
: Given (a, 0) (b, 1)
: Find how many x1's are smaller than a.
: Find how many x2's are smaller than b.
: If the number is not the same, there is an intersection.
: B) Find how many x1's are smaller than x
: Find how many x2's are smaller than x.
: return the smaller one.
| r***u
发帖数: 241 | 4 looks similar to a section in CLRS algorithm textbook
【在 y****r 的大作中提到】
: 今天面试给了一道数据结构题，哥们用个二叉树摆弄半天最后还是载了。
: 谁给说说咋整的
: implement a data structure that stores non-overlaping line segments of the
: form ((x1,0)(x2,1))(that is, the bottom vertex has y-coordinate 0, and the
: top vertex has y-coordinate 1.)
: Describe (in pseudocode) a data structure that:
: A: when a new line segment is inserted, checks in O(log n) time (where n is
: the number of line segments in the data structure) if the new line segment
: intersects any of the original ones, and inserts it in the data structure in
: O
| a******t
发帖数: 100 | 5
I just defined the segment as (x, 0), (x, 1).
【在 a****s 的大作中提到】
: A is nice, but B is wrong I think.
: For B, we can just define a compare function of x and a segment, and use this
: compare function to search the tree.
| r****c
发帖数: 2585 | 6 why A) is correct?
even the number is same, it also can have intersection
the simple example is
two lines from (0,0) (4,1), (3,0) (1,1)
what about the line (2,0) (2,1)?
the data structure matters
hehe
try to think deeper
【在 a******t 的大作中提到】
: A)
: Given (a, 0) (b, 1)
: Find how many x1's are smaller than a.
: Find how many x2's are smaller than b.
: If the number is not the same, there is an intersection.
: B) Find how many x1's are smaller than x
: Find how many x2's are smaller than x.
: return the smaller one.
| c*****t
发帖数: 1879 | 7
These two segments intersect. One of the cannot be in the structure.
【在 r****c 的大作中提到】
: why A) is correct?
: even the number is same, it also can have intersection
: the simple example is
: two lines from (0,0) (4,1), (3,0) (1,1)
: what about the line (2,0) (2,1)?
: the data structure matters
: hehe
: try to think deeper
| c*****t
发帖数: 1879 | 8 B is wrong. Just consider a case where a slanted segment passing through
the point. Moving slight left and right will not change your solution but
# of segments to the left of point is actually different.
A solution simply: use binary search to search the top points, goes from
this point through the point to be checked and compute the lower point
position. Check if this segment intersects any (just need to check neighbors).
If no intersections, solution found. If intersect, keep trying.
【在 a******t 的大作中提到】
: A)
: Given (a, 0) (b, 1)
: Find how many x1's are smaller than a.
: Find how many x2's are smaller than b.
: If the number is not the same, there is an intersection.
: B) Find how many x1's are smaller than x
: Find how many x2's are smaller than x.
: return the smaller one.
| r****c
发帖数: 2585 | 9 hehe
The problem only say, the lines do not overlap, it does not say
it is not intersect.
It only require for one new line, if there is intersection,
then do not put into the data structure.
Anyway, your explanation is also correct, the problem is misleading
【在 c*****t 的大作中提到】
: B is wrong. Just consider a case where a slanted segment passing through
: the point. Moving slight left and right will not change your solution but
: # of segments to the left of point is actually different.
: A solution simply: use binary search to search the top points, goes from
: this point through the point to be checked and compute the lower point
: position. Check if this segment intersects any (just need to check neighbors).
: If no intersections, solution found. If intersect, keep trying.
| r****c
发帖数: 2585 | 10 If there is no intersection, then too simple
【在 c*****t 的大作中提到】
: B is wrong. Just consider a case where a slanted segment passing through
: the point. Moving slight left and right will not change your solution but
: # of segments to the left of point is actually different.
: A solution simply: use binary search to search the top points, goes from
: this point through the point to be checked and compute the lower point
: position. Check if this segment intersects any (just need to check neighbors).
: If no intersections, solution found. If intersect, keep trying.
| r****c
发帖数: 2585 | 11 If we assume in the structure there is not intersection
of the lines, then B is also very simple, just binary search on
the x_1, find the x_1 such that the line begin with x_i is
at left and x_i+1 is at right. hoho
【在 c*****t 的大作中提到】
: B is wrong. Just consider a case where a slanted segment passing through
: the point. Moving slight left and right will not change your solution but
: # of segments to the left of point is actually different.
: A solution simply: use binary search to search the top points, goes from
: this point through the point to be checked and compute the lower point
: position. Check if this segment intersects any (just need to check neighbors).
: If no intersections, solution found. If intersect, keep trying.
| a******t
发帖数: 100 | 12
Depends on how you define left. I think a segment is on the left side
of (x, y) if and only if both ends of the segment is on the left side of
segment (x, 0) (x, 1). You may define different segment according to
(x, y), but the idea is the same. It is only more complicated to compute
the points on y = 0 and y = 1.
【在 c*****t 的大作中提到】
: B is wrong. Just consider a case where a slanted segment passing through
: the point. Moving slight left and right will not change your solution but
: # of segments to the left of point is actually different.
: A solution simply: use binary search to search the top points, goes from
: this point through the point to be checked and compute the lower point
: position. Check if this segment intersects any (just need to check neighbors).
: If no intersections, solution found. If intersect, keep trying.
| a******t
发帖数: 100 | 13
Wrong.
【在 r****c 的大作中提到】
: If we assume in the structure there is not intersection
: of the lines, then B is also very simple, just binary search on
: the x_1, find the x_1 such that the line begin with x_i is
: at left and x_i+1 is at right. hoho
| j********e
发帖数: 124 | 14 Let's see if this is a solution to the most general case:
i.e., in the n given line segaments, there are zero or some intersections
already.
Denotation: For a line segament ( (x1,0)(x2,1) ), we use to denote it.
Base observation: For two segaments and , assuem a1 < a2. They
intersect
if and only if b2
Now the data structure and algorithms:
Given n segaments ... , sort them according to ai
values.
Now, we use ... to denote the
【在 r****c 的大作中提到】
: why A) is correct?
: even the number is same, it also can have intersection
: the simple example is
: two lines from (0,0) (4,1), (3,0) (1,1)
: what about the line (2,0) (2,1)?
: the data structure matters
: hehe
: try to think deeper
|
|
