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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 楼主，你说的table，是指数组？还是什么数据结构？
|
