w*5
2 楼
一个平面上n个点，需要两两配对，但有个constraint是距离不能大于k，这样有些点可
能最后无法被配对。有没有算法使得能配对的点最多？
follow-up是求出最小的k，使得所有点都能配上对。
这个应该怎么考虑？
能最后无法被配对。有没有算法使得能配对的点最多？
follow-up是求出最小的k，使得所有点都能配上对。
这个应该怎么考虑？
H*1
3 楼
G(V,E) where |V| = n as points, E = {(u,v)| dist(u,v) <= k}
Now what you are looking at are matchings, so just apply Edmonds' algorithm.
O(\sqrt(V) * E). Since the G is a unit disk graph here, you may be able to
improve the algorithm, google or wait till DaNiu post an answer.
For finding the smallest k, there are probably smarter ways, but a 糙快猛
practical solution could be:
Find d = closest pair distance O(nlgn)
Find D = farthest pair distance O(nlgn)
Binary Search on [d, D] O(lg(D-d) * \sqrt(V) * E) until you find the k
Now what you are looking at are matchings, so just apply Edmonds' algorithm.
O(\sqrt(V) * E). Since the G is a unit disk graph here, you may be able to
improve the algorithm, google or wait till DaNiu post an answer.
For finding the smallest k, there are probably smarter ways, but a 糙快猛
practical solution could be:
Find d = closest pair distance O(nlgn)
Find D = farthest pair distance O(nlgn)
Binary Search on [d, D] O(lg(D-d) * \sqrt(V) * E) until you find the k
w*5
4 楼
多谢大牛
algorithm.
【在 H*******1 的大作中提到】
: G(V,E) where |V| = n as points, E = {(u,v)| dist(u,v) <= k}
: Now what you are looking at are matchings, so just apply Edmonds' algorithm.
: O(\sqrt(V) * E). Since the G is a unit disk graph here, you may be able to
: improve the algorithm, google or wait till DaNiu post an answer.
: For finding the smallest k, there are probably smarter ways, but a 糙快猛
: practical solution could be:
: Find d = closest pair distance O(nlgn)
: Find D = farthest pair distance O(nlgn)
: Binary Search on [d, D] O(lg(D-d) * \sqrt(V) * E) until you find the k
algorithm.
【在 H*******1 的大作中提到】
: G(V,E) where |V| = n as points, E = {(u,v)| dist(u,v) <= k}
: Now what you are looking at are matchings, so just apply Edmonds' algorithm.
: O(\sqrt(V) * E). Since the G is a unit disk graph here, you may be able to
: improve the algorithm, google or wait till DaNiu post an answer.
: For finding the smallest k, there are probably smarter ways, but a 糙快猛
: practical solution could be:
: Find d = closest pair distance O(nlgn)
: Find D = farthest pair distance O(nlgn)
: Binary Search on [d, D] O(lg(D-d) * \sqrt(V) * E) until you find the k
l*n
5 楼
这是哪儿的面试题？
还是课程作业
【在 w********5 的大作中提到】
: 一个平面上n个点，需要两两配对，但有个constraint是距离不能大于k，这样有些点可
: 能最后无法被配对。有没有算法使得能配对的点最多？
: follow-up是求出最小的k，使得所有点都能配上对。
: 这个应该怎么考虑？
还是课程作业
【在 w********5 的大作中提到】
: 一个平面上n个点，需要两两配对，但有个constraint是距离不能大于k，这样有些点可
: 能最后无法被配对。有没有算法使得能配对的点最多？
: follow-up是求出最小的k，使得所有点都能配上对。
: 这个应该怎么考虑？
b*m
6 楼
奇数个点，多大的k也不行呀。
相关阅读
eBay 裁人, 招人, 到底哪一个更真? (转载)求FB Data Scientist面经现在PYTHON，SAS， R 在工业界怎么个比例？谁知道怎么通过JDBC让java连上hive？做事要有原则和底线----评花大价钱买培训课程事件 (转载)纽约 position帮朋友招人: 要很强business solution的senior level data scientist请问哪里可以下载到所有在美国发表的书籍的数据哪里可以找到DS的面试题？Santa Clara data scientist position加大伯克利分校著名科学家：大数据的“冬天”即将到来?请教各位大牛现在面对data science或programming的找工作和竞赛做题网站是泥沙俱下啊答:如何向其他组老板提出想申请他组里的职位 (转载)推荐一个Data Science入门和进阶的帖子为什么现在本科，硕士就能当data scientistMachine Learning硕士求推荐新出炉的FB面经想组织一次湾区版聚AIG的quantitative analyst怎么样 (转载)