标 题: Qualcomm的面经
发信站: BBS 未名空间站 (Mon Apr 4 20:14:32 2011, 美东)
倒是没有问什么太难的算法和数据结构方面的题，大多是和实际工作相结合的题目，比如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（或者vector）吧？
而且，map的access复杂度似乎比Hash Table要差吧？不好意思，还没查到map的access复杂度是多少。
发信人: HanSolo7 (隼), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Mon Apr 4 20:22:48 2011, 美东)
Hash table with a really good hash function (if he really wanna constant time access). That's my answer.
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Mon Apr 4 20:25:13 2011, 美东)
一个很好的hash function是不是能把linked list的长度减到尽可能的低？反正我是想不出来还是什么更好的数据结构了。
顺便问一下，map的access复杂度是多少啊？
发信人: HanSolo7 (隼), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Mon Apr 4 20:38:21 2011, 美东)
是啊。map在c++里是红黑树实现的吧。那就是O(logn)吧。
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Mon Apr 4 20:56:13 2011, 美东)
对了，想起来当时因为大叔提出用数组range不好确定，我还提出了用vector，但是忘记是出于什么原因，也被否决了。
其实vector是个不错的选择，而且能实现O(1)的access，但为什么也不行呢？纳闷。
发信人: gzou (gzou), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Mon Apr 4 22:54:50 2011, 美东)
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, 所以不知道这是否符合要求呢？
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 09:00:11 2011, 美东)
谢谢楼上的回复。对，我面的是experienced的职位。大叔说的acess time是O(1)的意思应该是access每个元素的意思吧，他当时没提到最大或者最小。
另外，vector的access time是不是O(1)啊？不晓得vector有什么劣势。
昨晚睡了一觉，又想起来一些当时的具体情节。
有个函数，void timeout_register(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才能尽量减小链表长度呢？
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 09:05:32 2011, 美东)
顺带说一下，如果可以用array的话，那么我把这个time_out的值作为这个array的index，也可以实现O(1)的search（实质上已经转换为array的index操作）。不过因为range不好事先确定，所以不能用。
发信人: gzou (gzou), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 09:35:49 2011, 美东)
我的想法是如果需要 time-out call对应的function的话，那么只要一个heap或者说priority_queue就可以了：一开始把所有time-out的时间推入，然后堆顶的元素就是下一个我们需要执行的函数的方程。
heap中的每个节点对应的是
access的time是O(1).
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 10:06:50 2011, 美东)
大叔似乎说过time_out的排列是无序的，比如：5，3，1，10，……这种情况下，也可以把它们推进一个堆里吗？
另外问一下，http://www.cplusplus.com/里面没有找到heap的数据结构的解释和说明，还有什么地方可以参考吗？
发信人: gzou (gzou), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 10:41:04 2011, 美东)
在stl里面已经包含了heap的实现，见：http://www.cplusplus.com/reference/stl/priority_queue/
输入无序没有关系，heap可以自动调整（heapify），它可以保证推定的元素就是目前堆中最小的元素(min heap)，调整的时间是o(log n)，但是access time的话就是O(1)， 每次取堆顶就可以了。
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 10:59:38 2011, 美东)
－－－
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.
－－－
从这里看，好象堆顶的元素是最大的啊。怎样让它弹出最小元素呢？
发信人: gzou (gzou), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 11:10:45 2011, 美东)
check this: http://www.cplusplus.com/reference/stl/priority_queue/priority_queue/
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.
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 11:37:30 2011, 美东)
谢谢，了解了。
顺便再问一下，如果我用vector来做，用time_out的值做index，是不是也可以做到O(1)的access呢？
发信人: speeddy (Wade), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 11:47:34 2011, 美东)
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-System/dp/0201702452
No comments:
Post a Comment