今天面试问题：有一个整数数组，如何find kth smallest element,如果数据是dynamic# JobHunting - 待字闺中
a*e
1 楼
就是说不断有新数据输入，而且数据量很大，分布在多个机器上，（新的data push到
哪个机器上是随机的)。
怎样做效率比较高？谢谢。
哪个机器上是随机的)。
怎样做效率比较高？谢谢。
c*t
2 楼
maintain a k size min-heap on each machine. Then merge-sort them to a master
machine.
machine.
j*y
3 楼
每台机器用一个 max queue of size k 保留 k个最小的数
然后再 merge 这些不同机器上的 queque
【在 a**********e 的大作中提到】
: 就是说不断有新数据输入，而且数据量很大，分布在多个机器上，（新的data push到
: 哪个机器上是随机的)。
: 怎样做效率比较高？谢谢。
然后再 merge 这些不同机器上的 queque
【在 a**********e 的大作中提到】
: 就是说不断有新数据输入，而且数据量很大，分布在多个机器上，（新的data push到
: 哪个机器上是随机的)。
: 怎样做效率比较高？谢谢。
P*r
4 楼
max heap of the smallest k numbers？如果有个新数，小于max, delete max,
heapify。
master
【在 c********t 的大作中提到】
: maintain a k size min-heap on each machine. Then merge-sort them to a master
: machine.
heapify。
master
【在 c********t 的大作中提到】
: maintain a k size min-heap on each machine. Then merge-sort them to a master
: machine.
c*t
5 楼
你说得对！
【在 P******r 的大作中提到】
: max heap of the smallest k numbers？如果有个新数，小于max, delete max,
: heapify。
:
: master
【在 P******r 的大作中提到】
: max heap of the smallest k numbers？如果有个新数，小于max, delete max,
: heapify。
:
: master
e*s
6 楼
delete max 应该是 replace max with new value吧？
【在 P******r 的大作中提到】
: max heap of the smallest k numbers？如果有个新数，小于max, delete max,
: heapify。
:
: master
【在 P******r 的大作中提到】
: max heap of the smallest k numbers？如果有个新数，小于max, delete max,
: heapify。
:
: master
a*e
7 楼
谢谢。
既然涉及master machine，可不可以每次有data进来，（在store在各个机器上的同时
），直接
把data也push一份到master machine上，这样只要在master machine上维持max heap就
可以了。
这样有什么问题呢？
master
【在 c********t 的大作中提到】
: maintain a k size min-heap on each machine. Then merge-sort them to a master
: machine.
既然涉及master machine，可不可以每次有data进来，（在store在各个机器上的同时
），直接
把data也push一份到master machine上，这样只要在master machine上维持max heap就
可以了。
这样有什么问题呢？
master
【在 c********t 的大作中提到】
: maintain a k size min-heap on each machine. Then merge-sort them to a master
: machine.
c*t
8 楼
我觉得，选择push还是poll要看requirement，如果这k个数据很常用，时时刻刻都会被
调用，那就push吧，如果只是偶尔查，那就要用的时候再从各个机器上poll.无论哪种
，都要在每台机器上存这个heap,否则传输出什么问题怎么办？
【在 a**********e 的大作中提到】
: 谢谢。
: 既然涉及master machine，可不可以每次有data进来，（在store在各个机器上的同时
: ），直接
: 把data也push一份到master machine上，这样只要在master machine上维持max heap就
: 可以了。
: 这样有什么问题呢？
:
: master
调用，那就push吧，如果只是偶尔查，那就要用的时候再从各个机器上poll.无论哪种
，都要在每台机器上存这个heap,否则传输出什么问题怎么办？
【在 a**********e 的大作中提到】
: 谢谢。
: 既然涉及master machine，可不可以每次有data进来，（在store在各个机器上的同时
: ），直接
: 把data也push一份到master machine上，这样只要在master machine上维持max heap就
: 可以了。
: 这样有什么问题呢？
:
: master
相关阅读
谢谢某培训机构一直帮 来Offer 打广告人在已经开始工作h1b还没批下来 怎么去中国领事馆换护照请问offer一般给几天时间答复？有多少人参加了FLG在market上举办的庆祝活动？老中Bart janitor 年收入 $270，000请问，跳槽h1b transfer期间方便回国签证吗？“蒙面小王子”（侧田）太为码农长志了OPT extension 是不是最好尽量往后拖拖申请？这样延长整个opt时间？Uber 也没传说中的压力山大啊，我看uber可以砍一半弱弱的问问：一道排序的题芝加哥地区招Data Scientist和偏重前端的Analyst最后10天博彩：2016年第58届美国总统大选 (转载)问一个java generic的问题google明年的fresh graduate现在就开始要team match吗？[长期，稳定，迅速]提供Amazon内推求Uber, twosigma and snapchat referralUber ATC我其实一直想为一家在美的中国公司工作请问版上有在Oracle的吗？求refer有人会降薪跳槽吗？