由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问一道F的面试题 - 找kNN for 2D points
相关主题
问两道google面试题刚做完Amazon Online Assessment
问个google面试题一个NxN矩阵每行每列都sort好,如何排序?
这几个题目怎么做啊问一个时间复杂度的问题,数组里取k个最大数
问个题。bb FSD 电面
G电面的一个题a very difficult interview question
LinkedIn面经(已跪),攒个rp【什么时候需要做heap, 什么时候需要做BST】
请教大神们一道算法题关于实时输出Top K最频繁变动的股价google 一题
一道小题找最近的点,这题咋解?
相关话题的讨论汇总
话题: 2d话题: points话题: heap话题: knn话题: 面试题
进入JobHunting版参与讨论
1 (共1页)
d*********i
发帖数: 104
1
Given 2D coordinates , find the k points which are closest to the origin.
Propose a data structure for storing the points and the method to get the k
points. Also point out the complexity of the code.
好像见讨论过,怎么做比较好呢
p*****2
发帖数: 21240
2

k
priority queue?

【在 d*********i 的大作中提到】
: Given 2D coordinates , find the k points which are closest to the origin.
: Propose a data structure for storing the points and the method to get the k
: points. Also point out the complexity of the code.
: 好像见讨论过,怎么做比较好呢

B***i
发帖数: 724
3
k-d tree
D**********d
发帖数: 849
4
max-heap O(nlg(k))
d*********i
发帖数: 104
5

恩 我也觉得pq, max-heap 这个可行,不知道还有没有更优呢

【在 D**********d 的大作中提到】
: max-heap O(nlg(k))
f*****e
发帖数: 2992
6
quick-sort similar idea, find the kth element in n elements. All elements on
its right are suitable candidates. Not good for online large data.

【在 d*********i 的大作中提到】
:
: 恩 我也觉得pq, max-heap 这个可行,不知道还有没有更优呢

c********t
发帖数: 5706
7
感觉已经最优,除非要求O(1)空间,只能in place sort,时间复杂度就是O(nlogn)了

【在 d*********i 的大作中提到】
:
: 恩 我也觉得pq, max-heap 这个可行,不知道还有没有更优呢

l*******b
发帖数: 2586
8
heap本身就可以in place 实现吧。O(n)时间构造,O(k log n) 提取k个最小的

【在 c********t 的大作中提到】
: 感觉已经最优,除非要求O(1)空间,只能in place sort,时间复杂度就是O(nlogn)了
g*****e
发帖数: 282
9
面过一个类似的题,其他相同,但不是求离原点最近k个,而是对任意输入,求离这个
点最近的k个点,k是常数。
我给出的是BF,分支定界,但time complexity不变。any better idea?

【在 c********t 的大作中提到】
: 感觉已经最优,除非要求O(1)空间,只能in place sort,时间复杂度就是O(nlogn)了
c********t
发帖数: 5706
10
说到这里,我有很菜的java问题,heap,map,set, list,如果存的是object,应该只是存
储reference.对吧? 但是也要算作O(n)储存空间吧,怎么能算in place呢?
你可能与上面说的方法不同,解法是构造 k size的 max heap O(n log k);

【在 l*******b 的大作中提到】
: heap本身就可以in place 实现吧。O(n)时间构造,O(k log n) 提取k个最小的
相关主题
LinkedIn面经(已跪),攒个rp刚做完Amazon Online Assessment
请教大神们一道算法题关于实时输出Top K最频繁变动的股价一个NxN矩阵每行每列都sort好,如何排序?
一道小题问一个时间复杂度的问题,数组里取k个最大数
进入JobHunting版参与讨论
c********t
发帖数: 5706
11
感觉是一样的,只是每个点先要算一下到给定点距离,比较距离

【在 g*****e 的大作中提到】
: 面过一个类似的题,其他相同,但不是求离原点最近k个,而是对任意输入,求离这个
: 点最近的k个点,k是常数。
: 我给出的是BF,分支定界,但time complexity不变。any better idea?

l*******b
发帖数: 2586
12
嗯,我想的是做一遍heap sort. 数据太大应该用辅助空间比较好。

【在 c********t 的大作中提到】
: 说到这里,我有很菜的java问题,heap,map,set, list,如果存的是object,应该只是存
: 储reference.对吧? 但是也要算作O(n)储存空间吧,怎么能算in place呢?
: 你可能与上面说的方法不同,解法是构造 k size的 max heap O(n log k);

c********s
发帖数: 817
13
> k size的 max heap
弱问:when building the heap, 如果新的element最终被放到 > k position时,就是
如何知道新的element不在
top k positions,if 只用k size heap? 对k有特殊的要求吗 (power of 2-1)?

【在 c********t 的大作中提到】
: 说到这里,我有很菜的java问题,heap,map,set, list,如果存的是object,应该只是存
: 储reference.对吧? 但是也要算作O(n)储存空间吧,怎么能算in place呢?
: 你可能与上面说的方法不同,解法是构造 k size的 max heap O(n log k);

l*******b
发帖数: 2586
14
没要求吧,新的元素不会被放到 >k的位置呀,先和root比较,如果比root大,就直接
丢了。比root 小就把root 丢了,新的元素插到root然后sift down.
root存的是最大的元素,所以叫max heap吧。最后找到的却是所有n个元素里,k个最小
的。

【在 c********s 的大作中提到】
: > k size的 max heap
: 弱问:when building the heap, 如果新的element最终被放到 > k position时,就是
: 如何知道新的element不在
: top k positions,if 只用k size heap? 对k有特殊的要求吗 (power of 2-1)?

c********s
发帖数: 817
15
懂了,谢谢!

【在 l*******b 的大作中提到】
: 没要求吧,新的元素不会被放到 >k的位置呀,先和root比较,如果比root大,就直接
: 丢了。比root 小就把root 丢了,新的元素插到root然后sift down.
: root存的是最大的元素,所以叫max heap吧。最后找到的却是所有n个元素里,k个最小
: 的。

g*****e
发帖数: 282
16
我总感觉可以怎么预处理一下,减少重复计算 =)

【在 c********t 的大作中提到】
: 感觉是一样的,只是每个点先要算一下到给定点距离,比较距离
1 (共1页)
进入JobHunting版参与讨论
相关主题
找最近的点,这题咋解?G电面的一个题
小公司面试官问我做出的最大成就是什么?LinkedIn面经(已跪),攒个rp
TopK nearest points为啥用heap不用selection sort?请教大神们一道算法题关于实时输出Top K最频繁变动的股价
微软面试题一道小题
问两道google面试题刚做完Amazon Online Assessment
问个google面试题一个NxN矩阵每行每列都sort好,如何排序?
这几个题目怎么做啊问一个时间复杂度的问题,数组里取k个最大数
问个题。bb FSD 电面
相关话题的讨论汇总
话题: 2d话题: points话题: heap话题: knn话题: 面试题