c***n 发帖数: 588 | 1 T大家都知道,就不说了。
搜索引擎经常做的,每秒可能上千次请求,每来一个query, 马上找到百万个结果匹配
,现在要排序,问题如下.
Given 两个大数组(million level),分别是ID和Value数组,ID[i]的分数对应Value[i
],现在已知这两个大数组按照ID排序,要求现在把Value按照从大到小排序,ID数组也
做根据Value相应变化。
实现以下function:
BortByVal(int[] ID, double[] Value)
没有明白这道题要考什么,不就是quick sort吗, 难道两个数组有何trick? |
i**********e 发帖数: 1145 | 2 Value[] 数组里有给一个range吗?
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
c***n 发帖数: 588 | 3 say between [0,1]
any clue here?
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Value[] 数组里有给一个range吗? : 一些常见面试题的答案与总结 - : http://www.ihas1337code.com
|
i**********e 发帖数: 1145 | 4 Assume you can use extra memory, you can use a bitmap.
Depend on the precision you need, the memory used might be big. If you need
double's precision to be 8, then slots needed is 10^8. Put its ID into the
bitmap using the multiplied value (x10^8) as index.
At the end, traverse the bitmap in order and copy back to the array of ID
and values.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 c***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : say between [0,1] : any clue here?
|
c***n 发帖数: 588 | 5 what about value repeats, meaning the value corrresponding to multiple IDs?
repeated values should be a very common thing I think.
need
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Assume you can use extra memory, you can use a bitmap. : Depend on the precision you need, the memory used might be big. If you need : double's precision to be 8, then slots needed is 10^8. Put its ID into the : bitmap using the multiplied value (x10^8) as index. : At the end, traverse the bitmap in order and copy back to the array of ID : and values. : 一些常见面试题的答案与总结 - : http://www.ihas1337code.com
|
i**********e 发帖数: 1145 | 6 Sure.
Assume if there's at most 7 duplicates,you can use 3 bits to store the
number of IDs for each value. This require 3x the original space.
You can implement this very efficiently using bitmask and shifting operation.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 c***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : what about value repeats, meaning the value corrresponding to multiple IDs? : repeated values should be a very common thing I think. : : need
|
c***n 发帖数: 588 | 7 i see, looks like I need to have two tables, one for counting, another one
for inserting IDs based on the counting table, only this can make O(
n), right? otherwise, using 1 table, can not gurantee it's O(n) bitmask and
shifting
operation.
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Sure. : Assume if there's at most 7 duplicates,you can use 3 bits to store the : number of IDs for each value. This require 3x the original space. : You can implement this very efficiently using bitmask and shifting operation. : 一些常见面试题的答案与总结 - : http://www.ihas1337code.com
|
i**********e 发帖数: 1145 | 8 Ah... I forgot about the IDs. Instead of using two tables, why not use a
linked list? Each values index to the head of the list that stores all IDs
that have the value.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
and
【在 c***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : i see, looks like I need to have two tables, one for counting, another one : for inserting IDs based on the counting table, only this can make O( : n), right? otherwise, using 1 table, can not gurantee it's O(n) bitmask and : shifting : : operation.
|
c***n 发帖数: 588 | 9 then the problem is more complex since you have to decide whether a value is
an index or an Linkedlist address, furthermore, if repeats are a lot, the
Linkedlist is not efficient due to locality problem
so how about just using another table directly:)
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Ah... I forgot about the IDs. Instead of using two tables, why not use a : linked list? Each values index to the head of the list that stores all IDs : that have the value. : 一些常见面试题的答案与总结 - : http://www.ihas1337code.com : : and
|
c******t 发帖数: 1500 | 10 楼主,你说的table,是指数组?还是什么数据结构? |
c***n 发帖数: 588 | 11 array
【在 c******t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 楼主,你说的table,是指数组?还是什么数据结构?
|