求教一个dropbox面试题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

求教一个dropbox面试题

求教一个dropbox面试题# JobHunting - 待字闺中

a*d2015-01-17 08:01

1 楼

Implement two functions that assign/release unique id's from a pool. Memory
usage should be minimized and the assign/release should be fast, even under
high contention.
目前想法就是两个HashSet 一个放用过的ID 一个放没用过的ID, 每次assign 和
release时修改这两个HashSet.
不过如果多线程情况下容易成为瓶颈.

a*d2015-01-17 08:01

2 楼

或者可以把所有可用IDs 分成N 段, 然后这N段IDs 之间互相独立, 就可以并行访问修
改了.
目前只能想到这么多.

Memory
under

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

: Implement two functions that assign/release unique id's from a pool. Memory
: usage should be minimized and the assign/release should be fast, even under
: high contention.
: 目前想法就是两个HashSet 一个放用过的ID 一个放没用过的ID, 每次assign 和
: release时修改这两个HashSet.
: 不过如果多线程情况下容易成为瓶颈.

h*c2015-01-17 08:01

3 楼

如你第二段说，如果把线性分段设置成树状结构呢？
锁树节点而不是锁，assign, release,可能好一些

w*i2015-01-17 08:01

4 楼

hashset虽然耗的内存是O(N)，但是常数大。我onsite也面过这题，做出来后说把
hashset换掉。纯array做都不够，最后被逼着往bitmap上想。这个有点类似于实现一个
文件系统，metadata区域有个bitmap表示哪些block被分配。
个人觉得这题很坑爹，最后用居然时间换内存。bitmap上只能线性查找，只不过用多层
不同粒度去优化。

a*u2015-01-17 08:01

5 楼

bitmap上线性查找是指做assign的时候要找没用过的id？
多层不同粒度优化是指，先用查大block里面有没有没有的id然后再逐步深入到更小的
block里？

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

: hashset虽然耗的内存是O(N)，但是常数大。我onsite也面过这题，做出来后说把
: hashset换掉。纯array做都不够，最后被逼着往bitmap上想。这个有点类似于实现一个
: 文件系统，metadata区域有个bitmap表示哪些block被分配。
: 个人觉得这题很坑爹，最后用居然时间换内存。bitmap上只能线性查找，只不过用多层
: 不同粒度去优化。

w*i2015-01-17 08:01

6 楼

这题我当时做得不好，不知道最优解法是什么。根据那人的提示大概就是这样。我也觉
得线性查找很坑爹。

【在 a******u 的大作中提到】

: bitmap上线性查找是指做assign的时候要找没用过的id？
: 多层不同粒度优化是指，先用查大block里面有没有没有的id然后再逐步深入到更小的
: block里？