Google virtual onsite

llcourage123 发表于 2020-3-25 16:38
楼主我仔细想了下，单纯的sliding window的确解不了
有两种解法。
第一种是用两个heap，min heap 和max ...

恩恩，我觉得heap就是面试官想要的
二分这个我倒是没有想到，不过肯定也是可以解的，厉害

gzs 发表于 2020-3-25 19:12
多谢楼主分享。很详细！
第二题我写了一下treemap解法，不知道和楼主是否一样，如果有问题请帮忙指出，多 ...

不大一样，我用的是TreeMap<int, int> key是num，value是count，出现的次数，防止有重复。我是treemap还要加上sliding window
TreeMap的话删除和添加都是logn所以总体是nlogn

reliveinfire 发表于 2020-3-25 21:55
请问第一道题, 最后用histogram 不是也需要O(N)的时间吗?
全部的点是O(N^2), 这样时间是否应该是O(N^3)

是O(N^2)，每行做两件事请，第一个调用第一问的方法，O(n), 第二个算柱状图的面积，O(n), 一共n行，所以O(N^2)

convexopt 发表于 2020-3-25 16:25
恭喜楼主加米了
第二题用deque的话好像只能求固定长度窗口大极值？那还是要二分答案，复杂度是一样的？
...

deque不一定要固定窗口
通过删除给定string的某些character来生成字典中的词，至于是删连续的字母还是都可以删，我有点不记得了

楼主，你能详细解释下第四题题干么，我的理解是，如果一个长度大于1的substring出现过两次，那么就输出这个substring第一次出现的range。比如abcabc，那么就输出[[0，2]]? 但是这样好像有点问题。。

lz 能降低一点积分要求吗？300分好高。。。

恭喜楼主! 第一题matrix O(n^2) 做法确实很巧妙.. 想了下第二题, 如果用两个队列应该就是分别maintain 当前窗口的min和max ?  这样的话sliding window走法好像和用treemap是一样的吧, 就是如果当前min和max 差值不满足k, 就缩小左端点?  

dynf 发表于 2020-3-26 13:08
恭喜楼主! 第一题matrix O(n^2) 做法确实很巧妙.. 想了下第二题, 如果用两个队列应该就是分别maintain 当前 ...

对的，基本是一样的，就是队列时间复杂度小，但是代码量会多一些。对的，大于K就缩小窗口