i********2
发帖数: 5 | 1 一个面试题，上周面的，想了很久也木有想出来。
题目如下：
假设有一群朋友在一个城市里，这个城市是2维的，每一个人都有一个自己的二维坐标
例如：
ID x y
1 0.0 0.0
2 10.1 -10.1
3 -12.2 12.2
4 38.3 38.3
5 79.99 179.99
其中每一个id代表一个人，找出对于每一个最近的3个朋友并打印出来，例如以上的这
堆人的结果就是：
1 2,3,4
2 1,3,4
3 1,2,4
4 1,2,3
5 4,3,1
要求是算法复杂度要小于n2
各位大牛有神马思路都提示一下吧，想了很久也没有很好的解决方法，有想到老师讲过
的nearest pair，但是貌似也不是很合适的方法。感觉至少算一下每两个点的距离都要
n2，然后就没有思路了。 |
b*****e
发帖数: 131 | 2 全部点按照X坐标排序，O(NlogN) , 然后就好办了。 |
H***e
发帖数: 476 | 3 这不是k-nearest neighbors吗
有成熟算法吧
【在 i********2 的大作中提到】
: 一个面试题，上周面的，想了很久也木有想出来。
: 题目如下：
: 假设有一群朋友在一个城市里，这个城市是2维的，每一个人都有一个自己的二维坐标
: 例如：
: ID x y
: 1 0.0 0.0
: 2 10.1 -10.1
: 3 -12.2 12.2
: 4 38.3 38.3
: 5 79.99 179.99
|
f*******t
发帖数: 7549 | |
r****t
发帖数: 10904 | 5 成熟算法 < O(N^2) 么？
【在 H***e 的大作中提到】
: 这不是k-nearest neighbors吗
: 有成熟算法吧
|
v***a
发帖数: 365 | 6 或许可以这样：
构造 Voronoi Diagram, O(NLogN) 可以构造出来
Voronoi 最多有 3N 条边
求每个点最近的点，只需要检查每条 voronoi的边，O(2 * 3N )
求每个点最近的2个点，除了检查每条边，还要检查，离他最近点的所有voronoi的边，
O(? * 3N), ? is constant,
求最近的3个点，还要检查第二近的点的所有边，以及第一近的点的所有voronnoi的边
，可以证明肯定在这些边里，O(? * 3N), ? is also constant.
Anyway, O(NLogN）
请问你面的什么公司？
这种计算几何的题目，估计 G/FB 也不会考的吧，做地图的公司？
如果还有position的话，也想投一下试试，
投了无数公司，现在一个面试都没有……杯具啊 |
i**********e
发帖数: 1145 | 7 这道题很久以前做过，跟facebook puzzle上一模一样的。有个优化办法，可以大大提
高性能。
把所有点按照(x,y)归类为 k*k 个格子里，那么你要搜索离一个位置最近的三个点，那
么最有可能就是先搜属于这个位置的格子里的所有点。如果找到最近的三个点，就完成
任务了。如果还没找到，那就扩展到更外面一圈的格子，以此类推。 |
r****t
发帖数: 10904 | 8 discretization 只能近似吧，方格子按层数算距离有很大误差。
【在 i**********e 的大作中提到】
: 这道题很久以前做过，跟facebook puzzle上一模一样的。有个优化办法，可以大大提
: 高性能。
: 把所有点按照(x,y)归类为 k*k 个格子里，那么你要搜索离一个位置最近的三个点，那
: 么最有可能就是先搜属于这个位置的格子里的所有点。如果找到最近的三个点，就完成
: 任务了。如果还没找到，那就扩展到更外面一圈的格子，以此类推。
|
i**********e
发帖数: 1145 | 9 我想了一下，有个edgecase，就是最近的三个点不一定是格子里边的点，有可能是格子
旁边的。所以附近的一些格子也必须搜索。
【在 r****t 的大作中提到】
: discretization 只能近似吧，方格子按层数算距离有很大误差。
|
H***e
发帖数: 476 | 10 觉得这个不work，你search到不管哪一层都无法断定就此停止
【在 i**********e 的大作中提到】
: 这道题很久以前做过，跟facebook puzzle上一模一样的。有个优化办法，可以大大提
: 高性能。
: 把所有点按照(x,y)归类为 k*k 个格子里，那么你要搜索离一个位置最近的三个点，那
: 么最有可能就是先搜属于这个位置的格子里的所有点。如果找到最近的三个点，就完成
: 任务了。如果还没找到，那就扩展到更外面一圈的格子，以此类推。
|
|
|
i********2
发帖数: 5 | 11 那你这相当于把这个看做一张图 按单位半径增长穷举搜索么？
这个复杂度就和n没关系了吧 和数值之间的差距有关系 也就是最小半径和最大半径？
那么应该是n*k 我觉得是一定情况下比n*n小 但是要看点的稀疏程度
我的理解对么？
【在 i**********e 的大作中提到】
: 这道题很久以前做过，跟facebook puzzle上一模一样的。有个优化办法，可以大大提
: 高性能。
: 把所有点按照(x,y)归类为 k*k 个格子里，那么你要搜索离一个位置最近的三个点，那
: 么最有可能就是先搜属于这个位置的格子里的所有点。如果找到最近的三个点，就完成
: 任务了。如果还没找到，那就扩展到更外面一圈的格子，以此类推。
|
i********2
发帖数: 5 | 12 一个东部的startup，一共十个人的公司
估计你兴趣不大啊，算是找实习，不是fulltime
【在 v***a 的大作中提到】
: 或许可以这样：
: 构造 Voronoi Diagram, O(NLogN) 可以构造出来
: Voronoi 最多有 3N 条边
: 求每个点最近的点，只需要检查每条 voronoi的边，O(2 * 3N )
: 求每个点最近的2个点，除了检查每条边，还要检查，离他最近点的所有voronoi的边，
: O(? * 3N), ? is constant,
: 求最近的3个点，还要检查第二近的点的所有边，以及第一近的点的所有voronnoi的边
: ，可以证明肯定在这些边里，O(? * 3N), ? is also constant.
: Anyway, O(NLogN）
: 请问你面的什么公司？
|
i********2
发帖数: 5 | 13 请问然后就好办了是什么意思？
当时我也想到的是nearest pair，算法导论上有这个东西，也是大概按一个坐标轴排序
，然后呢？
能给点细节么？
【在 b*****e 的大作中提到】
: 全部点按照X坐标排序，O(NlogN) , 然后就好办了。
|
i********2
发帖数: 5 | 14 你所说的成熟的算法具体是什么呢？
我有查到一些idea，但是也没有具体的复杂度什么的，
因为这个题目是要求给一个小时 让把代码写出来 然后发回去 当时一个小时也没写出
来...
请问具体实现是怎么实现呢？
【在 H***e 的大作中提到】
: 这不是k-nearest neighbors吗
: 有成熟算法吧
|
v***a
发帖数: 365 | 15 你是要写代码？还是设计 < O(N^2)的算法？这2个是不一样的
【在 i********2 的大作中提到】
: 你所说的成熟的算法具体是什么呢？
: 我有查到一些idea，但是也没有具体的复杂度什么的，
: 因为这个题目是要求给一个小时 让把代码写出来 然后发回去 当时一个小时也没写出
: 来...
: 请问具体实现是怎么实现呢？
|
i**********e
发帖数: 1145 | 16 几年前写的程序，忘了。基本思路是分成 n_w x n_h 个格子没错。
n_w 是多少个 column，n_h 是多少个 row.
然后生成 buckets:
bucket = new list[n_w*n_h];
把每个点 hash 到相对的格子去:
temp_pt.x = coor_x[i]; temp_pt.y = coor_y[i]; temp_pt.id = i;
int col = (int)((coor_x[i] - min_x) / j);
int row = (int)((coor_y[i] - min_y) / k);
int index = row * n_w + col;
bucket[index].push_back(temp_pt);
然后就是搜索的算法了，用 visited table 来记录搜过的格子，然后一层一层往外搜
。当时没考虑可读性，写的比较乱，请见谅。
http://ideone.com/suHFu
【在 i********2 的大作中提到】
: 那你这相当于把这个看做一张图 按单位半径增长穷举搜索么？
: 这个复杂度就和n没关系了吧 和数值之间的差距有关系 也就是最小半径和最大半径？
: 那么应该是n*k 我觉得是一定情况下比n*n小 但是要看点的稀疏程度
: 我的理解对么？
|
q****x
发帖数: 7404 | 17 按x/y分别排序。
任何一个点只需检查其x坐标上下六个和y坐标上下六个点。
这样是O(nlogn)+O(12n) = O(nlgn)。
【在 i********2 的大作中提到】
: 一个面试题，上周面的，想了很久也木有想出来。
: 题目如下：
: 假设有一群朋友在一个城市里，这个城市是2维的，每一个人都有一个自己的二维坐标
: 例如：
: ID x y
: 1 0.0 0.0
: 2 10.1 -10.1
: 3 -12.2 12.2
: 4 38.3 38.3
: 5 79.99 179.99
|
i**********e
发帖数: 1145 | 18 这不对，我举了个反例（看贴图）。
X1,X2,X3 是 X标上下最近的三个点，Y1,Y2,Y3 是Y 标上下最近的三个点（你可以自由
添加到六个点也行）。
但是 Z 确是最近的点。当然，我可以在 Z 同样的位置自由添加多两个点。那么，最近
的三个点都不在 X1..X6 和 Y1... Y6 。
【在 q****x 的大作中提到】
: 按x/y分别排序。
: 任何一个点只需检查其x坐标上下六个和y坐标上下六个点。
: 这样是O(nlogn)+O(12n) = O(nlgn)。
|
q****x
发帖数: 7404 | 19 你理解有误。Z点的x/y坐标投影显然比x1,x2,x3和y1,y2,y3更近。
数学上很容易证明。
对于任意一点p(x,y)，假设：
a1，a2，a3是x坐标小于p.x的点里x坐标最大的三个点；
a4，a5，a6是x坐标大于p.x的点里x坐标最小的三个点；
类似定义b1~b6，关于y坐标。
那么距离p最近的三个点一定在a1~6和b1~6里。这样只需查12个点。
【在 i**********e 的大作中提到】
: 这不对，我举了个反例（看贴图）。
: X1,X2,X3 是 X标上下最近的三个点，Y1,Y2,Y3 是Y 标上下最近的三个点（你可以自由
: 添加到六个点也行）。
: 但是 Z 确是最近的点。当然，我可以在 Z 同样的位置自由添加多两个点。那么，最近
: 的三个点都不在 X1..X6 和 Y1... Y6 。
|
i**********e
发帖数: 1145 | 20 请看我贴的新图，帮忙看看哪里有误。
根据我的理解：
X1,X2,X3 是 x 坐标 小于 P.x 最大的三个点，
X4,X5,X6 是 x 坐标 大于 P.x 最小的三个点。
类似于 Y1,...Y6.
我肯定漏掉了一些重要的信息，如果理解有误请耐心指教，谢谢!
【在 q****x 的大作中提到】
: 你理解有误。Z点的x/y坐标投影显然比x1,x2,x3和y1,y2,y3更近。
: 数学上很容易证明。
: 对于任意一点p(x,y)，假设：
: a1，a2，a3是x坐标小于p.x的点里x坐标最大的三个点；
: a4，a5，a6是x坐标大于p.x的点里x坐标最小的三个点；
: 类似定义b1~b6，关于y坐标。
: 那么距离p最近的三个点一定在a1~6和b1~6里。这样只需查12个点。
|
|
|
q****x
发帖数: 7404 | 21 good catch. you are right. my conclusion is wrong.
i think my 12 points （actually, 6) can serve as filter to narrow down the search.
assume the interested point is (0,0), if x^2+y^2 <= x1^2+y1^2, we must have
x < x1 || y < y1. if x1 is already the min, any point whose y is bigger than
y1 is eliminated.
【在 i**********e 的大作中提到】
: 请看我贴的新图，帮忙看看哪里有误。
: 根据我的理解：
: X1,X2,X3 是 x 坐标 小于 P.x 最大的三个点，
: X4,X5,X6 是 x 坐标 大于 P.x 最小的三个点。
: 类似于 Y1,...Y6.
: 我肯定漏掉了一些重要的信息，如果理解有误请耐心指教，谢谢!
|
a********m
发帖数: 15480 | 22 有。 n层最远的点距离也不会超过n+2层最近的点。
【在 H***e 的大作中提到】
: 觉得这个不work，你search到不管哪一层都无法断定就此停止
|
b*****e
发帖数: 131 | 23
先考虑简化问题，只考虑求每个点的最近一点。按X坐标排序后，计算距离
m[n] = {INT_MAX};
for(int i = 0; i < n; i++)
{
for(int j= i+1; j < n; j++ )
{
if(square(X[i] - X[j]) > m[i]) //按X坐标排序的好处就在这里，只有
少量点需要计算
break;
d = square(X[i] - X[j]) + square(Y[i] - Y[j]);
m[i] = min(m[i], d);
}
}
算最近三个点应该类似，复杂度上没什么变化
【在 i********2 的大作中提到】
: 请问然后就好办了是什么意思？
: 当时我也想到的是nearest pair，算法导论上有这个东西，也是大概按一个坐标轴排序
: ，然后呢？
: 能给点细节么？
|
b*****e
发帖数: 131 | 24
先考虑简化问题，只考虑求每个点的最近一点。按X坐标排序后，计算距离
m[n] = {INT_MAX};
for(int i = 0; i < n; i++)
{
for(int j= i+1; j < n; j++ )
{
if(square(X[i] - X[j]) > m[i]) //按X坐标排序的好处就在这里，只有
少量点需要计算
break;
d = square(X[i] - X[j]) + square(Y[i] - Y[j]);
m[i] = min(m[i], d);
}
}
算最近三个点应该类似，复杂度上没什么变化
【在 i********2 的大作中提到】
: 请问然后就好办了是什么意思？
: 当时我也想到的是nearest pair，算法导论上有这个东西，也是大概按一个坐标轴排序
: ，然后呢？
: 能给点细节么？
|
b*****e
发帖数: 131 | 25
先考虑简化问题，只考虑求每个点的最近一点。按X坐标排序后，计算距离
m[n] = {INT_MAX};
for(int i = 0; i < n; i++)
{
for(int j= i+1; j < n; j++ )
{
if(square(X[i] - X[j]) > m[i]) //按X坐标排序的好处就在这里，只有
少量点需要计算
break;
d = square(X[i] - X[j]) + square(Y[i] - Y[j]);
m[i] = min(m[i], d);
}
}
算最近三个点应该类似，复杂度上没什么变化
【在 i********2 的大作中提到】
: 请问然后就好办了是什么意思？
: 当时我也想到的是nearest pair，算法导论上有这个东西，也是大概按一个坐标轴排序
: ，然后呢？
: 能给点细节么？
|
b*****e
发帖数: 131 | 26
先考虑简化问题，只考虑求每个点的最近一点。按X坐标排序后，计算距离
m[n] = {INT_MAX};
for(int i = 0; i < n; i++)
{
for(int j= i+1; j < n; j++ )
{
if(square(X[i] - X[j]) > m[i]) //按X坐标排序的好处就在这里，只有
少量点需要计算
break;
d = square(X[i] - X[j]) + square(Y[i] - Y[j]);
m[i] = min(m[i], d);
}
}
算最近三个点应该类似，复杂度上没什么变化
【在 i********2 的大作中提到】
: 请问然后就好办了是什么意思？
: 当时我也想到的是nearest pair，算法导论上有这个东西，也是大概按一个坐标轴排序
: ，然后呢？
: 能给点细节么？
|
