Google 11/10 onsite MTV

feierqi 发表于 2015-11-20 05:03
第四题好多解法，我已开始说了个brute force的就是类似missing range然后找random，time是O（range of ar ...

我的思路和楼主可能差不多：

先数出每个missing range中的元素个数。比如上下界是[0 10000]，数组是
A =【1 5 7 】
那么总共有4个missing range，其中元素个数分别是
Nmiss = [1 3 1 9993]
再对Nmiss的累加求和，得
Ncum = [1 4 5 9998]

用getRandom得到[0, 1]上的数字，再映射到[0 10000]上。比如我们得到的是3，那么就在Ncum中找第一个大于3的元素（即4）的位置。4是第2个元素，也就是说我们新生成的元素将在A的第1个元素1和第2个元素5之间。然后再调用一次getRandom，映射到[2, 4]上。即得最终要求的元素。


补充内容 (2015-11-21 11:33):
不用再调用第二次getRandom了。只要将第一次得到的数字3减去Ncum中“最后一个小于3的数字”，得2，然后取出[2 4]中第2个数字，即3就可以了。

请问第二题getSum(x,y)是算(0, 0) 到 (x, y)子矩阵所有值的和吗? 那个rb_tree需要自己实现吗? 还是直接调用就行呀? 比如STL的map什么的?

stellari 发表于 2015-11-20 13:32
我的思路和楼主可能差不多：

先数出每个missing range中的元素个数。比如上下界是[0 10000]，数组是

你这个应该是rand生成0到9998之间才行。
其实可以直接存好missing_range_start{0,2,6,8}
然后存个missing_range_cumlength{1,4,5,9998}

random这题就是用segment tree。

楼主能不能讨论一下：

补充内容 (2015-11-27 09:07):
发太快了， #1 为什么用到LRU？是不是read each line 然后 找到longest sub string 就可以了？ #2 能不能具体说说第二题两个方法是什么， 怎么用RBTree？

补充内容 (2015-11-27 09:08):
#4， 被random pick到的number 需不需要从missing range中取出来， 这样就需要split missing range

LifeGoesOn 发表于 2015-11-27 09:04
楼主能不能讨论一下：

补充内容 (2015-11-27 09:07):

自己figure out 第二题了， 大概就是用个TreeMap<x, TreeMap<y, value>> 吧， LZ的题各种tricky啊

先恭喜楼主拿到offer! 请教一个问题： 对于第二题要自己实现RB Tree吗，还是可以直接用java自带的TreeMap呢，谢谢楼主！