j***y
发帖数: 2074 | 1 倒是没有问什么太难的算法和数据结构方面的题，大多是和实际工作相结合的题目，比
如debug一段程序，等等，都不算难。
不过还是有个数据结构的问题把我问倒了：
具体问题的起源我也记不清了，反正就是要求我implement一个数据结构，要求access
是O(1)量级的。
一开始我提了用数组，但是被否决，因为将要储存的数据量很大而且预先不知道终止条
件，所以很难给定数组的range。
用list显然也不可行，因为list一般是unsorted的，要找一个数据，必须遍历一次，也
就是O(n)的complexity。
接着我又提了Hash Table，隐约记得Hash Table的access是O(1)的量级，但大叔说如果
Hash Table的row是M，而每个entry（key mapped via hash function）是个linked
list（因为不同key的key-value pair经过hash function的运算后得出相同的index）
，假设linked list里面所含的元素是N，那么access的时间复杂度是O(N/M)。好了，再
次被枪毙。
最后，我在大叔这里面试的时间到了，大叔一边把我送到下个interviewer那里，一边
在路上叫我继续考虑这个问题。郁闷啊。
难道还有比Hash Table更快access的数据结构？难道是C++里面的map？但是map如果key
有重复的话，value也是一个linked list吧？
而且，map的access复杂度似乎比Hash Table要差吧？不好意思，还没查到map的access
复杂度是多少。 |
H******7
发帖数: 1728 | 2 hash table with a really good hash function. (if he really wanna constant
time access)
That's my answer. |
j***y
发帖数: 2074 | 3 一个很好的hash function是不是能把linked list的长度减到尽可能的低？反正我是想
不出来还是什么更好的数据结构了
顺便问一下，map的access复杂度是多少啊？ |
H******7
发帖数: 1728 | 4 是啊。
map在c++里是红黑树实现的吧。那就是O(logn)吧。
【在 j***y 的大作中提到】
: 一个很好的hash function是不是能把linked list的长度减到尽可能的低？反正我是想
: 不出来还是什么更好的数据结构了
: 顺便问一下，map的access复杂度是多少啊？
|
j***y
发帖数: 2074 | 5 对了，想起来当时因为大叔提出用数组range不好确定，我还提出了用vector，但是忘
记是出于什么原因，也被否决了。
其实vector是个不错的选择，而且能实现O(1)的access，但为什么也不行呢？纳闷。 |
g**u
发帖数: 583 | 6 lz面的是experienced？，为什么都是问工作的问题
可以解释下access time 是 O(1)？ 具体的是要access每一个element都是O(1)，还是
说只是说access最大或者最小是O(1)? 需要保持插入有序么，还是只要取出有序就可以
了？
要取得所有的element的access time O(1)的话，应该是hash了。
BTW， std::map的实现是红黑树，时间是log(n)， 但是std::tr1::unordered_map的可
以达到O(1)access time，但是它的实现也适用到了hasher function, 所以不知道这是
否符合要求呢？ |
j***y
发帖数: 2074 | 7 谢谢楼上的回复。对，我面的是experienced的职位。大叔说的acess time是O(1)的意
思应该是access每个元素的意思吧，他当时没提到最大或者最小。
另外，vector的access time是不是O(1)啊？不晓得vector有什么劣势。
昨晚睡了一觉，又想起来一些当时的具体情节。
有个函数，void do_something(int time_out, void (*fprt)(float *), .../*
parameter list to the function pointer */)
有个timer，每隔一秒钟就timeout一次，会call这个do_something()，要求是设计并实
现一个数据结构，以达到当timeout时，找出当前的time_out值对应的function，跑一
遍，再从数据结构里删除这个entry。
比如，time_out的值是3秒的时候，必须把这个数据结构里面3秒所对应的function调出
来跑。
要求对找到这个function entry的search的时间复杂度是O(1)。
用hash table的话，如果key-value pair中value是一个很长的链表，确实效率不太高
。为此，一般对string作key的hash table，会用一个特定的multiplier（通常是31）
来multiply这个string中每个char的值生成一个index，再%sizeof(hash_table)以达到
链表的长度最小。
但是对我这个问题，我想如果用time_out的值作为key的话，该用什么样的hash
function才能尽量减小链表长度呢？ |
j***y
发帖数: 2074 | 8 顺带说一下，如果可以用array的话，那么我把这个time_out的值作为这个array的
index，也可以实现O(1)的search（实质上已经转换为array的index操作）。不过因为
range不好事先确定，所以不能用。 |
g**u
发帖数: 583 | 9 我的想法是如果需要 time-out call对应的function的话，那么只要一个heap或者说
priority_queue就可以了， 一开始把所有time-out的时间入推，然后堆顶的元素就是
下一个我们需要执行的函数的方程。
heap中的每个节点对应的是， 每次堆顶的元素
就是我们需要执行的函数了。
access的time是 O(1).
【在 j***y 的大作中提到】
: 谢谢楼上的回复。对，我面的是experienced的职位。大叔说的acess time是O(1)的意
: 思应该是access每个元素的意思吧，他当时没提到最大或者最小。
: 另外，vector的access time是不是O(1)啊？不晓得vector有什么劣势。
: 昨晚睡了一觉，又想起来一些当时的具体情节。
: 有个函数，void do_something(int time_out, void (*fprt)(float *), .../*
: parameter list to the function pointer */)
: 有个timer，每隔一秒钟就timeout一次，会call这个do_something()，要求是设计并实
: 现一个数据结构，以达到当timeout时，找出当前的time_out值对应的function，跑一
: 遍，再从数据结构里删除这个entry。
: 比如，time_out的值是3秒的时候，必须把这个数据结构里面3秒所对应的function调出
|
j***y
发帖数: 2074 | 10 大叔似乎说过time_out的排列是无序的，比如：5，3，1，10，……这种情况下，也可
以把它们推进一个堆里吗？
另外问一下，http://www.cplusplus.com/里面没有找到heap的数据结构的解释和说明，还有什么地方可以参考吗？
谢谢gzou。 |
|
|
g**u
发帖数: 583 | 11
在 std里面已经包含了 heap的实现， 见：
http://www.cplusplus.com/reference/stl/priority_queue/
输入无需没有关系，heap可以自动调整（heapify），它可以保证推定的元素就是目前
堆中最小的元素(min heap)， 调整的时间是o(log n)， 但是access time的话就是 O(
1)， 每次取堆顶就可以了
【在 j***y 的大作中提到】
: 大叔似乎说过time_out的排列是无序的，比如：5，3，1，10，……这种情况下，也可
: 以把它们推进一个堆里吗？
: 另外问一下，http://www.cplusplus.com/里面没有找到heap的数据结构的解释和说明，还有什么地方可以参考吗？
: 谢谢gzou。
|
j***y
发帖数: 2074 | 12 －－－
Priority queues are a type of container adaptors, specifically designed such
that its first element is always the greatest of the elements it contains,
according to some strict weak ordering condition.
－－－
从这里看，好象堆顶的元素是最大的啊。怎样让它弹出最小元素呢？ |
g**u
发帖数: 583 | 13
such
,
check this:
http://www.cplusplus.com/reference/stl/priority_queue/priority_
All you need to do is to override the default comparator, so that you can
pass your own one. In this case, you can put the smallest at the top.
Just try run the examples in the link, and see what you get.
【在 j***y 的大作中提到】
: －－－
: Priority queues are a type of container adaptors, specifically designed such
: that its first element is always the greatest of the elements it contains,
: according to some strict weak ordering condition.
: －－－
: 从这里看，好象堆顶的元素是最大的啊。怎样让它弹出最小元素呢？
|
j***y
发帖数: 2074 | 14 谢谢，了解了。
顺便再问一下，如果我用vector来做，用time_out的值做index，是不是也可以做到O(1
)的access呢？ |
s*****y
发帖数: 897 | 15 Look at freebsd source code
It seems in timer.h.
Freebsd's author talk about this how he implenmenet the timer in his freebsd
teaching videos.
The book is http://www.amazon.com/Design-Implementation-FreeBSD-Operating-Sy
stem/dp/0201702452
【在 j***y 的大作中提到】
: 谢谢楼上的回复。对，我面的是experienced的职位。大叔说的acess time是O(1)的意
: 思应该是access每个元素的意思吧，他当时没提到最大或者最小。
: 另外，vector的access time是不是O(1)啊？不晓得vector有什么劣势。
: 昨晚睡了一觉，又想起来一些当时的具体情节。
: 有个函数，void do_something(int time_out, void (*fprt)(float *), .../*
: parameter list to the function pointer */)
: 有个timer，每隔一秒钟就timeout一次，会call这个do_something()，要求是设计并实
: 现一个数据结构，以达到当timeout时，找出当前的time_out值对应的function，跑一
: 遍，再从数据结构里删除这个entry。
: 比如，time_out的值是3秒的时候，必须把这个数据结构里面3秒所对应的function调出
|
j***y
发帖数: 2074 | 16 请问speedy可否将timer.h的相关部分贴一下？我不知道去哪里下载FreeBSD的源代码。 |
c*****l
发帖数: 879 | |
