最近的一对白点和黑点怎么做？# JobHunting - 待字闺中
c*p
1 楼
平面上一堆白点一堆黑点，找最近的白点和黑点。这个题怎么做？
我说说我的想法：
用2个arraylist分别记录白点黑点坐标。每个白点找它最近的黑点。然后把这些最近的
距离比较。
这个复杂度是O(n^2).
求更好的方法～
我说说我的想法：
用2个arraylist分别记录白点黑点坐标。每个白点找它最近的黑点。然后把这些最近的
距离比较。
这个复杂度是O(n^2).
求更好的方法～
A*i
2 楼
隐约觉得可以用DP来做
和那个三角形问题差不多
和那个三角形问题差不多
c*p
3 楼
哪个三角形？
求三角形问题链接。
【在 A*****i 的大作中提到】
: 隐约觉得可以用DP来做
: 和那个三角形问题差不多
求三角形问题链接。
【在 A*****i 的大作中提到】
: 隐约觉得可以用DP来做
: 和那个三角形问题差不多
k*t
4 楼
感觉想leetcode中Pascal's Triangle那道题啊
【在 A*****i 的大作中提到】
: 隐约觉得可以用DP来做
: 和那个三角形问题差不多
【在 A*****i 的大作中提到】
: 隐约觉得可以用DP来做
: 和那个三角形问题差不多
c*p
5 楼
啊？？请问这个是怎么联系起来的。。。。。
【在 k*******t 的大作中提到】
: 感觉想leetcode中Pascal's Triangle那道题啊
【在 k*******t 的大作中提到】
: 感觉想leetcode中Pascal's Triangle那道题啊
k*t
6 楼
那个也是三角形，而且也用dp啊。不知道对不对，求教牛人出来数清楚点
【在 c********p 的大作中提到】
: 啊？？请问这个是怎么联系起来的。。。。。
【在 c********p 的大作中提到】
: 啊？？请问这个是怎么联系起来的。。。。。
c*p
7 楼
我问的这个问题，是怎么和三角形联系起来的呢？
【在 k*******t 的大作中提到】
: 那个也是三角形，而且也用dp啊。不知道对不对，求教牛人出来数清楚点
【在 k*******t 的大作中提到】
: 那个也是三角形，而且也用dp啊。不知道对不对，求教牛人出来数清楚点
i*t
8 楼
对每个白点 在黑点钟查找最近的 用kd tree 之类的 binary tree
建树 大概 nlogn ?
查找 logn
所以 总的复杂度是 假设 白点个数也是 n
nlogn + logn n = 2nlogn = nlogn
不知道对不对
建树 大概 nlogn ?
查找 logn
所以 总的复杂度是 假设 白点个数也是 n
nlogn + logn n = 2nlogn = nlogn
不知道对不对
c*p
9 楼
什么是kd tree？
【在 i******t 的大作中提到】
: 对每个白点 在黑点钟查找最近的 用kd tree 之类的 binary tree
: 建树 大概 nlogn ?
: 查找 logn
: 所以 总的复杂度是 假设 白点个数也是 n
: nlogn + logn n = 2nlogn = nlogn
: 不知道对不对
【在 i******t 的大作中提到】
: 对每个白点 在黑点钟查找最近的 用kd tree 之类的 binary tree
: 建树 大概 nlogn ?
: 查找 logn
: 所以 总的复杂度是 假设 白点个数也是 n
: nlogn + logn n = 2nlogn = nlogn
: 不知道对不对
i*t
10 楼
就是类似于 bst 但是 多维的
感觉是比较典型的 nearest neighbor search 问题 一般都是 kdtree
【在 c********p 的大作中提到】
: 什么是kd tree？
感觉是比较典型的 nearest neighbor search 问题 一般都是 kdtree
【在 c********p 的大作中提到】
: 什么是kd tree？
c*p
11 楼
哦哦，，，一会看看别人怎么说这个题。。
我还是非常confused
【在 i******t 的大作中提到】
: 就是类似于 bst 但是 多维的
: 感觉是比较典型的 nearest neighbor search 问题 一般都是 kdtree
我还是非常confused
【在 i******t 的大作中提到】
: 就是类似于 bst 但是 多维的
: 感觉是比较典型的 nearest neighbor search 问题 一般都是 kdtree
x*8
12 楼
分而治之？看看这样如何:
1. sort the points based on some axis, to divide them rough to two parts
2. the solution is 1 of the following 4:
a) on the left -> recursive call
b) on the right -> recursive call
c) one black on left, one white on right
d) one white on left, one black on right
3. search of c and d can be constrained by the upper limit we get in a) and
b)
【在 c********p 的大作中提到】
: 哦哦，，，一会看看别人怎么说这个题。。
: 我还是非常confused
1. sort the points based on some axis, to divide them rough to two parts
2. the solution is 1 of the following 4:
a) on the left -> recursive call
b) on the right -> recursive call
c) one black on left, one white on right
d) one white on left, one black on right
3. search of c and d can be constrained by the upper limit we get in a) and
b)
【在 c********p 的大作中提到】
: 哦哦，，，一会看看别人怎么说这个题。。
: 我还是非常confused
e*8
13 楼
这个是bichromatic closest pair问题（是computational geometry里很经典的问题）
。觉得面试问不到这种问题吧，实在太偏了，不是那种人人都应该知道的东西。。。。
当然除非你的方向本来就是computational geometry (或者面试官的背景是
computational geometry -_-||)
几个可以考虑的解法：http://stackoverflow.com/questions/8203576/closest-distance-between-two-pointsdisjoint-set
上面有人说的kd tree，就是种nearest neighbor data structure
。觉得面试问不到这种问题吧，实在太偏了，不是那种人人都应该知道的东西。。。。
当然除非你的方向本来就是computational geometry (或者面试官的背景是
computational geometry -_-||)
几个可以考虑的解法：http://stackoverflow.com/questions/8203576/closest-distance-between-two-pointsdisjoint-set
上面有人说的kd tree，就是种nearest neighbor data structure
l*i
14 楼
what if you have all white on left and all black on right, then a) and b)
tell you nothing about min dist between a black and a white.
and
【在 x****8 的大作中提到】
: 分而治之？看看这样如何:
: 1. sort the points based on some axis, to divide them rough to two parts
: 2. the solution is 1 of the following 4:
: a) on the left -> recursive call
: b) on the right -> recursive call
: c) one black on left, one white on right
: d) one white on left, one black on right
: 3. search of c and d can be constrained by the upper limit we get in a) and
: b)
tell you nothing about min dist between a black and a white.
and
【在 x****8 的大作中提到】
: 分而治之？看看这样如何:
: 1. sort the points based on some axis, to divide them rough to two parts
: 2. the solution is 1 of the following 4:
: a) on the left -> recursive call
: b) on the right -> recursive call
: c) one black on left, one white on right
: d) one white on left, one black on right
: 3. search of c and d can be constrained by the upper limit we get in a) and
: b)
x*y
15 楼
Is there any differene from finding 2 closest points in 2-D space, which is
a classic "divide and conquer" problem?
【在 c********p 的大作中提到】
: 平面上一堆白点一堆黑点，找最近的白点和黑点。这个题怎么做？
: 我说说我的想法：
: 用2个arraylist分别记录白点黑点坐标。每个白点找它最近的黑点。然后把这些最近的
: 距离比较。
: 这个复杂度是O(n^2).
: 求更好的方法～
a classic "divide and conquer" problem?
【在 c********p 的大作中提到】
: 平面上一堆白点一堆黑点，找最近的白点和黑点。这个题怎么做？
: 我说说我的想法：
: 用2个arraylist分别记录白点黑点坐标。每个白点找它最近的黑点。然后把这些最近的
: 距离比较。
: 这个复杂度是O(n^2).
: 求更好的方法～
相关阅读
认识hiring manager，中国人，热情推荐加州硅谷 box.com偶然间看到了andrew ng 老婆。。。和CEO电面会谈些什么呀？2016 Google 内推UBER司机挣得比马工多多了眼红U家国人发财的U黑简直无法无天了面试的项目不给钱怎么办硅谷泡沫破裂前兆：高楼+应召女郎 独角兽到独角尸不升职的情况下如何要求涨工资 (转载)G家一道onsite题目Tech Marketing Engineer/Senior Engineer openings (转载)同一家公司的不同方向的职位，能找不同的人内推么？请问现在哪家bar低啊。。。Junior职位[招人] VP Model Validation Analyst最近陪同学看房子找了几个中国人出租的house，全部给隔成了小单间猎头一大早打电话说有个top global bank招人请问有人有facebook ML design面经吗已经寄给移民局offer letter申请OPT延期, 公司又改了开始工作的时间膜拜airbnb终极大神，coursera最硬软广告有没有这样一种专利，Uber申请之后别家不许做一样的事情？