f*****2
发帖数: 10 | 1 M个数放到了N个数组里， 每个数组都是升序，长度不一
找第K个最小的元素
我这是最近面到的。
我首先抛出了找K的经典解法， Selection Algorithm + Median of Medians, 当然它
是针对一个无序的数组。如果每个数组都比K长，我可以取每个数组的前K个，视它为一
个一维无序数组。这个给否了。
我又抛出 Median of Two Sorted Arrays, 分4区，然后抛弃1区的解法， 给否了。
我又抛出海量数据处理Top-K的典型解法， Max-Heap，假如数组非常大。 给否了。
大家有木有好方法， 有一点要注意的是， 分析K相对于数组长度， 解法也许不同。 |
k*******t
发帖数: 144 | 2 用N个指针＋min_heap＋counter，N个指针一开始都指向每个数组的第一个元素，并把N
个指针对应的值放到min_heap, 产生一个最小的值，
do {pop, 同时找出pop出去元素所在的数组，++counter, 该数组的当前指针再往前移
动一位，并把该指针的值放入min_heap} 直到counter等于k。这个方法相对于max_heap
的好处就是不需要将M个数都放到heap中去。 说不定还有更好的解法，等待牛人解答。 |
p*****2
发帖数: 21240 | 3
把N
heap
如果K＝＝M？
【在 k*******t 的大作中提到】
: 用N个指针＋min_heap＋counter，N个指针一开始都指向每个数组的第一个元素，并把N
: 个指针对应的值放到min_heap, 产生一个最小的值，
: do {pop, 同时找出pop出去元素所在的数组，++counter, 该数组的当前指针再往前移
: 动一位，并把该指针的值放入min_heap} 直到counter等于k。这个方法相对于max_heap
: 的好处就是不需要将M个数都放到heap中去。 说不定还有更好的解法，等待牛人解答。
|
c********p
发帖数: 1969 | |
k*******t
发帖数: 144 | 5 这个方法还是linear的。突然想起来有个求kth element of two sorted elements的题
, 比较优的方法用binary search的方法做的，感觉可以借鉴binary search的方法。不
知是否好点啦。
【在 p*****2 的大作中提到】
:
: 把N
: heap
: 如果K＝＝M？
|
p*****2
发帖数: 21240 | 6
有可能。不过代码不太好写呀。
【在 k*******t 的大作中提到】
: 这个方法还是linear的。突然想起来有个求kth element of two sorted elements的题
: , 比较优的方法用binary search的方法做的，感觉可以借鉴binary search的方法。不
: 知是否好点啦。
|
s***5
发帖数: 2136 | 7 maxheap也不需要把数都放进去啊。放k个就行。
把N
heap
【在 k*******t 的大作中提到】
: 用N个指针＋min_heap＋counter，N个指针一开始都指向每个数组的第一个元素，并把N
: 个指针对应的值放到min_heap, 产生一个最小的值，
: do {pop, 同时找出pop出去元素所在的数组，++counter, 该数组的当前指针再往前移
: 动一位，并把该指针的值放入min_heap} 直到counter等于k。这个方法相对于max_heap
: 的好处就是不需要将M个数都放到heap中去。 说不定还有更好的解法，等待牛人解答。
|
k*******t
发帖数: 144 | 8 确实。继续求更好的方法
【在 p*****2 的大作中提到】
:
: 有可能。不过代码不太好写呀。
|
a*****u
发帖数: 1712 | 9 sorted!这么重要的条件，你的方法一方法三都没有用！
应该用类似merge sorted array/linkedlist的一个方法，用一个size为N的min heap,
时间复杂度O(k) |
a*****u
发帖数: 1712 | 10 我说的就这个方法。面试的时候这个方法就够用了，如果有更好的当然是bonus，这个
都没给出来就想更fancy的方法就不合适了。
把N
heap
【在 k*******t 的大作中提到】
: 用N个指针＋min_heap＋counter，N个指针一开始都指向每个数组的第一个元素，并把N
: 个指针对应的值放到min_heap, 产生一个最小的值，
: do {pop, 同时找出pop出去元素所在的数组，++counter, 该数组的当前指针再往前移
: 动一位，并把该指针的值放入min_heap} 直到counter等于k。这个方法相对于max_heap
: 的好处就是不需要将M个数都放到heap中去。 说不定还有更好的解法，等待牛人解答。
|
|
|
f*****2
发帖数: 10 | 11 我要是面人，觉得答出这个也就行了。这个hirING Bar是有点高。
提过用heap， 不过还没说完就给直接否定了。显然不是他想要的，应该还有最优的，
可能是分治，某种分治。
你说的这个大致是 O（K*logK）time， O（K) space, for the heap of size K.
讨论讨论K相对M的情况。。。有没有新点子。
==
我说的就这个方法。面试的时候这个方法就够用了，如果有更好的当然是bonus，这个
都没给出来就想更fancy的方法就不合适了。
把N
heap
【在 k*******t 的大作中提到】
: 用N个指针＋min_heap＋counter，N个指针一开始都指向每个数组的第一个元素，并把N
: 个指针对应的值放到min_heap, 产生一个最小的值，
: do {pop, 同时找出pop出去元素所在的数组，++counter, 该数组的当前指针再往前移
: 动一位，并把该指针的值放入min_heap} 直到counter等于k。这个方法相对于max_heap
: 的好处就是不需要将M个数都放到heap中去。 说不定还有更好的解法，等待牛人解答。
|
f*****2
发帖数: 10 | 12 K很小，min heap, O（K*logK）time 是可行的，
K接近M，视为无序一维的，median of medians, O(M) 更好。
这些讨论是假设单机内存可以装得下M。征更好的解。。
，
【在 f*****2 的大作中提到】
: 我要是面人，觉得答出这个也就行了。这个hirING Bar是有点高。
: 提过用heap， 不过还没说完就给直接否定了。显然不是他想要的，应该还有最优的，
: 可能是分治，某种分治。
: 你说的这个大致是 O（K*logK）time， O（K) space, for the heap of size K.
: 讨论讨论K相对M的情况。。。有没有新点子。
: ==
: 我说的就这个方法。面试的时候这个方法就够用了，如果有更好的当然是bonus，这个
: 都没给出来就想更fancy的方法就不合适了。
:
: 把N
|
a*****u
发帖数: 1712 | 13 你好像理解错了，heap size是N，不是K，你再仔细看一下
，
【在 f*****2 的大作中提到】
: 我要是面人，觉得答出这个也就行了。这个hirING Bar是有点高。
: 提过用heap， 不过还没说完就给直接否定了。显然不是他想要的，应该还有最优的，
: 可能是分治，某种分治。
: 你说的这个大致是 O（K*logK）time， O（K) space, for the heap of size K.
: 讨论讨论K相对M的情况。。。有没有新点子。
: ==
: 我说的就这个方法。面试的时候这个方法就够用了，如果有更好的当然是bonus，这个
: 都没给出来就想更fancy的方法就不合适了。
:
: 把N
|
e*******8
发帖数: 94 | 14 这题我记得programming problems上好象有(selection in big data) |
f*****2
发帖数: 10 | 15 展开说说？这是书吗？
【在 e*******8 的大作中提到】
: 这题我记得programming problems上好象有(selection in big data)
|
f*****2
发帖数: 10 | 16 谢谢纠正
【在 a*****u 的大作中提到】
: 你好像理解错了，heap size是N，不是K，你再仔细看一下
:
: ，
|
f*****2
发帖数: 10 | 17 说详细点？
有可能。不过代码不太好写呀。
【在 k*******t 的大作中提到】
: 这个方法还是linear的。突然想起来有个求kth element of two sorted elements的题
: , 比较优的方法用binary search的方法做的，感觉可以借鉴binary search的方法。不
: 知是否好点啦。
|
s*******n
发帖数: 305 | |
g**e
发帖数: 6127 | 19 master node随机选个数t，发送给slave nodes，每个node找出比t小的个数返回master
node。如果加起来等于K，结束。否则抛弃一半，继续找。
这算法没意思，应该直接引申到怎么从n个node选master node的leader election设计
。当然像半海大牛那样直接说zookeeper就完事了
的题
。不
【在 f*****2 的大作中提到】
: 说详细点？
:
: 有可能。不过代码不太好写呀。
|
z****e
发帖数: 54598 | 20 原来是变形的mapreduce题呀
一开始被一堆数组迷惑了，还以为是算法题呢
master
【在 g**e 的大作中提到】
: master node随机选个数t，发送给slave nodes，每个node找出比t小的个数返回master
: node。如果加起来等于K，结束。否则抛弃一半，继续找。
: 这算法没意思，应该直接引申到怎么从n个node选master node的leader election设计
: 。当然像半海大牛那样直接说zookeeper就完事了
:
: 的题
: 。不
|
h****p
发帖数: 87 | |
