11/09 Google Onsite

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

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

感觉不行啊，假设有N/k个batch，每个batch的长度为k，所以，每compare两个batch的时间复杂度是k，从N/k个batch中间选出第m大的时间复杂度是N/k, 所以总的复杂度就是k*N/k。
但是，你如何保证确实有那么一个batch，其k个数对应着要求的k个数呢？
谢谢了

lz，第二题也有点不清楚，难道就是根据大写字母来决定pattern？
thx

Leetcode 有个类似的题

returning 发表于 2016-1-10 22:44
lz，第二题也有点不清楚，难道就是根据大写字母来决定pattern？
thx

不仅仅是大写.
大写之后的小写是可选的,但是如果给了你小写就必须要match.
FooBar -> FB , match
FooBar -> FoB, match
FooBar -> FaB, not match

Nero_hu 发表于 2016-1-20 01:13
不仅仅是大写.
大写之后的小写是可选的,但是如果给了你小写就必须要match.
FooBar -> FB , match

所以这道题你是怎么解的，是不是遇到大写字母就开始构建trie？
谢谢了。

returning 发表于 2016-1-20 16:38
所以这道题你是怎么解的，是不是遇到大写字母就开始构建trie？
谢谢了。

可以这么做,或者就是直接match,直接扫,以大写为分隔符.
直接扫其实也是O(n)了.

看楼主答的挺好的，为什么黑了呀

tltzhsajsdr 发表于 2016-1-22 01:39
看楼主答的挺好的，为什么黑了呀

findcamel那轮脑残了,最后没写完....

Nero_hu 发表于 2016-1-22 01:46
findcamel那轮脑残了,最后没写完....

好吧。。加油！祝早日拿到理想offer