m**r
发帖数: 574 | 1 G家的：Describe an algorithm to find the largest 1 million numbers in 1
billion numbers. Assume that the computer memory can hold all one billion
numbers.
find the Kth number.
能不能给我讲讲这种题应该怎么写？ |
s*******s
发帖数: 1031 | 2 use a 1million size 的 min-heap.
在填满1M数后，当碰到 <= minimum的数，skip，
当碰到> minimum的数的时侯， pop出当前的最小数，插入新的大数。
然后对min-heap 排序
Time: 1G * log(1M)
【在 m**r 的大作中提到】
: G家的：Describe an algorithm to find the largest 1 million numbers in 1
: billion numbers. Assume that the computer memory can hold all one billion
: numbers.
: find the Kth number.
: 能不能给我讲讲这种题应该怎么写？
|
r*******e
发帖数: 7583 | 3 这是单机器的答案，常见的follow-up是如何利用多台机器加快速度
billion
【在 s*******s 的大作中提到】
: use a 1million size 的 min-heap.
: 在填满1M数后，当碰到 <= minimum的数，skip，
: 当碰到> minimum的数的时侯， pop出当前的最小数，插入新的大数。
: 然后对min-heap 排序
: Time: 1G * log(1M)
|
h****y
发帖数: 137 | 4 有linear的解法, 直接用selection algorithm
【在 s*******s 的大作中提到】
: use a 1million size 的 min-heap.
: 在填满1M数后，当碰到 <= minimum的数，skip，
: 当碰到> minimum的数的时侯， pop出当前的最小数，插入新的大数。
: 然后对min-heap 排序
: Time: 1G * log(1M)
|
s*******s
发帖数: 1031 | 5 对，那样就要map reduce了。
【在 r*******e 的大作中提到】
: 这是单机器的答案，常见的follow-up是如何利用多台机器加快速度
:
: billion
|
b******7
发帖数: 92 | 6 题目都说了memory can hold all one billion，干嘛要用堆以及map reduce ？
直接selection algorithm就ok了
这不是常见的那道题，常见的那道内存放不下全部数据。这种题感觉就是在测试你是不
是在刷题 |
c********p
发帖数: 1969 | |
p*****2
发帖数: 21240 | 8 我面G的时候我说用quick selection, 面试官张口就说“你敢写吗？”，我心想为什么
不敢写。但是客气的说，我可以试试。结果被要求写了一个nlogk的。然后他说他有一
个更好的可以O(n), 后来发现space 也需要O(n)。 |
