MS 电面面经，攒人品 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

MS 电面面经，攒人品

MS 电面面经，攒人品# JobHunting - 待字闺中

m*n2010-03-19 07:03

1 楼

印度人，一个平面上有N个点，N很大，找到所有穿过3个以上点
的直线和这些点，要求空间和时间最优的算法。感觉答的不是太好，
只给了30分钟。我就是说把每个点A和其他点B的角度值存在哈希表里，
然后根据每个值B寻找其他有同样角度值的点C。找到穿过3个点的
线以后，再去找第4个点，以此类推。有没有更好的算法？

b*v2010-03-19 07:03

2 楼

我只能想得出O(N^3)的算法，也就是brutal force的办法

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

: 印度人，一个平面上有N个点，N很大，找到所有穿过3个以上点
: 的直线和这些点，要求空间和时间最优的算法。感觉答的不是太好，
: 只给了30分钟。我就是说把每个点A和其他点B的角度值存在哈希表里，
: 然后根据每个值B寻找其他有同样角度值的点C。找到穿过3个点的
: 线以后，再去找第4个点，以此类推。有没有更好的算法？

b*v2010-03-19 07:03

3 楼

遍历i=1, ..., N个点
以每个点i作为原点，计算其他(N-1)个点的角度，有相同的则记录下来
这样的复杂度是O(N^2)

【在 b******v 的大作中提到】

: 我只能想得出O(N^3)的算法，也就是brutal force的办法

c*f2010-03-19 07:03

4 楼

谢

s*n2010-03-19 07:03

5 楼

但是你怎么找相同的的角度呢，如果不hash那又是一个n,
如果hash的话，浮点数容易hash么？比如说最后一位不一样怎么处理？

【在 b******v 的大作中提到】

: 遍历i=1, ..., N个点
: 以每个点i作为原点，计算其他(N-1)个点的角度，有相同的则记录下来
: 这样的复杂度是O(N^2)

h*r2010-03-19 07:03

6 楼

这个不需要hash，把任何两点间（Xi，Yi），（Xj,Yj)构成的角度放在一个n×n矩阵里
即可。这个矩阵只需要上半三角或者下半三角。
最后按行遍历这个半三角矩阵，如果同一行中出现重复的角度，就把这些列数代表的点
print出来。

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

: 但是你怎么找相同的的角度呢，如果不hash那又是一个n,
: 如果hash的话，浮点数容易hash么？比如说最后一位不一样怎么处理？

r*o2010-03-19 07:03

7 楼

角度也是浮点数阿，怎么判断两个角度相等？设个门限?

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

: 这个不需要hash，把任何两点间（Xi，Yi），（Xj,Yj)构成的角度放在一个n×n矩阵里
: 即可。这个矩阵只需要上半三角或者下半三角。
: 最后按行遍历这个半三角矩阵，如果同一行中出现重复的角度，就把这些列数代表的点
: print出来。

i*a2010-03-19 07:03

8 楼

h*r2010-03-19 07:03

9 楼

浮点数也可以比较啊，只是需要有精度的取舍，规定一下比到小数点后哪一位。
真怕浮点数的话，这里没必要用浮点代表吧，比如角度等于2/27的用2.27表示不就行了。
算法，又不是算术。

【在 r****o 的大作中提到】

: 角度也是浮点数阿，怎么判断两个角度相等？设个门限?

l*o2010-03-19 07:03

10 楼

假定坐标是整数, 那么dy/dx是个分数, 约分. 然后两个分数相等仅当分子分母的绝对
值相等. 这里用绝对值是因为两个点可能在另一边.
此外, 不是O(N^2), 每个点作为圆心, 然后比较其他N个角度的话怎么说也要O(NlogN),
此后每个点重复一遍, 所以是O(N^2 logN)的.
比如说N个值, 不排序, O(N)怎么找重复的? 排序怎么说也要O(N logN).
别说什么hashtable, hashtable你只能说一般情况下是O(1), 最坏情况还是O(N), 所以
不能用O(1)来分析算法复杂度的.

浮点数也可以比较啊，只是需要有精度的取舍，规定一下比到小数点后哪一位。
真怕浮点数的话，这里没必要用浮点代表吧，比如角度等于2/27的用2.27表示不就行了。
算法，又不是算术。

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

: 浮点数也可以比较啊，只是需要有精度的取舍，规定一下比到小数点后哪一位。
: 真怕浮点数的话，这里没必要用浮点代表吧，比如角度等于2/27的用2.27表示不就行了。
: 算法，又不是算术。

l*m2010-03-19 07:03

11 楼

h*r2010-03-19 07:03

12 楼

你这两点都错了吧。
1.以任何一个点为起点，计算和其他任何一个点之间的角度的话无非是计算一次（Xi -
Xj）/（Yi - Yj)，第一个起点需要计算N-1次，然后逐个起点的计算量递减一次。这个怎么会需要O(NlogN)？ O（N）足以。总共N个点。O(N^2)足够完成全部计算。
2.无需排序，只要已经做过起点的点不再继续参加角度计算即可，这个第一层for loop
就会帮你解决问题。你想一下我前面提到的n阶对称矩阵就明白了。只需要计算出一个
上半或者下半矩阵的角度就结了。任何两点间的角度只会计算一次，没有重复。

),

【在 l******o 的大作中提到】

: 假定坐标是整数, 那么dy/dx是个分数, 约分. 然后两个分数相等仅当分子分母的绝对
: 值相等. 这里用绝对值是因为两个点可能在另一边.
: 此外, 不是O(N^2), 每个点作为圆心, 然后比较其他N个角度的话怎么说也要O(NlogN),
: 此后每个点重复一遍, 所以是O(N^2 logN)的.
: 比如说N个值, 不排序, O(N)怎么找重复的? 排序怎么说也要O(N logN).
: 别说什么hashtable, hashtable你只能说一般情况下是O(1), 最坏情况还是O(N), 所以
: 不能用O(1)来分析算法复杂度的.
:
: 浮点数也可以比较啊，只是需要有精度的取舍，规定一下比到小数点后哪一位。
: 真怕浮点数的话，这里没必要用浮点代表吧，比如角度等于2/27的用2.27表示不就行了。

l*o2010-03-19 07:03

13 楼

这么问你吧, N个数, 你怎么在O(N)的时间里找到重复的?
用hashset的那个方法忽略, 理由已经说过了.

你这两点都错了吧。
1.以任何一个点为起点，计算和其他任何一个点之间的角度的话无非是计算一次（Xi -
Xj）/（Yi - Yj)，第一个起点需要计算N-1次，然后逐个起点的计算量递减一次。这
个怎么会需要O(NlogN)？ O（N）足以。总共N个点。O(N^2)足够完成全部计算。
2.无需排序，只要已经做过起点的点不再继续参加角度计算即可，这个第一层for loop
就会帮你解决问题。你想一下我前面提到的n阶对称矩阵就明白了。只需要计算出一个
上半或者下半矩阵的角度就结了。任何两点间的角度只会计算一次，没有重复。
),

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

: 你这两点都错了吧。
: 1.以任何一个点为起点，计算和其他任何一个点之间的角度的话无非是计算一次（Xi -
: Xj）/（Yi - Yj)，第一个起点需要计算N-1次，然后逐个起点的计算量递减一次。这个怎么会需要O(NlogN)？ O（N）足以。总共N个点。O(N^2)足够完成全部计算。
: 2.无需排序，只要已经做过起点的点不再继续参加角度计算即可，这个第一层for loop
: 就会帮你解决问题。你想一下我前面提到的n阶对称矩阵就明白了。只需要计算出一个
: 上半或者下半矩阵的角度就结了。任何两点间的角度只会计算一次，没有重复。
:
: ),

a*92010-03-19 07:03

14 楼

l*o2010-03-19 07:03

15 楼

此外你那个对称矩阵, 只不过是把复杂度降低一半而已, 没有从阶上得到降低.

这么问你吧, N个数, 你怎么在O(N)的时间里找到重复的?
用hashset的那个方法忽略, 理由已经说过了.
你这两点都错了吧。
1.以任何一个点为起点，计算和其他任何一个点之间的角度的话无非是计算一次（Xi -
Xj）/（Yi - Yj)，第一个起点需要计算N-1次，然后逐个起点的计算量递减一次。这
个怎么会需要O(NlogN)？ O（N）足以。总共N个点。O(N^2)足够完成全部计算。
2.无需排序，只要已经做过起点的点不再继续参加角度计算即可，这个第一层for loop
就会帮你解决问题。你想一下我前面提到的n阶对称矩阵就明白了。只需要计算出一个
上半或者下半矩阵的角度就结了。任何两点间的角度只会计算一次，没有重复。
),

【在 l******o 的大作中提到】

: 这么问你吧, N个数, 你怎么在O(N)的时间里找到重复的?
: 用hashset的那个方法忽略, 理由已经说过了.
:
: 你这两点都错了吧。
: 1.以任何一个点为起点，计算和其他任何一个点之间的角度的话无非是计算一次（Xi -
: Xj）/（Yi - Yj)，第一个起点需要计算N-1次，然后逐个起点的计算量递减一次。这
: 个怎么会需要O(NlogN)？ O（N）足以。总共N个点。O(N^2)足够完成全部计算。
: 2.无需排序，只要已经做过起点的点不再继续参加角度计算即可，这个第一层for loop
: 就会帮你解决问题。你想一下我前面提到的n阶对称矩阵就明白了。只需要计算出一个
: 上半或者下半矩阵的角度就结了。任何两点间的角度只会计算一次，没有重复。

h*r2010-03-19 07:03

16 楼

呵呵，这个问题是越辩越明了。
计算出上半矩阵来，需要O(N^2)。
列出矩阵里每行里出现的重复角度需要排序，这个是O(NlogN)，N行即为O(N^2logN)。
所以复杂度是O(N^2) + O(N^2logN)，也就是O(N^2logN)。

-
loop

【在 l******o 的大作中提到】

c*g2010-03-19 07:03

17 楼

zan~

S*a2010-03-19 07:03

18 楼

不是有传说中的perfect hasing吗？
前面的面试我一直用O（1）来算hase的复杂度的。。。
求赐教

),
了。

【在 l******o 的大作中提到】

f*e2010-03-19 07:03

19 楼

如果1245在一条线上，245也会在一条线上，怎么才能remove redundancy?

w*a2010-03-19 07:03

20 楼

zan~

b*v2010-03-19 07:03

21 楼

这个容易，第i个点考虑过后，就把它从点集中移除

【在 f****e 的大作中提到】

: 如果1245在一条线上，245也会在一条线上，怎么才能remove redundancy?

K*g2010-03-19 07:03

22 楼

为什么这么复杂啊，我觉得很简单啊。
随便挑一个点为原点，然后求剩下的N-1个点与x轴的夹角，把所有的夹角排序，然后不
久找出在同一条直线上的点了吗？
N-1+NlgN

x*r2010-03-19 07:03

23 楼

如果斜率无穷大也不好存。要不不存斜率存一个pair的话，还要求最简才能
比较，如果两个都是浮点就更没发弄了。

x*r2010-03-19 07:03

24 楼

，，，，
经过很多点那条线很可能不经过你这个点。。。

【在 K******g 的大作中提到】

: 为什么这么复杂啊，我觉得很简单啊。
: 随便挑一个点为原点，然后求剩下的N-1个点与x轴的夹角，把所有的夹角排序，然后不
: 久找出在同一条直线上的点了吗？
: N-1+NlgN

c*f2010-03-19 07:03

25 楼

这题真难

f*42010-03-19 07:03

26 楼

为啥都只用斜率来表示直线啊？就算斜率相同也可能是平行线啊
从N中取所有任意2天求直线，(k,y0)代表那个直线做hashtable key，value (
lineCounter,*linklist)
这里linklist 节点存储的是点对(xi,yi,xj,yj)
只要是相同直线，lineCounter++,点对放到linklist里面
然后遍历hashtable,对所有的lineCounter>3的，输出不重复的点（用个set）
就是比较费空间

w*12010-03-19 07:03

27 楼

不知道从哪里看到过
存成很多个集合，集合中包含任意两个点和他们连线后的夹角。
再在这个集合中找同角度的，有重复点的最大集合。