z****1
发帖数: 1103 | 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***A
发帖数: 849 | |
z****1
发帖数: 1103 | 3 testing whether a number is in the set in constant time＂
这个让我感觉要hash。除了hash，啥方式保证search是 constant time？
不过也别被我误导，因为我不知道答案。
【在 U***A 的大作中提到】
: BIT MAP?
|
d**********6
发帖数: 4434 | 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****1
发帖数: 1103 | 5 我正是这么想的：考点是找到合适的hash function。
但因为memory efficient的要求，我找不到合适的。要能找到long long类型的数据啊
！stack直接暴掉。去heap里刨地方，不符合memory efficient。反正我黔驴了。
【在 d**********6 的大作中提到】
: hash符合存储都是O(1)，就是memory efficient这个问题要麻烦点
: 感觉他要你写的是这个hash函数
|
z****1
发帖数: 1103 | 6 STL 里的set就是hash bashed, 你随便放long long。这个hash function几十年前就做
好了。
不知道如何 set 里的hash function 原码google 出来。 |
m*****g
发帖数: 71 | 7 我觉得别想太复杂了，应该就是问hash table吧，hash function也不用复杂，用mod就
得了，size设成prime number，就能满足要求了。主要是和面试官讨论数据有多大，考
虑要不要用1个bit来代表一个数字，数据不大用byte就行了。
我分析考点是看你知不知道hash table，别上来开一个2^64的bool数组就行了。 |
D***n
发帖数: 149 | |
