Another interview problem ~ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

Another interview problem ~

Another interview problem ~# JobHunting - 待字闺中

t*a2010-08-28 07:08

1 楼

Given a 2 dimensional plane in which there are n points. Give an algorithm
to
generate the equation of a line that divides the plane such that there are n
/2 points
on one side and n/2 points on the other.

S*n2010-08-28 07:08

2 楼

分类器

n

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

: Given a 2 dimensional plane in which there are n points. Give an algorithm
: to
: generate the equation of a line that divides the plane such that there are n
: /2 points
: on one side and n/2 points on the other.

t*a2010-08-28 07:08

3 楼

Man, could you explain it a little bit more that someone can implement it.

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

: 分类器
:
: n

h*k2010-08-28 07:08

4 楼

分类器处理的问题不同。对于分类器，输入的点本来就标定为两类。这个问题中输入点
没有区别。

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

: 分类器
:
: n

h*k2010-08-28 07:08

5 楼

如果用二分法，似乎可以做到O(n)。
选一个新点，在所有的输入的n个点的左下方。然后计算每个输入点到新点的连线的斜
率，得到一个大小为n的实数数组。现在题目变为在这个数组中找median element。

n

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

t*a2010-08-28 07:08

6 楼

这个办法挺好。
但是如果多个斜率相等且等于median element的时候，这条线无法分开那些点。

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

: 如果用二分法，似乎可以做到O(n)。
: 选一个新点，在所有的输入的n个点的左下方。然后计算每个输入点到新点的连线的斜
: 率，得到一个大小为n的实数数组。现在题目变为在这个数组中找median element。
:
: n

h*k2010-08-28 07:08

7 楼

在线上的点其实可以看成在线的哪一边都行。
如果面试官一定要深究，可以这么做。假设在这条直线上一共有m个点，直线一边是k个
点，则另一边是n-k-m个点。找到直线上的第n/2-k个点，然后以这个点重新构建一个直
线，它的斜率和原来的直线斜率相差一个极小值，并使得m个点中的前n/2-k点和k点在
直线的一边。

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

: 这个办法挺好。
: 但是如果多个斜率相等且等于median element的时候，这条线无法分开那些点。