问问谁会这道算法的面试题？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

问问谁会这道算法的面试题？

问问谁会这道算法的面试题？# JobHunting - 待字闺中

z*12015-03-10 07:03

1 楼

Design a data structure to track whether a given number is in a collection.
The structure must be memory efficient, able to house all the numbers
possible with an unsigned long long, alow adding numbers to the set in
constant time, and testing whether a number is in the set in constant time。

U*A2015-03-10 07:03

2 楼

BIT MAP?

z*12015-03-10 07:03

3 楼

testing whether a number is in the set in constant time＂
这个让我感觉要hash。除了hash，啥方式保证search是 constant time？
不过也别被我误导，因为我不知道答案。

【在 U***A 的大作中提到】

: BIT MAP?

d*62015-03-10 07:03

4 楼

hash符合存储都是O(1)，就是memory efficient这个问题要麻烦点
感觉他要你写的是这个hash函数

【在 z****1 的大作中提到】

: testing whether a number is in the set in constant time＂
: 这个让我感觉要hash。除了hash，啥方式保证search是 constant time？
: 不过也别被我误导，因为我不知道答案。

z*12015-03-10 07:03

5 楼

我正是这么想的：考点是找到合适的hash function。
但因为memory efficient的要求，我找不到合适的。要能找到long long类型的数据啊
！stack直接暴掉。去heap里刨地方，不符合memory efficient。反正我黔驴了。

【在 d**********6 的大作中提到】

: hash符合存储都是O(1)，就是memory efficient这个问题要麻烦点
: 感觉他要你写的是这个hash函数

z*12015-03-10 07:03

6 楼

STL 里的set就是hash bashed, 你随便放long long。这个hash function几十年前就做
好了。
不知道如何 set 里的hash function 原码google 出来。

m*g2015-03-10 07:03

7 楼

我觉得别想太复杂了，应该就是问hash table吧，hash function也不用复杂，用mod就
得了，size设成prime number，就能满足要求了。主要是和面试官讨论数据有多大，考
虑要不要用1个bit来代表一个数字，数据不大用byte就行了。
我分析考点是看你知不知道hash table，别上来开一个2^64的bool数组就行了。