Google onsite 面经

pyemma 发表于 2015-11-17 11:31
第二题只需要检查0, 1/4, 2/4, 3/4 4/4位置的元素看它们是不是就可以了，检查每一个数用二分搜索找左右boun ...

检查0是多余的，因为如果0的数字是popular的，那在1/4处还是它。

面假空虚 发表于 2015-11-17 11:36
检查0是多余的，因为如果0的数字是popular的，那在1/4处还是它。

4也是多余的吧？最多只可能有3个数字，所以需要检查1, 2, 3

楼主结果出来了没呀？

七夜雪 发表于 2015-11-17 13:02
4也是多余的吧？最多只可能有3个数字，所以需要检查1, 2, 3

最后一个位置不多余啊，最后1/4段包括4/4那个点不包括3/4那个点。

面假空虚 发表于 2015-11-17 13:14
最后一个位置不多余啊，最后1/4段包括4/4那个点不包括3/4那个点。

对的。。。最多可能有4个这样的数。。。

为什么没有人第五题是什么意思啊？有例子说明题目什么意思吗？

补充内容 (2015-11-17 14:30):
好吧。请问： window size k, 是指size 为k 的 string array 吗？

面假空虚 发表于 2015-11-17 13:14
最后一个位置不多余啊，最后1/4段包括4/4那个点不包括3/4那个点。

话说最后那题有什么efficient的方法吗？我能想到的办法就是建一个map看每个词的出现次数， 然后根据map重新建一个array，做到相同的elements之间的距离大于k.不过这样应该是O(n) time O(n) space.

补充内容 (2015-11-17 13:40):
噢time应该是O(NlogN)因为需要按照出现次数排序

七夜雪 发表于 2015-11-17 13:35
话说最后那题有什么efficient的方法吗？我能想到的办法就是建一个map看每个词的出现次数， 然后根据map重 ...

感觉时间上应该这样是最优了。

感谢楼主分享，第一道题，一个string里面有一个词放不下放到下一行，意思是这个词放到下一行吧？楼主当时是如何做的哎？

面假空虚 发表于 2015-11-16 19:36
检查0是多余的，因为如果0的数字是popular的，那在1/4处还是它。

即使多于也不影响，留出预留空间放置意外