G面试题求解 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

G面试题求解

G面试题求解# JobHunting - 待字闺中

h*r2014-09-15 07:09

1 楼

版上曾经出现的一道题，没想出正确解法，大牛们讨论讨论，指点一下
给两个部分排序的文件和partially sorted的值m，部分排序是定义为比如1 2 4 5
6 7 3， 3应该在2后面，那么3的partially sorted的值就是4.因为最多放在该点前面
4个index的位置。要实现两个file merge的输出，要输出的file是排序的。限制是file
很大很大，不能放在内存里面处理。

r*32014-09-15 07:09

2 楼

只有最后一个数字是乱序的么？
如果m不是很大，可以每次读m+1个数字，在缓存中，如果发现最后一个数字小于第一个
数字，就把最后一个数字先比较。

file

【在 h***r 的大作中提到】

: 版上曾经出现的一道题，没想出正确解法，大牛们讨论讨论，指点一下
: 给两个部分排序的文件和partially sorted的值m，部分排序是定义为比如1 2 4 5
: 6 7 3， 3应该在2后面，那么3的partially sorted的值就是4.因为最多放在该点前面
: 4个index的位置。要实现两个file merge的输出，要输出的file是排序的。限制是file
: 很大很大，不能放在内存里面处理。

a*a2014-09-15 07:09

3 楼

应该是两个size为m的min-heap（这样能确保min再其中一个heap里面）
heap 1 负责 file 1, heap 2 负责 file 2
每次extract min(root1, root2) 写到 f3, 然后insert new value into the heap
直到file读完 heaps 都为空
至于内存限制.... f3 写的差不多了就存到disk一下