由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Find the intersection of two sorted arrays【扩展】
相关主题
请教一下external sorting的问题a question
找2个sorted array中的第K小的元素,有O(lgn)方法吗?新鲜C3 energy面经
两个Sorted Array,找K smallest element问道面试题
一道google题Extension problem of finding intersection of two sorted array
贡献两个Amazon的电话面试题The time complexity on finding the kth largest element in a
被Facebook的面试的一道题目难倒了一个小公司面经
老问题了,网上竟然找不到答案问一道老题
问一下deep copy和shallow copy的问题(C#)分享下Google电面题
相关话题的讨论汇总
话题: memory话题: find话题: arrays话题: sorted
进入JobHunting版参与讨论
1 (共1页)
h*****g
发帖数: 312
1
Let’s called array1 as A and array2 as B, each with size m and n.
正常的话,O(m+n)应该可以搞定,但是。。。
if n is very very large, the memory can not hold it.
i) What if elements of array B is stored on disk, and the memory is limited
such that you cannot load all elements into the memory at once?
ii) How will the complexity change in this case? Are there any factors you
need to consider?
iii) How do you change your solution to adapt to this situation?
如果用external sort类似的方法,该咋做呢?
f***g
发帖数: 214
2
External 是k-way,这里只有2个。
不是已经有序了吗,每次都load一部分到内存。
然后merge,不够了再load一部分。
要不就binary search,如果m小的话。
h*****g
发帖数: 312
3
如果2-way merge,时间复杂度是多少?还是O(m+n)吧

【在 f***g 的大作中提到】
: External 是k-way,这里只有2个。
: 不是已经有序了吗,每次都load一部分到内存。
: 然后merge,不够了再load一部分。
: 要不就binary search,如果m小的话。

m**q
发帖数: 189
4
How about using B+ tree?
The tree itself will reside in memory, and you can do
a search in the tree for each element in A, locate the
appropriate block range and lock it into memory. That
way you don't need to traverse the whole B array and
thus should be faster, assuming m is relatively small.

limited

【在 h*****g 的大作中提到】
: Let’s called array1 as A and array2 as B, each with size m and n.
: 正常的话,O(m+n)应该可以搞定,但是。。。
: if n is very very large, the memory can not hold it.
: i) What if elements of array B is stored on disk, and the memory is limited
: such that you cannot load all elements into the memory at once?
: ii) How will the complexity change in this case? Are there any factors you
: need to consider?
: iii) How do you change your solution to adapt to this situation?
: 如果用external sort类似的方法,该咋做呢?

1 (共1页)
进入JobHunting版参与讨论
相关主题
分享下Google电面题贡献两个Amazon的电话面试题
amazon tel interview被Facebook的面试的一道题目难倒了
请问一个老的google题老问题了,网上竟然找不到答案
One Amazon question问一下deep copy和shallow copy的问题(C#)
请教一下external sorting的问题a question
找2个sorted array中的第K小的元素,有O(lgn)方法吗?新鲜C3 energy面经
两个Sorted Array,找K smallest element问道面试题
一道google题Extension problem of finding intersection of two sorted array
相关话题的讨论汇总
话题: memory话题: find话题: arrays话题: sorted