一道T的题。 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道T的题。

一道T的题。# JobHunting - 待字闺中

c*n2011-05-06 07:05

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*e2011-05-06 07:05

2 楼

Value[] 数组里有给一个range吗？
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

c*n2011-05-06 07:05

3 楼

say between [0,1]
any clue here?

【在 i**********e 的大作中提到】

: Value[] 数组里有给一个range吗？
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

i*e2011-05-06 07:05

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*n2011-05-06 07:05

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*e2011-05-06 07:05

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*n2011-05-06 07:05

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*e2011-05-06 07:05

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*n2011-05-06 07:05

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