11/09 Google Onsite

RagingSword 发表于 2015-11-20 08:39
有N/K 个batches， 所以是O(K * N / K) = O(K)

补充内容 (2015-11-20 08:39):

谢谢，虽然还是不太懂 额
stream里面每一个新数到了以后，怎么决定去哪一个batch呢？然后每个batch里面怎么用quick select啊？

stonezms 发表于 2015-11-20 09:34
谢谢，虽然还是不太懂 额
stream里面每一个新数到了以后，怎么决定去哪一个batch呢？然后每个batch里面 ...

不是一个一个进来，而是一个batch一个batch进来，每个batch的size就是k

RagingSword 发表于 2015-11-20 09:47
不是一个一个进来，而是一个batch一个batch进来，每个batch的size就是k

了解，谢了！

bobzhang2004 发表于 2015-11-20 09:30
第五题2k window不行吧，如果去后面k个全部小于前面k个，岂不是都会被去除，然后前面的k个会被移走？

你每次select第(total - k)个元素,前面的都remove就好了.
对total = 2K的情况 就是第K个
少于2K就remove前面那些留下K个就好了.

Nero_hu 发表于 2015-11-20 09:52
你每次select第(total - k)个元素,前面的都remove就好了.
对total = 2K的情况 就是第K个
少于2K就remov ...

是不是 quickselect 的时候需要找出这2k 个数的中位数作为 pivot 来做

第五题真是有水平。。。

感觉是维护一个2K length 的空间，保证前K个，然后每次从stream 进来k个，2k个数做一次quickselect，然后把后面那k扔掉。。。

第五题为什么minheap不行？

第三题是什么意思？LZ能再解释一下么？

姐姐不吃糖 发表于 2015-11-30 12:12
第三题是什么意思？LZ能再解释一下么？

就是经典的那道压缩string.