Google 11/10 onsite MTV

feierqi 发表于 2016-1-13 16:19
LRU就是为了来减少内存使用量啊，substring不可能不能放到内存里的，否则这道题没有意义了啊

如果substring可以放到内存，直接用一个queue作为cache，用一个hashmap统计queue里面的字符和对应的频次不就可以了？

feierqi 发表于 2016-1-13 16:21
你的这个做法是最最worst的solution，因为time complexity是O（range of array），我给出的solution是O（ ...

嗯  我想了一下 确实就存在直接lgn的解法，直接binary search就好了 不用产生 accumulate array
因为可以通过sorted array的头尾值和array长度判断多少个missing range

补充内容 (2016-1-14 09:09):
楼主的解法确实最优！

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

为什么不用deque呢？操作更方便吧

feierqi 发表于 2015-11-20 05:09
多谢多谢啦先。第三题扩展到多个长方形没让写code，就是讨论，所以不要太过担心，其实就是用写的那个找ov ...

请问overlap的坐标指的overlap各个角的坐标吗？

只想问楼主 第二轮 难道真的要45分钟之内写一个红黑树么…… 还有2维红黑树…… 结点不平衡怎么旋转啊？

我只能想到平面四叉树这种法子，但还是不知道怎么能动态平衡树高

feierqi 发表于 2015-12-10 05:12
第四题的答案，time complexity lgN的最优解，大家可以拿的去参考：

line39 为什么要返回array[mid] + 1 呢？如果按照楼主的思路，input array = {1,6,7,11} ，假设line 32得到的randWeight是4，line 37得到的也是4，那返回的就是7了