Google 11/10 onsite MTV

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

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

请问你为什么可以映射到［0 10000］？一共只有9998个数字不在原array中，如果你是9999，那算哪一个呢？

silenceleaf 发表于 2015-12-31 06:53
请问你为什么可以映射到［0 10000］？一共只有9998个数字不在原array中，如果你是9999，那算哪一个呢？

发帖时打错了。多谢指出。

会rb tree的都是牛人，第二题是不是lc原题？https://leetcode.com/problems/range-sum-query-2d-mutable/，我是用segment tree解决的。

请问楼主用treemap的话要改写api吗？因为往左路径走的时候要更新父节点的value啊！

feierqi 发表于 2015-12-10 05:19
不好意思，好久没来，回复的晚了。第一题因为是cannot fit into memory，所以要用LRU cache来remove最早 ...

第一题还是不太理解楼主的意思
cannot fit into memory指的是什么不能装进内存？
如果是说整个stream不能装进内存，那么用leetcode的方法，一个queue 加一个hashmap统计次数就可以了
如果说连substring都不能fit进内存，那楼主的解法也超出内存了，因为你的LRUcache用的内存就超了
期待楼主解答！

第二题不是leetcode原题吗

第三题也是leetcode

第四题  找到一共多少个missing 数字 用random随便产生一个
然后再生成一个关于missing number 的 accumulative array，然后二分找就ok了

补充内容 (2016-1-13 12:36):
array: 2 3 8 10 21

missing = 4-7 + 9 + 11-20 = 15
accumulate array = 0 0 4 5 15

random = 10
binary search: start = 5, end = 15
result = missing[startIndex] + (random - start) = 10 + 5 = 15