G家电面

楼主好人!能给我也发一份背包的code吗~拜托拜托

第一题Id很多是要用分布式系统做吗？

hj867955629 发表于 2015-8-25 19:53
就二分去查找区间吧

用二分查找区间然后在区间里面继续二分查找吗？这样好像时间复杂度并没有改善，不过用的空间少了就是。

yawnzh 发表于 2015-8-26 16:00
用二分查找区间然后在区间里面继续二分查找吗？这样好像时间复杂度并没有改善，不过用的空间少了就是。

用的空间为什么会少呢？

jiebour 发表于 2015-8-25 00:37
楼主，总体积一半以上，但还是需要保持整数对吧？

恩，就是在背包的两层循环里，加上一层从 当前物品体积的一半 到 全部体积 的 步长为1 的判断

w41q 发表于 2015-8-26 02:49
请问怎么优化呢？

优化的话，大致是这样：
现在概率分布是 0.2 0.3 0.5
如果想在O(1)时间找出 random结果对应的区间
我们可以做一个预处理：
现在有n个id，我们将这些id分到n个大小均为1/n的桶
思想是，把较大的概率均分给较小的概率，但是每个桶里面，只有两个id的概率，概率较大的id， 为该桶最后输出的id


桶0： (0.2(id1)+0.13(id3))   >> id1
桶1： (0.3(id2)+0.03(id3)) >> id2
桶2： （0.33(id3)） >> id3

一次random出[0,n-1]桶号，就可以O(1)得到对应的id

上面是个简单的例子，如果写代码做这件事情，可能需要minheap和maxheap来做这样的均匀桶

可能出现的是，可能本来很大的概率，没有装满一个桶，而是被分到其他的桶里，而没有random得到对应id的机会。
细节也没有想太多，应该可以跟面官讨论

wenqiang88 发表于 2015-8-26 19:53
用的空间为什么会少呢？

如果用的是区间-id的hashmap,空间并没有少
用二分查找的是random(0,1)出的值在哪个区间 O(logn)，不然就是从左往右扫一遍O(n)
二分查找时要注意的是，区间应该是半开半闭的，也就是区间边界要么贴左边，要么贴右边

alucardzhou 发表于 2015-8-24 03:00
第一题感觉是设计一个hashing function
随机到一个0到1之间的double
然后将它变成ID

0.88是怎么来的？

alittlesheep 发表于 2015-8-26 20:51
如果用的是区间-id的hashmap,空间并没有少
用二分查找的是random(0,1)出的值在哪个区间 O(logn)，不然就 ...

嗯，同意

wenqiang88 发表于 2015-8-26 03:53
用的空间为什么会少呢？

如果id太多不能都放到内存里的话，第一次二分查找区间，第二次在区间内二分查找，只需要把这个区间load到内存吧，我是这样觉得的。